C++ Primer Plus 学习笔记第十六章算法其他库

Love The Way You Lie 2022-01-05 23:39 250阅读 0赞

总体设计

通过迭代器来标识要处理的数据区间和结果放置位置，有些算法函数接收参数

使用模板来提供泛型

使用迭代器来访问容器中的通用表示

STL算法分组:

非修改式序列操作:操作容器元素但不修改：find(),for\_each(）等

修改式序列操作：可以修改容器内容或排列顺序transform(), random\_shuffle() copy()等

排序和相关操作：集合操作。

通用数字运算：计算内部乘积，计算相邻差等函数

![20190624092713742.png][]

算法有两个版本

就地版和复制版

复制版的算法函数名要加\_copy结尾

就地版不用

\_if版本：根据函数应用于容器元素得到的结果来决定是否将容器中的值直接替换

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70][]

![20190624092934417.png][]

示例

#include <iostream>
    #include <string>
    #include <algorithm>
    
    int main()
    {
      using namespace std;
      string letters;
      cout << "Enter the letter grouping (quit to quit): ";
      while(cin >> letters && letters != "quit")
      {
        cout << "Permutations of " << letters << endl;
        sort(letters.begin(), letters.end());
        cout << letters << endl;
    // 全排序 吧容器的所有元素可能产生的排序组合（唯一的）全部迭代出来
        while(next_permutation(letters.begin(), letters.end()))
          cout <<letters << endl;
        cout << "Enter next sequence(quit to quit): ";
      }
      cout << "Done.\n";
      return 0;
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70 1][]

有时候 使用某个容器自由的成员函数来处理一些算法是更好地选择

比如list容器  自带remove() 再删除了特定的元素后会自动调整容器长度（list是链表类型的数据结构）

而非成员函数 remove()只能删除元素，无法自动调整容器长度

程序示例

#include <iostream>
    #include <list>
    #include <algorithm>
    void Show(int);
    const int LIM = 10;
    int main()
    {
      using namespace std;
      int ar[LIM] = {4, 5, 4, 2, 2, 3, 4, 8, 1, 4};
      list<int> la(ar, ar + LIM);
      list<int> lb(la);
      cout << "Original list contents:\n\t";
      for_each(la.begin(), la.end(), Show);
      cout << endl;
    // 使用了list的成员函数 删除值为4的元素
      la.remove(4);
      cout << "After using the remove() method:\n";
      cout << "la:\t";
      for_each(la.begin(), la.end(), Show);
      cout << endl;
      list<int>::iterator last;
    // 非成员函数remove() 在删除完相应的元素之后 会将未删除的元素相应的写到list对象的开头位置
    // 替换掉原来的值
    // 然后返回一个指向新的超尾值的迭代器
      last = remove(lb.begin(), lb.end(), 4);
      cout << "After using the remove(0 function:\n";
      cout << "lb:\t";
      for_each(lb.begin(), lb.end(), Show);
      cout << endl;
    // 删除从last开始到原list迭代器尾部的这部分元素。因为后面那几个元素已经没有存在的意义了
      lb.erase(last, lb.end());
      cout << "After using the erase(0 method:\n";
      cout << "lb:\t";
      for_each(lb.begin(), lb.end(), Show);
      cout << endl;
          
      return 0;
    }
    
    void Show(int v)
    {
      std::cout << v << ' ';
    }

运行结果

![20190624102332954.png][]

![20190624102442101.png][]

程序示例

#include <iostream>
    #include <string>
    #include <vector>
    #include <set>
    #include <map>
    #include <iterator>
    #include <algorithm>
    #include <cctype>
    using namespace std;
    
    char toLower(char ch) {return tolower(ch);}
    string & ToLower(string & st);
    void display(const string & s);
    
    int main()
    {
      vector<string> words;
      cout << "Enter words (enter quit to quit):\n";
      string input;
      while(cin >> input && input != "quit")
        words.push_back(input);
    
      cout << "You entered the following words:\n";
      for_each(words.begin(), words.end(), display);
      cout << endl;
    
      set<string> wordset;
    // set容器 自动排序去重
      transform(words.begin(), words.end(), insert_iterator<set<string>> (wordset, wordset.begin()), ToLower);
      cout << "\nAlphabetic list of words:\n";
      for_each(wordset.begin(), wordset.end(), display);
      cout << endl;
    
      map<string, int> wordmap;
      set<string>::iterator si;
    // 计算各个单词出现的次数
      for(si = wordset.begin(); si != wordset.end(); si++)
        wordmap[*si] = count(words.begin(), words.end(), *si);
      cout << "\nWord frequency:\n";
      for (si = wordset.begin(); si != wordset.end(); si++)
        cout << *si << ": " << wordmap[*si] << endl;
    
      return 0;
    }
    // 大写string转换成小写string（迭代每个字符）
    string & ToLower(string & st)
    {
      transform(st.begin(), st.end(), st.begin(), toLower);
      return st;
    }
    
    void display(const string & s)
    {
      cout << s << " ";
    }

程序结果

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70 2][]

![20190624111941366.png][]

其他库

comlex为复数使用的类模板

random提供随机数模板

vector valarray array容器的不同作用

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70 3][]

slice类 可以用作数组索引

#include <iostream>
    #include <valarray>
    #include <cstdlib>
    
    const int SIZE = 12;
    typedef std::valarray<int> vint;
    void show(const vint & v, int cols);
    int main()
    {
      using std::cout;
      using std::slice;
      vint valint(SIZE);
    
      int i;
      for (i = 0; i < SIZE; ++i)
        valint[i] = std::rand() % 10;
      cout << "Original array:\n";
      show(valint, 3);
    // slice格式： 起始下标， 数量， 跨距
      vint vcol(valint[slice(1, 4, 3)]);
      cout << "Second column:\n";
      show(vcol, 1);
      vint vrow(valint[slice(3, 3, 1)]);
      cout << "Second row:\n";
      show(vrow,3);
      valint[slice(2, 4, 3)] = 10;
      cout << "Set last column to 10:\n";
      show(valint, 3);
      cout << "Set first column to sum of next tow:\n";
      valint[slice(0, 4, 3)] = vint(valint[slice(1, 4, 3)])
                               + vint(valint[slice(2, 4, 3)]);
      show(valint, 3);
      return 0;
    }
    
    void show(const vint & v, int cols)
    {
      using std::cout;
      using std::endl;
    
      int lim = v.size();
      for (int i = 0; i < lim; ++i)
      {
        cout.width(3);
        cout << v[i];
        if (i % cols == cols - 1)
          cout << endl;
        else
          cout << ' ';
      }
      if (lim % cols != 0)
        cout << endl;
    }

程序结果

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70 4][]

initializer\_list 将STL容器初始化为一些列值：

std::vector<double> payments \{45.99, 39.23, 19.95, 89.01\};

![20190624134434199.png][]

总结：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70 5][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70 6][]

![20190624134606331.png][]

第十六章完结 卧槽终于完结了

[20190624092713742.png]: /images/20211228/abd7c417de0d410b92f222a21e9af6f1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70]: /images/20211228/ff7f44f874d04107af49f3100f7715aa.png
[20190624092934417.png]: /images/20211228/5ebcf128174b46d791f5041f56bbb37c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70 1]: /images/20211228/757224ed4a4247bb9fa82c67906cc8a4.png
[20190624102332954.png]: /images/20211228/dfda934033fd4f3d94925f86f30fdfaa.png
[20190624102442101.png]: /images/20211228/c08659d657204b1a9c12294b1736eb38.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70 2]: /images/20211228/abae8acf53ff412784cd06d4f6769e18.png
[20190624111941366.png]: /images/20211228/b3273129c349413da6ac43cd6734fbd1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70 3]: /images/20211228/258f8797640e46e4b6d0b68b2643e7a5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70 4]: /images/20211228/003de2987b824317a7a67793e781da3c.png
[20190624134434199.png]: /images/20211228/4a9fb11052054891ac6306b3ca7bebc5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70 5]: /images/20211228/e3af6ee20e76436d8f3a7713fbf901b0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70 6]: /images/20211228/7b6d12c2173a4a21b517782740fe0b6d.png
[20190624134606331.png]: /images/20211228/0e9f8352cd7c4741bff347d43c313c2c.png