how does the stl's multimap insert respect orderings?
I have some data which come with a integer index. I am continuous generating new data which needs to added to the collection of data I have, sorted by that index, at the same time I want to easily be able to go the start of the data and iterate through it. This sounds like std::multimap is just what I need.
However, I also need data with the same index to be kept in the order in which it was inserted, in this case meaning that when I iterate through the data I get to the earlier data before the later data.
Does multimap do this?
I haven't found any guarantees that this is the case. In the sgi manual, I didn't see any mention of whether. I tried it on gcc 4.3.4 implementation and it seemed to be true for some limited test cases, but of course I was wondering whether the standard demands this and I can rely on this fact.
Edit: To be clearer in response to some of the answers, I wanted the data sorted first by (non-unique) index and second by insertion time. I had hoped that maybe the second part came for free with multimap, but it seems like it doesn't.
Answer
It seems the new standard (C++11) changed this:
The order of the key-value pairs whose keys compare equivalent is the order of insertion and does not change.[cppreference]
I'm hesitating to use it though, as this seems like a detail easily overlooked when modifying the standard library to be C++11 compliant and it's the sort of detail that will silently cause errors if your compiler's library failed to implement properly.