在有序和无序的vector中查找元素

通常，需要确定某种元素在某个容器范围内是否存在。如果存在，我们会对这个值进行修改，或者访问与其相关的值。

查找元素的目的是不同的。当想要让在一段已排序的元素中进行查找，可以使用二分查找法，这种方法要比线性查找快的多。如果没有排序，那么就只能进行线性遍历来查找对应的值。

传统的STL查找算法我们都可以使用，所以了解一下这些算法。本节将会使用两个不同的算法，线性查找算法std::find，二分查找算法std::equal_range。

How to do it…

本节，我们将对一个比较小的数据集进行线性和二分查找：

  1. 包含必要的头文件，以及声明所使用的命名空间。

    1. #include <iostream>
    2. #include <vector>
    3. #include <list>
    4. #include <algorithm>
    5. #include <string>
    7. using namespace std;

  2. 数据集会包含city结构体，只是存储的城市的名字和人口数量：

    1. struct city {
    2.     string name;
    3.     unsigned population;
    4. };

  3. 搜索算法需要将元素与目标对象进行对比，所以我们需要重载city结构体的==操作符：

    1. bool operator==(const city &a, const city &b) {
    2.     return a.name == b.name && a.population == b.population;
    3. }

  4. 我们也需要将city实例进行打印，所以我们对其输出操作符<<也进行了重载：

    1. ostream& operator<<(ostream &os, const city &city) {
    2.     return os << "{" << city.name << ", "
    3.         << city.population << "}";
    4. }

  5. 查找函数通常会返回迭代器。当函数找到相应的元素时，会返回指向其的迭代器，否则就会返回容器的end迭代器。第二种情况下，我们就不能对该迭代器进行访问。因为要打印输出结果，所以需要实现一个函数，这个函数会返回另一个函数对象，并会将数据结构的end迭代器进行包装。当要对结果进行打印时，会与容器的end迭代器相比较，如果不是end，那么打印出查找到的值；如果是end，则仅打印<end>：

    1. template <typename C>
    2. static auto opt_print (const C &container)
    3. {
    4.     return [end_it (end(container))] (const auto &item) {
    5.         if (item != end_it) {
    6.             cout << *item << '\n';
    7.         } else {
    8.             cout << "<end>\n";
    9.         }
    10.     };
    11. }

  6. 我们使用德国的一些城市对vector进行实例化：

    1. int main()
    2. {
    3.     const vector<city> c {
    4.         {"Aachen", 246000},
    5.         {"Berlin", 3502000},
    6.         {"Braunschweig", 251000},
    7.         {"Cologne", 1060000}
    8.     };

  7. 使用这个辅助函数构造一个城市打印函数，其会获取到城市vector容器的end迭代器c：

    1.     auto print_city (opt_print(c));

  8. 使用std::find在vector中找到相应的元素——科隆(Cologne)。因为可以直接获得这个元素，所以这个搜索看起来毫无意义。不过，在查找之前并不知道这个元素在vector中的位置，而find函数告诉我们这个元素的具体位置。我们也可以写一个循环，仅对城市名进行比较，而无需比较人口数量。不过，这是个不是很好的设计。下一步，我们将做另外一个实验：

    1.     {
    2.         auto found_cologne (find(begin(c), end(c),
    3.             city{"Cologne", 1060000}));
    4.         print_city(found_cologne);
    5.     }

  9. 当不需要知道对应城市的人口数量时，就不需要使用==操作符，只需要比较城市名称就好。std::find_if函数可以接受一个函数对象作为谓词函数。这样，就能只使用城市名来查找“科隆”了：

    1.     {
    2.         auto found_cologne (find_if(begin(c), end(c),
    3.             [] (const auto &item) {
    4.             return item.name == "Cologne";
    5.             }));
    6.         print_city(found_cologne);
    7.     }

  10. 为了让搜索更加优雅，可以实现谓词构建器。population_higher_than函数对象能接受一个人口数量，并且返回人口数量比这个数量多的城市。在这个小数据集中找一下多于2百万人口的城市。例子中，只有柏林(Berlin)符合条件：

    1. {
    2.    auto population_more_than ([](unsigned i) {
    3.        return [=] (const city &item) {
    4.            return item.population > i;
    5.        };
    6.    });
    7.    auto found_large (find_if(begin(c), end(c),
    8.        population_more_than(2000000)));
    9.    print_city(found_large);
    10. }

  11. 使用的查找函数，线性的遍历容器，查找的时间复杂度为O(n)。STL也有二分查找函数，其时间复杂度为O(log(n))。让我们生成一个新的数据集，其包含了一些整数，并构建了另一个print函数:

    1.     const vector<int> v {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    3.     auto print_int (opt_print(v));

  12. std::binary_search函数会返回一个布尔值，这个布尔值会告诉你函数是否找到了相应的元素，但是不会将指向元素的迭代器返回。二分查找需要查找的列表是已排序的，否则二分查找将出错：

    1.     bool contains_7 {binary_search(begin(v), end(v), 7)};
    2.     cout << contains_7 << '\n';

  13. 如果需要获得查找的元素，就需要使用其他STL函数。其中之一就是std::equal_range。其不会返回对应元素的迭代器给我们，不过会返回一组迭代器。第一个迭代器是指向第一个不小于给定值的元素。第二个迭代器指向第一个大于给定值的元素。我们的范围为数字1到10，那么第一个迭代器将指向7，因为其是第一个不小于7的元素。第二个迭代器指向8，因为其实第一个大于7的元素：

    1.     auto [lower_it, upper_it] (
    2.         equal_range(begin(v), end(v), 7));
    3.     print_int(lower_it);
    4.     print_int(upper_it);

  14. 当需要其中一个迭代器，可以使用std::lower_bound或std::upper_bound。lower_bound函数只会返回第一个迭代器，而upper_bound则会返回第二个迭代器：

    1.     print_int(lower_bound(begin(v), end(v), 7));
    2.     print_int(upper_bound(begin(v), end(v), 7));
    3. }

  15. 编译并运行这个程序，我们看到如下输出：

    1. $ ./finding_items
    2. {Cologne, 1060000}
    3. {Cologne, 1060000}
    4. {Berlin, 3502000}
    5. 1
    6. 7
    7. 8
    8. 7
    9. 8

How it works…

本节使用的STL查找算法：

算法函数 作用
std::find 可将一个搜索范围和一个值作为参数。函数将返回找到的第一个值的迭代器。线性查找。
std::find_if 与std::find原理类似，不过其使用谓词函数替换比较值。
std::binary_search 可将一个搜索范围和一个值作为参数。执行二分查找，当找到对应元素时，返回true；否则，返回false。
std::lower_bound 可将一个查找返回和一个值作为参数，并且执行二分查找，返回第一个不小于给定值元素的迭代器。
std::upper_bound 与std::lower_bound类似，不过会返回第一个大于给定值元素的迭代器。
std::equal_range 可将一个搜索范围和一个值作为参数，并且返回一对迭代器。其第一个迭代器和std::lower_bound返回结果一样，第二个迭代器和std::upper_bound返回结果一样。

所有这些函数，都能接受一个自定义的比较函数作为可选参数传入。这样就可以自定义的进行查找，就如我们在本章做的那样。

来看一下std::equal_range是如何工作的。假设我们有一个vector，v = {0, 1, 2, 3, 4, 5, 6, 7, 7, 7, 8}，并且调用equal_range(begin(v), end(v), 7);，为了执行对7的二分查找。如equal_range要返回一对上下限迭代器那样，这个结果将返回一段区域{7, 7, 7}，因为原始vector中有很多7，所以这个子队列中也有很多7。下图能说明其运行的原理：

在有序和无序的vector中查找元素 - 图1

首先，equal_range会使用典型的二分查找，直到其找到那个不小于查找值的那个元素。而后，另一个迭代器也是用同样的方式找到。如同分开调用lower_bound和upper_bound一样。

为了获得一个二分查找函数，并返回其第一个适配条件的元素。我们可以按照如下的方式实现：

  1. template <typename Iterator, typename T>
  2. Iterator standard_binary_search(Iterator it, Iterator end_it, T value)
  3. {
  4.     const auto potential_match (lower_bound(it, end_it, value));
  5.     if (potential_match != end_it && value == *potential_match) {
  6.         return potential_match;
  7.     }
  8.     return end_it;
  9. }

这个函数使用std::lower_bound，为的就是找到第一个不大于value的元素。返回结果potential_match，有三种情况：

  • 没有值不小于value。这样，返回值和end_it(end迭代器)一样。
  • 遇到的第一个不小于value的元素，同时也大于value。因此需要返回end_it，表示没有找到相应的值。
  • potential_match指向的元素与value相同。这个匹配没毛病。因此就返回相应的迭代器。

当类型T没有==操作符时，需要为二分查找提供一个<操作实现。然后，可以将比较重写为!(value < *potential_match) && !(*potential_match < value)。如果它们不小于，也不大于，那么必定等于。

STL中因为缺少对多次命中的“定义”，所以并没有提供相应的函数来适配多次命中。

Note：

需要留意std::map和std::set等数据结构，它们有自己的find函数。它们携带的find函数要比通用的算法快很多，因为他们的实现与数据结构强耦合。