Is the order of iterating through std::map known (and guaranteed by the standard)?

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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.

Answer 5

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.

Answer 6

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.

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