基於集合的數據結構

在C++中，映射基於黑紅樹，因此插入/刪除函數將花費O（logn），並且hash_map基於散列值。基於集合的數據結構

但我徘徊，什麼數據結構設置爲基礎？

Set是按地圖排序的，因此，它也是基於黑紅樹設置的？

它的密鑰和值如何存儲在該樹中？

如果是這樣，unorder_set的數據結構是什麼？謝謝！

來源

2013-10-30 DoReMi

沒有保證。標準要求唯一的是操作成本，因此實施者可以自由使用他們想要的任何數據結構。通常std::set和std::map是平衡的二叉樹。

此外，std::unordered_set和std::unordered_map是散列表。我相信這實際上是由標準保證的，因爲您可以手動指定散列函數。

來源

2013-10-30 19:45:25 bstamour

的set和map類型可以實現相當多，但是你會喜歡的，只要它符合C++規範，它立足於一個平衡二叉搜索樹的時間複雜度的時間複雜度的時間複雜度的要求。雖然紅色/黑色樹木對於map和set很常見，但它們不是唯一的選擇。你可以讓他們用AVL樹，B樹，AA樹等實現。

希望這有助於！

來源

2013-10-30 19:45:39 templatetypedef

我想你回答了我的其他問題一次，謝謝！這對我有意義。但如果是這樣，地圖和設置有什麼區別？ – DoReMi

我不認爲splay樹能夠保證訂單關聯容器所需的最差情況訪問複雜性。 –

@DietmarKühl-我無法找到任何說複雜性是最壞情況保證的東西，但我也找不到任何說它不是。你有任何一種參考嗎？ – templatetypedef

有序的關聯容器，即std::set<...>和std::map<...>及其「多」版本，都是基於節點的，並且具有最壞情況的複雜性。這意味着使用平衡樹。除了複雜性之外，當樹被突變時，指針和迭代器都不會失效（當然，除了指向對象的指針或迭代器）。

一棵B樹遺憾地沒有正確的迭代器無效屬性（對於映射需要鍵的重複存儲以獲得由於使用std::pair<Key, Value>的強制表示而獲得的大部分優點）。在實踐中，似乎紅/黑樹是最有效的，但還有其他可能的平衡策略，例如AVL樹。跳過列表也可能具有必要的屬性。無論哪種情況，該標準都沒有強制實施具體的戰略。

來源

2013-10-30 19:54:45

正如其他人所說，標準中似乎沒有任何具體實施的保證。但是，標準確實做出了某些性能保證，例如插入O（log n）時間集合，這似乎是您所問的真正問題。

來源

2013-10-30 21:13:06

基於集合的數據結構

回答

相關問題