Find Median from Data Stream.cpp

class MedianFinder {
public:
    /** initialize your data structure here. */
    MedianFinder() {
        
    }
    
    void addNum(int num) {
        if(set.empty())
        {
            set.insert(num);
            iter = set.begin();
        }
        else
        {
            //always keep iter at mid for odd numbers
            //and highter one for even numbers
            //for duplicates insertion it always append at the end of all duplicates
            set.insert(num);
            if(num < *iter)--iter;
            if(set.size() % 2 == 0)++iter;
        }
    }
    
    double findMedian() {
        if(set.size() % 2)
            return *iter;
        else
            return (*prev(iter, 1) + *iter) / 2.0;
    }
    
private:
    multiset<int> set;
    multiset<int>::iterator iter;
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */