Thread: std::list question

Originally Posted by Daved

If you are doing all your insertions at once in the beginning, and then searching afterwards, then a vector would probably be even better than a map/multimap/set/multiset. Fill the vector with all your data, then sort it, then use binary_search, lower_bound, and/or upper_bound to find what you are looking for. This will be even better than the map solutions because those keep the data sorted as you are inserting which is a bit slower than sorting it once at the end. In addition, the vector uses less memory overhead than the map solutions.

Another option is the unordered_map/unordered_multimap that will be part of the next standard. You can find an implementation from boost if your library doesn't have one. They're basically hashed maps, which have even faster lookups than the regular map or binary_search.

Well that depends on actual data. If your data are not in form key/value than maybe it's better to use set container. Here's one quick and dirty example:

Code:

#include <iostream>
#include <set>

using namespace std;

int main ( ) 
{
    set <int> iSet;
    for (int i = 0; i < 10; i++)
    {
        iSet.insert(rand()%100);
    } 
    set <int> :: iterator it;
    for (it = iSet.begin(); it != iSet.end(); ++it)
    {
        cout << *it << " ";
    } 
    return 0;
}

I don't think that vector container would be good solution. You insert elements (needs time), sort elements (needs time) and then search for one particular element (needs time). Using set, map or multimap data are automatically sorted when inserted into container. Search of such structure is logarithmic (since it's basically binary search tree "under the hood") because it involves binary search.

I don't think that vector container would be good solution. You insert elements (needs time), sort elements (needs time) and then search for one particular element (needs time). Using set, map or multimap data are automatically sorted when inserted into container. Search of such structure is logarithmic (since it's basically binary search tree "under the hood") because it involves binary search.

Inserting an element to a vector takes amortized constant time, so a sequence of insertions takes linear time. Inserting an element to a set would be an O(log n) operation, so a sequence of insertions would be O(n log n), which is the same as the sort of the vector. A search of the sorted vector takes logarithmic time too.

Nicolai Josuttis, in chpater 6, section 9 of The C++ Standard Library: A Tutorial and Reference notes:
"The automatic sorting of associative containers does not mean that these containers perform better when sorting is needed. This is because an associative container sorts each time a new element gets inserted. An often faster way is to use a sequence container and to sort all elements after they are all inserted by using one of the several sort algorithms."

He then goes on to compare using a set to using a vector in sorting unique strings. The results for his system were stated as:
"When I tried both programs with about 150,000 strings on my system, the vector version was approximately 10% faster. Inserting a call of reserve() made the vector version 5% faster. Allowing duplicates (using a multiset instead of a set and calling copy() instead of unique_copy() respectively) changed things dramatically: The vector version was more than 40% faster! These measurements are not representative; however, they do show that it is often worth trying different ways of processing elements."

Interesting reading, thanks laserlight. however i said that all this depends on actual data that is used. What applies to integers and string no necessarlly applies to to other types (user defined types). So decision of what container to use is based on data types and the way they're inserted (if they are inserted all at once or not). In his case I would recommend to try different containers and to choose what is best for him. Also it will be a valueable experience and opportunity to learn something new!

I'll give the vector idea a try too Daved.
@IfYouSaySo: I see. Those are redundant calculations if kept inside the loop. <-- Right?

however i said that all this depends on actual data that is used. What applies to integers and string no necessarlly applies to to other types (user defined types). So decision of what container to use is based on data types and the way they're inserted (if they are inserted all at once or not). In his case I would recommend to try different containers and to choose what is best for him.

Of course. In fact, Josuttis goes on to write that:
"In practice, predicting which container type is the best is often difficult. The big advantage of the STL is that you can try different versions without much effort. The major work - implementing the different data structures and algorithms - is done. You have only to combine them in a way that is best for you."

Those are redundant calculations if kept inside the loop.

I suspect it might be optimised away by the compiler.