Search code examples
c++sortingmedian

Finding a median of a collection of values in c++

Possible Duplicate:
Compute Median of Values Stored In Vector - C++?

I need to store a collection of values and then have the ability to calculate its median value.

What is the best container in c++ to store these values, and how do I find the median?

(I might also want to be able to remove specific elements, so I am thinking set may not be the best option...)

Solution

  • Short of any other specific requirements, you should default to a std::vector. You mention that you want to remove items later; this implies that you may want to consider a std::list instead.

    To find the median, you can use std::nth_element, asking it to pivot on the N/2-th (or (N-1)/2-th) element. This runs in O(N) time.