我應該使用哪個容器快速查找元素，知道通過構建它已經訂購了？

Question

我必須使用一個容器，這個容器的構造已經訂購了，我需要一個快速查找功能。

我的想法是使用一個集合來利用它的set.find，這應該足夠快，但構建我的集合set.insert可能會很慢，因爲我已經知道元素是有序的！

對於這部分，我可以使用帶有vector.push_back的矢量，但是我應該自己寫這個查找函數，它也會比set::find慢......你對我有什麼建議？

編輯：

• 容器需要修改，但將永遠是有序的，並且其規模將始終是相同的（但我不知道它的先驗）
• 沒有重複值。
• 發現比插入更多。
• 我只需要知道它是否存在，而不是它的位置。
• 我找到了std :: binary_search。好嗎？

Answer 1

如果輸入範圍已經排序，那麼從一對迭代器構造set保證爲O（N），因此您可以使用它。 （例如參見http://en.cppreference.com/w/cpp/container/set/set。）

後續插入是O（logN）。

雖然如果總大小不是那麼大的排序vector傾向於擊敗一切，因爲它是如此緩存友好。 std::binary_search是O（log N），與set::find相同。

std::unordered_set不關心您的訂購，但確實會給你O（1）查找（平均而言，沒有保證）。

Answer 2

std::vector與std::make_heap()，push_heap()，pop_heap()和sort_heap()可以幫助你以最快的速度std::set處理。但是，您需要手動使用std :: binary_search。