使用排序向量進行快速元素查詢

所述 <algorithm> 頭提供了許多有用的功能與排序的向量工作。

使用有序向量的一個重要先決條件是儲存的值與 < 相當。

可以使用函式 std::sort() 對未排序的向量進行排序 ：

std::vector<int> v;
// add some code here to fill v with some elements
std::sort(v.begin(), v.end());

排序向量允許使用函式 std::lower_bound() 進行有效的元素查詢。與 std::find() 不同，它在向量上執行有效的二進位制搜尋。缺點是它只為排序的輸入範圍提供有效結果：

// search the vector for the first element with value 42
std::vector<int>::iterator it = std::lower_bound(v.begin(), v.end(), 42);
if (it != v.end() && *it == 42) {
    // we found the element!
}

注意： 如果請求的值不是向量的一部分，則 std::lower_bound() 將向第一個元素返回一個大於請求值的迭代器。這種行為允許我們在已經排序的向量中的正確位置插入一個新元素：

int const new_element = 33;
v.insert(std::lower_bound(v.begin(), v.end(), new_element), new_element);

如果你需要一次插入很多元素，首先為所有元素呼叫 push_back() 可能會更有效，然後在插入所有元素後呼叫 std::sort()。在這種情況下，分揀成本的增加可以抵消在向量末端而不是在中間插入新元素的降低成本。

如果向量包含多個具有相同值的元素，std::lower_bound() 將嘗試將迭代器返回到搜尋值的第一個元素。但是，如果需要在搜尋值的最後一個元素之後插入一個新元素，則應使用函式 std::upper_bound()， 因為這將導致元素周圍移動較少：

v.insert(std::upper_bound(v.begin(), v.end(), new_element), new_element);

如果你需要上限和下限迭代器，你可以使用函式 std::equal_range() 通過一次呼叫有效地檢索它們：

std::pair<std::vector<int>::iterator,
          std::vector<int>::iterator> rg = std::equal_range(v.begin(), v.end(), 42);
std::vector<int>::iterator lower_bound = rg.first;
std::vector<int>::iterator upper_bound = rg.second;

為了測試元素是否存在於有序向量中（儘管不是向量特定），你可以使用函式 std::binary_search() ：

bool exists = std::binary_search(v.begin(), v.end(), value_to_find);