RunningMedian< T, Compare > Class Template Reference

For use in the efficient computation of a running median. More...

#include <RunningMedian.h>

Public Member Functions

 RunningMedian (unsigned n=0)
 
void set_nth (unsigned n)
 
unsigned get_nth () const
 
void clear ()
 Erases all of the elements.
 
void insert (const T &element)
 Insert an element.
 
void erase (const T &element)
 Erase an element.
 
const T & get_median () const
 Get the current median value.
 

Static Protected Member Functions

static T popFirstElement (std::multiset< T, Compare > &S)
 
static T popLastElement (std::multiset< T, Compare > &S)
 

Detailed Description

template<typename T, typename Compare = std::less<T>>
class RunningMedian< T, Compare >

For use in the efficient computation of a running median.

There are quite a few different approaches to this problem, including

1) O(sqrtN) algorithm by Soumya D. Mohanty

2) O(logN) algorithm based on an indexable skiplist by Raymond Hettinger

3) O(logN) algorithm based on std::multiset (TopCoder Match Editorial)

The last of these is quite clever, and requires very little coding.

This implementation is based on the example from the TopCoder web-site

http://community.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm310 (accessed on 20 April 2012)


The documentation for this class was generated from the following file:

Generated using doxygen 1.8.17