Sign up ×

What I mean is - we know that the std::map's elements are sorted according to the keys. So, let's say the keys are integers. If I iterate from std::map::begin() to std::map::end() using a for, does the standard guarantee that I'll iterate consequently through the elements with keys, sorted in ascending order?


std::map<int, int> map_;
map_[1] = 2;
map_[2] = 3;
map_[3] = 4;
for( std::map<int, int>::iterator iter = map_.begin();
     iter != map_.end();
     ++iter )
    std::cout << iter->second;

Is this guaranteed to print 234 or it's implementation defined?

Real life reason: I have a std::map with int keys. In very rare situations, I'd like go iterate through all elements, with key, greater than a concrete int value. Yep, it sounds like std::vector would be the better choice, but notice my "very rare situations".

EDIT: I know, that the elements of std::map are sorted.. no need to point it out (for most of the answers here). I even wrote it in my question.
I was asking about the iterators and the order when I'm iterating through a container. Thanks @Kerrek SB for the answer.

share|improve this question
In case you didn't know: in your real life use you can use map::upper_bound to find the point to start iterating. –  Steve Jessop Oct 4 '11 at 13:38
I know this and I know the exact place I'd start iterating. I just wandered if the order is guaranteed. –  Kiril Kirov Oct 4 '11 at 13:47
A sparse vector wouldn't be sensible if your keys (numeric indices) vary tremendously across the board. I'm using a similar solution for which the numeric index represents a Cartesian y-coordinate in 3-dimensional space. Using a vector in this scenario would increase my memory footprint by gigabytes. So I don't think the vector is a panacea here, far from it. –  Jonathan Neufeld Oct 4 '14 at 23:05

5 Answers 5

up vote 56 down vote accepted

Yes, that's guaranteed. Moreover, *begin() gives you the smallest and *rbegin() the largest element, as determined by the comparison operator, and two key values a and b for which the expression !compare(a,b) && !compare(b,a) is true are considered equal. The default comparison function is std::less<K>.

The ordering is not an lucky bonus feature, but rather, it is a fundemental aspect of the data structure, as the ordering is used to determine when two keys are the same (by the above rule) and to perform efficient lookup (essentially a binary search, which has logarithmic complexity in the number of elements).

share|improve this answer
Nice, thanks! That's what I needed - about *begin() and *rbegin(). –  Kiril Kirov Oct 4 '11 at 15:36
std::map is implemented using binary trees, so technically no binary search is performed. –  jupp0r Jun 23 at 9:49
@jupp0r: Structuring a range as a binary search tree is a particular method to implement binary search through the range. "Binary search" is an abstract concept rather than a particular implementation. It doesn't matter whether you jump through offsets into an array or follow link nodes; those are just specific ways of "bisecting the range". –  Kerrek SB Jun 23 at 9:51
@KerrekSB thanks for enlightening me :) –  jupp0r Jun 24 at 19:53

This is guaranteed by Associative container requirements in the C++ standard. E.g. see 23.2.4/10 in C++11:

The fundamental property of iterators of associative containers is that they
iterate through the containers in the non-descending order of keys where
non-descending is defined by the comparison that was used to construct them.
For any two dereferenceable iterators i and j such that distance from i to j is
  value_comp(*j, *i) == false

and 23.2.4/11

For associative containers with unique keys the stronger condition holds,
  value_comp(*i, *j) != false.
share|improve this answer
+ thanks for the ref to standard –  Slava Feb 13 at 11:13

I think there is a confusion in data structures.

In most languages, a map is simply an AssociativeContainer: it maps a key to a value. In the "newer" languages, this is generally achieved using a hash map, thus no order is guaranted.

In C++, however, this is not so:

  • std::map is a sorted associative container
  • std::unordered_map is a hash-table based associative container introduced in C++11

So, in order to clarify the guarantees on ordering.

In C++03:

  • std::set, std::multiset, std::map and std::multimap are guaranteed to be ordered according to the keys (and the criterion supplied)
  • in std::multiset and std::multimap, the standard does not impose any order guarantee on equivalent elements (ie, those which compare equal)

In C++11:

  • in std::multiset and std::multimap, the Standard imposes that equivalent elements (those which compare equal) are ordered according to their insertion order (first inserted first)
  • std::unordered_* containers are, as the name imply, not ordered. Most notably, the order of elements may change when the container is modified (upon insertion/deletion).

I hope this clears up any confusion.

share|improve this answer
This doesn't have anything to do with my question, sorry :) I know which one are ordered, and which - not. And I'm asking for the order when I'm iterating through the elements. –  Kiril Kirov Oct 4 '11 at 15:32
@KirilKirov: well, the definition of an ordered associative container is that when iterating through it the elements are ordered. –  Matthieu M. Oct 4 '11 at 17:44
Well, I guess you're right, but I didn't know that and that's exactly what I was asking :) –  Kiril Kirov Oct 4 '11 at 18:13

Yes ... the elements in a std::map have a strict weak-ordering, meaning that the elements will be composed of a set (i.e., there will be no repeats of keys that are "equal"), and equality is determined by testing on any two keys A and B, that if key A is not less than key B, and B is not less than A, then key A is equal to key B.

That being said, you cannot properly sort the elements of a std::map if the weak-ordering for that type is ambiguous (in your case, where you are using integers as the key-type, that is not a problem). You must be able to define a operation that defines a total order on the type you are using for the keys in your std::map, otherwise you will only have a partial order for your elements, or poset, which has property where A may not be comparable to B. What will typically happen in this scenario is that you'll be able to insert the key/value pairs, but you may end up with duplicate key/value pairs if you iterate through the entire map, and/or detect "missing" key/value pairs when you attempt to perform a std::map::find() of a specific key/value pair in the map.

share|improve this answer
As the other answers, this does not actually answers my question, thanks anyway. –  Kiril Kirov Oct 4 '11 at 15:35

Is this guaranteed to print 234 or it's implementation defined?

Yes, std::map is a sorted container, ordered by the Key with the supplied Comparator. So it is guaranteed.


That is surely possible.

share|improve this answer

Your Answer


