C ++ std ::设置迭代顺序（按规范） [英] C++ std::set iteration order (by specification)

问题描述

此处 http://www.cplusplus.com/reference/stl/set/ 我读过在C ++中的std :: set是通常实现为一个树（红黑一个？），它被排序。

我不明白， 按规范设置的迭代顺序始终为升序？

解决方案

根据C ++标准，这是一个常见的实现细节，在 std :: set 中的元素的迭代按照 std :: less 或由可选的比较谓词模板参数。

（另外根据C ++标准，插入，查找和删除最多花费O（lg n ，所以平衡的搜索树目前是 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?

解决方案

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.)

这篇关于C ++ std ::设置迭代顺序（按规范）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！