• CPP 核心编程9-STL

    STL初识

    2.1 STL的诞生

    • 长久以来，软件界一直希望建立一种可重复利用的东西
    • C++的面向对象和泛型编程思想，目的就是复用性的提升
    • 大多情况下，数据结构和算法都未能有一套标准,导致被迫从事大量重复工作
    • 为了建立数据结构和算法的一套标准,诞生了STL

    ​

    2.2 STL基本概念

    • STL(Standard Template Library,标准模板库)
    • STL 从广义上分为: 容器(container) 算法(algorithm) 迭代器(iterator)
    • 容器和算法之间通过迭代器进行无缝连接。
    • STL 几乎所有的代码都采用了模板类或者模板函数

    2.3 STL六大组件

    STL大体分为六大组件，分别是:容器、算法、迭代器、仿函数、适配器（配接器）、空间配置器

    1. 容器：各种数据结构，如vector、list、deque、set、map等,用来存放数据。
    2. 算法：各种常用的算法，如sort、find、copy、for_each等
    3. 迭代器：扮演了容器与算法之间的胶合剂。
    4. 仿函数：行为类似函数，可作为算法的某种策略。
    5. 适配器：一种用来修饰容器或者仿函数或迭代器接口的东西。
    6. 空间配置器：负责空间的配置与管理。

    2.4 STL中容器、算法、迭代器

    **容器：**置物之所也

    STL容器就是将运用最广泛的一些数据结构实现出来

    常用的数据结构：数组, 链表,树, 栈, 队列, 集合, 映射表 等

    这些容器分为序列式容器和关联式容器两种:

    ​ 序列式容器:强调值的排序，序列式容器中的每个元素均有固定的位置。 关联式容器:二叉树结构，各元素之间没有严格的物理上的顺序关系

    **算法：**问题之解法也

    有限的步骤，解决逻辑或数学上的问题，这一门学科我们叫做算法(Algorithms)

    算法分为:质变算法和非质变算法。

    质变算法：是指运算过程中会更改区间内的元素的内容。例如拷贝，替换，删除等等

    非质变算法：是指运算过程中不会更改区间内的元素内容，例如查找、计数、遍历、寻找极值等等

    **迭代器：**容器和算法之间粘合剂

    提供一种方法，使之能够依序寻访某个容器所含的各个元素，而又无需暴露该容器的内部表示方式。

    每个容器都有自己专属的迭代器

    迭代器使用非常类似于指针，初学阶段我们可以先理解迭代器为指针

    迭代器种类：

    种类

    功能

    支持运算

    输入迭代器

    对数据的只读访问

    只读，支持++、==、！=

    输出迭代器

    对数据的只写访问

    只写，支持++

    前向迭代器

    读写操作，并能向前推进迭代器

    读写，支持++、==、！=

    双向迭代器

    读写操作，并能向前和向后操作

    读写，支持++、--，

    随机访问迭代器

    读写操作，可以以跳跃的方式访问任意数据，功能最强的迭代器

    读写，支持++、--、[n]、-n、、>=

    常用的容器中迭代器种类为双向迭代器，和随机访问迭代器

    2.5 容器算法迭代器初识

    了解STL中容器、算法、迭代器概念之后，我们利用代码感受STL的魅力

    STL中最常用的容器为Vector，可以理解为数组，下面我们将学习如何向这个容器中插入数据、并遍历这个容器

    2.5.1 vector存放内置数据类型

    容器： vector

    算法： for_each

    迭代器： vector::iterator

    1. #include "iostream"
    2. #include "vector"
    3. #include "algorithm"
    4. using namespace std;
    5.  
    6. void myPrint(int val)
    7. {
    8.     cout << val << endl;
    9. }
    10. void test()
    11. {
    12.     //创建vector容器对象 并且通过模板参数指定容器中存放的数据类型
    13.     vector<int> v;
    14.     //向容器中放数据
    15.     v.push_back(1);
    16.     v.push_back(2);
    17.     v.push_back(3);
    18.     v.push_back(4);
    19.     v.push_back(5);
    20.     //每一个容器都有自己的迭代器，迭代器是用来遍历容器中的元素
    21.     // v.begin()返回迭代器，这个迭代器指向容器中第一个数据
    22.     // v.end()返回迭代器，这个迭代器指向容器元素的最后一个元素的下一个位置
    23.     // vector::iterator 拿到vector这种容器的迭代器类型
    24.     vector<int>::iterator iterBegin = v.begin();
    25.     vector<int>::iterator iterEnd = v.end();
    26.     //第一种遍历
    27.     while (iterBegin != iterEnd)
    28.     {
    29.         cout << *iterBegin << endl;
    30.         iterBegin++;
    31.     }
    32.     cout << endl;
    33.     //第二种遍历
    34.     for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
    35.     {
    36.         cout << *it << endl;
    37.     }
    38.     cout << endl;
    39.     //第三种遍历
    40.     //使用STL提供的遍历算法 头文件 algorithm
    41.     for_each(v.begin(), v.end(), myPrint);
    42. }
    43. int main()
    44. {
    45.     test();
    46.     return 0;
    47. }

    互换容器

    1. #include "iostream"
    2. #include "vector"
    3.  
    4. using namespace std;
    5.  
    6. //vector容器互换
    7. void printVector(vector<int> v) {
    8.     for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
    9.         cout << *it << " ";
    10.     }
    11.     cout << endl;
    12. }
    13.  
    14. //1 基本使用
    15. void test1() {
    16.     vector<int> v1;
    17.  
    18.     for (int i = 0; i < 10; i++) {
    19.         v1.push_back(i);
    20.     }
    21.     cout << "交换前：" << endl;
    22.     printVector(v1);
    23.  
    24.     vector<int> v2;
    25.     for (int j = 10; j > 0; j--) {
    26.         v2.push_back(j);
    27.     }
    28.     printVector(v2);
    29.  
    30.     cout << "交换后：" << endl;
    31.     v1.swap(v2);
    32.  
    33.     printVector(v1);
    34.     printVector(v2);
    35. }
    36. //2 实际用途：巧用swap可以收缩内存空间
    37.  
    38. void test2() {
    39.     vector<int> v;
    40.     for (int i = 0; i < 100000; i++) {
    41.         v.push_back(i);
    42.     }
    43.     cout << "v的容量为：" << v.capacity() << endl;
    44.     cout << "v的大小为：" << v.size() << endl;
    45.     v.resize(3);
    46.     cout << "resize后 v的容量为：" << v.capacity() << endl;
    47.     cout << "resize后 v的大小为：" << v.size() << endl;
    48.  
    49.     //巧用swap收缩内存空间  后面有图片解释
    50.     vector<int>(v).swap(v);
    51.     cout << "swap后 v的容量为：" << v.capacity() << endl;
    52.     cout << "swap后 v的大小为：" << v.size() << endl;
    53. }
    54.  
    55. int main() {
    56.     test1();
    57.     test2();
    58.     return 0;
    59. }
    60. 交换前：
    61. 0 1 2 3 4 5 6 7 8 9 
    62. 10 9 8 7 6 5 4 3 2 1 
    63. 交换后：
    64. 10 9 8 7 6 5 4 3 2 1 
    65. 0 1 2 3 4 5 6 7 8 9 
    66. v的容量为：131072
    67. v的大小为：100000
    68. resize后 v的容量为：131072
    69. resize后 v的大小为：3
    70. swap后 v的容量为：3
    71. swap后 v的大小为：3

    总结：swap可以使两个容器互换，可以达到实用的收缩内存效果

     

     

    上图解释：

    vector(v) 利用拷贝构造函数创建了一个匿名对象，新的对象没有名，x代表这个匿名对象，会按照v当前size来初始化匿名对象，所以匿名对象一开始size=3,capacity=3,只不过这是匿名对象。

    上面的匿名对象，系统会帮助我们回收，匿名对象有一个特点，当前行执行完，编译器发现它是匿名对象，马上回收。

    1. #include "iostream"
    2. #include "vector"
    3.  
    4. using namespace std;
    5.  
    6. //vector 容器 预留空间
    7. void test() {
    8.     vector<int> v;
    9.     int num = 0;//统计开辟次数
    10.     int *p = nullptr;
    11. //    for (int i = 0; i < 100000; i++) {
    12. //        v.push_back(i);
    13. //        if (p != &v[0]) {
    14. //            p = &v[0];
    15. //            num++;
    16. //        }
    17. //    }
    18.     int capacity = 0;
    19.     for (int i = 0; i < 100000; i++) {
    20.         v.push_back(i);
    21.         if (v.capacity() != capacity) {
    22.             capacity = v.capacity();
    23.             num++;
    24.         }
    25.     }
    26.     cout << "不用reserve时，动态扩展次数：" << num << endl;
    27.  
    28.     int num2 = 0;
    29.  
    30.     int capacity2 = 0;
    31.     vector<int> v2;
    32.     v2.reserve(100000);
    33.     for (int j = 0; j < 100000; j++) {
    34.         v2.push_back(j);
    35.         if (v2.capacity() != capacity) {
    36.             capacity = v2.capacity();
    37.             num2++;
    38.         }
    39.     }
    40.     cout << "使用reserve时，动态扩展次数：" << num2 << endl;
    41.  
    42. }
    43.  
    44. int main() {
    45.     test();
    46.     return 0;
    47. }
    48. 不用reserve时，动态扩展次数：18
    49. 使用reserve时，动态扩展次数：1
    1. #include "iostream"
    2. #include "deque"
    3. #include "vector"
    4. #include "algorithm"
    5.  
    6. using namespace std;
    7.  
    8. void printDeque(deque<int> &d) {
    9.     for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
    10.         cout << *it << " ";
    11.     }
    12.     cout << endl;
    13. }
    14.  
    15. //deque容器排序
    16. void test() {
    17.     deque<int> d;
    18.     d.push_back(10);
    19.     d.push_back(20);
    20.     d.push_back(30);
    21.     d.push_front(100);
    22.     d.push_front(200);
    23.     d.push_front(300);
    24.  
    25.     cout << "排序前：" << endl;
    26.     printDeque(d);
    27.  
    28.     //默认从小到大 升序
    29.     //对于支持随机访问的迭代器的容器，都可以利用sort算法直接对其进行排序
    30.     //vector容器也可以利用 sort进行排序
    31.     sort(d.begin(), d.end());
    32.  
    33.     cout << "排序后：" << endl;
    34.     printDeque(d);
    35. }
    36.  
    37. void test2() {
    38.     vector<int> v;
    39.     v.push_back(134);
    40.     v.push_back(54);
    41.     v.push_back(1432);
    42.     v.push_back(43);
    43.     v.push_back(1);
    44.     sort(v.begin(), v.end());
    45.     cout << "vector 排序后：" << endl;
    46.     for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
    47.         cout << *it << " ";
    48.     }
    49.     cout << endl;
    50. }
    51.  
    52. int main() {
    53.     test();
    54.     test2();
    55.     return 0;
    56. }
    57. 排序前：
    58. 300 200 100 10 20 30 
    59. 排序后：
    60. 10 20 30 100 200 300 
    61. vector 排序后：
    62. 1 43 54 134 1432

    总结：sort算法非常实用，使用时包含头文件algorithm

    1. #include "iostream"
    2. #include "vector"
    3. #include "deque"
    4. #include "algorithm"
    5.  
    6. using namespace std;
    7.  
    8. class Person {
    9. public:
    10.     Person(string name, int score) {
    11.         this->m_Name = name;
    12.         this->m_Score = score;
    13.     }
    14.  
    15.     int m_Score;
    16.     string m_Name;
    17. };
    18.  
    19. void createPerson(vector &vp) {
    20.     string nameSeed = "ABCDE";
    21.     for (int i = 0; i < 5; i++) {
    22.         Person p("选手" + to_string(i + 1), 0);
    23.         vp.push_back(p);
    24.     }
    25. }
    26.  
    27. void printInfo(vector &p) {
    28.     for (vector::iterator it = p.begin(); it != p.end(); it++) {
    29.         cout << "姓名：" << (*it).m_Name << " 平均分:" << (*it).m_Score << endl;
    30.     }
    31. }
    32.  
    33. void setScore(vector &p) {
    34.     srand((unsigned int) time(NULL));
    35.     for (vector::iterator it = p.begin(); it != p.end(); it++) {
    36.         deque<int> d;
    37.         cout << "选手：" << it->m_Name << "的打分：" << endl;
    38.         for (int i = 0; i < 10; i++) {
    39.             int score = rand() % 41 + 60;
    40.             d.push_back(score);
    41.             cout << score << " ";
    42.         }
    43.         cout << endl;
    44.         //排序
    45.         sort(d.begin(), d.end());
    46.         //去除最高和最低
    47.         d.pop_back();
    48.         d.pop_front();
    49.         int sum = 0;
    50.         for (deque<int>::const_iterator dit = d.begin(); dit != d.end(); dit++) {
    51.             sum += *dit;
    52.         }
    53.         it->m_Score = sum / d.size();
    54.     }
    55. }
    56.  
    57. //评委打分
    58. void test() {
    59. //1创建5名选手
    60.     vector v;
    61.     createPerson(v);
    62.     printInfo(v);
    63. //2 给5名选手打分
    64.     setScore(v);
    65.     printInfo(v);
    66.  
    67. //3 显示最后得分
    68. }
    69.  
    70. int main() {
    71.     test();
    72.     return 0;
    73. }
    74. 姓名：选手1 平均分:0
    75. 姓名：选手2 平均分:0
    76. 姓名：选手3 平均分:0
    77. 姓名：选手4 平均分:0
    78. 姓名：选手5 平均分:0
    79. 选手：选手1的打分：
    80. 83 96 87 61 93 65 87 77 71 73 
    81. 选手：选手2的打分：
    82. 83 70 77 97 63 88 79 62 70 70 
    83. 选手：选手3的打分：
    84. 94 100 64 68 83 96 81 92 85 73 
    85. 选手：选手4的打分：
    86. 65 78 89 62 73 67 71 96 90 62 
    87. 选手：选手5的打分：
    88. 63 78 93 99 84 81 83 88 62 91 
    89. 姓名：选手1 平均分:79
    90. 姓名：选手2 平均分:75
    91. 姓名：选手3 平均分:84
    92. 姓名：选手4 平均分:74
    93. 姓名：选手5 平均分:82

     

    1. #include "iostream"
    2. #include "stack"
    3.  
    4. using namespace std;
    5.  
    6. //栈
    7. //特点，先进后出
    8. void test() {
    9.     stack<int> s;
    10.     s.push(1);
    11.     s.push(2);
    12.     s.push(3);
    13.     s.push(4);
    14.     cout << "栈的大小：" << s.size() << endl;
    15.     while (!s.empty()) {
    16.         cout << s.top() << endl;
    17.         s.pop();
    18.     }
    19.     cout << "栈的大小：" << s.size() << endl;
    20. }
    21.  
    22. int main() {
    23.     test();
    24.     return 0;
    25. }
    1. #include "iostream"
    2. #include "queue"
    3.  
    4. using namespace std;
    5.  
    6. //queue容器
    7. void test() {
    8.     queue<int> q;
    9.     q.push(1);
    10.     q.push(2);
    11.     q.push(3);
    12.     q.push(4);
    13.     while (!q.empty()) {
    14.         cout << "front=" << q.front() << " back=" << q.back() << " q.size() =" << q.size() << endl;
    15.         q.pop();
    16.     }
    17. }
    18.  
    19. int main() {
    20.     test();
    21.     return 0;
    22. }
    23. front=1 back=4 q.size() =4
    24. front=2 back=4 q.size() =3
    25. front=3 back=4 q.size() =2
    26. front=4 back=4 q.size() =1

     

     

    1. #include "iostream"
    2. #include "list"
    3.  
    4. using namespace std;
    5.  
    6. void printList(const list<int> &l) {
    7.     for (auto i:l) {
    8.         cout << i << " ";
    9.     }
    10.     cout << endl;
    11. }
    12.  
    13. //list容器构造函数
    14. void test() {
    15.     list<int> l1;
    16.     l1.push_back(1);
    17.     l1.push_back(2);
    18.     l1.push_back(3);
    19.     l1.push_back(4);
    20.     printList(l1);
    21.  
    22.     //区间方式构造
    23.     list<int> l2(l1.begin(), l1.end());
    24.     printList(l2);
    25.     //拷贝构造
    26.     list<int> l3(l2);
    27.     printList(l3);
    28.     //n个element
    29.     list<int> l4(10, 1);
    30.     printList(l4);
    31. }
    32.  
    33. int main() {
    34.     test();
    35.     return 0;
    36. }
    37. 1 2 3 4 
    38. 1 2 3 4 
    39. 1 2 3 4 
    40. 1 1 1 1 1 1 1 1 1 1 
    1. #include "iostream"
    2. #include "list"
    3.  
    4. using namespace std;
    5.  
    6. void printList(const list<int> &l) {
    7.     for (list<int>::const_iterator it = l.begin(); it != l.end(); it++) {
    8.         cout << *it << " ";
    9.     }
    10.     cout << endl;
    11. }
    12.  
    13. //list赋值和交换
    14. void test() {
    15.     list<int> l1;
    16.     l1.push_back(1);
    17.     l1.push_back(2);
    18.     l1.push_back(3);
    19.     l1.push_back(4);
    20.     printList(l1);
    21.  
    22.     list<int> l2 = l1;
    23.     printList(l2);
    24.  
    25.     list<int> l3;
    26.     l3.assign(l2.begin(), l2.end());
    27.     printList(l3);
    28.  
    29.     list<int> l4;
    30.     l4.assign(10, 1);
    31.     printList(l4);
    32.  
    33.  
    34. }
    35.  
    36. //交换
    37. void test2() {
    38.     list<int> l1;
    39.     l1.push_back(1);
    40.     l1.push_back(2);
    41.     l1.push_back(3);
    42.     l1.push_back(4);
    43.  
    44.     list<int> l2;
    45.     l2.assign(10, 1);
    46.     cout << "交换前:" << endl;
    47.     printList(l1);
    48.     printList(l2);
    49.     l1.swap(l2);
    50.     cout << "交换后:" << endl;
    51.     printList(l1);
    52.     printList(l2);
    53. };
    54.  
    55. int main() {
    56.     test();
    57.     cout << endl;
    58.     test2();
    59.     return 0;
    60. }
    61. 1 2 3 4 
    62. 1 2 3 4 
    63. 1 2 3 4 
    64. 1 1 1 1 1 1 1 1 1 1 
    65.  
    66. 交换前:
    67. 1 2 3 4 
    68. 1 1 1 1 1 1 1 1 1 1 
    69. 交换后:
    70. 1 1 1 1 1 1 1 1 1 1 
    71. 1 2 3 4 
    1. #include "iostream"
    2. #include "list"
    3.  
    4. using namespace std;
    5.  
    6. void printList(const list<int> &l) {
    7.     for (list<int>::const_iterator it = l.begin(); it != l.end(); it++) {
    8.         cout << *it << " ";
    9.     }
    10.     cout << endl;
    11. }
    12.  
    13. //list 大小操作
    14. void test() {
    15.     list<int> l1;
    16.     l1.push_back(1);
    17.     l1.push_back(2);
    18.     l1.push_back(3);
    19.     l1.push_back(4);
    20.     printList(l1);
    21.     if (l1.empty()) {
    22.         cout << "l1为空" << endl;
    23.     } else {
    24.         cout << "l1不为空" << endl;
    25.         cout << "l1个数：" << l1.size() << endl;
    26.     }
    27.     //重新指定大小
    28.     l1.resize(2);
    29.     printList(l1);
    30.     l1.resize(4, 100);
    31.     printList(l1);
    32. }
    33.  
    34. int main() {
    35.     test();
    36.     return 0;
    37. }
    38. 1 2 3 4 
    39. l1不为空
    40. l1个数：4
    41. 1 2 
    42. 1 2 100 100
    1. #include "iostream"
    2. #include "list"
    3.  
    4. using namespace std;
    5.  
    6. void printList(list<int> &l) {
    7.     for (auto i:l) {
    8.         cout << i << " ";
    9.     }
    10.     cout << endl;
    11. }
    12.  
    13. //list 插入和删除
    14. void test() {
    15.     list<int> l1;
    16.     //尾插
    17.     l1.push_back(1);
    18.     l1.push_back(2);
    19.     l1.push_back(3);
    20.     l1.push_back(4);
    21.     //头插
    22.     l1.push_front(100);
    23.     l1.push_front(200);
    24.     l1.push_front(300);
    25.  
    26.     printList(l1);
    27.  
    28.     //尾删
    29.     l1.pop_back();
    30.     //头删
    31.     l1.pop_front();
    32.     printList(l1);
    33. //    200 100 1 2 3
    34.     l1.insert(l1.begin(), 1000);
    35. //    1000 200 100 1 2 3
    36.     printList(l1);
    37.     list<int>::iterator it = l1.begin();
    38.     l1.insert(++it, 2000);
    39. //    1000 2000 200 100 1 2 3
    40.     printList(l1);
    41.  
    42.     it = l1.begin();
    43.  
    44.     //删除
    45.     l1.erase(it);
    46.     //   2000 200 100 1 2 3
    47.     printList(l1);
    48.  
    49.     l1.erase(++it);
    50.     //   200 100 1 2 3
    51.     printList(l1);
    52.  
    53.     it = l1.begin();
    54.     l1.erase(++it);
    55.     //   200 1 2 3
    56.     printList(l1);
    57.  
    58.     //移除
    59.     l1.push_back(200);
    60.     l1.push_back(1);
    61. //    200 1 2 3 200 1
    62.     printList(l1);
    63.  
    64.  
    65.     l1.remove(1);
    66. //    200 2 3 200
    67.     printList(l1);
    68.  
    69.     //clear
    70.     l1.clear();
    71.     printList(l1);
    72.  
    73. }
    74.  
    75. int main() {
    76.     test();
    77.     return 0;
    78. }
    79. 300 200 100 1 2 3 4 
    80. 200 100 1 2 3 
    81. 1000 200 100 1 2 3 
    82. 1000 2000 200 100 1 2 3 
    83. 2000 200 100 1 2 3 
    84. 200 100 1 2 3 
    85. 200 1 2 3 
    86. 200 1 2 3 200 1 
    87. 200 2 3 200

    list 反转和排序

    **功能描述：**

    * 将容器中的元素反转，以及将容器中的数据进行排序

    **函数原型：**

    * `reverse();` //反转链表

    * `sort();` //链表排序

    1. #include "iostream"
    2. using namespace std;
    3. #include "list"
    4. #include "algorithm"
    5. void printList(const list<int> &l)
    6. {
    7.     for (list<int>::const_iterator it = l.begin(); it != l.end(); it++)
    8.     {
    9.         cout << *it << " ";
    10.     }
    11.     cout << endl;
    12. }
    13. bool myCompare(int a, int b)
    14. {
    15.     return a > b;
    16. }
    17. void test()
    18. {
    19.     list<int> l;
    20.     l.push_back(1);
    21.     l.push_back(2);
    22.     l.push_back(3);
    23.     l.push_back(4);
    24.     printList(l);
    25.     //反转
    26.     l.reverse();
    27.     printList(l);
    28.  
    29.     //排序
    30.     // sort(l.begin(), l.end()); list不支持随机访问,不能用sort,得用内置的排序算法
    31.     l.sort(); // 1 2 3 4  默认从小到大排序
    32.     printList(l);
    33.     l.sort(myCompare); //指定规则，从大到小
    34.     printList(l);
    35. }
    36. int main()
    37. {
    38.     test();
    39.     return 0;
    40. }

    总结：

    * 反转 --- reverse

    * 排序 --- sort （成员函数）

    3.7.8 排序案例

    案例描述：将Person自定义数据类型进行排序，Person中属性有姓名、年龄、身高

    排序规则：按照年龄进行升序，如果年龄相同按照身高进行降序

    1. #include "iostream"
    2. #include "list"
    3. using namespace std;
    4. //排序案例
    5. class Person
    6. {
    7. public:
    8.     Person(string name, int age, int height)
    9.     {
    10.         mage = age;
    11.         mname = name;
    12.         mheight = height;
    13.     }
    14.     string mname;
    15.     int mage;
    16.     int mheight;
    17. };
    18.  
    19. void printList(const list &l)
    20. {
    21.     for (list::const_iterator it = l.begin(); it != l.end(); it++)
    22.     {
    23.         cout << it->mname << " " << it->mage << " " << it->mheight << endl;
    24.     }
    25. }
    26. bool myCompare(const Person &p1, const Person &p2)
    27. {
    28.     if (p1.mage == p2.mage)
    29.     {
    30.         return p1.mheight > p2.mheight;
    31.     }
    32.     return p1.mage < p2.mage;
    33. }
    34. void test()
    35. {
    36.     Person p1("a", 33, 178);
    37.     Person p2("b", 45, 172);
    38.     Person p3("c", 22, 183);
    39.     Person p4("d", 22, 156);
    40.     Person p5("e", 22, 188);
    41.  
    42.     list l;
    43.     l.push_back(p1);
    44.     l.push_back(p2);
    45.     l.push_back(p3);
    46.     l.push_back(p4);
    47.     l.push_back(p5);
    48.  
    49.     cout << "before sort:" << endl;
    50.     printList(l);
    51.     l.sort(myCompare);
    52.     cout << "after sort:" << endl;
    53.     printList(l);
    54. }
    55. int main()
    56. {
    57.     test();
    58.     return 0;
    59. }
    60. before sort:
    61. a 33 178
    62. b 45 172
    63. c 22 183
    64. d 22 156
    65. e 22 188
    66. after sort:
    67. e 22 188
    68. c 22 183
    69. d 22 156
    70. a 33 178
    71. b 45 172

    总结：

    • 对于自定义数据类型，必须要指定排序规则，否则编译器不知道如何进行排序
    • 高级排序只是在排序规则上再进行一次逻辑规则制定，并不复杂

    3.8 set/ multiset 容器

    3.8.1 set基本概念

    简介：

    • 所有元素都会在插入时自动被排序

    本质：

    • set/multiset属于关联式容器，底层结构是用二叉树实现。

    set和multiset区别：

    • set不允许容器中有重复的元素
    • multiset允许容器中有重复的元素

    3.8.2 set构造和赋值

    功能描述：创建set容器以及赋值

    构造：

    • set st; //默认构造函数：
    • set(const set &st); //拷贝构造函数

    赋值：

    • set& operator=(const set &st); //重载等号操作符
    1. #include "iostream"
    2. #include "set"
    3. using namespace std;
    4. // set
    5. void printSet(const set<int> s)
    6. {
    7.     for (set<int>::iterator it = s.begin(); it != s.end(); it++)
    8.     {
    9.         cout << *it << " ";
    10.     }
    11.     cout << endl;
    12. }
    13.  
    14. void test()
    15. {
    16.     set<int> s;
    17.     s.insert(1);
    18.     s.insert(3);
    19.     s.insert(43);
    20.     s.insert(33);
    21.     s.insert(2);
    22.     printSet(s); //排好序的 默认是从小打到
    23.  
    24.     set<int> s2(s);
    25.     printSet(s2);
    26.  
    27.     set<int> s3;
    28.     s3 = s2;
    29.     printSet(s3);
    30. }
    31. int main()
    32. {
    33.     test();
    34.     return 0;
    35. }

    总结：

    • set容器插入数据时用insert
    • set容器插入数据的数据会自动排序

    3.8.3 set大小和交换

    功能描述：

    • 统计set容器大小以及交换set容器

    函数原型：

    • size(); //返回容器中元素的数目
    • empty(); //判断容器是否为空
    • swap(st); //交换两个集合容器
    1. #include "iostream"
    2. #include "set"
    3. using namespace std;
    4. // set
    5. void printSet(const set<int> s)
    6. {
    7.     for (set<int>::iterator it = s.begin(); it != s.end(); it++)
    8.     {
    9.         cout << *it << " ";
    10.     }
    11.     cout << endl;
    12. }
    13.  
    14. void test()
    15. {
    16.     set<int> s;
    17.     s.insert(1);
    18.     s.insert(3);
    19.     s.insert(43);
    20.     s.insert(33);
    21.     s.insert(2);
    22.     printSet(s); //排好序的 默认是从小打到
    23.  
    24.     set<int> s2(s);
    25.     printSet(s2);
    26.  
    27.     set<int> s3;
    28.     s3 = s2;
    29.     printSet(s3);
    30. }
    31. //大小
    32. void test2()
    33. {
    34.     set<int> s1;
    35.     s1.insert(1);
    36.     s1.insert(3);
    37.     s1.insert(2);
    38.     s1.insert(4);
    39.     if (s1.empty())
    40.     {
    41.         cout << "empty" << endl;
    42.     }
    43.     else
    44.     {
    45.         cout << "not empty,size is " << s1.size() << endl;
    46.     }
    47. }
    48. //交换
    49. void test3()
    50. {
    51.     set<int> s1;
    52.     s1.insert(1);
    53.     s1.insert(3);
    54.     s1.insert(2);
    55.     s1.insert(4);
    56.     set<int> s2;
    57.     s2.insert(100);
    58.     s2.insert(300);
    59.     s2.insert(200);
    60.     s2.insert(400);
    61.     cout << "before swap" << endl;
    62.     printSet(s1);
    63.     printSet(s2);
    64.     cout << endl;
    65.     cout << "after swap" << endl;
    66.     s1.swap(s2);
    67.     printSet(s1);
    68.     printSet(s2);
    69. }
    70. int main()
    71. {
    72.     test();
    73.     test2();
    74.     test3();
    75.     return 0;
    76. }

    总结：

    • 统计大小 --- size
    • 判断是否为空 --- empty
    • 交换容器 --- swap

    3.8.4 set插入和删除

    功能描述：

    • set容器进行插入数据和删除数据

    函数原型：

    • insert(elem); //在容器中插入元素。
    • clear(); //清除所有元素
    • erase(pos); //删除pos迭代器所指的元素，返回下一个元素的迭代器。
    • erase(beg, end); //删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。
    • erase(elem); //删除容器中值为elem的元素。
    1. #include "iostream"
    2. #include "set"
    3. using namespace std;
    4. // set
    5. void printSet(const set<int> s)
    6. {
    7.     for (set<int>::iterator it = s.begin(); it != s.end(); it++)
    8.     {
    9.         cout << *it << " ";
    10.     }
    11.     cout << endl;
    12. }
    13.  
    14. void test()
    15. {
    16.     set<int> s1;
    17.     //插入
    18.     s1.insert(10);
    19.     s1.insert(30);
    20.     s1.insert(20);
    21.     s1.insert(40);
    22.     printSet(s1);
    23.  
    24.     //删除
    25.     s1.erase(s1.begin());
    26.     printSet(s1);
    27.  
    28.     s1.erase(30);
    29.     printSet(s1);
    30.  
    31.     //清空
    32.     // s1.erase(s1.begin(), s1.end());//等同下面
    33.     s1.clear();
    34.     printSet(s1);
    35. }
    36. int main()
    37. {
    38.     test();
    39.     return 0;
    40. }

    总结：

    • 插入 --- insert
    • 删除 --- erase
    • 清空 --- clear

    3.8.5 set查找和统计

    功能描述：

    • 对set容器进行查找数据以及统计数据

    函数原型：

    • find(key); //查找key是否存在,若存在，返回该键的元素的迭代器；若不存在，返回set.end();
    • count(key); //统计key的元素个数
    1. #include "iostream"
    2. using namespace std;
    3. #include "set"
    4. void test()
    5. {
    6.     set<int> s;
    7.     s.insert(1);
    8.     s.insert(2);
    9.     s.insert(3);
    10.     s.insert(4);
    11.  
    12.     //查找
    13.     set<int>::iterator it = s.find(3);
    14.     if (it != s.end())
    15.     {
    16.         cout << "found" << endl;
    17.     }
    18.     else
    19.     {
    20.         cout << "not found" << endl;
    21.     }
    22.  
    23.     //统计
    24.     int num = s.count(2);
    25.     cout << "num:" << num << endl;
    26. }
    27. int main()
    28. {
    29.     test();
    30.     return 0;
    31. }

    总结：

    • 查找 --- find （返回的是迭代器）
    • 统计 --- count （对于set，结果为0或者1）

    3.8.6 set和multiset区别

    学习目标：

    • 掌握set和multiset的区别

    区别：

    • set不可以插入重复数据，而multiset可以
    • set插入数据的同时会返回插入结果，表示插入是否成功
    • multiset不会检测数据，因此可以插入重复数据
    1. #include "iostream"
    2. #include "set"
    3. using namespace std;
    4. // set 和 multiset 区别
    5. void test()
    6. {
    7.     set<int> s;
    8.     pairint>::iterator, bool> ret = s.insert(10);
    9.     if (ret.second)
    10.     {
    11.         cout << "fisrt insert ok" << endl;
    12.     }
    13.     else
    14.     {
    15.         cout << "fisrt insert not ok" << endl;
    16.     }
    17.     ret = s.insert(10);
    18.     if (ret.second)
    19.     {
    20.         cout << "second insert ok" << endl;
    21.     }
    22.     else
    23.     {
    24.         cout << "second insert not ok" << endl;
    25.     }
    26.  
    27.     // multiset
    28.     multiset<int> ms;
    29.     ms.insert(1);
    30.     ms.insert(2);
    31.     ms.insert(1);
    32.     for (multiset<int>::iterator it = ms.begin(); it != ms.end(); it++)
    33.     {
    34.         cout << *it << " ";
    35.     }
    36.     cout << endl;
    37. }
    38. int main()
    39. {
    40.     test();
    41.     return 0;
    42. }
    43. fisrt insert ok
    44. second insert not ok
    45. 1 1 2

    总结：

    • 如果不允许插入重复数据可以利用set
    • 如果需要插入重复数据利用multiset

    3.8.7 pair对组创建

    功能描述：

    • 成对出现的数据，利用对组可以返回两个数据

    两种创建方式：

    • pair p ( value1, value2 );
    • pair p = make_pair( value1, value2 );
    1. #include "iostream"
    2. using namespace std;
    3. //创建对组
    4. void test()
    5. {
    6.     pairint> p("aa", 1);
    7.     cout << p.first << "  " << p.second << endl;
    8.  
    9.     pair<int, char> p2 = make_pair(1, 'c');
    10.     cout << p2.first << "  " << p2.second << endl;
    11. }
    12. int main()
    13. {
    14.     test();
    15.     return 0;
    16. }
    17. aa  1
    18. 1  c

    总结：

    两种方式都可以创建对组，记住一种即可

    3.8.8 set容器排序

    学习目标：

    • set容器默认排序规则为从小到大，掌握如何改变排序规则

    主要技术点：

    • 利用仿函数，可以改变排序规则
    1. #include "iostream"
    2. #include "set"
    3. using namespace std;
    4. class MyCompare
    5. {
    6. public:
    7.     bool operator()(int a, int b)
    8.     {
    9.         return a > b;
    10.     }
    11. };
    12. void test()
    13. {
    14.     set<int> s1;
    15.     s1.insert(10);
    16.     s1.insert(40);
    17.     s1.insert(20);
    18.     s1.insert(30);
    19.     s1.insert(50);
    20.  
    21.     //默认从小到大
    22.     for (set<int>::iterator it = s1.begin(); it != s1.end(); it++)
    23.     {
    24.         cout << *it << " ";
    25.     }
    26.     cout << endl;
    27.  
    28.     //指定排序规则
    29.     set<int, MyCompare> s2;
    30.     s2.insert(10);
    31.     s2.insert(40);
    32.     s2.insert(20);
    33.     s2.insert(30);
    34.     s2.insert(50);
    35.  
    36.     for (set<int, MyCompare>::iterator it = s2.begin(); it != s2.end(); it++)
    37.     {
    38.         cout << *it << " ";
    39.     }
    40.     cout << endl;
    41. }
    42. int main()
    43. {
    44.     test();
    45.     return 0;
    46. }
    47. 10 20 30 40 50 
    48. 50 40 30 20 10

    总结：利用仿函数可以指定set容器的排序规则

    示例二 set存放自定义数据类型

    1. #include "iostream"
    2. #include "set"
    3. using namespace std;
    4. class Person
    5. {
    6. public:
    7.     Person(string name, int age)
    8.     {
    9.         m_Name = name;
    10.         m_Age = age;
    11.     }
    12.     string m_Name;
    13.     int m_Age;
    14. };
    15.  
    16. class comparePerson
    17. {
    18. public:
    19.     bool operator()(const Person &p1, const Person &p2)
    20.     {
    21.         return p1.m_Age > p2.m_Age;
    22.     }
    23. };
    24.  
    25. void test()
    26. {
    27.     set s;
    28.  
    29.     Person p1("fad", 23);
    30.     Person p2("sgdf", 27);
    31.     Person p3("hgf", 25);
    32.     Person p4("grwe", 21);
    33.  
    34.     s.insert(p1);
    35.     s.insert(p2);
    36.     s.insert(p3);
    37.     s.insert(p4);
    38.  
    39.     for (set::iterator it = s.begin(); it != s.end(); it++)
    40.     {
    41.         cout << "name: " << it->m_Name << " age: " << it->m_Age << endl;
    42.     }
    43. }
    44. int main()
    45. {
    46.     test();
    47.     return 0;
    48. }
    49. name: sgdf age: 27
    50. name: hgf age: 25
    51. name: fad age: 23
    52. name: grwe age: 21

    总结：

    对于自定义数据类型，set必须指定排序规则才可以插入数据

    3.9 map/ multimap容器

    3.9.1 map基本概念

    简介：

    • map中所有元素都是pair
    • pair中第一个元素为key（键值），起到索引作用，第二个元素为value（实值）
    • 所有元素都会根据元素的键值自动排序

    本质：

    • map/multimap属于关联式容器，底层结构是用二叉树实现。

    优点：

    • 可以根据key值快速找到value值

    map和multimap区别：

    • map不允许容器中有重复key值元素
    • multimap允许容器中有重复key值元素

    3.9.2 map构造和赋值

    功能描述：

    • 对map容器进行构造和赋值操作

    函数原型：

    构造：

    • map mp; //map默认构造函数:
    • map(const map &mp); //拷贝构造函数

    赋值：

    • map& operator=(const map &mp); //重载等号操作符
  • 相关阅读:
    算法复杂度分析中的渐近分析（基于输入大小）
    四向车立体库｜四向穿梭车AGV如何进行入库和出库？
    java计算机毕业设计网上拍卖系统MyBatis+系统+LW文档+源码+调试部署
    京东二面：高并发设计，都有哪些技术方案？
    蓝桥杯官网填空题（矩形切割）
    欢度中秋节！从零开始实现一个月饼检测器
    docke安装mysql以及主从搭建(并且指定数据生成路径)
    Vuex④(多组件共享数据、Vuex模块化+namespace)
    2、适配器模式
    水电站与数据可视化：洞察未来能源趋势的窗口
  • 原文地址：https://blog.csdn.net/wade1010/article/details/128210539