Is the std set iteration order always ascending according to the C specification

Question

According to what I've read, std::set in C++ is "usually" implemented as a tree (red-black one?) that is sorted.

I'm not sure what you mean; does it indicate that the iteration order of the set is always ascending by specification?

Or is it just "normal implementation detail," and some library/compiler may break this convention from time to time?

Answer 1

Iteration over the elements in a std::set goes in sorted order, as specified by std::less or the optional comparison predicate template parameter, according to the C++ standard.

(Also, according to the C++ standard, insertion, lookup, and deletion all take at most O(lg n) time, therefore balanced search trees are presently the only possible implementation choice for std::set, even if the usage of red-black trees is not required.)