A class to keep the median of a stream of values.

median-keeper.hpp

#ifndef MEDIAN_KEEPER_HPP
#define MEDIAN_KEEPER_HPP

#include <queue>
#include <vector>

template<typename T>
class MedianKeeper
{
public:
	
	MedianKeeper() = default;
	
	MedianKeeper(std::initializer_list<T> list)
	{
		for (const auto& item : list) push(item);
	}
	
	void push(const T& item)
	{
		if (seen() > 0 && item > _median)
		{
			_right.push(item);
			
			if (_right.size() == _left.size() + 2)
			{
				_left.push(_right.top());
				
				_right.pop();
			}
		}
		
		else
		{
			_left.push(item);
			
			if (_left.size() == _right.size() + 2)
			{
				_right.push(_left.top());
				
				_left.pop();
			}
		}
		
		_median = _compute();
	}
	
	T& operator()()
	{
		return median();
	}
	
	const T& operator()() const
	{
		return median();
	}
	
	T& median()
	{
		if (is_empty())
		{
			throw std::out_of_range("No values inserted yet!s");
		}
		
		return _median;
	}
	
	const T& median() const
	{
		if (is_empty())
		{
			throw std::out_of_range("No values inserted yet!s");
		}
		
		return _median;
	}
	
	
	T pop()
	{
		auto old = _median;
		
		if (seen() % 2 == 0)
		{
			_left.pop();
			_right.pop();
		}
		
		else if (_left.size() > _right.size()) _left.pop();
		
		else _right.pop();
		
		_median = _compute();
		
		return old;
	}
	
	void clear()
	{
		_left.clear();
		_right.clear();
	}
	
	
	size_t seen() const
	{
		return _left.size() + _right.size();
	}
	
	bool is_empty() const
	{
		return seen() == 0;
	}
	
private:
	
	T _compute()
	{
		if (seen() % 2 == 0)
		{
			return (_left.top() + _right.top()) / 2;
		}
		
		else if (_left.size() > _right.size()) return _left.top();
		
		else return _right.top();
	}
	
	std::priority_queue<T> _left;
	
	std::priority_queue<T, std::vector<int>, std::greater<T>> _right;
	
	T _median;
};

#endif /* MEDIAN_KEEPER_HPP */