c++ std::map question about iterator order

Question

Hi all,

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.

Answer 1

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

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

Answer 2

First off, std::map isn't constant-time lookup. It's O(log n). Just thought I should set that straight.

Anyway, you have to specify your own comparison function if you want to use a different ordering. There isn't a built-in comparison function that can order by insertion time, but, if your object holds a timestamp field, you can arrange to set the timestamp at the time of insertion, and using a by-timestamp comparison.

Answer 3

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.

Answer 4

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.

Answer 5

Map is not meant for placing elements in some order - use vector for that.

If you want to find something in map you should "search" by the key using [the operator

If you need both: iteration and search by key see this topic

Answer 6

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.