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.

Answer 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.