c++ std::map question about iterator order

Question

I am a C++ newbie trying to use a map so I can get constant time lookups for the find() method.

The problem is that when I use an iterator to go over the elements in the map, elements do not appear in the same order that they were placed in the map.

Without maintaining another data structure, is there a way to achieve in order iteration while still retaining the constant time lookup ability?

Please let me know.

Thanks, jbu

edit: thanks for letting me know map::find() isn't constant time.

Solution 1

Without maintaining another data structure, is there a way to achieve in order iteration while still retaining the constant time lookup ability?

No, that is not possible. In order to get an efficient lookup, the container will need to order the contents in a way that makes the efficient lookup possible. For std::map, that will be some type of sorted order; for std::unordered_map, that will be an order based on the hash of the key.

In either case, the order will be different then the order in which they were added.

Solution 2

First of all, std::map guarantees O(log n) lookup time. You might be thinking about std::tr1::unordered_map. But that by definitions sacrifices any ordering to get the constant-time lookup.

You'd have to spend some time on it, but I think you can bash boost::multi_index_container to do what you want.

Solution 3

What about using a vector for the keys in the original order and a map for the fast access to the data?

Something like this:

vector<string> keys;
map<string, Data*> values;

// obtaining values
...
keys.push_back("key-01");
values["key-01"] = new Data(...);
keys.push_back("key-02");
values["key-02"] = new Data(...);
...

// iterating over values in original order
vector<string>::const_iterator it;
for (it = keys.begin(); it != keys.end(); it++) {
    Data* value = values[*it];
}

Solution 4

Items are ordered by operator< (by default) when applied to the key.

PS. std::map does not gurantee constant time look up.
It gurantees max complexity of O(ln(n))

Solution 5

I'm going to actually... go backward.

If you want to preserve the order in which elements were inserted, or in general to control the order, you need a sequence that you will control:

• std::vector (yes there are others, but by default use this one)

You can use the std::find algorithm (from <algorithm>) to search for a particular value in the vector: std::find(vec.begin(), vec.end(), value);.

Oh yes, it has linear complexity O(N), but for small collections it should not matter.

Otherwise, you can start looking up at Boost.MultiIndex as already suggested, but for a beginner you'll probably struggle a bit.

So, shirk the complexity issue for the moment, and come up with something that work. You'll worry about speed when you are more familiar with the language.

View more solutions

Comments

[C. K. Young]

In the Java world, there is a way to do amortised-constant time lookups, and still preserve insertion order, using a LinkedHashMap (space-time tradeoff). I wonder how easy that'd be to implement in C++.

[Mark Ransom]

And if not a timestamp, then a simple incrementing index.

[foraidt]

Note that using operator[] has the side effect of creating an element if it does not exist. find() returns map::end() if the search failed.

[Steve Jessop]

@Chris: I'm pretty sure that it's about as easy as implementing unordered_map: in principle the list doesn't add a great deal of difficulty beyond what you're already doing to implement a hash. So not exactly "easy", but not challenging if you know what you're doing.

[pm100]

actually people use maps all the time for placing things in order - just not in insertion order.

[Emile Cormier]

Yes, boost::multi_index_container should work nicely (once you wrap your head around its weird usage syntax).