C++之STL常用算法

程序员文章站 2022-07-12 14:00:59

...

一、写前概述：

C++中：继承机制支持派生类重用基类的代码；多态机制使得一个继承层次中的所有派生类可以重用在抽象基类中定义的纯虚函数接口；标准模板库（Standard Template Library,STL）使得可以重用函数定义或类定义来处理不同类型的数据结构。STL主要包括三个部分：①容器（包含对象的对象）、②迭代器（相当于指向元素对象的指针）、③算法（一些能在各种容器中通用的标准算法，如排序、插入）。算法使用迭代器在容器上进行操作（以迭代器为界分隔了容器和算法——容器只要实现某算法对迭代器的要求，便可应用于该算法）！

STL中算法的具体形式为“函数模板”，算法的操作都是通过迭代器实现的。算法的共同特征有：①算法的主要模板参数是迭代器类型，而函数参数是对应类型的迭代器实例；②一个算法若从若干序列中读取数据再向某个序列中写入数据，则所读取序列的迭代器参数在前，所写序列的迭代器参数在后；③有些算法还接受“函数约束条件”。

二、准备知识：
1、迭代器：

迭代器是建立在类模板上的泛型指针，它可以在不同的数据结构上以统一的方式进行访问操作。包括：

输入迭代器（input iterator），读功能，支持：*（右值）、->、=、++、==、!=。
输出迭代器（output iterator），写功能，支持：*（左值）、++、=。
正向迭代器（forward iterator），读/写功能，支持：输入、输出迭代器支持的所有功能（*既可左值，也可右值）。
双向迭代器（bidirectional iterator），读/写功能，支持：正向迭代器功能和“–”。
随机访问迭代器（random access iterator），读/写功能，支持：双向迭代器的所有功能，迭代器比较（<、<=、>、>=），迭代器对象与整型值n之间的+、+=、-、-=，两个迭代器对象相减（-），下标操作（[]）。

注意：vector与deque的迭代器是随机访问迭代器；list迭代器是双向迭代器；所有关联容器的迭代器都是双向迭代器；容器适配器不支持迭代器。
2、lambda表达式：

C++的lambda表达式用于便捷地创建一个匿名函数——于使用的地方现场定义，其书写格式为：`[capture list] (params list) mutable exception-> return type { function body }`。capture list：捕获外部变量列表；params list：形参列表（不能有默认参数、不支持可变参数、参数必须有名）；mutable指示符：是否可以修改捕获的变量；exception：异常设定；return type：返回类型；function body：函数体。lambda表达式有如下简写格式：

[capture list] (params list) -> return type {function body}；//const类型
[capture list] (params list) {function body}； //返回类型由return 决定或为void
[capture list] {function body}。 //无参数表

C++11中lambda表达式的捕获形式

捕获形式	说明
[]	不捕获任何外部变量
[变量名]	以值的形式捕获指定的外部变量（用逗号分隔）；如果引用捕获，需使用&说明
[this]	以值的形式捕获this指针
[=]	以值的形式捕获所有外部变量
[&]	以引用形式捕获所有外部变量
[=, &x]	变量x以引用形式捕获，其余变量以传值形式捕获
[&, x]	变量x以值的形式捕获，其余变量以引用形式捕获

三、STL算法：

算法的主要参数为：迭代器+谓词（lambda表达式）。我们将五种迭代器分别简写为：①输入迭代器→(ii0,ii1)；②输出迭代器→(oi0,oi1)；③正向迭代器→(fi0,fi1)；④双向迭代器→(di0,di1)；⑤随机访问迭代器→(ri0,ri1)。【注：后一种（复杂的）迭代器实现了前一种（简单的）的功能。示例基本以vector为例！】

1、foreach的写法：

for_each(ii0, ii1, func)(C++11之前)：将指定范围内每一个元素应用于一个单目函数（或函数对象）func之上。
for(auto item:容器对象)(C++11新有)：基于范围的for循环，遍历数组、容器等的每一个元素（可改变元素）。
boost库预定义的BOOST_FOREACH宏。

2、查询（搜索）：
（1）查询单个元素：

find(ii0, ii1, v)：在范围[ii0, ii1)中查询首个v，查到返回其迭代器，否则返回c.end()（c为容器对象）；
find_if(ii0, ii1, pred)：查询首个满足pred（单目；常用lambda表达式）的元素；
find_if_not(ii0, ii1,pred)：查询首个不满足pred的元素。

示例代码如下：

#include<algorithm>
#include<string>
#include<vector>

    vector<string >a = { "abc","erfg","dfhy","werf" };
    //vector<string>::iterator iter;
    auto iter = find_if(a.begin(), a.end(), [](string x) {return  x[0]=='d';}); //②
    auto iter = find(a.begin(), a.end(), "erfg");  //①
    cout << (*iter).c_str() << endl;

（2）查询子序列：
①search(fi0, fi1, fi2, fi3)/find_end(fi0, fi1, fi2, fi3)：在[fi0,fi1)内搜索子序列[fi2,fi3)首次/最后一次出现的位置；

#include<algorithm>
#include<string>
#include<vector>

    vector<string >a = { "abc","erfg","dfhy","werf" ,"yxy","erfg","dfhy","wxx" };
    vector<string>b = { "erfg","dfhy" };
    //auto iter = search(a.begin(), a.end(), b.begin(), b.end());  //werf
    auto iter = find_end(a.begin(), a.end(), b.begin(), b.end());  //wxx
    cout << (*(iter+2)).c_str() << endl;

②search(fi0, fi1, fi2, fi3, bpred)/find_end(fi0, fi1, fi2, fi3, bpred)：在[fi0,fi1)内搜索满足bpred子序列[fi2,fi3)首次/最后一次出现的位置；

#include<algorithm>
#include<vector>

    vector<int>a = { 1,2,3,4,5,6,2,3,4,109 };
    vector<int>b = { 20,30,40 };
    auto iter1 = search(a.begin(), a.end(), b.begin(), b.end(), [](int x, int y) {return (x * 10 == y);});
    auto iter2 = find_end(a.begin(), a.end(), b.begin(), b.end(), [](int x, int y) {return (x * 10 == y);});
    cout << "search()" << iter1 - a.begin() << endl;  //输出：1
    cout << "find_end()" << iter2 - a.begin() << endl;  //输出：6

③adjacent_find(fi0, fi1)：首次连续两个元素相同的位置；search_n(fi0, fi1, n, v)：首次连续出现n个v的位置；adjacent_find(fi0, fi1, bpred)：首次连续两个元素满足bpred的位置。

#include<algorithm>
#include<vector>

    vector<int>a = { 2,2,3,4,3,40,5,3,3,7 };
    auto iter1 = search_n(a.begin(), a.end(), 2, 3);
    cout << "首次连续两个3：" << iter1 - a.begin() << endl; //输出：7
    auto iter2 = adjacent_find(a.begin(), a.end()); 
    cout << iter2 - a.begin() << endl;  //输出：0
    auto iter3 = adjacent_find(a.begin(), a.end(), [](int x, int y) {return y - x == 37;});
    cout << iter3 - a.begin() << endl;  //输出：4

3、计数与比较：
①count(ii0, ii1, v)：返回与v相等的元素总数；count_if(ii0, ii1, pred)：返回满足pred的元素总数；

#include<algorithm>
#include<vector>

    vector<int>a = { 2,2,3,4,3,40,5,3,3,7 };
    auto x = count(a.begin(), a.end(), 3);  //4
    auto y = count_if(a.begin(), a.end(), [](int c) {return c >= 5;}); //3

②mismatch(ii0, ii1, ii2, bpred)：返回两序列（[ii0,ii1）、[ii2,*)）首次不满足bpred的位置；

#include<algorithm>
#include<vector>

    vector<int>a = { 3,4,39,40,5,3,3,7 };
    vector<int>b = { 4,5,40,45,3 };
    auto iter = mismatch(a.begin(), a.end(), b.begin(), [](int x, int y) {return x + 1 == y;});
    cout << iter.first - a.begin() << endl; //3
    cout << iter.second - b.begin() << endl; //3

③equal(ii0, ii1, ii2, bpred)：判断两序列（[ii0,ii1）、[ii2,*)）满足谓词bpred下的相等。

#include<algorithm>
#include<vector>

    vector<int>a = { 1,3,5,7,9 };
    vector<int>b = { 2,6,10,14,18 };
    auto x = equal(a.begin(), a.end(), b.begin(), [](int x, int y) {return x * 2 == y;});
    cout << x << endl;  //1（true）

4、复制、替换与删除：
①copy(ii0, ii1, oi)：将序列[ii0,ii1)中的元素复制到另一个由oi引领的序列中；copy_backward(bi0, bi1, bi2)：将序列[bi0,bi1)中的元素复制到另一个由bi2结尾的序列中；copy_if (ii0, ii1, oi, pred)：复制序列中满足pred的元素。

#include<algorithm>
#include<vector>

    vector<int>a = { 1,3,5,7,9 };
    vector<int>b(count_if(a.begin(), a.end(), [](int x) {return x <= 5;})); //要预分配空间
    copy_if(a.begin(), a.end(), b.begin(), [](int x) {return x <= 5;});
    for_each(b.begin(), b.end(), [](int x) {cout << x << " ";});

②replace(fi0, fi1, old_v, new_v)：将序列中所有旧值换成新值；replace_if(fi0, fi1, pred, new_v)：将序列中满足pred的旧值替换为新值；

#include<algorithm>
#include<vector>

    vector<int> vec = { 1,2,3,4,5 };
    replace_if(vec.begin(), vec.end(), [](int x) {return x <= 3;}, 100);
    copy(vec.begin(), vec.end(), ostream_iterator<int>(cout, " ")); //100,100,100,4,5

③remove(fi0, fi1, v)：删除序列中所有的v值；remove(fi0, fi1, pred)：删除序列中所有满足pred的值。注意：remove后将目标元素放置于前，非目标元素由返回的迭代器引领直到序列末尾！

#include<algorithm>
#include<vector>

    int array[] = { 0,0,0,1,2,3 };
    vector<int>myvec(array, array + 6);
    copy(myvec.begin(), myvec.end(), ostream_iterator<int>(cout, " ")); //输出删除前序列：0,0,0,1,2,3
    auto iter = remove(myvec.begin(), myvec.end(), 0); //删除0，返回删除后目标子列末尾的迭代器（非目标首元素处）
    //也便是说，remove后获得：1,2,3,1,2,3
    myvec.erase(iter, myvec.end());  //真正的删除：从iter到原容器末尾！
    copy(myvec.begin(), myvec.end(), ostream_iterator<int>(cout," ")); //输出真正删除后序列：1,2,3

说明：vector适合用remove+erase删除，因为它擅长“批量操作”；list适合find+erase一次删除一个节点，因为它擅长“单点操作”。此外，还存在remove_copy(ii0,ii1,oi,v) 和remove(ii0,ii1,oi,pred)用于创建一个新的删除数据后的序列。

5、排序：
①is_sorted(fi0, fi1)：判断序列[fi0,fi1)是否有序；sort(ri0, ri1, bpred)：没有谓词时默认为“升序”排，有谓词时则按bpred排；stable_sort(ri0, ri1, bpred)：保证两等价元素于排序前后相对位置不改变；

#include<algorithm>
#include<vector>

    vector<int> vec = { 2,5,8,4,3,6 };
    if (!is_sorted(vec.begin(), vec.end()))
    {
        sort(vec.begin(), vec.end(), [](int x, int y) {return x > y;});
        copy(vec.begin(), vec.end(), ostream_iterator<int>(cout, " "));
    }

②partial_sort(ri0, ri1, ri2)/ partial_sort(ri0, ri1, ri2, pred)：将[ri0,ri1)范围内的元素排好序（默认升序、谓词），而[ri1,ri2)内的不保证，但这之中的元素总体上“占优/劣势”。

#include<algorithm>
#include<vector>

    vector<int> vec = { 2,5,8,4,3,6 };
    if (!is_sorted(vec.begin(), vec.end()))
    {
        //partial_sort(vec.begin(), vec.begin() + 4, vec.end());  //默认“升序”
        partial_sort(vec.begin(), vec.begin() + 3, vec.end(), [](int x, int y) {return x > y;});
        copy(vec.begin(), vec.end(), ostream_iterator<int>(cout, " "));
    }

6、二分搜索（针对已排序的）：
①binary_search(fi0, fi1, v)/ binary_search(fi0, fi1, v,pred )：返回值为“true”或者”false”；

#include<algorithm>
#include<vector>

    vector<int> vec = { 2,5,8,4,3,6 };
    if (!is_sorted(vec.begin(), vec.end()))
    {
        sort(vec.begin(), vec.end());
    }
    auto res = binary_search(vec.begin(), vec.end(), 4); //true

②还有lower_bound/upper_bound/equal_range也利用二分算法实现。

#include<algorithm>
#include<vector>

    vector<int> vec = { 2,5,8,4,3,6,5 };  
    if (!is_sorted(vec.begin(), vec.end())){
        sort(vec.begin(), vec.end()); //2,3,4,5,5,6,8
    }
    auto yxy = equal_range(vec.begin(), vec.end(), 5);
    cout << yxy.first - vec.begin() << endl;  //3
    cout << yxy.second - vec.begin() << endl;  //5

7、集合运算：
假定S_1=[ii0,ii1)，S_2=[ii2,ii3)，则存在如下集合运算：

1.includes(ii0, ii1, ii2, ii3)：判断S_2是否为S_1的子集（一一对应）；
2. set_union(ii0, ii1, ii2, ii3, oi)：求两个集合的并集；
3. set_intersection(ii0, ii1, ii2, ii3, oi)：求两个集合的交集；
4. set_difference(ii0, ii1, ii2, ii3, oi)：求两个集合的差集。

8、其他运算：

求序列的最大值、最小值：max_element/min_element；
倒序排列：reverse；
将一个序列循环左移（中剖分旋转180°）：rotate；
去除重复元素（保前删后）：unique；
未完待续……

- - - - - - - - - - - -祝您学习愉快(*^▽^*)- - - - - - - – - - -

上一篇： Spring IOC

下一篇： Ubuntu16.04下nvidia-smi:command not found解决

C++之STL常用算法

c++之STL(12) STL 算法 - 最小值和最大值

iOS常用算法之两个有序数组合并（要求时间复杂度为0(n)）

C++的STL算法

c/c++ 通用的（泛型）算法之只读算法，写算法，排序算法

C++常用排序算法总结

排序算法之快速排序代码c++

C++算法之冒泡排序、选择排序算法实例讲解

C++程序员应了解的那些事（94）之STL容器内存释放问题

C++程序员应了解的那些事（32）STL 源码剖析-算法stl_numeric.h

C++之标准模板库STL续（容器，算法）

C++之STL常用算法

c++之STL(12) STL 算法 - 最小值和最大值

iOS常用算法之两个有序数组合并（要求时间复杂度为0(n)）

C++的STL算法

c/c++ 通用的（泛型）算法 之 只读算法，写算法，排序算法

C++常用排序算法总结

排序算法之快速排序代码c++

C++算法之冒泡排序、选择排序算法实例讲解

C++程序员应了解的那些事（94）之STL容器内存释放问题

C++程序员应了解的那些事（32）STL 源码剖析-算法stl_numeric.h

C++之标准模板库STL续（容器，算法）

c/c++ 通用的（泛型）算法之只读算法，写算法，排序算法