C++ STL 模板函数 find, find_if, find_if_not 详解

在C++ STL（标准库）中提供了很多常用的函数，其中包括在容器中查找元素的函数：find, find_if, find_if_not。这些函数在设计上使用了模板技术，因此很灵活，可以操作不同类型的容器和元素。本文将详细介绍这些函数的使用方法。

find 函数

函数说明

find 函数用于在区间 [first, last) 中查找等于 value 的元素，返回该元素的迭代器。如果没有找到，则返回 last。

template< class InputIt, class T >
InputIt find( InputIt first, InputIt last, const T& value );

代码范例

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    vector<int> vec = {1, 2, 3, 4, 5, 6};
    auto result = find(vec.begin(), vec.end(), 3);
    if(result != vec.end()) {
        cout << "Found 3 at position " << result - vec.begin() << endl;
    }
    else {
        cout << "3 not found." << endl;
    }
    return 0;
}

输出结果

Found 3 at position 2

解析

首先定义一个 vector 对象 vec，包含了从 1 到 6 的整数。然后通过调用 find 函数在 vec 中查找值为 3 的元素。如果找到了，则返回指向该元素的迭代器，可以像代码中一样判断迭代器是否等于 vec 的尾后迭代器来确定是否找到了元素。

find_if 函数

函数说明

find_if 函数用于在区间 [first, last) 中查找符合指定条件的元素，条件由用户指定。该函数返回第一个满足条件的迭代器，如果没有找到，则返回 last。

template< class InputIt, class UnaryPredicate >
InputIt find_if( InputIt first, InputIt last, UnaryPredicate p );

其中，UnaryPredicate 是一个可调用对象，接受一个参数，并返回 bool 类型的值。函数将遍历整个区间，对于每个元素，调用 p 函数，如果返回值为 true，则返回指向该元素的迭代器。

代码范例

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool is_odd(int x) {
    return x % 2 != 0;
}

int main() {
    vector<int> vec = {1, 2, 3, 4, 5, 6};
    auto result = find_if(vec.begin(), vec.end(), is_odd);
    if(result != vec.end()) {
        cout << "Found odd number at position " << result - vec.begin() << endl;
    }
    else {
        cout << "No odd number found." << endl;
    }
    return 0;
}

输出结果

Found odd number at position 0

解析

首先定义一个 vector 对象 vec，包含了从 1 到 6 的整数。然后定义了一个函数 is_odd，用于判断一个整数是否为奇数。调用 find_if 函数，在 vec 中查找第一个奇数，代码通过传递 is_odd 函数作为 UnaryPredicate 参数，实现了查找奇数的功能。

find_if_not 函数

函数说明

find_if_not 函数用于在区间 [first, last) 中查找不符合指定条件的元素，条件由用户指定。该函数返回第一个不满足条件的迭代器，如果没有找到，则返回 last。

template< class InputIt, class UnaryPredicate >
InputIt find_if_not( InputIt first, InputIt last, UnaryPredicate q );

代码范例

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool is_odd(int x) {
    return x % 2 != 0;
}

int main() {
    vector<int> vec = {1, 2, 3, 4, 5, 6};
    auto result = find_if_not(vec.begin(), vec.end(), is_odd);
    if(result != vec.end()) {
        cout << "Found even number at position " << result - vec.begin() << endl;
    }
    else {
        cout << "No even number found." << endl;
    }
    return 0;
}

输出结果

Found even number at position 1

解析

同样使用了 vector 对象 vec，包含了从 1 到 6 的整数。然后定义了一个函数 is_odd，用略在C++17中，以上三个函数还提供了使用执行策略的版本，用于在并行执行的情况下提高查找速度。这里以 find 函数为例。

函数说明

template< class ExecutionPolicy, class ForwardIt, class T >
ForwardIt find( ExecutionPolicy&& policy,
                ForwardIt first, ForwardIt last, const T& value );

其中，ExecutionPolicy 是一个执行策略类型的参数，用于控制查找的执行方式。常见的执行策略有 std::seq、std::par、std::par_unseq，分别表示顺序执行、并行执行、并行不确定执行。ForwardIt 是迭代器类型参数，用于指定查找的区间，T 是元素类型参数，用于指定要查找的元素的类型。函数将在指定区间中查找等于 value 的元素，返回指向该元素的迭代器，如果没有找到，则返回 last。

代码范例

#include <iostream>
#include <vector>
#include <algorithm>
#include <execution>

using namespace std;

int main() {
    vector<int> vec = {1, 2, 3, 4, 5, 6};
    auto result = find(execution::par, vec.begin(), vec.end(), 3);
    if(result != vec.end()) {
        cout << "Found 3 at position " << result - vec.begin() << endl;
    }
    else {
        cout << "3 not found." << endl;
    }
    return 0;
}

输出结果

Found 3 at position 2

解析

这段代码与之前介绍的 find 函数的范例类似，但是在调用 find 函数时，指定了执行策略 execution::par，表示要并行执行。执行策略是一个枚举类型，包含顺序、并行和并行不确定三种方式。

结论

C++ STL 的 find, find_if, find_if_not 函数提供了方便的元素查找功能，通过模板技术，这些函数可以处理不同类型的容器和元素，并支持使用执行策略来提高查找速度。在实际使用中，可以根据需要选择最合适的函数和执行策略来进行元素查找操作。

除了以上介绍的函数，C++ STL 还提供了其他的查找函数，如 lower_bound、upper_bound、equal_range、binary_search 等，本文将在下一部分逐一介绍。

lower_bound

lower_bound 函数用于在有序的序列中查找第一个大于等于给定值的元素位置。

函数说明

template< class ForwardIt, class T >
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value );

其中，ForwardIt 是迭代器类型参数，用于指定查找的区间，T 是元素类型参数，用于指定要查找的元素的类型。该函数将在指定区间中查找第一个大于等于 value 的元素位置，返回指向该位置的迭代器，如果所有元素都小于 value，则返回 last。

代码范例

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    vector<int> vec = {1, 2, 3, 4, 5, 6};
    auto result = lower_bound(vec.begin(), vec.end(), 3);
    if(result != vec.end()) {
        cout << "The first element >= 3 is " << *result << endl;
    }
    else {
        cout << "3 is greater than all elements." << endl;
    }
    return 0;
}

输出结果

The first element >= 3 is 3

解析

这段代码创建了一个有序的整数序列，使用 lower_bound 函数在该序列中查找第一个大于等于 3 的元素位置，结果输出该位置所对应的元素值。

upper_bound

upper_bound 函数用于在有序的序列中查找第一个大于给定值的元素位置。

函数说明

template< class ForwardIt, class T >
ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value );

其中，ForwardIt 是迭代器类型参数，用于指定查找的区间，T 是元素类型参数，用于指定要查找的元素的类型。该函数将在指定区间中查找第一个大于 value 的元素位置，返回指向该位置的迭代器，如果所有元素都小于等于 value，则返回 last。

代码范例

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    vector<int> vec = {1, 2, 3, 4, 5, 6};
    auto result = upper_bound(vec.begin(), vec.end(), 3);
    if(result != vec.end()) {
        cout << "The first element > 3 is " << *result << endl;
    }
    else {
        cout << "3 is greater than or equal to all elements." << endl;
    }
    return 0;
}

输出结果

The first element > 3 is 4

解析

这段代码创建了一个有序的整数序列，使用 upper_bound 函数在该序列中查找第一个大于 3 的元素位置，结果输出该位置所对应的元素值。

equal_range

equal_range 函数用于在有序的序列中查找相等元素的范围。

函数说明

template< class ForwardIt, class T >
std::pair<ForwardIt,ForwardIt> equal_range( ForwardIt first, ForwardIt last, const T& value );

其中，ForwardIt 是迭代器类型参数，用于指定查找的区间，T 是元素类型参数，用于指定要查找的元素的类型。该函数将在指定区间中查找等于 value 的元素的范围，返回一个 pair 对象，包含两个指向该范围的迭代器。如果没有找到相等元素，则两个迭代器都指向最后一个小于 value 的元素位置。

代码范例

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    vector<int> vec = {1, 2, 3, 3, 3, 4};
    auto result = equal_range(vec.begin(), vec.end(), 3);
    cout << "The range of elements equal to 3 is: ";
    for(auto it = result.first; it != result.second; ++it) {
        cout << *it << " ";
    }
    cout << endl;
    return 0;
}

输出结果

The range of elements equal to 3 is: 3 3 3

解析

这段代码创建了一个有序的整数序列，使用 equal_range 函数在该序列中查找等于 3 的元素范围，结果输出范围内所有元素的值。

binary_search

binary_search 函数用于在有序的序列中判断是否存在给定值的元素。

函数说明

template< class ForwardIt, class T >
bool binary_search( ForwardIt first, ForwardIt last, const T& value );

其中，ForwardIt 是迭代器类型参数，用于指定查找的区间，T 是元素类型参数，用于指定要查找的元素的类型。该函数将在指定区间中判断是否存在等于 value 的元素，如果存在，返回 true，否则返回 false。

代码范例

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    vector<int> vec = {1, 2, 3, 4, 5, 6};
    if(binary_search(vec.begin(), vec.end(), 3)) {
        cout << "3 is found." << endl;
    }
    else {
        cout << "3 is not found." << endl;
    }
    return 0;
}

输出结果

3 is found.

解析

这段代码创建了一个有序的整数序列，使用 binary_search 函数判断是否存在等于 3 的元素，结果输出找到该元素。注意，这个函数只能用于有序序列的查找，而且容器中的元素必须支持比较运算符（如 <）或者提供自己的比较函数。