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

Posted by sharkin on Stack Overflow See other posts from Stack Overflow or by sharkin
Published on 2009-11-12T00:32:32Z Indexed on 2010/04/05 16:03 UTC
Read the original article Hit count: 342

Filed under:

c++

|

stl

|

containers

|

median

Let's say I need to retrieve the median from a sequence of 1000000 random numeric values.

If using anything but STL::list, I have no (built-in) way to sort sequence for median calculation.

If using STL::list, I can't randomly access values to retrieve middle (median) of sorted sequence.

Is it better to implement sorting myself and go with e.g. STL::vector, or is it better to use STL::list and use STL::list::iterator to for-loop-walk to the median value? The latter seems less overheadish, but also feels more ugly..

Or are there more and better alternatives for me?

© Stack Overflow or respective owner

Related posts about c++

Which C++ book shold I get between "C++ Primer" vs "C++ Primer Plus"

as seen on Stack Overflow - Search for 'Stack Overflow'
I want to learn C++ by using Vim and MinGW as compiler. I'm interesting at "C++ Primer (4th Edition)" and "C++ Primer Plus (5th Edition)" but I don't know how about it different. It has no book store that I can review those books, so I want to know, what is the different between those book and which… >>> More
C++ : C++ Primer (Stanley Lipmann) or The C++ programming language (special edition)

as seen on Stack Overflow - Search for 'Stack Overflow'
I have a Computer Science degree (long2 time ago) .. I do know Java OOP but i am now trying to pick up C++. I do have C and of course data structure using C or pascal. I have started reading Bjarne Stroustrup book (The C++ Programming Language - Special Edition) but find it extremely difficult esp… >>> More
I need help on my C++ assignment using MS Visual C++

as seen on Stack Overflow - Search for 'Stack Overflow'
Ok, so I don't want you to do my homework for me, but I'm a little lost with this final assignment and need all the help I can get. Learning about programming is tough enough, but doing it online is next to impossible for me... Now, to get to the program, I am going to paste what I have so far. This… >>> More
Managed c++ std::string not accessible in unmanaged c++

as seen on Stack Overflow - Search for 'Stack Overflow'
In unmanaged c++ dll i have a function which takes constant std::string as argument Prototype : void read ( const std::string &imageSpec_ ) I call this function from managed c++ dll by passing a std::string. When i debug the unmanaged c++ code the parameter imageSpec_ shows the value correctly… >>> More
The Definitive C++ Book Guide and List

as seen on Stack Overflow - Search for 'Stack Overflow'
After more than a few questions about deciding on C++ books I thought we could make a better community wiki version. Providing QUALITY books and an approximate skill level. Maybe we can add a short blurb/description about each book that you have personally read / benefited from. Feel free to debate… >>> More

Related posts about stl

Fastest way to write large STL vector to file using STL

as seen on Stack Overflow - Search for 'Stack Overflow'
I have a large vector (10^9 elements) of chars, and I was wondering what is the fastest way to write such vector to a file. So far I've been using next code: vector<char> vs; // ... Fill vector with data ofstream outfile("nanocube.txt", ios::out | ios::binary); ostream_iterator<char>… >>> More
question about STL thread-safe and STL debugging

as seen on Stack Overflow - Search for 'Stack Overflow'
I have two questions about STL 1) why STL is not thread-safe? Is there any structure that is thread-safe? 2) How to debug STL using GDB? In GDB, how can I print a vector? >>> More
The C++ Standard Template Library as a BDB Database (part 1)

as seen on Oracle Blogs - Search for 'Oracle Blogs'
If you've used C++ you undoubtedly have used the Standard Template Libraries. Designed for in-memory management of data and collections of data this is a core aspect of all C++ programs. Berkeley DB is a database library with a variety of APIs designed to ease development, one of those APIs extends… >>> More
Design approach, string table data, variables, stl memory usage

as seen on Stack Overflow - Search for 'Stack Overflow'
I have an old structure class like this: typedef vector<vector<string>> VARTYPE_T; which works as a single variable. This variable can hold from one value over a list to data like a table. Most values are long,double, string or double [3] for coordinates (x,y,z). I just convert them as… >>> More
Sort list using stl sort function

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm trying to sort a list (part of a class) in descending containg items of a struct but it doesn't compile(error: no match for 'operator-' in '__last - __first'): sort(Result.poly.begin(), Result.poly.end(), SortDescending()); And here's SortDescending: struct SortDescending { bool operator()(const… >>> More