How are std::map's ordered

Question

I'm trying to understand the ordering in a std::map.

http://www.cplusplus.com/reference/map/map/

Internally, the elements in a map are always sorted by its key following a specific strict weak ordering criterion indicated by its internal comparison object (of type Compare).

If I do this:

   myMap["two"] = 2;
   myMap["three"] = 3;
   myMap["one"] = 1;

and then iterate over myMap, printing out the value as I go, what will the output be?

I'm looking for a container where the elements are in the order that they are added. In this case I'd expect the output 2, 3, 1 for iteration.

Well no `std::map` keeps the elements ordered by key (in your case `string` lexicographic ordering) to allow fast (logarithmic) time access by key. It doesn't retain insersion order. — Antoine, Mar 19 '13 at 12:51
This may answer your question: http://stackoverflow.com/questions/1098175/a-stdmap-that-keep-track-of-the-order-of-insertion — Dave G, Mar 19 '13 at 12:52
"If I do this and then iterate over myMap, printing out the value as I go, what will the output be?" -- have you considered *trying* it and seeing what happens? What's the worst that could happen? — jalf, Mar 19 '13 at 12:52
`unordered_set` has good performance and *in my experience* iterates in *reverse* insertion order, but that is probably implementation specific. Just use `vector< pair >` if you don't need fast access by key. — Antoine, Mar 19 '13 at 12:58
@Antoine you can't make any assumptions about the order of iteration of an `unordered_set`. — juanchopanza, Mar 19 '13 at 13:00

score 2 · Answer 1 · answered Mar 19 '13 at 12:50

2

A vector/FIFO queue would simply do what you desire, without you needing to worry about how the map stores the objects internally OR bloating your code with a data structure that is more complicated for the job at hand.

std::queue is a FIFO queue

answered Mar 19 '13 at 12:50

Amit

1,836
15
24

score 1 · Answer 2 · answered Mar 19 '13 at 13:00

The order in your example depends on the definition of your std::map. Note that std::map is a template with four template parameters:

std::map< Key, Value, Compare, Allocator >

where the third one is important for the order. Given that you have std::map< std::string, int >, the default for the third parameter Compare is std::less< Key >, which is std::less< std::string >, which in turn means that the keys (which are of type std::string) are compared with <. Hence the order in your case would be 1, 3, 2 because std::string("one") < std::string("three") and std::string("three") < std::string("two").

As already pointed out by others, you are looking for a different container which models a sequence container.

How are std::map's ordered

2 Answers2