在C++中設置實現？

根據以下鏈接 - http://www.cplusplus.com/reference/set/set/在C++的STL中的集合通常實現爲二叉搜索樹，我能夠在諸如整數或字符集或浮點數或字符串的情況下評估數據類型的行爲，如在這些情況下很容易看到BST排序被強加在集合元素上，但考慮到集合的二叉搜索樹數據結構實現，我無法想象如何使用二叉搜索樹實現以下數據類型：在C++中設置實現？

set<vector<int>>或set<vector<string>>或set<vector<double>>或set<list<int>>
set<map<int, int>>
set<stack<int>>

或與此有關的許多其他數據類型，如何分配給這些類型的內存，以及如何保持排序。

此外，無論何時將新矢量添加到集合中，集合數據類型是否內部檢查集合中的所有矢量用於相似度還是所有用於相似度的地圖，我都無法弄清楚以下內容：我無法弄清楚。如果有人能幫助我想象這些概念，那將是非常棒的。

感謝提前:)

來源

2013-04-07 AnkitSablok

內存分配相同（即代替'new int'它是'new vector '），並且排序也是一樣的（使用'operator <'）（例如，[這裏是一個鏈接]（ http://en.cppreference.com/w/cpp/container/vector/operator_cmp）給vector的比較運算符）。 – Cornstalks 2013-04-07 16:02:36

一個set<T>總是以同樣的，無論是什麼具體類型T是。在插入時，它會通過使用std::less<T>（默認情況下調用operator<）將其與各種現有元素進行比較來計算放置新元素的樹^*中的哪個位置。如果operator<沒有超載爲T，那麼它將不會編譯。

因此，如何訂購T實例的細節是從如何維護集合的細節中抽象出來的。

_{*注意std::set不必使用一棵樹;這只是一個典型的實現。}

來源

2013-04-07 16:04:30

該集合使用嚴格的弱排序來確定每個元素的位置。這是默認使用std::less<T>完成的。這將導致致電operator<(const T&, const T&)。現在，容器如std::vectorhave such operators，它們只是執行所有元素的lexicographical comparison。這就是std::set<std::vector<int>>可以開箱即用的方式。

當插入一個新元素時，設置不是必須檢查所有元素。插入是一個對數複雜度操作，這就是爲什麼實現往往是一個自平衡二叉樹（我用這個相當奇怪的因果關鍵詞，因爲C++標準沒有指定實現應該是什麼樣子，它應該如何表現。）

來源

2013-04-07 16:04:42 juanchopanza

如果你在一個集合中插入一個向量，那麼如何插入是一個對數時間操作，這是一個複雜的理解我無法弄清楚的問題 – AnkitSablok 2013-04-07 16:15:39

@Coder是二叉搜索樹的全部點。如果您有一棵平衡樹，則執行O（log_2（N））比較來找到正確的位置。把它想象爲爲給定值執行正確位置的搜索。 – juanchopanza 2013-04-07 16:17:26

實現如何決定樹中插入向量的位置以及在什麼基礎上進行什麼樣的詞典對比？ – AnkitSablok 2013-04-07 16:20:00

在C++中設置實現？

回答

相關問題