Order of items in QMap and QMultiMap

Question

I would like to use QMultiMap (which is derived from QMap) to store key/value pairs. Since I can have keys multiple times I would prefer to use QMultiMap.

Assume I would insert the following pairs in the given order:

"C" -> 5
"A" -> 10
"B" -> 77
"B" -> 1
"X" -> 314159

When iterating over the map (using java style iterators preferably) I need the order of equal-key-pairs to be preserved. I.e. "B" -> 77 and "B" -> 1 should appear exactly in insertion order when iterating. The order between keys that are different does not matter.

Unfortunately the documentation doesn't tell something about that detail. It says

With QMap, the items are always sorted by key

but it does not say if/how it sorts equal keys.

Does QMap preserve the insertion order of pairs with equal keys or can it be preserved in some way?

Answer 1

From the Qt documentation about QMap::iterator :

Unlike QHash, which stores its items in an arbitrary order, QMap stores its items ordered by key. Items that share the same key (because they were inserted using QMap::insertMulti(), or due to a unite()) will appear consecutively, from the most recently to the least recently inserted value.

So it seems that QMap keeps the reversed insertion order of pairs with equal keys.

Answer 2

There is an overload QMap::insertMulti(const_iterator pos, const Key &key, const T &value), where pos is a "hint" and you can pass constBegin() or constEnd(), or some iterator in the middle of the collection where you want to make the insertion. This is the way to dictate the order when you have duplicate keys.

I think it might be luck that one can generally see the order preserved as though it were a stack...