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

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

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

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

How to do it...

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

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

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <string>

using namespace std;

数据集会包含city结构体，只是存储的城市的名字和人口数量：
```
struct city {
    string name;
    unsigned population;
};
```

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

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

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

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

查找函数通常会返回迭代器。当函数找到相应的元素时，会返回指向其的迭代器，否则就会返回容器的end迭代器。第二种情况下，我们就不能对该迭代器进行访问。因为要打印输出结果，所以需要实现一个函数，这个函数会返回另一个函数对象，并会将数据结构的end迭代器进行包装。当要对结果进行打印时，会与容器的end迭代器相比较，如果不是end，那么打印出查找到的值；如果是end，则仅打印<end>：
```
template <typename C>
static auto opt_print (const C &container)
{
    return [end_it (end(container))] (const auto &item) {
        if (item != end_it) {
            cout << *item << '\n';
        } else {
            cout << "<end>\n";
        }
    };
}
```

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

int main()
{
    const vector<city> c {
        {"Aachen", 246000},
        {"Berlin", 3502000},
        {"Braunschweig", 251000},
        {"Cologne", 1060000}
    };

使用这个辅助函数构造一个城市打印函数，其会获取到城市vector容器的end迭代器c：
```
    auto print_city (opt_print(c));
```
使用std::find在vector中找到相应的元素——科隆(Cologne)。因为可以直接获得这个元素，所以这个搜索看起来毫无意义。不过，在查找之前并不知道这个元素在vector中的位置，而find函数告诉我们这个元素的具体位置。我们也可以写一个循环，仅对城市名进行比较，而无需比较人口数量。不过，这是个不是很好的设计。下一步，我们将做另外一个实验：
```
    {
        auto found_cologne (find(begin(c), end(c),
            city{"Cologne", 1060000}));
        print_city(found_cologne);
    }
```

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

    {
        auto found_cologne (find_if(begin(c), end(c),
            [] (const auto &item) {
            return item.name == "Cologne";
            }));
        print_city(found_cologne);
    }

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

{
   auto population_more_than ([](unsigned i) {
       return [=] (const city &item) {
           return item.population > i;
       };
   });
   auto found_large (find_if(begin(c), end(c),
       population_more_than(2000000)));
   print_city(found_large);
}

使用的查找函数，线性的遍历容器，查找的时间复杂度为O(n)。STL也有二分查找函数，其时间复杂度为O(log(n))。让我们生成一个新的数据集，其包含了一些整数，并构建了另一个print函数:
```
    const vector<int> v {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    auto print_int (opt_print(v));
```
std::binary_search函数会返回一个布尔值，这个布尔值会告诉你函数是否找到了相应的元素，但是不会将指向元素的迭代器返回。二分查找需要查找的列表是已排序的，否则二分查找将出错：
```
    bool contains_7 {binary_search(begin(v), end(v), 7)};
    cout << contains_7 << '\n';
```
如果需要获得查找的元素，就需要使用其他STL函数。其中之一就是std::equal_range。其不会返回对应元素的迭代器给我们，不过会返回一组迭代器。第一个迭代器是指向第一个不小于给定值的元素。第二个迭代器指向第一个大于给定值的元素。我们的范围为数字1到10，那么第一个迭代器将指向7，因为其是第一个不小于7的元素。第二个迭代器指向8，因为其实第一个大于7的元素：
```
    auto [lower_it, upper_it] (
        equal_range(begin(v), end(v), 7));
    print_int(lower_it);
    print_int(upper_it);
```
当需要其中一个迭代器，可以使用std::lower_bound或std::upper_bound。lower_bound函数只会返回第一个迭代器，而upper_bound则会返回第二个迭代器：
```
    print_int(lower_bound(begin(v), end(v), 7));
    print_int(upper_bound(begin(v), end(v), 7));
}
```

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

$ ./finding_items
{Cologne, 1060000}
{Cologne, 1060000}
{Berlin, 3502000}
1
7
8
7
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。下图能说明其运行的原理：

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

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

template <typename Iterator, typename T>
Iterator standard_binary_search(Iterator it, Iterator end_it, T value)
{
    const auto potential_match (lower_bound(it, end_it, value));
    if (potential_match != end_it && value == *potential_match) {
        return potential_match;
    }
    return end_it;
}

这个函数使用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函数要比通用的算法快很多，因为他们的实现与数据结构强耦合。

Previous改变容器内容 Next将vector中的值控制在特定数值范围内——std::clamp

Last updated 5 years ago