根据 C++ 规范，std::set 迭代顺序是否总是升序？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/8833938/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Is the std::set iteration order always ascending according to the C++ specification?
提问by Rodion Gorkovenko
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.
在这里http://www.cplusplus.com/reference/stl/set/我读到 C++ 中的 std::set “通常”实现为一棵树（红黑树？）并且它被排序。
I could not understand, does it mean that by specificationiteration order of set is always ascending? Or is it only "usual implementation detail" and sometimes, some library/compiler may violate this convention?
我不明白，这是否意味着通过规范迭代集合的顺序总是升序？还是只是“通常的实现细节”，有时，某些库/编译器可能会违反此约定？
回答by Fred Foo
Per the C++ standard, iteration over the elements in an std::setproceeds in sorted order as determined by std::lessor by the optional comparison predicate template argument.
根据 C++ 标准，对元素中的迭代std::set按std::less由可选的比较谓词模板参数确定或由可选的比较谓词模板参数确定的排序顺序进行。
(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.)
（同样根据 C++ 标准，插入、查找和删除最多需要 O(lg n) 时间，因此平衡搜索树是目前唯一可行的实现选择std::set，即使标准没有强制要求使用红黑树.)
回答by Darhuuk
It means that internally std::setwill store its elements as a sorted tree. However, the specification says nothing about the sort order. By default, std::setuses std::lessand so will order from low to high. However, you can make the sorting function be whatever you want, using this template parameter:
这意味着在内部std::set将其元素存储为排序树。但是，规范没有说明排序顺序。默认情况下，std::set使用std::less等将从低到高排序。但是，您可以使用此模板参数使排序功能成为您想要的任何功能：
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 Shamim Hafiz
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.
是的，如果按顺序打印出来，set 的值总是升序的。正如描述所说，它通常使用红黑树（RBT）实现，但编译器作者可以选择违反这一点，但通常会坚持 RBT 的主题，因为任何其他实现都不会实现资源高效的任务set。
回答by Marian Petre
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.
默认比较器较小，因此集合将按升序排列。要更改此设置，您可以指定另一个现有的或自定义的比较器作为模板参数。
