STL常用算法总结（持续更新）

电玩女神 2022-02-16 01:51 471阅读 0赞

> STL中的谓词是什么？
> 
>  STL中的谓词是一个可调用的对象，其返回结果是一个能用作条件的值。标准库算法所使用的谓词分为两类：**一元谓词**（意味着它们有一个参数）和 **二元谓词**（意味着它们有两个参数）。接受谓词参数的算法对输入序列中的元素调用谓词。因此，元素类型必须能转换为谓词的参数类型。
> 
> 建议：本文中很多地方用到了Lambda表达式，如果不清楚的读者可以参考：[C++可调用对象][C]

### 文章目录 ###

*   *   *  一、排序
         *   *  1.sort函数（不稳定）
             *  2.stable\_sort函数（稳定）
         *  二、查找
         *   *  1.find函数
             *  2.find\_if函数
         *  三、去重
         *   *  unique函数
         *  四、删除
         *   *  remove\_if函数
         *  五、拷贝
         *   *  copy函数
         *  五、杂录
         *   *  1.distance函数
             *  2.begin 和 end 函数
             *  3.for\_each函数
             *  4.reverse函数

### 一、排序 ###

#### 1.sort函数（不稳定） ####

sort函数有两个版本，一个接受谓词，一个不接受谓词。

函数原型：

template <class RandomAccessIterator>
      void sort ( RandomAccessIterator first, RandomAccessIterator last );
    
    template <class RandomAccessIterator, class Compare>
      void sort ( RandomAccessIterator first, RandomAccessIterator last, Compare comp );

函数参数：

*  前者的两个参数为两个迭代器，表示算法应用的范围
 *  后者前两个参数同前者，第三个参数为二元谓词

demo：

[之前总结过的sort用法][sort]

#### 2.stable\_sort函数（稳定） ####

stable\_sort函数有两个版本，一个接受谓词，一个不接受谓词。

注意：这个函数不同于sort的地方在于，它在处理两个值相同（符合字典序相同的两个元素或者令谓词返回true的两个元素）的元素时，不会更改两者的相对位置

函数原型：

template <class RandomAccessIterator>
      void stable_sort ( RandomAccessIterator first, RandomAccessIterator last );
    
    template <class RandomAccessIterator, class Compare>
      void stable_sort ( RandomAccessIterator first, RandomAccessIterator last,
                         Compare comp );

函数参数：

*  前者的两个参数为两个迭代器，表示算法应用的范围
 *  后者前两个参数同前者，第三个参数为二元谓词

demo：

std::vector<std::string> words{ "for","first",
    							   "reinterpret","world","element","as"};
    //对words中的元素按照长度进行排序，具有相同长度的元素相对位置不会改变。
    std::stable_sort(words.begin(), words.end(), 
                     [](const std::string& s1, const std::string& s2)
                     {  return s1.size() < s2.size(); });

### 二、查找 ###

#### 1.find函数 ####

函数原型：

template <class InputIterator, class T>
       InputIterator find ( InputIterator first, InputIterator last, const T& value );

函数参数：

*  前两个元素是两个迭代器，表示算法应用的范围；第三个元素表示需要查找的值

函数返回值：

*  如果找到指定的元素，返回指向该元素的迭代器
 *  如果没找到，返回指向.end()的迭代器

demo：

//用于容器
    std::vector<int> ve{ 1, 2, 3, 4, 5, 6, 7};
    auto result = std::find(ve.begin(), ve.end(), 5);
    if(result == ve.end()){ 
        std::cout << "容器中不存在元素5" << std::endl;
    }else{ 
        //distance函数作用见本文杂录模块
        std::cout << "元素5的下标：" << std::distance(ve.begin, result) 
        	      << std::endl;
    }
    
    //用于内置类型
    int arr[] = { 1, 2, 3, 4, 5, 6, 7};
    //begin和end函数作用见本文杂录模块
    int* result = std::find(std::begin(arr), std::end(arr), 5);
    if(result == std::end(arr)){ 
        std::cout << "容器中不存在元素5" << std::endl;
    }else{ 
        std::cout << "元素5的下标：" << std::distance(std::begin(arr), result)
        		  << std::endl;
    }

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

#### 2.find\_if函数 ####

函数原型：

template <class InputIterator, class Predicate>
       InputIterator find_if ( InputIterator first, InputIterator last, Predicate pred );

函数参数：

*  前两个参数是一对迭代器，表示find\_if应用的范围
 *  第三个参数是一个一元谓词。find\_if算法对输入序列中每一个元素调用给定的这个谓词

函数返回值：

*  返回第一个使谓词返回非0值的元素
 *  如果不存在这样的元素，则返回尾后迭代器

demo：

//需求：找到单词集合中所有长度大于5的单词
    
    int sz = 5;
    std::vector<std::string> words{ "for","first","reinterpret",
    							   "world","element","as"};
    //对单词集合按照单词长度进行升序排序，stable_sort函数作用见本文排序模块
    std::stable_sort(words.begin(), words.end(), WordsCmp);
    //从前往后找到单词集合中第一个符合要求的单词位置
    auto divide = std::find_if(words.begin(), words.end(),
                               [sz](const std::string& s1){  
                                   return s1.size() > sz;
                               });
    //从找到的位置往后都是符合要求的单词，遍历打印之。for_each函数作用见本文杂录模块
    std::for_each(divide, words.end(), [](const string& s){  
    								   std::cout << s << " "; });
    std::cout << std::endl;

### 三、去重 ###

#### unique函数 ####

unqiue函数有两个版本，一个接受谓词，一个不接受谓词。

注意：泛型算法本身不会执行容器的操作，它们只会运行于迭代器之上，执行迭代器的操作。所以，算法永远不会改变底层容器的大小。所以在unique算法并不会删除容器中重复的元素，在调用unique算法后还要手动删除容器中重复的元素。

函数原型：

//不接受谓词
    template <class ForwardIterator>
      ForwardIterator unique ( ForwardIterator first, ForwardIterator last );
    
    //接受谓词
    template <class ForwardIterator, class BinaryPredicate>
      ForwardIterator unique ( ForwardIterator first, ForwardIterator last,
                               BinaryPredicate pred );

函数参数：

*  前者两个参数是一对迭代器，表示算法应用的范围
 *  后者前两个参数和前者相同；第三个参数是一个二元谓词

函数返回值：

*  返回一个指向不重复值范围末尾的迭代器（这句话结合下面这张图来理解）
    
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3phbmRhXw_size_16_color_FFFFFF_t_70]

demo1：

//需求：删除单词集合中重复的单词
    
    //注意：unique使用前要先对序列进行排序
    //按照字典序对单词集合进行排序，sort函数作用见本文排序模块
    std::sort(words.begin(), words.end());
    auto end_unqiue = std::unique(words.begin(), words.end());
    //删除单词集合中重复的单词
    words.erase(end_unique, words.end());

demo2：

//需求：删除 vector<Doc> doc_set 中重复的Doc成员，判断重复的依据是Doc中的weight
    // 成员值是否相同（Doc是自定义类型）
    struct Doc{ 
        int weight;
        std::string doc;
    };
    
    //sort函数作用见本文排序模块
    //对doc_set中元素按照自定义的谓词规则进行排序（此处传入的谓词为Lambda）
    std::sort(doc_set.begin(), doc_set.end(),
              [](const Doc& d1, const Doc& d2){  
                  return d1.weight < d2.weight
              });
    //此处传入的谓词为Lambda表达式
    auto end_unique = std::unique(doc_set.begin(), doc_set.end(),
                                  [](const Doc& d1, const Doc& d2) -> bool { 
                                      if(d1.weight == d2.weight)
                                          return true;
                                      return false;
                                  }
                                 );
    //删除doc_set中重复的元素
    doc_set.erase(end_unique, doc_set.end());
    //for_each函数的作用见本文杂录模块
    std::for_each(doc_set.begin(), doc_set.end(), 
                  [](const Doc& d){  std::cout << d.weight << "|" 
                  							  << d.doc << std::endl; });

### 四、删除 ###

#### remove\_if函数 ####

函数原型：

template < class ForwardIterator, class Predicate >
      ForwardIterator remove_if ( ForwardIterator first, ForwardIterator last,
                                  Predicate pred );

函数参数：

*  前者两个参数是一对迭代器，表示算法应用的范围
 *  第三个参数是一个一元谓词。remove\_if 算法对输入序列中每一个元素调用给定的这个谓词

函数返回值：

*  返回一个指向剩余值范围末尾的迭代器（结合find\_if函数那里那张图理解）

demo：

//需求：删除字符串中的所有逗号
    
    std::string str = "f,ar f,r,om ey,e far, from he,a,rt";
    auto devide = std::remove_if(str.begin(), str.end(), 
                                 [](char c) {  return c == ','; });
    //手动删除算法挑选出来的元素，这里即逗号
    str.erase(devide, str.end());
    std::cout << str << std::endl;

### 五、拷贝 ###

#### copy函数 ####

函数原型：

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

函数参数：

*  前两个参数是一对迭代器表示输入序列的范围
 *  第三个参数是一个指向需要拷贝的位置的迭代器

函数返回值：

*  指向拷贝的目标位置的迭代器

### 五、杂录 ###

#### 1.distance函数 ####

函数原型：

template<class InputIterator>
      typename iterator_traits<InputIterator>::difference_type
        distance (InputIterator first, InputIterator last);

函数参数：

*  两个参数都是同一个容器的迭代器

函数返回值：

*  返回参数中两个迭代器之间的距离，即第一个迭代器走几步能到达第二个迭代器

demo:

std::vector<int> ve{ 1, 2, 3, 4, 5};
    //下面这行代码相当于：ve.end() - ve.begin()
    std::cout << std::distance(ve.begin(), ve.end()) << std::endl;

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

#### 2.begin 和 end 函数 ####

函数原型：

template<class E> const E* begin (initializer_list<E> il) noexcept;

template<class E> const E* end (initializer_list<E> il) noexcept;

函数参数：

*  两个函数的参数都是容器 / 数组名

函数返回值：

*  begin函数返回指向容器 / 数组首元素的迭代器
 *  end函数返回指向容器 / 数组尾后元素的迭代器

demo：

int arr[] = { 1, 2, 3, 4, 5};
    int* pbeg = std::begin(arr); //pbeg指针指向数组arr的首元素
    int* pend = std::end(arr); //pend指针指向数组arr尾元素的下一位置（注意尾后指针不能解引用和递增）

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

#### 3.for\_each函数 ####

函数原型：

template <class InputIterator, class Function>
       Function for_each (InputIterator first, InputIterator last, Function f);

函数参数：

*  前者两个参数是一对迭代器，表示算法应用的范围
 *  第三个参数是一个可调用对象

函数返回值：

*  通常忽略

demo：

//需求：打印容器的每一个元素
    std::vector<int> ve{ 1, 2, 3, 4, 5, 6};
    //这里第三个参数传入的是一个Lambda表达式
    std::for_each(ve.begin(), ve.end(), [](const int n) {  std::cout << n << " "; });

#### 4.reverse函数 ####

函数原型：

template <class BidirectionalIterator>
      void reverse ( BidirectionalIterator first, BidirectionalIterator last);

函数参数：

*  参数是一对迭代器，表示算法应用的范围

demo：

std::vector<int> ve{ 1, 2, 3, 4, 5};
    //逆转传入的序列
    std::reverse(ve.begin(), ve.end());
    //遍历打印vector，for_each函数的作用见本文杂录模块
    std::for_each(ve.begin(), ve.end(), [](int n) {  std::cout << n << " "; });
    std::cout << std::endl;

[C]: https://blog.csdn.net/zanda_/article/details/89432048
[sort]: https://blog.csdn.net/zanda_/article/details/82902414
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3phbmRhXw_size_16_color_FFFFFF_t_70]: /images/20220216/a45540ccde74425298579566a1600acc.png