Menu
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.
327
Multimap is an associative container that contains a sorted list of key-value pairs, while permitting multiple entries with the same key. Sorting is done according to the comparison function Compare , applied to the keys. Search, insertion, and removal operations have logarithmic complexity.
Multimap is similar to a map with the addition that multiple elements can have the same keys. Also, it is NOT required that the key-value and mapped value pair have to be unique in this case. One important thing to note about multimap is that multimap keeps all the keys in sorted order always.
insert(key, value): Adds a new element or pair to the multimap. erase(iterator position): Removes the element at the position pointed by the iterator. erase(const x): Removes the key-value 'x' from the multimap. clear(): Removes all the elements from the multimap.
The map and the multimap are both containers that manage key/value pairs as single components. The essential difference between the two is that in a map the keys must be unique, while a multimap permits duplicate keys.
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.
146
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.
22
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
