Is the std::set iteration order always ascending according to the C++ specification?
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.)
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.
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
.