How Does the Stl's Multimap Insert Respect Orderings

how does the stl's multimap insert respect orderings?

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.

Does multimap guarantee that insertion order matches the order of elements given in its initializer?

[associative.reqmts]:

... i and j satisfy
input iterator requirements and refer to elements implicitly convertible to value_type, [i, j) denotes a
valid range ... il designates an object of type initializer_list<value_type> ...

Expression    Assertion/note
              pre-/post-condition

X(i,j,c)      Effects: Constructs an empty container
              and inserts elements from the range [i, j)
              into it; uses c as a comparison object.

X(i,j)        Effects: Same as above, but
              uses Compare() as a
              comparison object.

X(il)         same as X(il.begin(), il.end())

So, the effects being the same, ordering guarantees are same when constructing from an initialiser list, as they are when inserting a range of iterators.

Being input iterators, the range cannot in general be iterated out of order.

In a multimap when two iterator holds values with same key mapped to differnt Value . How can we find which of them comes before the other in map

I do not think it is possible to know which iterator comes before. It is not even guaranteed that the ordering is respected. You may find more information here.

The key_compare object only compares key values to know whether the first key goes before the second. You may consider it as a minor than operator for keys. It returns false because both keys are equal.

order of elements in std::unordered_multimap

I guess this is implementation specific. In an unordered_multimap elements with same key are stored in the same bucket if the implementation is a bucket hash map, in this case they could be in the same order of insertion (that is probably your situation).

But in an unordered_map implemented, for example, with an open addressing technique, the order could change. I don't know if there are STL implementations which uses different under the hood implementation but the contract of the class doesn't make any assumption on the order of the values for the same key so I don't think you can take it for granted.

Taken from here:

Internally, the elements in the unordered_map are not sorted in any particular order with respect to either their key or mapped values

---

Related Topics