198

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.

double-beep
  • 5,031
  • 17
  • 33
  • 41
Kiril Kirov
  • 37,467
  • 22
  • 115
  • 187
  • 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. – Steve Jessop Oct 04 '11 at 13:38
  • 1
    I know this and I know the exact place I'd start iterating. I just wandered if the order is guaranteed. – Kiril Kirov Oct 04 '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. – Coder Guy Oct 04 '14 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](https://stackoverflow.com/a/7649415/2757035).) – underscore_d Dec 10 '17 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 '22 at 01:13

7 Answers7

217

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

Alexis Wilke
  • 19,179
  • 10
  • 84
  • 156
Kerrek SB
  • 464,522
  • 92
  • 875
  • 1,084
  • std::map is implemented using binary trees, so technically no binary search is performed. – jupp0r Jun 23 '15 at 09: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 '15 at 09: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. – Adam Johnston May 25 '20 at 01: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 '22 at 15:01
48

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.
Konstantin Oznobihin
  • 5,234
  • 24
  • 31
44

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.

Matthieu M.
  • 287,565
  • 48
  • 449
  • 722
  • 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 04 '11 at 15:32
  • 12
    @KirilKirov: well, the *definition* of an ordered associative container is that when iterating through it the elements are ordered. – Matthieu M. Oct 04 '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 04 '11 at 18:13
7

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.

jpalecek
  • 47,058
  • 7
  • 102
  • 144
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.

Jason
  • 31,834
  • 7
  • 59
  • 78
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.

yugr
  • 19,769
  • 3
  • 51
  • 96
-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.

pyang
  • 109
  • 7