[ACCEPTED]-how does the stl's multimap insert respect orderings?-multimap

It seems the new standard (C++11) changed 9 this:

The order of the key-value pairs whose 8 keys compare equivalent is the order of 7 insertion and does not change.^{[cppreference]}

I'm hesitating 6 to use it though, as this seems like a detail 5 easily overlooked when modifying the standard 4 library to be C++11 compliant and it's the 3 sort of detail that will silently cause 2 errors if your compiler's library failed 1 to implement properly.

Unless I've missed something, the standard 13 doesn't provide any such guarantee.

The most 12 obvious workaround would be to include a 11 sequence number as a secondary key. For 10 example, in your class include a static 9 unsigned long, and each time you create 8 an object to insert in the multimap, put 7 its current value into your object, and 6 increment it. In your object's comparison 5 function, use that counter as the deciding 4 factor for ordering if the data you're currently 3 using as the key compares equal. Note that 2 in this case, each key will be unique, so 1 you can use a map instead of a multimap.

Boost multi_index supports what you are trying to do, if 2 you don't want to take the workaround given 1 by Jerry Coffin.

If I got you right - you need the data sorted 26 by some key. Whenever you insert 2 things 25 with the same key, you need to retrieve 24 them in the order of insertion.

If that's 23 the case, then you have to take a look at 22 the implementation of your multimap. Depending 21 on how it handles the case of multiple insertions 20 with the same key it may or may not have 19 this guarantee. I guess the standard does 18 not offer this kind of guarantee, since 17 it would limit the implementation for a 16 very special case.

Another approach is to go for a Map (not Multi) and create a compound key. The key consists of 15 the normal key you choose and an alway increasing 14 counter. On comparison, with equal keys, the 13 insertion number makes the key unique. This 12 way you force unique keys and the order 11 on equal "normal" keys (I hope this was 10 understandable).

I guess the last approach 9 is the easiest to implement.

Option: (not 8 preferable)

You can always go for a self-made 7 datastructure with this guarantee. I'd go 6 for a Tree (Red-Black or AVL for example) with 5 a vector to hold the inserted data. On iteration 4 you have to find the node, go to the vector 3 and iterate on it's content. Whenever you 2 finish with the vector, you continue with 1 the next node.

No it won't. If you want that, you should 2 use a "sequence container" like a vector. You 1 can load a vector with std::pairs for example?

It sounds like multimap is what you need...

However, I 17 also need data with the same index to 16 be kept in the order in which it was inserted, in 15 this case meaning that when I iterate 14 through the data I get to the earlier 13 data before the later data.

It will be 12 in the order of the index. If the index 11 increases over time as you insert more items, then 10 yes because of the nature of your index, the 9 "earlier" data will come first.

Otherwise, no. You 8 could keep two multimaps to the same data. One 7 kept in order of index, the other in order 6 of insertion time:

std::multimap<index, T*> orderedByIndex;
std::multimap<time, T*> orderedByInsertionTime;

Giving you the ability 5 to iterate the map both ways.

(Edit I'm reading 4 this to mean you want to sometimes iterate 3 by index or sometimes iterate by insertion 2 time, but see the above answer if you mean 1 first index then insertion time.)

The elements that belongs to the same key 4 is ordened by lower_bound and upper_bound functions when you retrieve 3 the information, therefore you don't have 2 the guarantee that you will access (by equal_range) the 1 elements in the order that they were inserted.