Does an STL map always give the same ordering when iterating from begin() to end()?

Question

It appears to from my simple testing but I'm wondering if this is guaranteed?

Are there conditions where the ordering will be not be guaranteed?

Edit: The case I'm particularly interested in is if I populate a map with a large number of entries, will the order of the itertator be the same across multiple runs of my executable? What if the entries are inserted in a different order?

Answer 1

Will an STL map give the same ordering with begin/end if it is unchanged? Yes. If you change the map though, do not depend on the ordering remaining the same.

Answer 2

On the same data set under the same implementation of STL, yes. It's not guaranteed to be the same across different implementations as far as I'm aware.

Answer 3

Yes, it maintains an internal order, so iteration over a set that isn't changing should always be the same. From here:

Internally, the elements in the map are sorted from lower to higher key value following a specific strict weak ordering criterion set on construction.

Answer 4

std::map is a sorted container, so, yes, order is guaranteed (the same as the ordering you use implicitly or explicitly in its constructor). Do not count on this for the popular (though not-yet-stanard) hashmap though -- it has very many advantages in many cases wrt std::map, but not a predictable order of iteration!

Answer 5

std::map is a sorted collection
and you would have to define the less than operator
imagine m is a map of type T:

assert(m.size() > 1);
for (std::map<T>::const_iterator i = m.begin(); i != m.end(); ++i) {
    std::map<T>::const_iterator j = i + 1;
    while ( j != m.end() ) {
        assert(*i < *j);
        ++j;
    }
}