剑指信奥 | C++ 之 STL - 算法 find
剑指信奥｜C++ 之 STL - 算法 find
用各种方法寻找你
find
今天我们继续学习 STL 算法库，主要围绕一个主题词展开 - find，这个词大家都认识，就是查找、寻找的意思。
跟 find 有关的函数有好几个，我们一个一个的加以说明，并用简练的代码进行示例。
首先，我们学习基本的 find() 函数。
find() 函数用于查找容器在指定范围内的某一个指定的值。
find() 函数接收 3 个参数：
起始元素的输入迭代器 first终止元素的后一个元素的输入迭代器 last要查找的元素值 value
代码示例：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
vector<int> vi = {1, 2, 3, 3, 3};
// 声明迭代器
vector<int>::iterator first, last, result;
// 查询范围是 [first, last)
first = vi.begin();
last = vi.end();
// 指定查询的元素值
int value = 0; result = find(first, last, value); if (result == last) {
cout << "vi does not contain " << value << endl;
} else {
cout << "vi contains " << value << endl;
}
return 0;
}
/*
output
vi does not contain 0
*/
这段代码在 vector 的 [first, last) 范围中查找元素 0，find() 函数返回的结果是，如果找到了，返回这个元素的迭代器，如果没找到，返回 last。
find_if
第二个函数是 find_if()。
find_if() 函数用于查找容器在指定范围内，谓词 p 返回为 true 的元素。
find_if() 函数接收 3 个参数：
起始元素的输入迭代器 first终止元素的后一个元素的输入迭代器 last谓词 p
代码示例：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
inline bool p(int x) {
return x % 3 == 0;
}
int main() {
vector<int> vi = {0, 1, 2, 3, 3, 3};
// 声明迭代器
vector<int>::iterator first, last, result;
// 查询范围是 [first, last)
first = vi.begin();
last = vi.end();
result = find_if(first, last, p);
if (result != last) {
cout << "第一个能被 3 整除的元素是：" << *result << "，索引是：" << result - first << endl;
} else {
cout << "没有元素能被 3 整除。" << endl;
}
return 0;
}
/*
output
第一个能被 3 整除的元素是：0，索引是：0
*/
我们定义的谓词函数是能被 3 整除的数，find_if() 返回第一个满足谓词的元素，如果都不满足，返回 last 迭代器。
find_if_not
第三个函数是 find_if_not()。
find_if_not() 函数用于查找容器在指定范围内，谓词 q 返回为 falst 的元素。
find_if_not() 函数接收 3 个参数：
起始元素的输入迭代器 first终止元素的后一个元素的输入迭代器 last谓词 q
代码示例：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
inline bool q(int x) {
return x % 3 == 0;
}
int main() {
vector<int> vi = {0, 1, 2, 3, 3, 3};
// 声明迭代器
vector<int>::iterator first, last, result;
// 查询范围是 [first, last)
first = vi.begin();
last = vi.end();
result = find_if_not(first, last, q);
if (result != last) {
cout << "第一个不能被 3 整除的元素是：" << *result << "，索引是：" << result - first << endl;
} else {
cout << "所有元素都能被 3 整除。" << endl;
}
return 0;
}
/*
output
第一个不能被 3 整除的元素是：1，索引是：1
*/
显然，find_if_not() 就是对 find_if() 取反。不使用 find_if_not() 对谓词函数返回值取反可以达到同样的结果。
find_end
第四个函数是 find_end()。
find_end() 函数用于查找容器在指定范围内最后一次出现的序列 [s_first, s_last)。
find_end() 函数接收 4 个参数：
起始元素的输入迭代器 first终止元素的后一个元素的输入迭代器 last子序列起始元素输入迭代器 s_first子序列终止元素的后一个元素的输入迭代器 s_last
代码示例：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
vector<int> vi = {1, 2, 3, 1, 2, 3}, vs = {1, 2, 3};
// 声明迭代器
vector<int>::iterator first, last, s_first, s_last, result;
// 查询范围是 [first, last)
first = vi.begin();
last = vi.end();
// 子序列范围是 [s_first, s_last)
s_first = vs.begin();
s_last = vs.end();
result = find_end(first, last, s_first, s_last);
if (result != last) {
cout << "最后一个子序列起始于：" << result - first << endl;
} else {
cout << "不存在这样的子序列。" << endl;
}
return 0;
}
/*
output
最后一个子序列起始于：3
*/
vi 中存在两个 vs，返回的是最后一个，也就是第二个子序列的第一个元素的迭代器。注意 end 的含义。
find_first_of
第五个函数是 find_first_of()。
find_first_of() 函数用于查找容器在指定范围内第一次出现的序列 [s_first, s_last)。
find_first_of() 函数接收 4 个参数：
起始元素的输入迭代器 first终止元素的后一个元素的输入迭代器 last子序列起始元素输入迭代器 s_first子序列终止元素的后一个元素的输入迭代器 s_last
代码示例：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
vector<int> vi = {1, 2, 3, 1, 2, 3}, vs = {1, 2, 3};
// 声明迭代器
vector<int>::iterator first, last, s_first, s_last, result;
// 查询范围是 [first, last)
first = vi.begin();
last = vi.end();
// 子序列范围是 [s_first, s_last)
s_first = vs.begin();
s_last = vs.end();
result = find_first_of(first, last, s_first, s_last);
if (result != last) {
cout << "第一个子序列起始于：" << result - first << endl;
} else {
cout << "不存在这样的子序列。" << endl;
}
return 0;
}
/*
output
第一个子序列起始于：0
*/
类似于 find_end()，find_first_of() 返回的是第一个子序列的第一个元素的迭代器。
adjacent_find
第六个函数是 adjacent_find()。
adjacent_find() 函数用于查找容器在指定范围内相等或满足二元谓词 binary_pred 的两个连续元素。
adjacent_find() 函数接收 3 个参数：
起始元素的输入迭代器 first终止元素的后一个元素的输入迭代器 last二元谓词 binary_pred
代码示例：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
vector<int> vi = {1, 2, 3, 3, 3};
// 声明迭代器
vector<int>::iterator first, last, result;
// 查询范围是 [first, last)
first = vi.begin();
last = vi.end();
// 使用 adjacent_find 进行查找
result = adjacent_find(first, last);
if (result != last) {
cout << "连续相等的元素是：" << *result << endl;
cout << "第一个元素起始于：" << result - first << endl;
} else {
cout << "不存在两个连续相等的元素。" << endl;
}
return 0;
}
/*
output
连续相等的元素是：3
第一个元素起始于：2
*/
这段代码查找 vector 内两个连续相等的元素，返回了元素值和第一个元素的索引。
再看第二种情况：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
// 二元谓词，相等且都为偶数
inline bool binary_pred(int x, int y) {
return (x == y) && (x % 2 == 0) && (y % 2 == 0);
}
int main() {
vector<int> vi = {1, 2, 3, 3, 3};
// 声明迭代器
vector<int>::iterator first, last, result;
// 查询范围是 [first, last)
first = vi.begin();
last = vi.end();
// 使用 adjacent_find 进行查找
result = adjacent_find(first, last, binary_pred);
if (result != last) {
cout << "连续相等的偶数元素是：" << *result << endl;
cout << "第一个偶数元素起始于：" << result - first << endl;
} else {
cout << "不存在两个连续相等的偶数元素。" << endl;
}
return 0;
}
/*
output
不存在两个连续相等的偶数元素
*/
这一次，我们定义了一个二元谓词，所谓二元的含义就是这个函数接收两个参数。
我们定义的条件是两个相等的偶数，所以这一次就没有满足条件的相邻元素了。
find 算法总结
最后，我们总结一下 find 相关的 6 个算法函数：
find()查找值相等的元素find_if()查找谓词为true的元素find_if_not()查找谓词为false的元素find_end()查找最后一个子序列find_first_of()查找第一个子序列adjacent_find()查找相等或满足条件的相邻元素
扫码关注趣乐博思教育微信公众号
