2

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...)

Community
  • 1
  • 1
user620189
  • 2,595
  • 7
  • 21
  • 19
  • To you want the most efficient method, or the simplest code? – Beta May 19 '11 at 13:42
  • @Bo and @Beta: I think what I was trying to get at... 1. Is there a built in function that calculated the median 2. What's the best container for sorting (which containers automatically sort), if not, what's the best way to sort.. MOST EFFICIENTLY, in terms of the speed. I will need to do this calculation 1000s of times. – user620189 May 19 '11 at 13:43
  • 1
    @user620189 - Follow the link! :-) It shows how to put the values in a vector and sort them. The median will end up, eh, in the middle. – Bo Persson May 19 '11 at 13:47

1 Answers1

6

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.

Oliver Charlesworth
  • 267,707
  • 33
  • 569
  • 680