此系列用于介绍STL库中algorithm中所有竞赛常用的算法，方便大家竞赛中可以快速的实现某个功能，建议大家要同步跟着敲写代码联系功能。

一、基础查找

1.find（基础线性查找）

    int a[105];
    vector<int> b;
    for (int i = 1; i <= 100; ++i)
    {
        a[i] = i + 5;
        b.push_back(a[i]);
    }
    auto it = find(begin(a), end(a), 1000);
    auto ti = find(b.begin(), b.end(), 10);
    if (it != end(a)) // 因为a中不存在1000，故不执行
    {
        int index = it - begin(a);
        cout << "a下标: " << index << endl;
    }
    if (ti != b.end())
    {
        int pos = ti - b.begin();
        //也可写为int pos = distance(b.begin(), ti)，迭代器专题再细讲
        cout << pos << endl  //输出下标
             << *ti << endl; //输出值
    }
    cout << end(a) << endl
         << it << endl; // 验证查询不着返回的结果是对应否为end(a)

find起到很简单的一个查询，find（查询起始位置指针，查询结束位置指针，查找值）;需要数以的是，插叙的区间是左闭右开的，因此就算end(a)返回的是最后一位元素的下一个位置的指针依旧可以执行，并不会出现编译问题。

至于end(a)和a.end()的区别，我在这简单提一下，a.end()属于特异化接口，对于像vector容器与deque容器而言是成员函数，而end(a)是c++所提供的通用接口，性能完全相同且支持静态数组，如果静态数组用a。end()则会出现编译错误，算法竞赛中常用后者，我们可以根据自己喜好自行调整。

2.count（基础线性技计数）

    // 对于容器使用count的方法
    vector<int> nums = {1, 2, 3, 2, 4, 2, 5};
    int target1 = 2;
    // 统计 nums 中 2 出现的次数
    int cnt1 = count(nums.begin(), nums.end(), target1);
    cout << "数字 " << target1 << " 出现了 " << cnt1 << " 次" << endl;
    // 输出：数字 2 出现了 3 次

    // 对于数组使用count的方法
    int arr[] = {5, 3, 5, 7, 5, 9};
    int n = sizeof(arr) / sizeof(arr[0]); // 或者int n = arr.size();
    // 数组长度
    int target2 = 5;
    // 统计数组中 5 出现的次数（用指针作为迭代器）
    int cnt2 = count(arr, begin(arr) + n, target2);
    // 同int cnt = count(begin(arr), end(arr), target);
    cout << "数字 " << target2 << " 出现了 " << cnt2 << " 次" << endl;
    // 输出：数字 5 出现了 3 次

    //对于字符串使用count的方法
    string s = "hello world";
    char target3 = 'l';
    // 统计字符串中 'l' 出现的次数
    int cnt3 = count(s.begin(), s.end(), target3);
    cout << "字符 '" << target3 << "' 出现了 " << cnt3 << " 次" << endl;
    // 输出：字符 'l' 出现了 3 次

count函数的内部逻辑其实很简单，相当于一个「自动循环计数」的过程：

1. 从 first 迭代器开始，遍历到 last 迭代器（不包含 last 指向的位置）。
2. 每遇到一个与 value 相等的元素，就将计数加 1。
3. 遍历结束后，返回总计数。

类似于以下的循环结构：

    // 手动模拟 count 函数的逻辑
    int manual_count(vector<int> &nums,int value)
    {
        int cnt = 0;
        for (int x : nums)
        {
            if (x == value)
                cnt++;
        }
        return cnt;
    }

代码很好理解，刚好我们就上面vector<int> &nums讲一下如果我们改为vector<int> nums会出现什么不同吗？答案是并不会，我们分析一下：

&在参数中表示引用传递，函数内操作的是原始数据的直接引用，修改会影响原变量。没有&是值传递，函数接收的是数据的独立副本，修改不会影响原始数据。对于manual_count函数，使用vector<int> &nums允许但不强制修改原始数据，而实际代码中并未修改；如果改为vector<int> nums会额外复制整个数组，性能较差但行为一致（因为只读取），因此，一般情况下我们的只读值传递采取const vector<int> &nums更加专业。

二、条件查找

1.find_if

和 find函数相同，find_if函数也用于在指定区域内执行查找操作。不同的是，前者需要明确指定要查找的元素的值，而后者则允许自定义查找规则。

自定义查找规则，实际上指的是有一个形参且返回值类型为 bool 的函数。值得一提的是，该函数可以是一个普通函数（又称为一元谓词函数），比如：

bool cmp(int i) {
  return ((i%2)==1);
}

上面的 cmp就是一个一元谓词函数，其可用来判断一个整数是奇数还是偶数。

确切地说，find_if函数会根据指定的查找规则，在指定区域内查找第一个符合该函数要求（使函数返回 true）的元素。

find_if() 函数的语法格式如下：

InputIterator find_if (InputIterator first, InputIterator last, UnaryPredicate pred);

其中，first 和 last 都为输入迭代器，其组合 [first, last) 用于指定要查找的区域；pred 用于自定义查找规则。值得一提的是，由于 first 和 last 都为输入迭代器，意味着该函数适用于所有的序列式容器。甚至当采用适当的谓词函数时，该函数还适用于所有的关联式容器（包括哈希容器）。

同时，该函数会返回一个输入迭代器，当查找成功时，该迭代器指向的是第一个符合查找规则的元素；反之，如果 find_if() 函数查找失败，则该迭代器的指向和 last 迭代器相同。

具体示例如下：

#include <iostream>     // std::cout
#include <algorithm>    // std::find_if
#include <vector>       // std::vector
using namespace std;
//自定义一元谓词函数
bool mycomp(int i) {
    return ((i % 2) == 1);
}
//以函数对象的形式定义一个 find_if() 函数的查找规则
class mycomp2 {
public:
    bool operator()(const int& i) {
        return ((i % 2) == 1);
    }
};
int main() {
    vector<int> myvector{ 4,2,3,1,5 };
    //调用 find_if() 函数，并以 IsOdd() 一元谓词函数作为查找规则
    vector<int>::iterator it = find_if(myvector.begin(), myvector.end(), mycomp2());
    cout << "*it = " << *it;
    return 0;
}

程序执行结果为：

*it = 3

结合程序执行结果不难看出，对于 myvector 容器中的元素 4 和 2 来说，它们都无法使 (i%2)==1 这个表达式成立，因此 mycomp2() 返回 false；而对于元素 3 来说，它可以使 mycomp2() 函数返回 true，因此，find_if() 函数找到的第一个元素就是元素 3。

2.find_if_not

find_if_not() 函数和 find_if() 函数的功能恰好相反，通过上面的学习我们知道，find_if() 函数用于查找符合谓词函数规则的第一个元素，而 find_if_not() 函数则用于查找第一个不符合谓词函数规则的元素。

find_if_not() 函数的语法规则如下所示：

InputIterator find_if_not (InputIterator first, InputIterator last, UnaryPredicate pred);

其中，first 和 last 都为输入迭代器，[first, last) 用于指定查找范围；pred 用于自定义查找规则。

和 find_if() 函数一样，find_if_not() 函数也适用于所有的容器，包括所有序列式容器和关联式容器。

同样，该函数也会返回一个输入迭代器，当 find_if_not() 函数查找成功时，该迭代器指向的是查找到的那个元素；反之，如果查找失败，该迭代器的指向和 last 迭代器相同。

具体示例如下：

#include <iostream>     // std::cout
#include <algorithm>    // std::find_if_not
#include <vector>       // std::vector
using namespace std;
//自定义一元谓词函数
bool mycomp(int i) {
    return ((i % 2) == 1);
}
int main() {
    vector<int> myvector{4,2,3,1,5};
    //调用 find_if() 函数，并以 mycomp() 一元谓词函数作为查找规则
    vector<int>::iterator it = find_if_not(myvector.begin(), myvector.end(), mycomp);
    cout << "*it = " << *it;
    return 0;
}

程序执行结果为：

*it = 4

可以看到，由于第一个元素 4 就不符合 (i%2)==1，因此 find_if_not() 成功找到符合条件的元素，并返回一个指向该元素的迭代器。

三、边界查找

1.adjacent_find

“adjacent”的意思是“相邻的”，adjacent_find(beg , end)函数的功能是：用于在序列[beg , end)中查找第一对相邻元素，这两个元素满足特定条件（默认是绝对相等），有返回值，如果找到第一对相邻相等元素，则返回指向该对元素的第一个元素的迭代器；否则返回容器的end()。

它的函数模型是：

//查找 2 个连续相等的元素
ForwardIterator adjacent_find (ForwardIterator first, ForwardIterator last);
//查找 2 个连续满足 pred 规则的元素
ForwardIterator adjacent_find (ForwardIterator first, ForwardIterator last,
 BinaryPredicate pred);

该函数作用于正向迭代器，也就是说支持所有序列式容器，也支持关联式容器但是意义不大（主要是equal_range()表现更好）,不支持容器适配器如stack容器等（没有迭代器）；同时，该函数也接受二元谓词，使得我们能够不拘泥于“==”绝对相等的关系，还可以有诸如“>=”等自定义关系。

具体示例如下：

#include<iostream>
#include<vector>
#include<map>
#include<iterator> //使用迭代器函数distance(beg,end) 计算下标，复习前面知识 
#include<algorithm>//包含算法头文件！
using namespace std;
/*adjacent_find()*/
/*用于在序列[beg , end)中查找第一对相邻元素，这两个元素满足特定条件（默认是绝对相等）*/
void test()
{
vector<int> v{1,2,3,3,4,5};
auto pos = adjacent_find(v.begin(),v.end());
if(pos!=v.end())
{
cout << "序列{1,2,3,3,4,5}中出现第一对相邻相等元素的起始下标是：【"<< distance(v.begin(),pos) << "】\n";
}
} 
int main(){
    test();
    return 0;
}

程序执行结果为：

序列{1,2,3,3,4,5}中出现第一对相邻相等元素的起始下标是：【2】

对于序列{1,2,3,3,4,5}，我们可以看到第一对两个相等的3且第一个3的下标是“2”，输出完全符合我们的猜想。再次加深印象，adjacent_find(beg , end)函数的功能是：在序列[beg , end)中查找第一对相邻元素，主要应用于检查数据是否重复、字符串和文本处理等场景。

四、模式查找

1.find_end

find_end用于查找容器内子序列的最后一次出现。它在范围[first1，last1)中搜索由[first2，last2)定义的序列的最后一次出现，然后将迭代器返回到其第一个元素，如果没有发现，则返回last1。

模板如下：

template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1,
   ForwardIterator2 first2, ForwardIterator2 last2);

参数列表的含义：

• first1 − 将迭代器转发到第一个序列的初始位置。
• last1 − 将迭代器转发到第一个序列的最终位置。
• first2 − 将迭代器转发到第二个序列的初始位置。
• last2 − 将迭代器转发到第二个序列的最终位置。

返回一个迭代器，指向 first1，last1中最后一次出现 (first2,last2)的第一个元素。如果元素比较或迭代器上的操作引发异常，则引发异常。请注意，无效参数会导致未定义的行为。

具体示例如下：

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

using namespace std;

int main(void) {
   vector<int> v1 = {1, 2, 1, 2, 1, 2};
   vector<int> v2 = {1, 2};

   auto result = find_end(v1.begin(), v1.end(), v2.begin(), v2.end());

   if (result != v1.end())
      cout << "Last sequence found at location "
         << distance(v1.begin(), result) << endl;

   v2 = {1, 3};

   result = find_end(v1.begin(), v1.end(), v2.begin(), v2.end());

   if (result == v1.end())
      cout << "Sequence doesn't present in vector." << endl;

   return 0;
}

程序执行结果为：

Last sequence found at location 4
Sequence doesn’t present in vector.

2.search

find_end函数用于在序列 A 中查找序列 B 最后一次出现的位置。那么，如果想知道序列 B 在序列 A 中第一次出现的位置，该如何实现呢？

search函能功能恰好和 find_end函数相反，用于在序列 A 中查找序列 B 第一次出现的位置。

例如，以如下两个序列为例：

序列 A：1,2,3,4,5,1,2,3,4,5
序列 B：1,2,3

可以看到，序列 B 在序列 A 中出现了 2 次。借助 find_end() 函数，我们可以找到序列 A 中最后一个（也就是第 2 个）{1,2,3}；而借助 search() 函数，我们可以找到序列 A 中第 1 个 {1,2,3}。

和 find_end相同，search函数也提供有以下 2 种语法格式：

//查找 [first1, last1) 范围内第一个 [first2, last2) 子序列
ForwardIterator search (ForwardIterator first1, ForwardIterator last1,
                        ForwardIterator first2, ForwardIterator last2);
//查找 [first1, last1) 范围内，和 [first2, last2) 序列满足 pred 规则的第一个子序列
ForwardIterator search (ForwardIterator first1, ForwardIterator last1,
                        ForwardIterator first2, ForwardIterator last2,
                        BinaryPredicate pred);

其中，各个参数的含义分别为：

• first1、last1：都为正向迭代器，其组合 [first1, last1) 用于指定查找范围（也就是上面例子中的序列 A）；
• first2、last2：都为正向迭代器，其组合 [first2, last2) 用于指定要查找的序列（也就是上面例子中的序列 B）；
• pred：用于自定义查找规则。该规则实际上是一个包含 2 个参数且返回值类型为 bool 的函数（第一个参数接收 [first1, last1) 范围内的元素，第二个参数接收 [first2, last2) 范围内的元素）。函数定义的形式可以是普通函数，也可以是函数对象。

实际上，第一种语法格式也可以看做是包含一个默认的 pred 参数，该参数指定的是一种相等规则，即在 [first1, last1) 范围内查找和 [first2, last2) 中各个元素对应相等的子序列；而借助第二种语法格式，我们可以自定义一个当前场景需要的匹配规则。

同时，search函数会返回一个正向迭代器，当函数查找成功时，该迭代器指向查找到的子序列中的第一个元素；反之，如果查找失败，则该迭代器的指向和 last1 迭代器相同。

具体示例如下：

#include <iostream>     // std::cout
#include <algorithm>    // std::search
#include <vector>       // std::vector
using namespace std;
//以普通函数的形式定义一个匹配规则
bool mycomp1(int i, int j) {
    return (i%j == 0);
}
//以函数对象的形式定义一个匹配规则
class mycomp2 {
public:
    bool operator()(const int& i, const int& j) {
        return (i%j == 0);
    }
};
int main() {
    vector<int> myvector{ 1,2,3,4,8,12,18,1,2,3 };
    int myarr[] = { 1,2,3 };
    //调用第一种语法格式
    vector<int>::iterator it = search(myvector.begin(), myvector.end(), myarr, myarr + 3);
    if (it != myvector.end()) {
        cout << "第一个{1,2,3}的起始位置为：" << it - myvector.begin() << ",*it = " << *it << endl;
    }
    int myarr2[] = { 2,4,6 };
    //调用第二种语法格式
    it = search(myvector.begin(), myvector.end(), myarr2, myarr2 + 3, mycomp2());
    if (it != myvector.end()) {
        cout << "第一个{2,3,4}的起始位置为：" << it - myvector.begin() << ",*it = " << *it;
    }
    return 0;
}

程序执行结果为：

第一个{1,2,3}的起始位置为：0,*it = 1
第一个{2,3,4}的起始位置为：3,*it = 4

通过程序的执行结果可以看到，第 22 行代码借助 search函数找到了 myvector 容器中第一个 {1,2,3}，并返回了一个指向元素 1 的迭代器（其下标位置为 0）。

而在第 29 行中，search函数使用的是第 2 种格式，其自定义了 mycomp2 匹配规则，即在 myvector 容器中找到第一个连续的 3 个元素，它们能分别被 2、4、6 整除。显然，myvector 容器中符合要求的子序列有 2 个，分别为 {4,8,12} 和 {8,12,18}，但 search() 函数只会查找到第一个，并返回指向元素 4 的迭代器（其下标为 3）。

注意，search函数的第一种语法格式，其底层是借助 == 运算符实现的。这意味着，如果 [first1, last1] 和 [first2, last2] 区域内的元素为自定义的类对象或结构体变量时，使用该函数之前需要对 == 运算符进行重载。

3.search_n

search_n函数和search函数很像，不同之处在于，前者查找的子序列中可包含多个不同的元素，而后者查找的只能是包含多个相同元素的子序列。

下面有三个实例：

序列 A：1,2,3,4,4,4,1,2,3,4,4,4
序列 B：1,2,3
序列 C：4,4,4

如果想查找序列 B 在序列 A 中第一次出现的位置，就只能使用 search函数；而如果想查找序列 C 在序列 A 中第一次出现的位置，既可以使用 search函数，也可以使用 search_n函数。

search_n函数的语法格式如下：

//在 [first, last] 中查找 count 个 val 第一次连续出现的位置
ForwardIterator search_n (ForwardIterator first, ForwardIterator last,
                          Size count, const T& val);
//在 [first, last] 中查找第一个序列，该序列和 count 个 val 满足 pred 匹配规则
ForwardIterator search_n ( ForwardIterator first, ForwardIterator last,
                           Size count, const T& val, BinaryPredicate pred );

其中，各个参数的含义分别为：

• first、last：都为正向迭代器，其组合 [first, last) 用于指定查找范围（也就是上面例子中的序列 A）；
• count、val：指定要查找的元素个数和元素值，以上面的序列 B 为例，该序列实际上就是 3 个元素 4，其中 count 为 3，val 为 4；
• pred：用于自定义查找规则。该规则实际上是一个包含 2 个参数且返回值类型为 bool 的函数（第一个参数接收[first, last) 范围内的元素，第二个参数接收 val）。函数定义的形式可以是普通函数，也可以是函数对象。

实际上，第一种语法格式也可以看做是包含一个默认的 pred 参数，该参数指定的是一种相等规则，即在 [first, last) 范围内查找和 count 个 val 相等的子序列；而借助第二种语法格式，我们可以自定义一个当前场景需要的匹配规则。同时，search_n函数会返回一个正向迭代器，当函数查找成功时，该迭代器指向查找到的子序列中的第一个元素；反之，如果查找失败，则该迭代器的指向和 last 迭代器相同。

具体示例如下：

#include <iostream>     // std::cout
#include <algorithm>    // std::search_n
#include <vector>       // std::vector
using namespace std;
//以普通函数的形式定义一个匹配规则
bool mycomp1(int i, int j) {
    return (i%j == 0);
}
//以函数对象的形式定义一个匹配规则
class mycomp2 {
public:
    bool operator()(const int& i, const int& j) {
        return (i%j == 0);
    }
};
int main() {
    int a[] = { 1,2,3,4,4,4,1,2,3,4,4,4 };
    //调用第一种语法格式,查找 myvector 容器中第一个 {4,4,4}
    int * it = search_n(a, a+12, 3, 4);
    if (it != a+12) {
        cout << "one：" << it - a << ",*it = " << *it << endl;
    }
    vector<int> myvector{1,2,4,8,3,4,6,8};
    //调用第二种语法格式，以自定义的 mycomp2 作为匹配规则，查找 myvector 容器中和 {16,16,16} 满足 mycomp2 规则的序列
    vector<int>::iterator iter = search_n(myvector.begin(), myvector.end(), 3, 2, mycomp2());
    if (iter != myvector.end()) {
        cout << "two：" << iter - myvector.begin() << ",*iter = " << *iter;
    }
    return 0;
}

程序执行结果为：

one：3,*it = 4
two：1,*iter = 2

程序中先后调用了 2 种语法格式的 search_n函数，其中第 28 行代码中，search_n函数不再采用默认的相等匹配规则，而是采用了自定义了 mycomp2 匹配规则。这意味着，该函数会去 myvector 容器中查找一个子序列，该序列中的 3 个元素都满足和 2 有 (i%j == 0) 的关系。显然，myvector 容器中符合条件的子序列有 2 个，分别为 {2,4,8} 和 {4,6,8}，但 search_n函数只会查找到 {2,4,8}。

注意，search_n函数的第一种语法格式，其底层是借助 == 运算符实现的。这意味着，如果 [first, last] 区域内的元素为自定义的类对象或结构体变量时，使用此格式的 search_n函数之前，需要对 == 运算符进行重载。

五、 有序查找

这一部分是算法竞赛中查找最常用的函数，非常重要。

1.binary_search

binary_search()函数用于查找指定区域内是否包含某个目标元素。

该函数有 2 种语法格式，分别为：

//查找 [first, last) 区域内是否包含 val
bool binary_search (ForwardIterator first, ForwardIterator last,
                      const T& val);
//根据 comp 指定的规则，查找 [first, last) 区域内是否包含 val
bool binary_search (ForwardIterator first, ForwardIterator last,
                      const T& val, Compare comp);

其中，first 和 last 都为正向迭代器，[first, last) 用于指定该函数的作用范围；val 用于指定要查找的目标值；comp 用于自定义查找规则，此参数可接收一个包含 2 个形参（第一个形参值为 val）且返回值为 bool 类型的函数，可以是普通函数，也可以是函数对象。

同时，该函数会返回一个 bool 类型值，如果 binary_search() 函数在 [first, last) 区域内成功找到和 val 相等的元素，则返回 true；反之则返回 false。

需要注意的是，由于 binary_search() 底层实现采用的是二分查找的方式，因此该函数仅适用于“已排好序”的序列。所谓“已排好序”，并不是要求 [first, last) 区域内的数据严格按照某个排序规则进行升序或降序排序，只要满足“所有令 element<val（或者 comp(val, element）成立的元素都位于不成立元素的前面（其中 element 为指定范围内的元素）”即可。

具体示例如下：

#include <iostream>     // std::cout
#include <algorithm>    // std::binary_search
#include <vector>       // std::vector
using namespace std;
//以普通函数的方式定义查找规则
bool mycomp(int i, int j) { return i > j; }
//以函数对象的形式定义查找规则
class mycomp2 {
public:
    bool operator()(const int& i, const int& j) {
        return i > j;
    }
};
int main() {
    int a[7] = { 1,2,3,4,5,6,7 };
    //从 a 数组中查找元素 4
    bool haselem = binary_search(a, a + 9, 4);
    cout << "haselem：" << haselem << endl;
    vector<int>myvector{ 4,5,3,1,2 };
    //从 myvector 容器查找元素 3
    bool haselem2 = binary_search(myvector.begin(), myvector.end(), 3, mycomp2());
    cout << "haselem2：" << haselem2;
    return 0;
}

程序执行结果为：

haselem：1
haselem2：1

此程序中演示了 binary_search() 函数的 2 种适用场景，其中 a[7] 数组中存储的为升序序列；而 myvector 容器中存储的序列虽然整体是乱序的，但对于目标元素 3 来说，所有符合 mycomp2(element, 3) 规则的元素都位于其左侧，不符合的元素都位于其右侧，因此 binary_search() 函数仍可正常执行。

2.lower_bound、upper_bound

 lower_bound() 和 upper_bound() 是两个用于在有序集合中进行二分查找的高效函数。它们的时间复杂度为 O(log n)，适用于快速查找特定值的位置或范围。

lower_bound() 函数返回指向第一个不小于给定值的元素的迭代器。如果所有元素都小于该值，则返回指向序列尾部的迭代器。如果存在多个相等的元素，则返回指向第一个元素的迭代器。

下面是使用 lower_bound() 函数的示例代码：

#include <bits/stdc++.h>
using namespace std;
int main() {
    vector<int> v = {1, 3, 5, 7, 9};      // 定义一个整数类型的向量 v，并初始化为 {1, 3, 5, 7, 9}
    int val = 5;                          // 定义一个整数变量 val，并赋值为 5
    auto it = lower_bound(v.begin(), v.end(), val);  // 使用 lower_bound() 函数查找在有序容器 v 中第一个大于或等于 val 的元素的迭代器
    if (it != v.end())                    // 如果找到了符合条件的元素
        cout << "Found at index: " << it - v.begin();  // 则输出该元素的索引（通过计算迭代器与起始迭代器的差值）
    else                                  // 如果没有找到符合条件的元素
        cout << "Not found";              // 则输出 "Not found"
    return 0;
}

程序中，auto it 是一个变量声明语句，使用 auto 关键字进行自动类型推导，它将根据右侧的初始化表达式的值来推断变量的类型。

程序执行结果为：

Found at index: 2

upper_bound() 函数返回指向第一个大于给定值的元素的迭代器。如果所有元素都不大于该值，则返回指向序列尾部的迭代器。如果存在多个等于目标值的元素，upper_bound() 函数会跳过它们，返回指向下一个大于给定值的元素。

下面是使用 upper_bound() 函数的示例代码：

#include <bits/stdc++.h>
using namespace std;
int main() {
    vector<int> v = {1, 3, 5, 7, 9};   // 定义一个整数类型的向量 v，并初始化为 {1, 3, 5, 7, 9}
    int val = 5;                       // 定义一个整数变量 val，并赋值为 5
    auto it = upper_bound(v.begin(), v.end(), val);  // 使用 upper_bound() 函数查找在有序容器 v 中第一个大于 val 的元素的迭代器
    if (it != v.end())                 // 如果找到了符合条件的元素
        cout << "First element greater than " << val << " is at index: " << it - v.begin();  // 则输出该元素的索引（通过计算迭代器与起始迭代器的差值）
    else                               // 如果没有找到符合条件的元素
        cout << "No elements are greater than " << val;  // 则输出 "No elements are greater than " 加上 val 的值
    return 0;                          // 返回值
}

程序的执行结果为：

First element greater than 5 is at index: 3

lower_bound() 和 upper_bound() 都假定输入范围是有序的。如果在无序的序列上使用它们，将无法保证结果正确。

为了更直白比较，lower_bound() 和 upper_bound()的对比图如下：

函数	lower_bound()	upper_bound()
功能	查找第一个不小于给定值的元素	查找第一个大于给定值的元素
返回值	迭代器	迭代器
条件要求	输入的序列必须是有序的	输入的序列必须是有序的
时间复杂度	O(log n)	O(log n)
返回元素条件	大于或等于给定值的第一个元素	大于给定值的第一个元素
返回值为 end 的条件	所有元素都小于给定值	所有元素都小于或等于给定值

3.equel_range

equel_range() 函数用于在指定范围内查找等于目标值的所有元素。

值得一提的是，当指定范围内的数据支持用 < 小于运算符直接做比较时，可以使用如下格式的 equel_range() 函数：

//找到 [first, last) 范围中所有等于 val 的元素
pair<ForwardIterator,ForwardIterator> equal_range (ForwardIterator first, ForwardIterator last, const T& val);

如果指定范围内的数据为自定义的类型（用结构体或类），就需要自定义比较规则，这种情况下可以使用如下格式的 equel_range() 函数：

//找到 [first, last) 范围内所有等于 val 的元素
pair<ForwardIterator,ForwardIterator> equal_range (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);

以上 2 种格式中，first 和 last 都为正向迭代器，[first, last) 用于指定该函数的作用范围；val 用于指定目标值；comp 用于指定比较规则，此参数可接收一个包含 2 个形参（第二个形参值始终为 val）且返回值为 bool 类型的函数，可以是普通函数，也可以是函数对象。

同时，该函数会返回一个 pair 类型值，其包含 2 个正向迭代器。当查找成功时：

1. 第 1 个迭代器指向的是 [first, last) 区域中第一个等于 val 的元素；
2. 第 2 个迭代器指向的是 [first, last) 区域中第一个大于 val 的元素。

反之如果查找失败，则这 2 个迭代器要么都指向大于 val 的第一个元素（如果有），要么都和 last 迭代器指向相同。

需要注意的是，由于 equel_range() 底层实现采用的是二分查找的方式，因此该函数仅适用于“已排好序”的序列。所谓“已排好序”，并不是要求 [first, last) 区域内的数据严格按照某个排序规则进行升序或降序排序，只要满足“所有令 element<val（或者 comp(element,val）成立的元素都位于不成立元素的前面（其中 element 为指定范围内的元素）”即可。

具体示例如下：

#include <iostream>     // std::cout
#include <algorithm>    // std::equal_range
#include <vector>       // std::vector
using namespace std;
//以普通函数的方式定义查找规则
bool mycomp(int i, int j) { return i > j; }
//以函数对象的形式定义查找规则
class mycomp2 {
public:
    bool operator()(const int& i, const int& j) {
        return i > j;
    }
};
int main() {
    int a[9] = { 1,2,3,4,4,4,5,6,7};
    //从 a 数组中找到所有的元素 4
    pair<int*, int*> range = equal_range(a, a + 9, 4);
    cout << "a[9]：";
    for (int *p = range.first; p < range.second; ++p) {
        cout << *p << " ";
    }
    vector<int>myvector{ 7,8,5,4,3,3,3,3,2,1 };
    pair<vector<int>::iterator, vector<int>::iterator> range2;
    //在 myvector 容器中找到所有的元素 3
    range2 = equal_range(myvector.begin(), myvector.end(), 3,mycomp2());
    cout << "\nmyvector：";
    for (auto it = range2.first; it != range2.second; ++it) {
        cout << *it << " ";
    }
    return 0;
}

程序执行结果为：

a[9]：4 4 4
myvector：3 3 3 3

此程序中演示了 equal_range() 函数的 2 种适用场景，其中 a[9] 数组中存储的为升序序列；而 myvector 容器中存储的序列虽然整体是乱序的，但对于目标元素 3 来说，所有符合 mycomp2(element, 3) 规则的元素都位于其左侧，不符合的元素都位于其右侧，因此 equal_range() 函数仍可正常执行。

实际上，equel_range() 函数的功能完全可以看做是 lower_bound() 和 upper_bound() 函数的合体。

好了，今天我们就先学到这里，大家一定要经常温习哦，我们一起进步！