A clean solution using multiset in C++
The key point here is to ensure the midIter always points to the median or if it's even array then to the first of the median.\n\nthe complete solution in C++ a
The key point here is to ensure the `midIter` always points to the median or if it's even array then to the first of the median.\n\nthe complete solution in C++ as follows.\n\n```\nclass MedianFinder {\nprivate:\n    int size; \n    multiset<int> numsSet;\n    multiset<int>::iterator midIter;\npublic:\n\n    // Adds a number into the data structure.\n    void addNum(int num) \n    {\n        if(numsSet.empty())\n        {\n            midIter = numsSet.insert(num);\n            size++;\n            return ; \n        }\n        numsSet.insert(num);\n        if((size&1) && num<*midIter) --midIter; \n        else if(!(size&1) && num>=*midIter) ++midIter;\n        size++;\n    }\n\n    // Returns the median of current data stream\n    double findMedian() \n    {\n        if(size & 1) return *midIter;   \n        else return (double)(*midIter+*next(midIter))/2;\n    }\n};\n```
[]