C++学习笔记(三)STL简介(二)

Myth丶恋晨 2022-08-01 06:12 196阅读 0赞

# Generic algorithm(泛型算法) #

![20150620192021769][]

--------------------

## 一.不修改序列的算法 ##

### 1.函数对象的概念 ###

函数对象是一个类的对象，但是它的使用方法与函数一样，又称为仿函数，其实质是通过重载运算符()。由于类的性质使这个函数具有一些特殊的功能，从而实现一些普通函数实现不了的功能。  
例：

#include <iostream>
    #include <algorithm>
    using namespace std;
    template<typename T>
    class print {
    public:
        void operator() (const T& t) {
            cout << t << endl;
        }
    };
    int main() {
        print<int> example;
        for (int i = 0; i < 6; i++) {
            example(i);
        }
        return 0;
    }

运行结果为：  
![20150620193150435][]

--------------------

### 2.不变序列算法 ###

#### a.概念： ####

不变序列算法顾名思义该算法不会改变序列中的元素，比如计算所有与关键值相同的元素个数的count()方法以及遍历容器中的每个元素的for\_each()方法。下面介绍些比较常用的算法，剩下的大家可以查阅网上相关资料进行学习

#### b.for\_each()算法 ####

for\_each函数可以用于遍历容器中的每个元素，函数的前两个参数确定遍历的范围，第三个参数接收一个函数对象，该函数对象执行对遍历的元素的操作。  
例：

#include <iostream>
    #include <algorithm>
    #include <vector>
    using namespace std;
    template <typename T>
    class print {
    public:
        void operator() (const T& t) {
            cout << t << endl;
        }
    };
    int main() {
        print<int> example2;
        vector<int> v;
        for (int i = 0; i < 6; i++) {
            v.push_back(i * i); // 注意这里不要用下标形式对向量容器进行赋值
        }
        for_each(v.begin(), v.end(), example2); // 利用for_each函数遍历向量
        return 0;
    }

运行结果  
![20150620194347066][]

#### c.count()算法 ####

count()算法返回容器中与给定值相同的元素的个数，如：count(first, last, val),该函数将搜索从first到last之间所有等于val的元素，并统计这些元素的个数总和，函数的返回值就是统计的结果int型。  
例：

#include <iostream>
    #include <algorithm>
    #include <set>
    using namespace std;
    typedef multiset<int>::iterator IT;
    int main() {
        multiset<int> s;
        s.insert(0);
        s.insert(1);
        s.insert(1);
        s.insert(2);
        s.insert(2);
        s.insert(1);
        cout << "该容器中的元素如下" << endl;
        for (IT it = s.begin(); it != s.end(); ++it)
            cout << *it << endl;
        int n = count(s.begin(), s.end(), 1); // 调用count函数
        cout << "该容器中有" << n << "个1" << endl;
        return 0;
    }

运行结果：  
![20150620201643940][]

#### d.count\_if()算法 ####

count\_if()算法作为count()算法的加强版的，有三个参数，前两个参数与count()算法相同表示范围，最后的参数接收一个bool类型的自定义仿函数，count\_if()算法的返回值为仿函数返回结果为true的个数  
例：

#include <iostream>
    #include <algorithm>
    #include <set>
    using namespace std;
    typedef multiset<int>::iterator IT;
    class condition {
    private:
        int lowerbound;
        int upperbound;
    public:
        condition(int ival1, int ival2) : lowerbound(ival1), upperbound(ival2) {}
        bool operator() (const int& val) {
            return (val > lowerbound && val < upperbound);         //count_if自定义的比较函数计算一定区间内的元素数目
        }
    };
    int main() {
        multiset<int> s;
        s.insert(0);
        s.insert(1);
        s.insert(1);
        s.insert(2);
        s.insert(2);
        s.insert(1);
        cout << "该容器中的元素如下" << endl;
        for (IT it = s.begin(); it != s.end(); ++it)
            cout << *it << endl;
        int n = count_if(s.begin(), s.end(), condition(0,2));
        cout << "该容器中有" << n << "个大于0小于2的数" << endl;
        return 0;
    }

运行结果：  
![20150620213635949][]

#### e.find()算法 ####

通用的find()算法声明如下，

template<typename InIt, typename T> // 声明了一个模板，两个参数分别为InIt和T
    InIt find(InIt first, InIt last, const T& val); // 声明了三个变量，first和last代表首尾指针，val代表所要查找的内容，find函数查找到时返回指向该元素的指针， 当find函数当查找不到所查找的内容时会返回尾指针。

例：

#include <iostream>
    #include <list>
    #include <string>
    #include <algorithm>
    using namespace std;
    int main() {
        list<string> str;
        list<string>::iterator it;
        str.push_back("张三");
        str.push_back("李四");
        str.push_back("王五");
        it = find(str.begin(), str.end(), "李四");
        if (it == str.end()) {
            cout << "没有找到李四" << endl; // find函数当查找不到所查找的内容时会返回尾指针
        } else {
            cout << *it << endl;
        }
        return 0;
    }

运行结果：  
李四

#### f.find\_if()算法 ####

find()算法的加强版本和find()的关系如同count\_if和count的关系，该方法接收一个函数对象的参数作为参数，并使用它来做更为复杂的条件检测，这里就不再赘述。

#### g.adjacent\_find()方法 ####

该方法返回指向容器中第一组相等元素的迭代器，参数如下

adjacent_find(first, last);

first和last确立了函数搜索的范围，adjacent\_find函数返回的就是从first到last之间指向第一组相同元素的迭代器（指向第一组相同元素中的第一个元素的迭代器）。  
例：

#include <iostream>
    #include <list>
    #include <string>
    #include <algorithm>
    using namespace std;
    int main() {
        list<string> str;
        list<string>::iterator it;
        str.push_back("张三");
        str.push_back("李四");
        str.push_back("王五");
        str.push_back("王五");
        str.push_back("赵六");
        str.push_back("赵六");
        cout << "正在查找第一组相同的元素：" << endl;
        it = adjacent_find(str.begin(), str.end());
        cout << *it << endl;
        it++;;
        cout << *it << endl;
        cout << "正在查找第二组相同的元素: " << endl;
        adjacent_find(it, str.end());
        it++;
        cout << *it << endl;
        it++;
        cout << *it << endl;
        return 0;
    }

运行结果：  
![20150620222358660][]

注：**adjacent\_find()方法返回的是指向一对邻近相等元素中的第一个元素的迭代器，可以看出，adjacent\_find方法找到的一组相等的元素是相邻的两个元素**

--------------------

## 二.改变序列的算法 ##

### 1.概念：改变序列的算法即执行改变序列中元素的运算，例如添加，删除，复制和填充，以及重新安排元素的运算。（注意：map,multimap,set 和 multiset会自动对元素进行排序，所以在遍历元素时对元素进行修改会导致排序的不正确。因此容器中的元素不能被修改，只能删除后再添加，向容器中添加元素必须重载<操作符来进行排序，所以大部分改变序列不能应用于上述四个容器中） ###

### 2.常见改变序列的算法 ###

#### a.fill()方法 ####

fill(first, last, val)该方法把数值val赋值到first到last之间的所有元素。  
例：

#include <iostream>
    #include <algorithm>
    #include <vector>
    using namespace std;
    int main() {
        vector<int> v(10);
        fill(v.begin(), v.begin() + 5, 1);  // 将vector容器中
        fill(v.begin() + 5, v.end(), 0);
        for (vector<int>::iterator it = v.begin(); it != v.end(); ++it)
            cout << *it << endl;
        return 0;
    }

![20150621115400971][]

#### b.partition()方法 ####

partition(first, last, pred)该方法将一个序列分成两部分，其中第一部分包括被函数对象pred作用后返回真值的元素，第二个部分包括被函数对象pred作用后返回假值的元素。partition函数返回一个指向两个部分分界处的迭代器.。pred表示的是函数对象，是一个只有一个参数返回值为bool型。  
例：

#include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    bool pred(int val) {
        return (val < 3);   // 将小于3的数分在一边，将大于等于3的数分在一边
    }
    void print(int val) {
        cout << val << endl;
    }
    int main() {
        vector<int> v;
        v.push_back(3);
        v.push_back(1);
        v.push_back(5);
        v.push_back(2);
        v.push_back(4);
        v.push_back(0);
        cout << "Before partition:" << endl;
        for_each(v.begin(), v.end(), print);
        partition(v.begin(), v.end(), pred);
        cout << "After partition:" << endl;
        for_each(v.begin(), v.end(), print);
        return 0;
    }

运行结果：

![20150622200810231][]

#### c.rotate()方法 ####

rotate(first, middle, last);该方法把middle到last范围中的元素向左旋转到first开始的范围中去。

#include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    void print(char val) {
        cout << val << " ";
    }
    int main() {
        vector<char> v;
        v.push_back('h');
        v.push_back('e');
        v.push_back('l');
        v.push_back('l');
        v.push_back('o');
        v.push_back('w');
        v.push_back('o');
        v.push_back('r');
        v.push_back('l');
        v.push_back('d');
        cout << "Before rotate:" << endl;
        for_each(v.begin(), v.end(), print);
        cout << endl;
        rotate(v.begin(), v.begin() + 5, v.end());
        cout << "After rotate:" << endl;
        for_each(v.begin(), v.end(), print);
        return 0;
    }

运行结果：  
![20150622201948598][]

#### d.next\_permutation()和prev\_permutation()方法 ####

next\_permutation()方法可以取出first到last范围的排列，并排序为下一个排列。如果存在下一个排列则返回true，如果是最后一个排列则返回false。而prev\_permutation()方法与其相反，他会得到当前排列的上一个排列。如果不存在上一个排列则返回false否则返回true。  
**next\_permutation()方法使数组中的元素按降序进行排列，这个按降序排列的过程叫做全排列**  
如果我们有数字1,2,3，那么它的全排列为：  
1 2 3  
1 3 2  
2 1 3  
2 3 1  
3 1 2  
3 2 1  
1,2,3的下一个排列为1,3,2； 1,3,2的下一个排列为2,1,3以此类推。  
例：

#include <iostream>
    #include <algorithm>
    using namespace std;
    int main() {
        int a[] = { 1, 2, 3 };
        do {
            cout << a[0] << " " << a[1] << " " << a[2] << endl;
        } 
        while (next_permutation(a, a + 3));
        return 0;
    }

![20150623234015818][]

--------------------

## 三.排序算法 ##

### 1.概念：排序算法即为对容器中的元素进行排序操作的算法，如sort()方法。 ###

### 2.常见的排序算法 ###

#### a.sort()方法 ####

sort(first, last)对迭代器范围内的左闭右开区间内的元素进行升序排列(使用<操作符进行元素比较)  
sort(first, last, cmp)排序的范围与上面的sort方法相同，但比较元素时使用自定义的cmp函数。  
例：

#include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    struct point {
        int x;
        int y;
    };
    void print(point p) {
        cout << p.x <<" " <<  p.y << endl;;
    }
    bool cmp(point a, point b) {
        return (a.x <= b.x && a.y <= b.y);      // 对结构体进行排序按照升序
    }
    int main() {
        vector<point> v;
        point a, b, c;
        a.x = 1;
        a.y = 1;
        b.x = 2;
        b.y = 2;
        c.x = 3;
        c.y = 3;
        v.push_back(c);
        v.push_back(b);
        v.push_back(a);
        cout << "Before sort:" << endl;
        for_each(v.begin(), v.end(), print);
        cout << endl;
        sort(v.begin(), v.end(), cmp);      // 利用自定义的cmp函数进行排序
        cout << "After sort:" << endl;
        for_each(v.begin(), v.end(), print);
        return 0;
    }

运行结果：  
![20150622210513092][]

#### b.partial\_sort()方法 ####

partial\_sort(first, middle, last)该方法将first到last之间的元素进行排序，并将排好序的元素放到first到middle之间，其他放到middle到last之间（即部分排序）。  
例：

#include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    void print(char val) {
        cout << val << endl;;
    }
    int main() {
        vector<int> v;
        v.push_back('c');
        v.push_back('b');
        v.push_back('a');
        v.push_back('e');
        v.push_back('d');
        cout << "Before partial_sort:" << endl;
        for_each(v.begin(), v.end(), print);
        cout << endl;
        partial_sort(v.begin(), v.begin() + 2, v.end());
        cout << "After partial_sort:" << endl;
        for_each(v.begin(), v.end(), print);
        return 0;
    }

运行结果：  
![20150623162337750][]

--------------------

## 四.泛化算术算法 ##

### 1.概念：泛化算术算法可以对一个序列的元素进行四种运算，又称数值算法，使用时需要包含头文件。 ###

### 2.四种算法： ###

#### a.accumulate()方法 ####

accumulate(first, last, init)方法是在first到last范围中计算init与每个元素的和，重载的版本需要自定义一个函数对象，且可以不做加法运算，而是将自定义的操作应用到元素上。  
例：

#include<iostream>
    #include<vector>
    #include<algorithm>
    #include<numeric>
    using namespace std;
    void print(int val) {
        cout << val << endl;
    }
    int main() {
        vector<int> v;
        for (int i = 0; i < 5; i++)
            v.push_back(i);
        for_each(v.begin(), v.end(), print);
        int result = accumulate(v.begin(), v.end(), 5); // 
        cout << "上述五个数与5相加的结果为：" << result << endl;
        return 0;
    }

运行结果：  
![20150623194944890][]

#### b.inner\_product()方法 ####

inner\_product()方法是求内积的一种方法，它首先计算first到last及first1所规定的范围中元素的内积之和(内积是通过把每一个序列中的元素与第二个序列中相同位置的元素相乘，然后把结果相加而得到)，再把这个结果与init相加并返回。重载的版本将会使用用户定义的操作。  
例：

#include<iostream>
    #include<vector>
    #include<algorithm>
    #include<numeric>
    using namespace std;
    void print(int val) {
        cout << val << endl;
    }
    int main() {
        vector<int> v1;
        vector<int> v2;
        for (int i = 0; i < 5; i++)
            v1.push_back(i);
        for (int i = 4; i >= 0; i--)
            v2.push_back(i);
        cout << "v1中的元素：" << endl;
        for_each(v1.begin(), v1.end(), print);
        cout << "v2中的元素：" << endl;
        for_each(v2.begin(), v2.end(), print);
        int result = inner_product(v1.begin(), v1.end(), v2.begin(), 0);
        cout << "v1与v2内积与0相加的结果为：" << result << endl;  // result = 0*4+1*3+2*2+3*1+4*0+0=10
        return 0;
    }

![20150623200408421][]

#### c.partial\_sum()方法 ####

partial\_sum()方法计算first到last所规定范围内的元素的部分和，并把结果放置到result开始的序列中。部分和的计算方式如下：首先将原序列中的第一个元素作为result序列的第一个元素，然后原序列中的前两个元素相加作为result序列的第二个元素；接着，原序列中的前三个元素相加作为result序列的第三个元素，以此类推例如:原序列为1, 2, 3, 4, 5….n 则result序列为：1， 1+2， 1+2+3， …， 1+2+3+…+n。同样我们还是可以利用重载版本，重载版本使用了自定义的操作代替加法。  
例：

#include<iostream>
    #include<vector>
    #include<algorithm>
    #include<numeric>
    using namespace std;
    void print(int val) {
        cout << val << endl;
    }
    int main() {
        vector<int> v1;
        vector<int> v2(5); // 声明容量为五个元素的v2即result容器
        for (int i = 0; i < 5; i++)
            v1.push_back(i);
        cout << "v1中的元素：" << endl;
        for_each(v1.begin(), v1.end(), print);
        partial_sum(v1.begin(), v1.end(), v2.begin());
        cout << "v2中的元素：" << endl;
        for_each(v2.begin(), v2.end(), print);
        return 0;
    }

运行结果：  
![20150623202656658][]

#### d.adjacent\_difference()方法 ####

adjacent\_difference(first, last, result)方法计算first到last所规定范围内的元素的相邻差，并把结果放置到resul开始的序列中。相邻差的计算方法是这样的：首先原序列中的第一个元素作为result序列的第一个元素，然后原序列中的前两个元素相减作为result序列的第二个元素(第二个减第一个)，紧接着以此类推，同样重载版本使用了自定义操作来代替加法。  
例：

#include<iostream>
    #include<vector>
    #include<algorithm>
    #include<numeric>
    using namespace std;
    void print(int val) {
        cout << val << endl;
    }
    int main() {
        vector<int> v1;
        vector<int> v2(5);
        for (int i = 0; i < 5; i++)
            v1.push_back(i);
        cout << "v1中的元素：" << endl;
        for_each(v1.begin(), v1.end(), print);
        adjacent_difference(v1.begin(), v1.end(), v2.begin());
        cout << "v2中的元素：" << endl;
        for_each(v2.begin(), v2.end(), print);
        return 0;
    }

运行结果：  
![20150623204521522][]

--------------------

### 呼呼总算把C++学习中极为重要的STL部分讲完了，其实所讲的不过是常用的一些知识的总结，更多需要自己去查阅官方文档使用，并且在不断地编程中去应用才能融汇贯通，我们下期见~！ ###

[20150620192021769]: /images/20220731/fe0ee14b902a432ab66930b76f2da08b.png
[20150620193150435]: /images/20220731/b4c8e76719704c5295686c03cd9d8835.png
[20150620194347066]: /images/20220731/c65385ba48b54e27a7de1e19ba61063d.png
[20150620201643940]: /images/20220731/4fc4068b33184adfa41e19ab758a0957.png
[20150620213635949]: /images/20220731/7d6ea95be8744c059d92a0297ef5f08f.png
[20150620222358660]: /images/20220731/08e23e02862a44b796f41cb5007cdf4d.png
[20150621115400971]: /images/20220731/2c8f0a329ea84e4ab1585eeaf96c552c.png
[20150622200810231]: /images/20220731/9b9db33f72684187a2a325b781c79f53.png
[20150622201948598]: /images/20220731/8281ee6de8ee4ff2a6d127191c057fbc.png
[20150623234015818]: /images/20220731/bb8bc1396b164afe8e5c308aafdcf22b.png
[20150622210513092]: /images/20220731/3157d702d9d249d09fc745eeecba25c6.png
[20150623162337750]: /images/20220731/865d3a5afd364242a6fd2df6e2d49d7b.png
[20150623194944890]: /images/20220731/938b0e5de6db4138b82a347ab94b4cb7.png
[20150623200408421]: /images/20220731/e08ebac799444a43a81c953d6d7763c4.png
[20150623202656658]: /images/20220731/833c0fc3c1f84978b5d1427393e69b05.png
[20150623204521522]: /images/20220731/7bc90dde3c7e435d834f14ceffb7531f.png