Solution using std::multiset and two iterators
Here is a solution using C++11 std::multiset.\nIt keep two iterators synchronized on lower and upper median.\nIt relies on the specification of C++11 multiset#i
Here is a solution using C++11 std::multiset.\nIt keep two iterators synchronized on lower and upper median.\nIt relies on the specification of C++11 multiset#insert that states that insertions of keys occurs at the upper bound of the range of keys with same values.\n\n    class MedianFinder {\n        std::multiset<int> data;\n        std::multiset<int>::iterator low_median, up_median;\n    public:\n        MedianFinder() : low_median(data.end()), up_median(data.end()) {}\n    \n        // Adds a number into the data structure.\n        void addNum(int num) {\n            // keep size BEFORE insertion\n            const size_t n = data.size();\n            \n            // do the insertion; we need the element in place to make\n            // sure our iterator shifting will point to it if necessary\n            data.insert(num);\n            \n            if (!n) {\n                // no elements before; use the new data at single median\n                low_median = up_median = data.begin();\n            } else if (n & 1) {\n                // odd size, low and up median are the same point\n                if (num < *up_median) {\n                    // num went on left side of single median, we use the \n                    // predecessor  of the median as the new low median\n                    --low_median;\n                } else { // num >= up\n                    // num wen on the right side of single median, use the \n                    // successor of median as new up\n                    ++up_median;\n                }\n            } else {\n                // even size, we have two different low and up median\n                if (num > *low_median && num < *up_median) {\n                    // we are in-between, by definition the new value \n                    // is the new single median\n                    ++low_median;\n                    --up_median;\n                } else if (num >= *up_median) {\n                    // since C++11, insert will put the new value at\n                    // end of range of values equal to up_median if num \n                    // is equal to up_median; if greater it will also\n                    // be to the right. So right side has one item more:\n                    ++low_median;\n                } else { // num <= low_median < up_median\n                    // since C++11, insert will put the new value at\n                    // end of rand; so low_median iterator may not be\n                    // valid anymore; we use the decremented up_median\n                    low_median = --up_median;\n                }\n            }\n        }\n    \n        // Returns the median of current data stream\n        double findMedian() {\n            return 0.5 * (static_cast<double>(*low_median) + *up_median);\n        }\n    };\n    \n    // Your MedianFinder object will be instantiated and called as such:\n    // MedianFinder mf;\n    // mf.addNum(1);\n    // mf.findMedian();
['Iterator', 'C++']