迭代std :: set/std :: map的時間複雜度是多少？

迭代通過std::set/std::map的時間複雜度是多少？我相信它在集合/地圖的大小上是線性的，但不太確定。它在語言標準中有規定嗎？迭代std :: set/std :: map的時間複雜度是多少？

來源

2012-08-02 updogliu

整個容器的迭代將始終是'O（n）'_at least_（我認爲真正愚蠢的實現可能會使它變得更糟糕） – Chad 2012-08-02 14:43:39

當你說「遍歷」時，你究竟是什麼意思？你在使用標準迭代器編寫一個while/for循環嗎？你在使用其中一種標準算法嗎？ – 2012-08-02 14:51:14

在draft C++11 standard N3337的答案可以在§找到24.2.1段8：

所有迭代器的類別只需要那些變現爲一個功能按固定時間給定類別（攤銷）。

由於上一個迭代每個操作必須是恆定的時間，通過n元件迭代必須O(n)。

來源

2012-08-02 14:55:45

如果使用父指針將映射/集合實現爲二叉樹，則遍歷所有元素將至多訪問每個樹節點3次。如果實現是一個帶有父指針的b樹，則每個節點最多訪問2 * n + 1次，n是節點中元素的數量。在這兩種情況下，這意味着每個迭代步驟的恆定平均時間複雜度。我不知道有任何其他符合實現地圖/設置的方法。 – WaltK 2017-04-08 14:21:38

我相信它在集合/地圖的大小上是線性的，但是肯定不是那麼的。

這是正確的。通過整個集合或地圖迭代是O(N)

來源

2012-08-02 14:41:37

迭代std :: set/std :: map的時間複雜度是多少？

回答

相關問題