時間的std ::複雜性上的排序向量

Question

我是從http://www.cplusplus.com/reference/algorithm/upper_bound/ 學習std::upper_bound和我遇到的事實，這可能會在線性時間非隨機訪問迭代器運行來LOWER_BOUND。

我需要使用此排序向量。現在我不知道什麼是非隨機訪問迭代器以及它是否會在排序後的向量上以對數時間運行。

任何人都可以清除這個給我。

Answer 1

§23.3.6.1 [vector.overview]/P1：

的載體是支持隨機訪問迭代器的序列容器。

甲random access iterator是一個能夠計算在一個恆定的時間的任意元素的偏移量，而不需要迭代從一個地方到另一個地方（會導致線性複雜什麼）。

std::lower_bound本身提供了二分法搜索算法的通用實現，它並不太在意用什麼迭代器來指示範圍（它只需要迭代器至少爲forward類別）。它使用像std::advance這樣的幫助函數來迭代限制二進制搜索中的範圍。隨着std::vector<T>::iterator其中是是隨機訪問類別，std::lower_bound以對數時間複雜度運行，涉及迭代元素所需的步驟數，因爲它可以在恆定時間內的每個步驟中將範圍劃分爲一半。

§25.4.3 [alg.binary.search]/P1：

所有的本節中的算法是二進制搜索的版本，並假定序列是 搜索相對於分配到一個表達式通過將搜索關鍵字與參數 綁定而形成隱式或顯式比較函數。他們在非隨機訪問迭代器上工作，最大限度地減少了比較次數，這對於所有類型的迭代器都是對數的。 對於隨機訪問迭代器，它們是特別合適的 ，因爲這些算法在數據結構中執行了一個對數數量的步驟。對於非隨機訪問迭代器，它們執行線性步數。