What is the right approach when using STL container for median calculation?

by

Any random-access container (like std::vector) can be sorted with the standard std::sort algorithm, available in the <algorithm> header.

For finding the median, it would be quicker to use std::nth_element; this does enough of a sort to put one chosen element in the correct position, but doesn’t completely sort the container. So you could find the median like this:

int median(vector<int> &v)
{
    size_t n = v.size() / 2;
    nth_element(v.begin(), v.begin()+n, v.end());
    return v[n];
}

More Related Contents:

  1. How can I use std::maps with user-defined types as key?
  2. What are the complexity guarantees of the standard containers?
  3. Why use iterators instead of array indices?
  4. Why isn’t vector a STL container?
  5. Heterogeneous containers in C++
  6. Where can I get a “useful” C++ binary search algorithm?
  7. std::transform() and toupper(), no matching function
  8. How to get a random element from a C++ container?
  9. c++ sort keeping track of indices [duplicate]
  10. Copy map values to vector in STL [duplicate]
  11. Reorder vector using a vector of indices [duplicate]
  12. What is an iterator’s default value?
  13. C++ Efficiently Calculating a Running Median [duplicate]
  14. Why does storing references (not pointers) in containers in C++ not work?
  15. Template class with template container
  16. How can I sort an STL map by value?
  17. How can std::make_heap be implemented while making at most 3N comparisons?
  18. std::back_inserter for a std::set?
  19. Do STL iterators guarantee validity after collection was changed?
  20. General use cases for C++ containers
  21. Is it more efficient to copy a vector by reserving and copying, or by creating and swapping? [duplicate]
  22. Why there is no std::copy_if algorithm?
  23. stl ordering – strict weak ordering
  24. Order Statistic Tree in C++
  25. Stack-buffer based STL allocator?
  26. Compute Median of Values Stored In Vector – C++?
  27. Checking if an iterator is valid
  28. Reading and writing a std::vector into a file correctly
  29. C++11 STL containers and thread safety
  30. Can I have polymorphic containers with value semantics in C++?

Leave a Comment