根据 C++ 规范，std::set 迭代顺序是否总是升序? [英] Is the std::set iteration order always ascending according to the C++ specification?

问题描述

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

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