C/C++编程：STL算法总结

喜欢ヅ旅行 2023-03-02 05:10 1阅读 0赞

# 分类 #

STL 中算法大致分为四类：

*  可变序列算法： 可以修改他们所操作的容器内容的算法
 *  非可变序列算法：不直接修改其所操作的容器内容的算法
 *  排序算法：包括对序列进行排序和合并的算法、搜索算法以及有序序列上的集合操作
 *  数值算法：对容器内容进行数值计算。

## 可变序列算法 ##

*  可以进行序列数据的复制、交换、替换、填充、移除、旋转、随机抖动、分割。这些算法对调迭代器有较高的要求，必须先检查容器的迭代器是否符合要求，防止编译错误。

### 元素复制算法 ###

#### insert ####

C++11中除了引入了很多新语法之外，还对标准库进行了强化，

> C++98中的insert方法声明

iterator insert (iterator position, 
                     const value_type& val);
    void insert (iterator position, 
                     size_type n,      
                     const value_type& val);
    template <class InputIterator>
    void insert (iterator position, 
                     InputIterator first,  
                     InputIterator last);

> C++11中的insert方法

iterator insert (const_iterator position, 
                     const value_type& val);
    iterator insert (const_iterator position,     
                     size_type n,   
                     const value_type& val);
    template <class InputIterator>
    iterator insert (const_iterator position, 
                     InputIterator first,
                     InputIterator last);
    iterator insert (const_iterator position,  
                     value_type&& val);
    iterator insert (const_iterator position,  
                      initializer_list<value_type> il);

> 细节比较

*  添加单个元素

iterator insert (const_iterator position, 
                     const value_type& val);

唯一的变化就是position的参数类型发生了变化，功能相同但是增加了对`const_iterator`的支持。这种变化适用于所有`insert`方法，下面就不再说明了

*  添加多个元素

iterator insert (const_iterator position,     
                     size_type n,   
                     const value_type& val);

这个方法可以在指定位置填充n个val。例如下面的代码：

std::list<int> demo{
        1, 2, 3, 4, 5, 6};
        auto position = std::find(demo.begin(), demo.end(), 3);
        demo.insert(position, 2 , 0);
        demo.insert(position, 2 , -1);
        for (int var: demo) {
        
            std::cout << var << ",";
        }
        std::cout << "\n";

![在这里插入图片描述][20210323150701528.png]

*  以移动的方式插入数据

iterator insert (const_iterator position,  
                     value_type&& val);

提供了对数据移动的支持，比如：

std::list<std::string> strlist{
        "are", "you"};
        std::string str("How");
        strlist.insert(strlist.begin(), std::move(str));
        for (const auto& var: strlist) {
        
            std::cout << var << ",";
        }
        std::cout << "\n";
        std::cout << "str=" << str << "\n";

![在这里插入图片描述][20210323150927182.png]  
可以看到，str的内容从str中移除并插入到strlist中。

*  支持initializer\_list

这个方法也是C++11中新追加的，提供对initializer\_list的支持。示例代码如下：

strlist.insert(strlist.begin(), {
        "C++", "11"});
        for (const auto& var: strlist) {
        
            std::cout << var << " ";
        }

![在这里插入图片描述][20210323152449514.png]

#### emplace ####

假设有下面Rect类

struct Rect
    {
        
        Rect(int l, int t, int r, int b)
                :left{
        l}, top{
        t}
                ,right{
        r}, bottom{
        b}
        {
        }
        int left; int top; int right; int bottom;
    };

当需要向容器添加Rect对象时，代码大致是这样的

std::list<Rect> rlist;
    rlist.push_front(Rect(10, 10, 20, 20));

在调用push\_front时，首先构造一个临时的Rect对象传递给push\_front方法，然后在push\_front的内部，复制一个Rect对象添加到容器中。全过程会发生一次创建动作和一次拷贝动作，才能将对象的内容添加到容器中。

**为了减少拷贝动作的次数，当然可以使用右值引用参数的成员函数。除此之外，C++11还提供了另一种方法：emplacement成员。使用这个成员可以直接传递用于生成对象的参数，对象的创建过程交给容器去执行：**

std::list<Rect> rlist;
        rlist.emplace_front(10, 10, 20, 20);

用法非常简单，只要保证参数和元素构造函数的参数相同即可。

除了emplace\_front以外，C++11还提供了emplace和emplace\_bak方法，分别对应insert和push\_back方法。

**注：当创建对象的目的只是为了将其添加到容器中，emplace提供了右值引用之外的另一个选择**

#### copy函数 ####

*  作用：

> 该函数用于容器间元素拷贝，将迭代器区间\[first, last)的元素复制到由复制目标迭代器result给定的区间\[result, result + (last - first))。

*  函数原型：

template<class InputIterator, class OutputIterator>
      OutputIterator copy (InputIterator first, InputIterator last, OutputIterator result)

*  要求：
    
     *  目标容器的容量要比待复制的内容大
 *  例子：

#include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    void print(int x) {
        
        cout << x << " ";
    }
    
    int main() {
        
        // 像是水管：从begin 开始一个个向前推。直到result的满了
        std::vector<int> v{
        2 , 4 , 3};
        std::vector<int> v2(4);
        for_each(v2.begin(), v2.end(), print); // 0 0 0 0
        // 0 0 0 0
        // 3 0 0 0
        // 4 3 0 0
        // 2 4 3 0
        cout << "\n";
        std::copy(v.begin(), v.end(), v2.begin());
        for_each(v2.begin(), v2.end(), print); // 2 4 3 0
        cout << "\n------------------------\n";
    
        std::vector<int> v3(4);
        v3.push_back(8);
        for_each(v3.begin(), v3.end(), print); //0 0 0 0 8
        cout << "\n";
        std::copy(v.begin(), v.end(), v3.begin());
        for_each(v3.begin(), v3.end(), print); // 2 4 3 0 8
        cout << "\n------------------------\n";
    
        std::vector<int> v4;
        v4.push_back(8);
        // 8
        // 3
        // 4 
        // 2
        for_each(v4.begin(), v4.end(), print); //8
        cout << "\n";
        std::copy(v.begin(), v.end(), v4.begin());
        for_each(v4.begin(), v4.end(), print); // 2 
    
        return 0;
    }

#### copy\_backward ####

作用：

> 将一个迭代器区间的内容复制到另一迭代器区间，与copy()相似，不同的是复制过程从最后的元素开始。

*  函数原型：

template<class BidirectionalIterator1, class BidirectionalIterator2>
      BidirectionalIterator2 copy_backward ( BidirectionalIterator1 first,
                                             BidirectionalIterator1 last,
                                             BidirectionalIterator2 result )

*  例子：

#include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    void print(int x) {
        
        cout << x << " ";
    }
    
    int main() {
        
        // 像是水管：从begin 开始一个个向前推。直到result的满了
        std::vector<int> v{
        2 , 4 , 3};
        std::vector<int> v2(4);
        for_each(v2.begin(), v2.end(), print); // 0 0 0 0
        // 0 0 0 0
        // 0 0 0 2
        // 0 0 2 4
        // 0 2 4 3
        cout << "\n";
        std::copy_backward (v.begin(), v.end(), v2.end());
        for_each(v2.begin(), v2.end(), print); //0 2 4 3
        cout << "\n------------------------\n";
    
        std::vector<int> v3(4);
        v3.push_back(8);
        // 0 0 0 0 8
        // 0 0 0 0 2
        // 0 0 0 2 4
        // 0 0 2 4 3
        for_each(v3.begin(), v3.end(), print); //0 0 0 0 8
        cout << "\n";
        std::copy_backward (v.begin(), v.end(), v3.end());
        for_each(v3.begin(), v3.end(), print); //  0 0 2 4 3
        cout << "\n------------------------\n";
    
        std::vector<int> v4;
        v4.push_back(8);
        for_each(v4.begin(), v4.end(), print); //8
        cout << "\n";
        std::copy_backward (v.begin(), v.end(), v4.begin());
        for_each(v4.begin(), v4.end(), print); // 8
    
        cout << "\n------------------------\n";
        std::vector<int> v5(2);
        v5[0] = 8;
        for_each(v5.begin(), v5.end(), print); //8 0
        cout << "\n";
        std::copy_backward (v.begin(), v.end(), v5.end());
        for_each(v5.begin(), v5.end(), print); // 4 3
        cout << "\n------------------------\n";
        return 0;
    }

### 元素交换算法 ###

#### swap ####

*  作用：

> 该函数的功能是实现两个元素的交换。虽然大多数容器内部都提供了swap函数，这里提供了更一般的迭代器形式。

*  函数原型如下：

template <class T> void swap ( T& a, T& b )

*  例子：

#include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    void print(int x) {
        
        cout << x << " ";
    }
    
    int main() {
        
        // 交换整数：
        int a = 2;
        int b = 3;
        swap(a, b);
        cout << a << ", " << b << endl; // 3, 2
    
        // 交换数组
        std::vector<int> v{
        2 , 4 , 3};
        std::vector<int> v2(4);
    
        for_each(v2.begin(), v2.end(), print); // 0 0 0 0
        cout << endl;
        swap(v, v2);
        for_each(v2.begin(), v2.end(), print); // 2 4 3
        
        return 0;
    }

#### iter\_swap ####

*  作用：

> 该算法是通过迭代器来完成元素的交换。

*  原型：

template <class ForwardIterator1, class ForwardIterator2>
      void iter_swap (ForwardIterator1 a, ForwardIterator2 b)

*  例子：

#include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    void print(int x) {
        
        cout << x << " ";
    }
    
    int main() {
        
    
        // 交换数组
        vector<int> v1 {
        1,2,3,4,5};
        vector<int> v2 {
        10,20,30,40,50};
    
        for_each(v2.begin(), v2.end(), print); // 0 0 0 0
        cout << endl;
        iter_swap(v1.begin(), v2.begin());
        for_each(v2.begin(), v2.end(), print); // 2 4 3
    
        cout << "\n ******************"<< endl;
    
        // 交换数组
        v1 = {
        1,2,3,4,5};
        v2 =  {
        10,20,30,40,50};
    
        for_each(v2.begin(), v2.end(), print); // 10 20 30 40 50
        cout << endl;
        iter_swap(v1.begin() + 1, v2.begin() + 1);
        for_each(v2.begin(), v2.end(), print); // 10 2 30 40 50
    
        return 0;
    }

#### swap\_ranges() ####

*  功能：

> 将两对应区间里的元素进行交换

*  函数原型：

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

*  函数例子：

#include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    void print(int x) {
        
        cout << x << " ";
    }
    
    int main() {
        
        vector<int> v1 {
        10,10,10,10,10};
        vector<int> v2 {
        20,20,20,20,20};
    
        for_each(v2.begin(), v2.end(), print); // 20 20 20 20 20
        cout << endl;
        std::swap_ranges(v1.begin()+1, v1.end()-1, v2.begin() + 1);
        for_each(v2.begin(), v2.end(), print); //20 10 10 10 20
        
        return 0;
    }

#### transform ####

*  作用：

> 该函数用于容器元素的变换操作。有两个使用原型，分别用于一元函数对象和二元函数操作。

*  函数原型：

// 一个将迭代器区间[first，last)中元素，执行一元函数对象op操作，交换后的结果放在[result，result+（last-first)）区间中。
    // 将迭代器区间[first1，last1)的元素*i，依次与[first2，first2+（last-first）)的元素*j，执行二元函数操作binary_op(*i,*j)，交换结果放在[result，result+（last1-first1)）。
    template <class InputIterator, class OutputIterator, class UnaryOperation>
    // first1, last1 : 指出要进行元素变换的第一个迭代器区间 [first1,last1)。
      OutputIterator transform (InputIterator first1, InputIterator last1,
      //result: 指出变换后的结果存放的迭代器区间的首个元素的迭代器位置
      // op: 用一元函数对象op作为参数，执行其后返回一个结果值。它可以是一个函数或对象内的类重载operator()。
                                OutputIterator result, UnaryOperation op)
    template <class InputIterator1, class InputIterator2,
              class OutputIterator, class BinaryOperation>
              //first2 :指出要进行元素变换的第二个迭代器区间的首个元素的迭代器位置，该区间的元素个数和第一个区间相等。
      OutputIterator transform (InputIterator1 first1, InputIterator1 last1,
                                InputIterator2 first2, OutputIterator result,
                                //binary_op: 用二元函数对象binary_op作为参数，执行其后返回一个结果值。它可以是一个函数或对象内的类重载operator()。
                                BinaryOperation binary_op)

*  例子：

#include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    void print(int x) {
        
        cout << x << " ";
    }
    int twice(int x){
        
        return 2 * x;
    }
    
    int main() {
        
    
        vector<int> v2 {
        20,20,20,20,20};
    
        for_each(v2.begin(), v2.end(), print); // 20 20 20 20 20
        cout << endl;
        std::transform(v2.begin()+1, v2.end()-1, v2.begin() + 1, twice);
        for_each(v2.begin(), v2.end(), print); //20 40 40 40 20
    
        return 0;
    }

[20210323150701528.png]: /images/20230208/f887d51dff4b47819bde9c809278be35.png
[20210323150927182.png]: /images/20230208/04d1e609a6254b6c8e692f32dd8662b8.png
[20210323152449514.png]: /images/20230208/f518f971fb2d4d8a855c178858d8bea3.png