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

Question

Here http://www.cplusplus.com/reference/stl/set/ I read that std::set in C++ is "typically" implemented as a tree (red-black one?) and it is sorted.

I could not understand, does it mean that by specification iteration order of set is always ascending? Or is it only "usual implementation detail" and sometimes, some library/compiler may violate this convention?

Answer 1

Per the C++ standard, iteration over the elements in an std::set proceeds in sorted order as determined by std::less or by the optional comparison predicate template argument.

(Also per the C++ standard, insertion, lookup and deletion take at most O(lg n) time, so balanced search trees are currently the only viable implementation choice for std::set, even though the use of red-black trees is not mandated by the standard.)

Answer 2

It means that internally std::set will store its elements as a sorted tree. However, the specification says nothing about the sort order. By default, std::set uses std::less and so will order from low to high. However, you can make the sorting function be whatever you want, using this template parameter:

std::set<valueType, comparissonStruct> myCustomOrderedSet;

So for example:

std::set<int, std::greater<int> > myInverseSortedSet;

or

struct cmpStruct {
  bool operator() (int const & lhs, int const & rhs) const
  {
    return lhs > rhs;
  }
};

std::set<int, cmpStruct > myInverseSortedSet;

In fact, these examples are also provided on the website you linked. More specifically here: set constructor.

Answer 3

by specification iteration order of set is always ascending

Yes, the values of set are always ascending if you print them out in sequence. As the description says, it's typically implemented using Red-Black Tree(RBT), but the compiler writers have the option to violate this, but usually the would stick to the Theme of RBT since any other implementation won't be resource efficient to achieve the task of set.

Answer 4

C++11 N3337 standard draft

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3337.pdf

23.2.4 "Associative containers" says:

1 Associative containers provide fast retrieval of data based on keys. The library provides four basic kinds of associative containers: set, multiset, map and multimap.

and:

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

so yes, order is guaranteed by the C++ standard.

This is why gcc 6.4.0 for example implements it as a BST instead of hashmap: What is the underlying data structure of a STL set in C++?

Contrast this with C++11 unordered_set, which tends to provide better performance with a hashmap implementation, at the cost of being more restricted (no free sorted traversal) as shown at:

• What is the underlying data structure of a STL set in C++?
• Why would anyone use set instead of unordered_set? e.g. using a hash set.

Answer 5

The default comparator is less, so the set will be ordered ascending. To change this you can specify another existing or custom comparator as a template argument.