C STL 中缺少樹容器

C 標準範本庫 (STL) 不提供任何「樹」容器。這項遺漏提出了一個問題：為什麼？什麼是合適的替代方案？

為什麼 STL 中沒有樹容器？

人們可能需要樹資料結構有兩個原因：

1.分層物件表示： 使用樹結構在程式碼中建模樹狀對象層次結構。

2。高效存取特點：保證根據排序關係快速存取元素，類似於二元搜尋樹。

樹結構的替代方案

• Boost Graph Library： 用來表示任意圖，包括分層圖

• 有序關聯容器：

  • std::map 和std::multimap：將鍵對應到值，按鍵排序。
  • std::set 和std::multiset：唯一元素的集合，排序依據value.

這些容器有效地作為平衡二元樹運行，保證插入、刪除和搜尋的高效對數存取時間。它們還提供了其他優點，例如：

• 按排序順序對元素進行恆定時間迭代器遍歷。
• 用於鍵排序的內建比較邏輯。
• 通用接口，允許它們與任何支援比較的鍵類型一起使用Operators.

範例：

如果要儲存員工的層級結構，其中以CEO 為根，並有多個層級的下屬，可以使用std::map<:string std::vector>>。這裡，映射鍵將是員工姓名，關聯向量將保存其直接報告的姓名。

結論

雖然 C STL 沒有提供直接樹容器，它為層次表示和高效存取特性提供了合適的替代方案。 Boost 的圖形庫可以處理複雜的圖形結構，而有序關聯容器則透過通用且完善的介面提供樹狀存取。