std::map::iterator

When iterating thorugh the elements of an std::map, do you always get them in sorted order (according to the "first"-element)? Tests suggests they do, but that may be implementation dependent, or?

Yes, they will always be in sorted order based on the key.

Maps and multimap containers are containers that manage key/value pairs as elements...They sort their elements automatically...The elements are sorted according to their keys, thus the value doesn't matter for the order of the elements.

The optional third template parameter argument defines the sorting criterion...If a special sorting criterion is not passed, the default criterion less is used. The function object less sorts the elements by comparing them with the operator <.

Maps and multimaps sort their elements automatically according to the keys. Thus they have good performance when searching for elements that have a certain key... Automatic sorting imposes an important constraint on maps and multimaps: You may not change the key of an element...because this might compromise the correct order. To modify the key of an element, you must remove the element that has the old key and insert a new element that has the new key and the old value. As a consequence, from the iterators point of view, the element's key is constant.

The C++ Standard Library(Josuttis) p. 194-196.