C++中使用了什麼算法stl map.find（）？

所以我覺得map.find()實現二進制搜索算法

是否確定？我使用的地圖是這樣的：

std::map<int,MyObject>

2013-10-16 makerj

由於'std :: map :: find'爲對數時間複雜度，因此強烈建議使用二進制搜索。如果你想知道它是如何實現的，你應該看看你的include目錄中的'map'標題。 – Zeta

備註：gcc 4.6.3使用紅黑樹，並以二進制方式遍歷樹。看看'/bits/stl_tree.h'並搜索'find'，'_M_lower_bound'。請記住'_S_left'，'_S_right'在迭代中返回左/右繼承者而不是下一個元素。如果您查看代碼，也不要發瘋。 – Zeta

庫標準沒有指定任何特定的實現，只是行爲和性能的要求。特別是，find()必須採取對數時間，這在實踐中需要類似二進制搜索的東西。

紅黑樹或其他平衡搜索樹是常見的實現。

2013-10-16 10:52:15

嚴。二進制搜索按間隔減半工作。幾乎可以肯定'std :: map :: find'不會*這樣做，除非你考慮樹遍歷是間隔減半（因爲你忽略了潛在的子樹）。不確定這是一個常用的術語。它似乎延伸了定義。 –

@KonradRudolph從一個稍微不同的角度來看，一個平衡二叉樹不過是一個可能的區間對分實現。所以我會說「二進制搜索」在這裏很好。 – Angew

@KonradRudolph：我會使用「二進制搜索」來表示「逐漸丟棄一半的搜索空間」，無論這個空間是否是一個間隔。其他人可能會堅持認爲它只應用於區間搜索，但我不知道在這種情況下應該使用通用術語。 –

回答