我在cplusplus.com上閱讀，通過傳遞迭代器作爲參數來刪除std::map中元素的操作是恆定時間。std :: map <t1, t2> ::擦除（迭代器位置）的工作？
如果我沒有錯（如果我是，請糾正我）迭代器基本上是指向映射中的元素++運算符只是返回當前元素的順序後繼我猜這就是排序結果通過遍歷std::map實現。
現在如果地圖是一棵紅黑樹，不應該刪除一個元素（使用它的地址）是對數時間操作，我想知道它們是如何在恆定時間內完成的（除非存在高度浪費的內存要做到這一點）。
對於初學者，我會警惕任何來自cplusplus.com的信息;該網站已知有一些錯誤。
訪問cppreference.com，我們得到複雜度爲攤銷恆定時間。這意味着即使單個擦除操作所花費的時間大於O（1），任何序列的操作都需要花費時間O（n）。
事實證明，從紅/黑樹插入或刪除所需的時間最終計算如下：每次插入或刪除花費時間O（log n）來找到節點的位置，但然後只有分期付款O（1）才能插入或刪除元素。這意味着從紅/黑樹插入或刪除節點所做的工作主要由確定該節點的位置所需的工作決定，而不是之後重新平衡樹所需的工作。因此，如果您已經有了一個指向紅/黑樹的指針，並且想要刪除該元素，那麼只需執行分段O（1）工作即可刪除該元素。每個單獨的刪除操作可能需要一些時間（最多O（log n）），但是在n個操作流中，完成的總工作數最多爲O（n）。
請注意，該標準不要求std::map使用紅色/黑色樹。它可以使用另一種類型的數據結構（例如，splay tree，scapegoat tree或確定性的skiplist），這也保證了這種時間複雜性。有趣的是，並非所有的平衡二叉搜索樹結構都可以支持平價的O（1）刪除。例如，AVL tree沒有這個保證。
希望這會有所幫助！
其實，cplusplus.com [也說]（http://www.cplusplus.com/reference/map/map/erase /）它是攤銷常量。 – 2013-03-24 20:03:26
@ ArmenTsirunyan-啊，謝謝！這就是說，我仍然堅持我原來的主張。 :-) – templatetypedef 2013-03-24 20:03:53
不要誤解我的意思。我不是衛冕cplusplus.com :) – 2013-03-24 20:05:18
如果您傳遞迭代器來映射以刪除元素，則根據http://www.cplusplus.com/reference/map/map/erase/將其分攤到不變的時間。
攤銷時間意味着「如果進行多項操作，每次操作所需的平均時間」。因此，可能會有一些操作需要比常量時間更長的時間，但如果您多次執行相同的操作，則會將其攤銷不變。
相關http://stackoverflow.com/questions/12078795/stdmaperase-which-overload-is-faster – 2013-03-24 20:02:45