std :: set迭代順序是否總是按照C++規範升序？

這裏http://www.cplusplus.com/reference/stl/set/我讀過C++中的std :: set是「通常」實現爲樹（紅黑色的？）並對它進行排序。std :: set迭代順序是否總是按照C++規範升序？

我聽不懂，是不是說按規格 set的迭代次序總是在遞增？或者它只是「通常的實現細節」，有時候，某些庫/編譯器可能會違反這個約定？

來源

2012-01-12 Rodion Gorkovenko

根據C++標準，對std::set中元素的迭代按std::less或可選比較謂詞模板參數確定的排序順序進行。

（也按照C++標準，插入，查找和刪除採取最多O（LG ñ）的時間，因此平衡搜索樹目前爲std::set唯一可行的實現選擇，即使採用紅黑樹木不是標準強制要求的。）

來源

2012-01-12 11:05:38

通過規範迭代順序組始終上升

是，設置的值總是上升的，如果你按順序打印出來。正如描述所述，它通常使用紅黑樹（RBT）實現，但編譯器編寫者可以選擇違反這個規則，但通常會堅持RBT的主題，因爲任何其他實現都不會實現資源高效set的任務。

來源

2012-01-12 11:04:47

默認比較器較少，所以該集合將按照升序排列。要改變這個，你可以指定另一個現有或自定義比較器作爲模板參數。

來源

2012-01-12 11:06:44

這意味着內部std::set將其元素作爲排序樹存儲。但是，該規範沒有說明排序順序。默認情況下，std::set使用std::less，所以會從低到高排列。但是，可以使排序功能是任何你想要的，使用此構造：

std::set<valueType, comparissonStruct> myCustomOrderedSet;

因此，例如：

std::set<int, std::greater<int> > myInverseSortedSet;

或

struct cmpStruct { 
    bool operator() (int const & lhs, int const & rhs) const 
    { 
    return lhs > rhs; 
    } 
}; 

std::set<int, cmpStruct > myInverseSortedSet;

事實上，這些例子也在您鏈接的網站上提供。更具體地說：set constructor。

來源

2012-01-12 11:07:15 Darhuuk

C++ 11 N3337標準草案http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3337.pdf

23.2.4 「關聯容器」表示：

1關聯容器提供一種基於密鑰數據的快速檢索。該庫提供四種基本種類的關聯容器：set，multiset，map和multimap。

和：

10關聯容器的迭代器的基本性質是它們通過在鍵的非遞減的次序，其中非下降是由那是比較所限定的容器迭代用於構建它們。

所以是，順序是由C++標準，作爲主要提到https://stackoverflow.com/a/11812871/895245需要平衡查找樹實現的保證。

也與C++ 11 unordered_set形成對比，其可以提供更好的性能，因爲它具有較少的限制：Why on earth would anyone use set instead of unordered_set?例如，使用哈希集。

來源

2017-01-02 10:11:04

std :: set迭代順序是否總是按照C++規範升序？

回答

相關問題