根据 C++ 规范，std::set 迭代顺序是否总是升序?
这里 http://www.cplusplus.com/reference/stl/set/ 我读到了C++ 中的 std::set 通常"被实现为一棵树(红黑树?)并且它被排序.
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?
推荐答案
根据 C++ 标准，对 std::set 中元素的迭代按照 std 确定的排序顺序进行::less 或通过可选的比较谓词模板参数.
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.
(同样按照 C++ 标准，插入、查找和删除最多需要 O(lg n) 时间，所以平衡搜索树是目前 std 唯一可行的实现选择:设置，即使标准没有强制要求使用红黑树.)
(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.)
相关文章