使用STL的紅黑樹內部實現

我知道我的STL（帶有g ++ 4.x.x）使用紅黑樹來實現像地圖這樣的容器。是否可以直接使用STL的內部紅黑樹。如果是這樣，怎麼樣？如果沒有，爲什麼不 - 爲什麼STL不暴露紅黑樹？使用STL的紅黑樹內部實現

令人驚訝的是，我找不到使用谷歌的答案。

編輯：我正在調查使用紅黑樹作爲解決額外的分配器構造函數調用插入。見this question。我的STL使用紅黑樹來實現地圖。的set和map

2012-07-08 Prasoon Tiwari

「我正在研究使用紅黑樹作爲插入時額外分配器構造函數調用的解決方案。」一個適當的解決方案是使用沒有這個屬性的標準容器的實現。 C++ 11需要有狀態的分配器，所以任何正確支持這個C++ 11特性的標準庫都會有更合理的行爲（儘管它仍然會構造不同的分配器實例，它只會從原始分配器對象中實現）。 – 2012-07-08 06:56:06

@Prasoon - 它不會幫助你，因爲它是構造函數調用的底層樹實現。嘗試比gcc 4.1更新的編譯器會是一個選項（前面的問題[STL映射的自定義內存分配器]（http：// stackoverflow。COM /問題/ 11373796 /自定義內存分配器換STL-MAP）） – 2012-07-08 07:16:34

其實 - 答案很簡單，而且與你的gcc版本無關。您可以從sgi's website下載stl源代碼，並查看自己的實施和使用情況。

例如，在版本3.2中，您可以在stl_tree.h文件中看到紅黑樹實現，以及它在stl_set.h中的使用示例。

請注意，由於stl類是模板類，實現實際上是在頭文件中。

來源

2012-07-08 08:02:41

大多數STL的實現是紅黑樹我相信，雖然沒有什麼是使用不同的數據結構實現它們阻止別人 - 如果我沒有記錯，C++標準不需要RB樹的實現。

STL不公開它，因爲這會違反OOP原則。如果其他人使用您的庫，公開底層數據結構可能會導致一些不受歡迎的行爲。也就是說，對於set和map，您應該只允許訪問符合set和map數據結構的方法。公開底層表示可能會導致用戶在set內出現重複，這很糟糕。

這就是說，有沒有辦法（據我所知）直接使用底層的紅黑樹..這將取決於你如何使用它。實現你自己的紅黑樹最有可能是你最好的選擇，或者點擊我們的第三方庫（也許升壓？）

來源

2012-07-08 06:32:22 adelbertc

你甚至不給保證所使用的數據結構是爲紅色黑樹（例如，它至少作爲一個AVL樹實現一次，而像B，B *或B +樹的東西可能也會很好）。因此，獲取內部消息的唯一方法是查看特定的實現，並利用它不公開的（至少試圖公開的）事物。

至於爲什麼：我認爲主要是因爲它是一個抽象的嘗試，而不是公開所有的實現細節。

來源

2012-07-08 06:33:41

使用STL的紅黑樹內部實現

回答

相關問題