Are the elements in a std::map guaranteed to be ordered?

Question

Is this just an implementation side effect (red-black tree) or the order is guaranteed by the c++ standard?

Answer 1

It's guaranteed by the c++ standard.

Answer 2

Guaranteed. If you want something that's not constrained by this try boost::unordered_map<>

Answer 3

Ordered iteration is not an implementation detail; it is guaranteed by the C++ standard. It is a fundamental property of all associative containers (C++03 §23.1.2/9):

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

value_comp is the comparator with which the map was constructed (by default, it is std::less<T>).

Answer 4

§23.1.2/2:

Each associative container is parameterized on Key and an ordering relation Compare that induces a strict weak ordering (25.3) on elements of Key. … The object of type Compare is called the comparison object of a container. This comparison object may be a pointer to function or an object of a type with an appropriate function call operator.

The default Compare object is the less-than function std::less<Key>.

The ordering is a property of the function. It's a requirement, not a side effect.

Sorting the objects is a side effect. 23.1.2/10 and 23.1.2/9 (quoted by James) guarantee that map/set and multimap/multiset have increasing/non-decreasing keys, respectively, over the sequence from begin to end.