不变序列算法

此类算法不会修改算法所作用的容器或对象，适用于所有容器。它们的时间复杂度都是O(n)的。
image.png

  • min 两个对象中较小的（可自定义比较器）
  • max 求两个对象中较大的（可自定义比较器）
  • min_element 求区间中的最小值（可自定义比较器）
  • max_element 求区间中的最大值（可自定义比较器）
  • for_each 对区间中的每个元素都做某种操作
  • count 计算区间中等于某值的元素个数
  • count_if 计算区间中符合某种条件的元素个数
  • find 再区间中查找等于某值的元素
  • find_if 在区间中查找符合某种条件的元素
  • search 在区间中查找另一个区间第一次出现的位置（可自定义比较器）
  • search_n 在区间中查找第一次出现等于某值的连续n个元素（可自定义比较器）
  • equal 判断两个区间是否相等（可自定义比较器）
  • mismatch 逐个比较两个区间的元素，返回第一次不相等的两个元素的位置（可自定义比较器）
  • lexicographical_compare 按字典序比较两个区间的大小（可自定义比较器）

image.png
image.png
image.png

  • min_element 和 max_element 都是从第一个元素逐个比较到最后

    1. #include <iostream>
    2. #include <algorithm>
    3. using namespace std;
    4. class A {
    5. public:
    6.   int n;
    7.   A(int i):n(i) {}
    8. };
    9. bool operator<(const A & a1, const A & a2) {
    10.    cout << "< called,a1=" << a1.n << " a2=" << a2.n << endl;
    11.   if(a1.n == 3 && a2.n == 7)
    12.       return true;
    13.   return false;
    14. }
    15. void main() {
    16.    A aa[] = {3, 5, 7, 2, 1};
    17.   cout << min_element(aa, aa+5)->n << endl;
    18.   cout << max_element(aa, aa+5)->n << endl;
    19. }
    20. /* 输出
    21. *    < called, a1=5 a2=3
    22. *    < called, a1=7 a2=3
    23. *    < called, a1=2 a2=3
    24. *    < called, a1=1 a2=3
    25. *  3
    26. *    < called, a1=3 a2=5
    27. *    < called, a1=3 a2=7
    28. *    < called, a1=7 a2=2
    29. *    < called, a1=7 a2=1
    30. *  7
    31. */

    image.png

    变值算法

    此类算法会修改源区间或目标区间元素的值。值被修改的那个区间，不可以是属于关联容器的

  • for_each 对区间中的每个元素都做某种操作

  • copy 复制一个区间到别处
  • copy_backward 赋值一个区间到别处，但目标区间是从后往前被修改的
  • transform 将一个区间的元素变形后拷贝到另一个区间
  • swap_ranges 交换两个区间内容
  • fill 用某个值填充区间
  • fill_n 用某个值替换区间中的n个元素
  • generate 用某个操作的结果填充区间
  • generate_n 用某个操作的结果替换区间中n个元素
  • replace 将区间中的某个值替换为另一个值
  • replace_if 将区间中符合某种条件的元素值替换成另一个值

image.png

  1. #include <vector>
  2. #include <iostream>
  3. #include <numeric>
  4. #include <list>
  5. #include <algorithm>
  6. #include <iterator>
  7. using namespace std;
  8. class CLessThan9 {
  9. public:
  10.     bool operator()(int n) {return n < 9;}
  11. };
  12. void outputSquare(int value) {cout << value * value << " ";}
  13. int calCube(int value) {return value * value * value;}
  14. void main() {
  15.      const int SIZE = 10;
  16.     int a1[] = {1,2,3,4,5,6,7,8,9,10};
  17.     int a2[] = {100, 2, 8,1,50,3,8,9,10,2};
  18.     vector<int> v(a1, a1 + SIZE);
  19.     ostream_iterator<int> output(cout, " ");
  20.     random_shuffle(v.begin(), v.end());
  21.     cout << endl << "1) ";
  22.     copy(v.begin(), v.end(), output);    // 输出 5 4 1 3 7 8 9 10 6 2
  23.     copy(a2, a2+SIZE, v.begin());     // copy的目标区间v必须有足够的区间，不然造成越界报错
  25.     cout << endl << "2) ";
  26.     cout << count(v.begin(), v.end(), 8);    // 输出 2
  28.     cout << endl << "3) ";    // 输出 6
  29.     cout << count_if(v.begin(), v.end(), ClessThan9()); // CLessThan9()是个对象
  31.     cout << endl << "4) ";    
  32.     cout << *(min_element(v.begin(), v.end())); // 输出 1
  33.     cout << endl << "5) ";
  34.     cout << *(max_element(v.begin(), v.end())); // 输出 100
  35.     cout << endl << "6) ";
  36.     cout << accumulate(v.begin(), v.end(), 0); // 求和
  38.     cout << endl << "7) ";
  39.     for_each(v.begin(), v.end(), outputSquare); // 输出 10000 4 ...
  40.     vector<int> cubes(SIZE);
  41.     transform(a1, a1+SIZE, cubes.begin(), calCube);
  42.     cout << endl << "8) ";
  43.     copy(cubes.begin(), cubes.end(), output); // 输出 1 8 27 64 ...
  44. }
  • copy 函数要有想象力

image.png
image.png

  • copy 的奇怪使用 ```cpp

    include

    include

    include

    include

    include

    using namespace std;

void main() { int a[4] = {1,2,3,4}; My_ostream_iterator oit(cout, ““); copy(a, a+4, oit); // 输出 1234 ofstream out_file(“test.txt”, ios::out); My_ostream_iterator oitf(out_file, “*”); copy(a, a+4, oitf); out_file.close(); }

  2. - 如何编写 `My_ostream_iterator` ?
  4. `copy` 的源代码：<br />![image.png](https://cdn.nlark.com/yuque/0/2020/png/805730/1589617850201-abdb2dd8-ece2-441b-88cc-efd3f2161e32.png#align=left&display=inline&height=305&margin=%5Bobject%20Object%5D&name=image.png&originHeight=610&originWidth=927&size=291936&status=done&style=none&width=463.5)<br />上面程序中调用语句 `copy(a, a+4, oit)` 实例化后得到的 `copy` 如下：
  5. ```cpp
  6. My_ostream_iterator<int> copy(int * _F, int * _L, My_ostream_iterator<int> _X) {
  7.      for(; _F != _L; ++_X, ++_F)
  8.         *_X = *_F;
  9.     return (_X);
  10. }
  1. 需要重载 ++ * = 三个运算符
    1. 因为赋值运算符 = 的存在，* 运算符需要返回引用
  2. 在 = 运算符中输出这个值就可以
    1. #include <iterator>
    2. using namespace std;
    3. class My_ostream_iterator: public iterator<output_iterator_tag, T> {
    4. private:
    5.  string sep; // 分隔符
    6.  ostream & os;
    7. public:
    8.  My_ostream_iterator(ostream & o, string s):sep(s), os(o){}
    9.  void operator ++(){}; // ++只需要定义就可以，不需要做什么
    10.  My_ostream_iterator & operator * () {return * this;}
    11.  My_ostream_iterator * operator = (const T & val) {
    12.      os << val << sep; return *this;
    13.  }
    14. };

    删除算法

    image.png
  • remove 删除区间中等于某个值的元素
  • unique 删除元素中连续相等的元素，只留下一个（可自定义比较器）

算法都是【STL】算法 - 图10
image.png
使用 unique 返回的迭代器减去 begin 就可以得到剩余的元素个数

  1. void main() {
  2.      int a[5] = {1,2,3,2,5};
  3.     int b[6] = {1,2,3,2,5,6};
  4.     ostream_iterator<int> oit(cout, ",");
  5.     int * p = remove(a, a+5, 2);
  6.     cout << "1) "; copy(a, a+5, oit); cout << endl; // 输出 1) 1,3,5,2,5
  7.     cout << "2) " << p - a << endl; // 输出 2) 3
  8.     vector<int> v(b, b+6);
  9.     remove(v.begin(), v.end(), 2);
  10.     cout << "3) "; copy(v.begin(), v.end(), oit); cout << endl; // 输出 3) 1,3,5,6,5,6
  11.     cout << "4) "; cout << v.size() << endl; // v中元素没有减少，输出 4) 6
  12. }

变序算法

image.png

  • reverse 颠倒区间的前后次序
  • next_permutation 将区间改为下一个排列（可自定义比较器）
    • 排列也是有大小顺序的
  • prev_permutation 将区间改为上一个排列（可自定义比较器）
  • random_shuffle 随机打乱区间内元素的顺序
  • partition 把区间内满足某个条件的元素移到前面，不满足的移到后面

image.png
image.pngimage.png

  • 字符串示例 ```cpp

    include

    include

    include

    using namespace std;

void main() { string str = “231”; char szStr[] = “324”; while(next_permutation(str.begin(), str.end())) { cout << str << endl;
} cout << ““ << endl; while(next_permutation(szStr, szStr+3)) { cout << szStr << endl;
} sort(str.begin(), str.end()); cout << ““ << endl; while(next_permutation(str.begin(), str.end())) { cout << str << endl;
} } /* 输出

  • 312
  • 321
  • 342
  • 423
  • 432
  • 132
  • 213
  • 231
  • 312
  • 321 */ ```
  • 整型示例 ```cpp

    include

    include

    include

    include

    include

    using namespace std;

int main() { int a[] = {8, 7, 10}; list ls(a, a + 3); while (next_permutation(ls.begin(), ls.end())) { list::iterator i; for (i = ls.begin(); i != ls.end(); ++i) cout << *i << “ “; cout << endl; }

  1. return 0;

}

  1. <a name="cBJu8"></a>
  2. # 排序算法
  3. ![image.png](https://cdn.nlark.com/yuque/0/2020/png/805730/1589636561724-9df5176f-caae-4a8e-924c-5a5bf3645373.png#align=left&display=inline&height=95&margin=%5Bobject%20Object%5D&name=image.png&originHeight=189&originWidth=1360&size=76623&status=done&style=none&width=680)
  5. - `sort` （可自定义比较器）
  6. - `stable_sort` 从小到大并保持想等元素之间的相对次序（可自定义比较器）
  7. - `partial_sort` 对区间部分排序，直到最小的n个元素就位（可自定义比较器）
  8. - `nth_element` 对区间部分排序，使得第n小的元素（n从0开始算）就位，而且比它小的都在它前面，比它大的都在它后面（可自定义比较器）
  9. - `make_heap` 使区间成为一个“堆”（可自定义比较器）
  10. - `push_heap` 将元素加入一个是“堆”的区间（可自定义比较器）
  11. - `pop_heap` 类似上
  12. - `sort_heap` 将一个“堆”区间进行排序，排序后该区间就是普通的有序区间了，不再是“堆”了
  14. ![image.png](https://cdn.nlark.com/yuque/0/2020/png/805730/1589636912796-208b5089-ca39-4adc-9cb7-67b90b6a9093.png#align=left&display=inline&height=298&margin=%5Bobject%20Object%5D&name=image.png&originHeight=595&originWidth=1309&size=134561&status=done&style=none&width=654.5)
  15. ```cpp
  16. #include <iostream>
  17. #include <algorithm>
  18. using namespace std;
  20. class MyLess
  21. {
  22. public:
  23.     bool operator()(int n1, int n2)
  24.     {
  25.         return (n1 % 10) < (n2 % 10);
  26.     }
  27. };
  29. int main()
  30. {
  31.     int a[] = {14, 2, 9, 222, 77};
  32.     sort(a, a + 5, MyLess());
  33.     int i;
  34.     for (i = 0; i < 5; ++i)
  35.         cout << a[i] << " ";
  36.     cout << endl;
  37.     sort(a, a + 5, greater<int>());
  38.     for (i = 0; i < 5; ++i)
  39.         cout << a[i] << " ";
  41.     return 0;
  42. }
  43. // 输出
  44. 2 222 14 77 9 
  45. 222 77 14 9 2

image.png

有序区间算法

image.png

  • binary_search 判断区间中是否包含某个元素
  • includes 判断是否一个区间中的每个元素，都在另一个区间中
  • lower_bound 查找最后一个不小于某值的元素的位置
  • upper_bound 查找第一个大于某值的元素的位置

  • equal_range 同时获取 lower_bound 和 upper_bound

  • merge 合并两个有序区间到第三个区间

  • set_union 将两个有序区间的并拷贝到第三个区间
  • set_intersection 将两个有序区间的交拷贝到第三个区间
  • set_difference 将两个有序区间的差拷贝到第三个区间
  • set_symmetric_difference 将两个有序区间的对称差拷贝到第三个区间

image.png

  1. #include <vector>
  2. #include <bitset>
  3. #include <iostream>
  4. #include <numeric>
  5. #include <list>
  6. #include <algorithm>
  7. #include <iterator>
  8. using namespace std;
  10. bool Greater10(int n)
  11. {
  12.     return n > 10;
  13. }
  14. int main()
  15. {
  16.     const int SIZE = 10;
  17.     int a1[] = {2, 8, 1, 50, 3, 100, 8, 9, 10, 2};
  18.     vector<int> v(a1, a1 + SIZE);
  19.     ostream_iterator<int> output(cout, " ");
  20.     vector<int>::iterator loc;
  21.     loc = find(v.begin(), v.end(), 10);
  22.     if (loc != v.end())
  23.     {
  24.         cout << endl
  25.              << "1) " << loc - v.begin();
  26.     }
  27.     loc = find_if(v.begin(), v.end(), Greater10);
  28.     if (loc != v.end())
  29.         cout << endl
  30.              << "2) " << loc - v.begin();
  32.     sort(v.begin(), v.end());
  33.     if (binary_search(v.begin(), v.end(), 9))
  34.         cout << "3) "
  35.              << "9 found" << endl;
  37.     return 0;
  38. }
  39. // 输出
  40. 1) 8
  41. 2) 3
  42. 3) 9 found

bitset

image.png
image.png
image.png
image.png