std :: map迭代器是如何工作的？

C++ STL類std :: map使用二叉樹實現O（log（n））查找。但是對於樹來說，迭代器如何工作並不明顯。 ++操作符在樹結構中究竟意味着什麼？而「下一個元素」的概念在數組中有明顯的實現，而對於我來說，它在樹中並不是那麼明顯。如何實現一個樹迭代器？std :: map迭代器是如何工作的？

來源

2012-09-04 Avi

您可以查看源代碼作爲啓動程序：http://www.sgi.com/tech/stl/stl_map.h – amit

查看典型的[自我平衡二叉搜索樹]（http：// en.wikipedia.org/wiki/Red%E2%80%93black_tree）。很容易看到一個算法從給定節點到另一個更大的節點，方法是查看正確的子節點或上下樹。有時你必須跳幾次，但它仍然是分期固定的時間（因爲樹的高度是元素數的對數）。 –

本維基百科文章可能會回答您的一些問題：[樹遍歷]（http://en.wikipedia.org/wiki/Tree_traversal）。基本上，「下一個」元素可以根據使用的遍歷類型而有所不同。在'std :: map'的情況下，按順序遍歷樹（從最小元素到最大元素）。 –

對於一個遍歷（可能也適用於其他），如果你的節點中有一個父指針，你可以做一個非遞歸遍歷。應該可以在你的迭代器中存儲兩個指針：你需要指出你在哪裏，你可能（我現在沒有在做研究）需要像「前一個」指針那樣的東西，所以你可以弄清楚你當前的移動方向（即，我是否需要進入左側子樹，還是隻是從它回來）。

「以前的」將會是可能是是類似「父母」，如果我們剛剛進入節點;如果我們從左側子樹回來，則返回「left」，如果我們從右側子樹回來，則返回「right」，如果我們返回的最後一個節點是我們自己的，則返回「self」。

來源

2012-09-04 08:42:45

一個實現可能知道節點指針是字對齊的，並濫用節點指針的低位來存儲狀態，而不是使用第二個指針。 – MSalters

我認爲這是我需要的。基本上我試圖爲一個通用樹類創建一個迭代器，並且這看起來適用於n元無序樹。 – Avi

考慮映射中不小於當前元素且不是當前元素的所有元素的集合。「下一個元素」是該元素集中的元素小於該集合中所有其他元素的元素。

爲了使用地圖，您必須有一個鍵。而且這個鍵必須執行一個「小於」操作。這決定了地圖的形成方式，以便查找，添加，刪除，增加和減少操作是有效的。

通常地圖內部使用某種樹。

來源

2012-09-04 08:34:21

std :: map迭代器是如何工作的？

回答

相關問題