You could use a std::set
, and the fact that insertions to sets won't invalidate iterators.
You can hold an iterator mIt
to the set's median element if N
is odd, and to the left of the two median elements, if N
is even.
Let's consider the different cases you can have when you insert elements:
Insertion when N
is odd: if the inserted element is smaller than *mIt
, old median becomes right of the two new median elements, so decrement the iterator. If it's bigger (or equal, for multiset
), all is well.
Insertion when N
is even: if the inserted element is bigger (or equal) than *mIt
, the old right median becomes median, so increment the iterator. If it's smaller, the old left median becomes median, and all is well.
template <class T>
class MedianHolder {
std::set<T> elements;
std::set<T>::const_iterator mIt;
public:
T const& getMedian() const { return *mIt; }
void insert(T const& t) {
if (elements.empty()) {
mIt = elements.insert(t).first;
return;
}
bool smaller = std::less<T>(t,getMedian());
bool odd = (elements.size() % 2) == 1;
if (!elements.insert(t).second)
return; //not inserted
if (odd && smaller) --mIt;
else if (!odd && !smaller) ++mIt;
}
};
I'll leave erasing elements as an exercise to you ;-)