std::set 迭代顺序是否始终根据 C++ 规范升序?
这里 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.)
相关文章