193

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?


Example:

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 is it implementation defined?


Real life reason: I have a std::map with int keys. In very rare situations, I'd like to 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.

5
  • 6
    In case you didn't know: in your real life use you can use map::upper_bound to find the point to start iterating. Oct 4, 2011 at 13:38
  • I know this and I know the exact place I'd start iterating. I just wandered if the order is guaranteed. Oct 4, 2011 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.
    – Coder Guy
    Oct 4, 2014 at 23:05
  • 1
    I don't understand the question, and I'll explain why through a thought-experiment. If you already know that the elements are ordered, how could iteration not be? What does ordering even mean, if it doesn't apply to iteration? What other cases are there where order matters, is detectable, etc.? (The answer was given by Konstantin.) Dec 10, 2017 at 12:27
  • 1
    This is actually quite a funny phenomenon :) People who understand data structure would not understand this question, but people who visualize std::map like a "list" would understand why this question was asked. (of course std::map is not a list). Actually, @underscore_d's comment hit home :)
    – starriet
    Aug 30, 2022 at 1:13

7 Answers 7

211

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 a lucky bonus feature, but rather, it is a fundamental 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).

4
  • std::map is implemented using binary trees, so technically no binary search is performed.
    – jupp0r
    Jun 23, 2015 at 9:49
  • 16
    @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, 2015 at 9:51
  • 2
    I know this is an old post, but to be clear the "efficient lookup" is relative. Technically the std::unordered_map has a more efficient lookup time of O(1). The advantage of std::map is in key ordering, but not lookup. May 25, 2020 at 1:54
  • 2
    @AdamJohnston: in general case with an appropiate key bit distribution you are right. But remember that O(1) is not guaranteed, in worse case scenario it degenerates to O(n). In contrast, O(log n) is guaranteed for any kind of key in the case of std::map.
    – Dredok
    Jan 31, 2022 at 15:01
47

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
positive,
  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.
0
43

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:

  • 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 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).

When the Standard says that elements are ordered in a way, it means that:

  • when iterating, you see the elements in the order defined
  • when iterating in reverse, you see the elements in the opposite order

I hope this clears up any confusion.

3
  • 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. Oct 4, 2011 at 15:32
  • 12
    @KirilKirov: well, the definition of an ordered associative container is that when iterating through it the elements are ordered. Oct 4, 2011 at 17:44
  • Well, I guess you're right, but I didn't know that and that's exactly what I was asking :) Oct 4, 2011 at 18:13
6

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.

I'd like go iterate through all elements, with key, greater than a concrete int value.

That is surely possible.

4

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.

1
  • As the other answers, this does not actually answers my question, thanks anyway. Oct 4, 2011 at 15:35
0

For completeness sake I'd like to mention that if your container includes pointers, the iteration order may differ in each new program run due to ASLR. So even though the order in one run is deterministic, the order across multiple runs is not.

Whether this is important for correctness depends on particular program.

-5

begin() may give the smallest element. But it is implementation depended. Is it specified in the C++ standard? If not, then it is dangerous to make this assumption.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.