使用排序向量进行快速元素查找

所述 <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);