Is std::multimap Really Just Nested Vectors

Question

I want to use a std::multimap container, but I need to know that it will always maintain order, as in the first element in will be the first element iterated over and the second will always be the second.
What I'm asking is this:

Is std::multimap< key, value > equivalent to std::vector< std::pair< const key, std::vector< value > > >

Answer 1

A multimap is not the equivalent of a vector, not in terms of implementation. Multimaps are usually implemented as a binary search tree. The elements of a multimap are always kept in a sorted order by their key following a strict weak order criteria indicated by the comparison object.

Thus, when you iterate over the elements of a multimap their order is the sorted order provided by the comparison object.

Answer 2

Is std::multimap< key, value > equivalent to std::vector< std::pair< const key, std::vector< value > > > ?

No, these are two different containers and they exhibit many differences in how they store underlying data, how they manage the memory, how you can access this data and in order the data is stored. In vector the data is stored in order that you have push_back ed it, but in multimap data is always sorted, so e.g. the last value you have inserted into multimap may be actually accessed with multimap.begin() or multimap.begin() + 10.

You can have an integer key in multimap and insert with incremented key to force order of sort be same as order of insertion.

Answer 3

Although they are not the same in terms of implementation, your question indicates that you're really just concerned about the ordering. I found the following information related to the ordering:

Multimaps are associative containers that store elements formed by a combination of a key value and a mapped value, following a specific order, and where multiple elements can have equivalent keys.

Internally, the elements in a multimap are always sorted by its key following a specific strict weak ordering criterion indicated by its internal comparison object (of type Compare).

_{Source, cplusplus.com}

Answer 4

A std::vector< std::pair< const key, std::vector< value > > > allows you to have any ordering of the key elements, whereas a std::multimap<key, value> doesn't.

From cppreference:

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.

It sounds like you are asking what is the order among equivalent entries.

The order of the key-value pairs whose keys compare equivalent is the order of insertion and does not change. (since C++11)

You can keep a vector in the same order as what a multimap provides, by making sure that you insert new entries after all the existing equivalent entries, but before any entries who's keys are later in the order. A simple way would to gate all insertion through

vec.insert(std::upper_bound(vec.begin(), vec.end(), to_insert, key_compare), to_insert);