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.