std::set 迭代顺序是否始终根据 C++ 规范升序?

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

这篇关于std::set 迭代顺序是否始终根据 C++ 规范升序?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持编程学习网！