信奥竞赛

系列

首页 | 信奥竞赛

剑指信奥 | C++ 之 STL - 算法 find

剑指信奥｜C++ 之 STL - 算法 find

用各种方法寻找你

find

今天我们继续学习 STL 算法库，主要围绕一个主题词展开 - find，这个词大家都认识，就是查找、寻找的意思。

跟 find 有关的函数有好几个，我们一个一个的加以说明，并用简练的代码进行示例。

首先，我们学习基本的 find() 函数。

find() 函数用于查找容器在指定范围内的某一个指定的值。

find() 函数接收 3 个参数：

  1. 起始元素的输入迭代器 first
  2. 终止元素的后一个元素的输入迭代器 last
  3. 要查找的元素值 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 个参数：

  1. 起始元素的输入迭代器 first
  2. 终止元素的后一个元素的输入迭代器 last
  3. 谓词 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 个参数：

  1. 起始元素的输入迭代器 first
  2. 终止元素的后一个元素的输入迭代器 last
  3. 谓词 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 个参数：

  1. 起始元素的输入迭代器 first
  2. 终止元素的后一个元素的输入迭代器 last
  3. 子序列起始元素输入迭代器 s_first
  4. 子序列终止元素的后一个元素的输入迭代器 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 个参数：

  1. 起始元素的输入迭代器 first
  2. 终止元素的后一个元素的输入迭代器 last
  3. 子序列起始元素输入迭代器 s_first
  4. 子序列终止元素的后一个元素的输入迭代器 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 个参数：

  1. 起始元素的输入迭代器 first
  2. 终止元素的后一个元素的输入迭代器 last
  3. 二元谓词 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 个算法函数：

  1. find() 查找值相等的元素
  2. find_if() 查找谓词为 true 的元素
  3. find_if_not() 查找谓词为 false 的元素
  4. find_end() 查找最后一个子序列
  5. find_first_of() 查找第一个子序列
  6. adjacent_find() 查找相等或满足条件的相邻元素