首页 > 编程笔记 > C++笔记 阅读：15

C++查找元素方法汇总（附带实例）

应用程序中最常见的操作之一就是搜索数据。因此，标准库提供了许多通用算法来搜索标准容器或者任何可以表示 range 并由开始迭代器和结束迭代器定义的内容，这并不奇怪。

对于本节中的所有例子，我们将使用 std::vector，但所有算法都使用由开始迭代器和结束迭代器定义的range，根据算法的不同，可以使用输入迭代器或前向迭代器，所有这些算法都可以在头文件 <algorithm> 的 std 命名空间中找到。

以下是可用于在 range 内查找元素的算法：
1) 使用 std::find() 在 range 内查找值。此算法将返回一个迭代器，该迭代器指向与该值相等的第一个元素： 
std::vector<int> v{ 1, 1, 2, 3, 5, 8, 13 };

auto it = std::find(v.cbegin(), v.cend(), 3);
if (it != v.cend()) std::cout << *it << '\n';

2) 使用 std::find_if() 在 range 内查找满足一元谓词条件的值。此算法将返回一个迭代器，该迭代器指向谓词返回 true 的第一个元素： 
std::vector<int> v{ 1, 1, 2, 3, 5, 8, 13 };

auto it = std::find_if(v.cbegin(), v.cend(),
    [](int const n) {return n > 10; });
if (it != v.cend()) std::cout << *it << '\n';

3) 使用 std::find_if_not() 在 range 内查找不满足一元谓词条件的值。此算法将返回一个迭代器，该迭代器指向谓词返回 false 的第一个元素： 
std::vector<int> v{ 1, 1, 2, 3, 5, 8, 13 };

auto it = std::find_if_not(v.cbegin(), v.cend(),
    [](int const n) {return n % 2 == 1; });
if (it != v.cend()) std::cout << *it << '\n';

4) 使用 std::find_first_of() 搜索 range 内的任何值在另一个 range 中的出现情况。此算法将返回一个指向找到的第一个元素的迭代器： 
std::vector<int> v{ 1, 1, 2, 3, 5, 8, 13 };
std::vector<int> p{ 5, 7, 11 };

auto it = std::find_first_of(v.cbegin(), v.cend(),
    p.cbegin(), p.cend());
if (it != v.cend())
    std::cout << "found " << *it
    << " at index " << std::distance(v.cbegin(), it)
    << '\n';

5) 使用 std::find_end() 查找 range 中元素的子 range 的最后一个匹配项。此算法将返回一个迭代器，该迭代器指向 range 中最后一个子 range 的第一个元素： 
std::vector<int> v1 { 1, 0, 0, 1, 0, 1, 0, 1, 0, 1 };
std::vector<int> v2 { 1, 0, 1 };

auto it = std::find_end(v1.cbegin(), v1.cend(),
    v2.cbegin(), v2.cend());
if (it != v1.cend())
    std::cout << "found at index "
    << std::distance(v1.cbegin(), it) << '\n';

6) 使用 std::search() 在 range 内搜索子 range 的第一个匹配项。此算法将返回一个迭代器，该迭代器指向 range 中子 range 的第一个元素： 
auto text = "The quick brown fox jumps over the lazy dog";
auto word = "over"s;
auto it = std::search(text.cbegin(), text.cend(),
    word.cbegin(), word.cend());
if (it != text.cend())
    std::cout << "found " << word
    << " at index "
    << std::distance(text.cbegin(), it) << '\n';

7) 将 std::search() 与搜索器结合使用，搜索器是一个实现搜索算法并满足某些预定义标准的类。这种 std::search() 的重载是在 C++17 中引入的，可用的标准搜索器实现了 Boyer-Moore 和 Boyer-Moore-Horspool 字符串搜索算法： 
auto text = "The quick brown fox jumps over the lazy dog";
auto word = "over"s;
auto it = std::search(
    text.cbegin(), text.cend(),
    std::make_boyer_moore_searcher(word.cbegin(), word.cend()));
if (it != text.cend())
    std::cout << "found " << word
    << " at index "
    << std::distance(text.cbegin(), it) << '\n';

8) 使用 std::search_n() 搜索 range 内连续出现 N 次的一个值。此算法返回一个迭代器，它指向在 range 内找到的序列的第一个元素： 
std::vector<int> v{ 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1 };
auto it = std::search_n(v.cbegin(), v.cend(), 2, 0);
if (it != v.cend())
    std::cout << "found at index "
    << std::distance(v.cbegin(), it) << '\n';

9) 使用 std::adjacent_find() 查找 range 内相等或满足二元谓词的两个相邻元素。此算法将返回一个迭代器，它指向找到的第一个元素： 
std::vector<int> v{ 1, 1, 2, 3, 5, 8, 13 };

auto it = std::adjacent_find(v.cbegin(), v.cend());
if (it != v.cend())
    std::cout << "found at index "
    << std::distance(v.cbegin(), it) << '\n';

auto it = std::adjacent_find(
    v.cbegin(), v.cend(),
    [](int const a, int const b) { return IsPrime(a) && IsPrime(b); });
if (it != v.cend())
    std::cout << "found at index "
    << std::distance(v.cbegin(), it) << '\n';

10) 使用 std::binary_search() 在排序 range 内查找是否存在某元素。此算法返回一个布尔值来指示是否找到该值： 
std::vector<int> v{ 1, 1, 2, 3, 5, 8, 13 };
auto success = std::binary_search(v.cbegin(), v.cend(), 8);
if (success) std::cout << "found" << '\n';

11) 使用 std::lower_bound() 在 range 内查找不小于指定值的第一个元素。此算法返回指向找到的第一个元素的迭代器： 
std::vector<int> v{ 1, 1, 2, 3, 5, 8, 13 };
auto it = std::lower_bound(v.cbegin(), v.cend(), 1);
if (it != v.cend())
    std::cout << "lower bound at "
    << std::distance(v.cbegin(), it) << '\n';

12) 使用 std::upper_bound() 在 range 内查找大于指定值的第一个元素。此算法返回指向找到的第一个元素的迭代器： 
std::vector<int> v{ 1, 1, 2, 3, 5, 8, 13 };
auto it = std::upper_bound(v.cbegin(), v.cend(), 1);
if (it != v.cend())
    std::cout << "upper bound at "
    << std::distance(v.cbegin(), it) << '\n';

13) 使用 std::equal_range() 在 range 内查找值等于指定值的子 range。该算法返回一对迭代器，即定义子 range 的开始迭代器和结束迭代器。这两个迭代器等价于 std::lower_bound() 和 std::upper_bound() 返回的迭代器： 
std::vector<int> v{ 1, 1, 2, 3, 5, 8, 13 };

auto bounds = std::equal_range(v.cbegin(), v.cend(), 1);
std::cout << "range between indexes "
    << std::distance(v.cbegin(), bounds.first)
    << " and "
    << std::distance(v.cbegin(), bounds.second)
    << '\n';

以上这些算法的工作方式非常相似，它们都将定义可搜索 range 的迭代器和依赖于每个算法的附加参数作为参数，std::search() 和 std::equal_range() 例外，前者返回一个布尔值，后者返回一对迭代器。它们都返回一个指向被搜索元素或子 range 的迭代器。这些迭代器必须与 range 的结束迭代器进行比较，以检查搜索是否成功。如果没有搜索到元素或子 range，则返回值为结束迭代器。

在前面所有的例子中，我们都使用了常量迭代器，但所有这些算法在使用可变迭代器和反向迭代器时都是一样的。因为它们将迭代器作为输入参数，所以可以使用标准容器、array 数组或任何表示序列并有可用迭代器的对象。

需要特别注意 std::binary_search() 算法，定义要搜索的 range 的迭代器参数至少应该满足前向迭代器的要求，无论所提供的迭代器的类型如何，比较的次数始终与 range 的大小成对数关系。但是，如果迭代器是随机访问的，则迭代器递增的次数是不同的，在这种情况下，递增次数也是对数的；如果迭代器不是随机访问的，在这种情况下，递增次数是线性的，并且与 range 的大小成正比。

除 std::find_if_not() 之外，所有这些算法在 C++11 之前都是可用的。但是，新的标准中引入了它们的一些重载，例如 std::search() 有几个在 C++17 中引入的重载，其中一个重载具有以下形式：
template<class ForwardIterator, class Searcher>
ForwardIterator search(ForwardIterator first, ForwardIterator last, const Searcher& searcher );
此重载搜索由搜索器函数对象定义的模式的出现情况，标准为该函数对象提供了几种实现：
许多标准容器都有一个 find() 成员函数，该函数用于查找容器中的元素。当这种方法可用并且匹配你的需求时，应该优先使用它，因为这些成员函数已根据每个容器的特殊性进行了优化。

相关文章