how does the stl's multimap insert respect orderings?

Question

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 1

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

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

Answer 2

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

Answer 3

It sounds like multimap is what you 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.

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

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

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

Giving you the ability to iterate the map both ways.

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

Answer 4

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

Answer 5

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

Answer 6

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

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

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

I guess the last approach is the easiest to implement.

---

Option: (not preferable)

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