工欲善其事，必先利其器。刷题从掌握常用STL 容器开始。

0 概念

STL（Stand Template Library），标准模板库。将数据和操作分离，数据由容器进行管理，操作由算法进行，迭代器是两者自检的粘合剂，使任何算法和任何容器交互操作。
容器（Containers） + 迭代器（Iterators） + 算法（Algorithms）

  • 容器：管理某类对象的集合。
  • 迭代器：在一个对象集合的元素上进行遍历的动作。这个对象集合可以是容器，也可以是容器的一部分。

  • 算法：处理对象集合中的元素，比如：sort，search，copy，erase，find, insert等。

    1 容器

    1.1 STL容器分类 - 两类

  • 顺序（序列）容器：vector，list，deque, string，stack( 适配器类)，queue( 适配器类), priority_queues( 适配器类)

  • 关联容器：set，multiset，map，multimap，bitset，hash_set，hash_map，hash_multiset， hash_multimap

    1.2 vector

    ```c

    include

    // 1. 声明和定义 // 一维数组 vector vec; //声明一个int型向量 vector vec(5); //声明一个初始大小为5的int向量 vector vec(10, 1); //声明一个初始大小为10且值都是1的向量 vector vec(tmp); //声明并用tmp向量初始化vec向量 vector tmp(vec.begin(), vec.begin() + 3); //用向量vec的第0个到第2个值初始化tmp /* 将arr数组的元素用于初始化vec向量
    • 说明：当然不包括arr[4]元素，末尾指针都是指结束元素的下一个元素，
    • 这个主要是为了和vec.end()指针统一。 */ int arr[5] = {1, 2, 3, 4, 5};
      vector vec(arr, arr + 5); //将arr数组的元素用于初始化vec向量 vector vec(&arr[1], &arr[4]); //将arr[1]~arr[4]范围内的元素作为vec的初始值

// 二维数组 vector> vec(10, vector(9, 0)); // 初始化一个10行 9列的二维数组

// 2. 基本操作 vec.size(); // 元素个数 vec.empty(); // return: TURE or FALse vec.push_back(1); // 末尾插入 vec.pop_back(); // 末尾删除 vec.clear() // 清空所有元素 vec.erase(vec.begin() + 5); // 删除指定元素, 删除第六个元素，参数只能是迭代器

// 3. 遍历 vector::iterator it; for (it = vec.begin(); it != vec.end(); it++) { cout << *it << endl; it = vec.erase(it);// 正确，遍历删除 // vec.erase(it); // 错误 // vec.erase(it++); // 正确，erase()返回的是删除的迭代器的下一个 } for (int i = 0; i < vec.size(); i++) { cout << vec.at(i) << endl; // 会检查越界 cout << vec[i] << endl; // 不会检查是否越界 } // 4. 查找、删除 vector::iterator it = std::find(vec.begin(), vec.end(), value); if (it != vec.end) { // 找到 a.erase(it); } else { // 未找到 }

  2. <a name="6c01bda1"></a>
  3. ## 1.3 stack
  4. ```c
  5. // stack:先进后出，不支持遍历，没有迭代器
  6. template <class T, class Container = deque<T> > class stack;
  7. // T 指定存放的数据类型
  8. // Container 指定栈的内存实现方式，可以是vector,deque,list，默认是deque。
  9. stack<int> st;
  10. st.empty(); // 堆栈为空则返回真
  11. st.pop();   // 移除栈顶元素
  12. st.push(8);  // 在栈顶增加元素
  13. st.size();
  14. st.top();   // 返回栈顶元素，只能通过top还访问栈顶元素
  15. while (!st.empty) {
  16.     st.pop();
  17. }

1.3 string

  1. #include <cstring>
  2. // 数字转化为string
  3. string to_string (int val); //int,long,long long,unsinged, float.etc.
  4. // 字符串转化为int
  5. int stoi (const string&  str, size_t* idx = 0, int base = 10);  // idx，表示从 base:表示当前string代表是什么进制。
  7. string strNum = "123";
  8. string strNum1 = "A";
  9. int num = atoi(strNum.c_str()); // 只能识别10进制, num = 123
  10. long int num = strol(strNum2.c_str(), nullptr, 16); // 可以识别其他进制, num = 10
  11. int num = stoi(strNum); // num = 123
  13. strNum.size();
  14. strNum.find("1"); // 未找到，则返回std::string::npos或者-1
  15. string s="abcdefg";
  16. //s.substr(pos1,n)返回字符串位置为pos1后面的n个字符组成的串
  17. string s2=s.substr(1,5);//bcdef
  18. //s.substr(pos)//得到一个pos到结尾的串
  19. string s3=s.substr(4);//efg
  20. //如果输入的位置超过字符的长度，会抛出一个out_of_range的异常

1.4.1 map

  1. map<int, int> myMap; // map中的元素是自动按Key升序排序，所以不能对map用sort函数
  2. // 内部是红黑数，key有序
  4. // 0.赋值, 三种方式
  5. myMap.insert(pair<int, int>(1, 2));
  6. myMap.at(1) = 2;
  7. myMap[1] = 2;
  9. myMap.size();
  10. myMap.empty();
  12. // 1. 遍历
  13. map<int, int>::iterator iter;  
  14. for(iter = myMap.begin(); iter != myMap.end(); iter++) {
  15.     cout<<iter->first<<' '<<iter->second<<endl; 
  16.     if (iter->first == 2) {
  17.         myMap.erase(iter++); // 正确, 在执行erase之前，iter已经被加1了。erase会使得以前那个未被加一的iter失效，而加了一之后的新的iter是有效的。
  18.         // 与以下代码等价
  19.         /*
  20.         map<int, int>::iterator iterTemp = iter; 
  21.         ++iter; 
  22.         mapData.erase(iterTemp);
  23.         */
  24.         // iter = myMap.erase(iter); // 正确
  25.         // myMap.erase(iter); iter++; // 错误，iter已经失效，后续再++ 也是无效
  26.     } else {
  27.         iter++;
  28.     }
  29. } 
  30. // 2. 遍历删除
  31. for(iter = myMap.begin(); iter != myMap.end(); iter++) {
  32.     cout<<iter->first<<' '<<iter->second<<endl; 
  33. } 
  34. // 3. 查找
  35. iter = myMap.find(2);
  36. if(iter != myMap.end()) {
  37.    cout<<"Find, the value is "<<iter->second<<endl;   
  38. } else {
  39.     // 未找到
  40. }
  41. // 4. 删除
  42. // 如果要删除1,用迭代器删除  
  43. iter = myMap.find(1);  
  44. myMap.erase(iter);  
  46. // 如果要删除1，用关键字删除  
  47. int n = myMap.erase(1);// 如果删除了会返回1，否则返回0  
  48. myMap.clear(); // 删除所有元素
  49. // 遍历删除

1.4.2 unordered_map

  1. unordered_map<int, int> mp; // 无序的
  2. // 内部是哈希表， 无序
  3. // 使用方法参考map
  4. // 初始化
  5. unordered_map<int, unordered_set<char>> mp = {
  6.   {1, {}},
  7.   {2, {'a', 'b', 'c'}},
  8.   {3, {'d', 'e', 'f'}},
  9.   {4, {'g', 'h', 'i'}},
  10.   {5, {'j', 'k', 'l'}},
  11.   {6, {'m', 'n', 'o'}},
  12.   {7, {'p', 'q', 'r', 's'}},
  13.   {8, {'t', 'u', 'v'}},
  14.   {9, {'w', 'x', 'y', 'z'}},
  15. };

1.5.1 queue

  1. queue<int> myQueue; // 先进先出
  2. myQueue.size();
  3. myQueue.empty();
  4. myQueue.front(); // 第一个元素
  5. myQueue.back();  // 最后一个元素
  6. myQueue.push(1); // 从末尾添加元素
  7. myQueue.pop();   //清除第一个元素
  9. queue<pair<int, int>> que;
  10. que.emplace(1, 2); // 插入元素
  11. while (!que.empty) {
  12.      int a = que.front.first();
  13.     int b = que.front.second();
  14.     que.pop();
  15. }
  17. // 清空队列：1、遍历出圈；2、用空队列对象赋值；3、使用swap，最高效
  18. void clear(queue<int>& q)
  19. {
  20.     queue<int> empty;
  21.     swap(empty,q);
  22. }

1.5.2 priority_queue

  1. priority_queue<std::string> que; // 最高优先级先出， 默认大顶堆，降序
  2. // 优先队列，元素具有优先级，按照一定的规则有序，最高优先级的元素先删除
  4. // 降序队列，大顶堆
  5. priority_queue<int, vector<int>, less<int>> que;
  6. // 升序队列，小顶堆
  7. priority_queue<int, vector<int>, greater<int>> que;
  9. //greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了
  10. #include<function>
  11. template <typename T>
  12. struct less {
  13.     // 定义新的排序规则
  14.     bool operator()(const T &_lhs, const T &_rhs) const {
  15.         return _lhs < _rhs;
  16.     }
  17. };
  19. template <typename T>
  20. struct greater {
  21.     // 定义新的排序规则
  22.     bool operator()(const T &_lhs, const T &_rhs) const {
  23.         return _lhs > _rhs;
  24.     }
  25. };
  28. // 规则：pair的比较，先比较第一个元素，第一个相等比较第二个。
  29. priority_queue<pair<int, int> > a;
  30. pair<int, int> b(1, 2);
  31. pair<int, int> c(1, 3);
  32. pair<int, int> d(2, 5);
  33. a.push(d);
  34. a.push(c);
  35. a.push(b);
  36. while (!a.empty()) {
  37.     cout << a.top().first << ' ' << a.top().second << '\n';
  38.     a.pop();
  39. }
  40. 2 5
  41. 1 3
  42. 1 2
  44. // 用自定义类型做优先队列元素的例子
  45. // 方法1 : 运算符重载 <
  46. struct Node {
  47.     int x;
  48.     Node(int a) : x(a) {}
  49.     bool operator<(const Node& a) const
  50.     {
  51.         return x < a.x; // 大顶堆
  52.     }
  53. };
  54. // 方法2 : 重写仿函数, 以函数对象的方式实现
  55. struct cmp {
  56.     bool operator() (Node a, Node b)
  57.     {   // 返回true时，a的优先级低于b的优先级（a排在b的后面）
  58.         return a.x < b.x; // 大顶堆
  59.     }
  60. };
  61. int main()
  62. {
  63.     tmp1 a(1);
  64.     tmp1 b(2);
  65.     tmp1 c(3);
  66.     priority_queue<Node> d;
  67.     d.push(b);
  68.     d.push(c);
  69.     d.push(a);
  70.     while (!d.empty()) {
  71.         cout << d.top().x << " ";
  72.         d.pop();
  73.     }
  74.     // 输出 3 2 1
  75.     priority_queue<Node, vector<Node>, cmp> f;
  76.     f.push(b);
  77.     f.push(c);
  78.     f.push(a);
  79.     while (!f.empty()) {
  80.         cout << f.top().x << " ";
  81.         f.pop();
  82.     }
  83.     // 输出 3 2 1
  84. }

1.5.3 deque

双端队列，头尾都可以插入数据。

  1. deque<int> que;
  3. void push_front(const T& x); // 双端队列头部增加一个元素X
  4. void push_back(const T& x);     // 双端队列尾部增加一个元素x
  6. iterator insert(iterator it,const T& x);   // 双端队列中某一元素前增加一个元素x
  7. void insert(iterator it,int n,const T& x); // 双端队列中某一元素前增加n个相同的元素x
  8. void insert(iterator it,const_iterator first,const_iteratorlast); // 双端队列中某一元素前插入另一个相同类型向量的[forst,last)间的数据
  10. void pop_front(); // 删除双端队列中最前一个元素
  11. void pop_back();  // 删除双端队列中最后一个元素
  13. void clear(); // 清空双端队列中最后一个元素
  15. que.front(); // 头端元素
  16. que.back()
  18. bool empty() const; // 向量是否为空，若true,则向量中无元素

1.6.1 set

  1. set<int> mySet;
  2. // 1. 关联容器，存储同一数据类型的数据类型。内部使用红黑树
  3. // 2. set中每个元素的值是唯一的。
  4. // 3. 有序的。（插入相同的元素，只存一个）
  5. // 4. 每次insert之后，以前保存的iterator不会失效。
  6. mySet.find(2);
  7. mySet.erase(2); // 删除2，返回值1或者0，1:成功，0:删除元素不存在
  8. mySet.empty();
  9. mySet.clear(); // 清空
  10. mySet.insert(2); // 插入2
  11. mySet.count(2); // 值为2的个数，0 或者 1
  13. // 1. 遍历
  14. set<int>::iterator it;
  15. for (it = mySet.begin(); it != mySet.end(); ++it) {
  16.     // todo:
  17. }
  18. // 2. 遍历删除
  19. for (it = mySet.begin(); it != mySet.end()) {
  20.     if (*it == 2) {
  21.         it = mySet.erase(it); // 正确，遍历删除
  22.         // mySet.erase(it++); // 正确，erase()返回的是删除的迭代器的下一个
  23.     } else {
  24.         it++;
  25.     }
  26. }
  27. // 2. 查找
  28. if (mySet.find(2) != mySet.end()) {
  29.     // 找到
  30. } else {
  31.     // 未找到
  32. }

1.6.2 unordered_set

  1. unordered_set<int, int> mySet; // 无序的
  2. // 内部是哈希表， 无序
  3. // 使用方法参考set

1.7 list

双向链表

  1. #include <list>
  2. list<int> l(n); // 声明一个n个元素的列表，每个元素都是0
  3. list<int> l(n, m); // 声明一个n个元素的列表，每个元素都是m
  5. // 遍历
  6. list<int>::iterator iter
  7. for (iter = l.begin(); iter != l.end(); iter++) {
  8.     cout << *iter << endl;
  9. }
  10. // 排序
  11. l.sort(); // 升序
  12. l.sort(cmp); // 按照回调函数cmp的实现进行排序
  14. l.push_back(2); // 在list的末尾插入
  15. l.push_front(2); // 在list的头部插入
  16. l.empty(); // 判断list是否为NULL
  17. l.clear(); // 清空list中的所有元素
  18. l.front(); // 获得list容器中的头部元素
  19. l.back();  // 可以获得list容器的最后一个元素
  20. // 注意：当list元素为空时，这时候调用front()和back()不会报错。因此在编写程序时，最好先调用empty()函数判断list是否为空，再调用front()和back()函数。
  21. l.pop_back();  // 删掉尾部第一个元素
  22. l.pop_front(); // 删掉头部第一个元素
  23. // 注意：list必须不为空，如果当list为空的时候调用pop_back()和pop_front()会使程序崩掉。
  24. l.assign(n, val); // 将l中的所有元素替换成n个val元素
  26. // 在指定位置插入一个或多个元素
  27. a.insert(a.begin(), 100);  //在a的开始位置（即头部）插入100
  28. a.insert(a.begin(),2, 100);   //在a的开始位置插入2个100
  29. a.insert(a.begin(),b.begin(), b.end());//在a的开始位置插入b从开始到结束的所有位置的元素
  31. // 删除一个元素或一个区域的元素
  32. a.erase(a.begin());  //将a的第一个元素删除
  33. a.erase(a.begin(),a.end());  //将a的从begin()到end()之间的元素删除。
  35. // 从list中删除元素
  36. list<int>a{6,7,8,9,7,10};
  37. a.remove(7); // 删除a中所有值为7的元素，此时a中元素为6,8,9,10
  40. l.resize(n); // 将list的长度改为只容纳n个元素，超出的元素将被删除。如果n比list原来的长度长，那么默认超出的部分元素置为0。
  41. l.resize(n, m) // 也可以用resize(n, m)的方式将超出的部分赋值为m。
  43. swap() // 交换两个链表
  44. a.swap(b)和swap(a, b)，都可以完成a链表和b链表的交换
  45. 。
  46. reverse() // list的翻转
  47. reverse(l.begin(), l.end());
  49. merge() // 合并
  50. // a.merge(b) 调用结束后b变为空，a中元素包含原来a和b的元素。
  51. list<int>a{6,7,8,9};
  52. list<int>b{2, 1, 3, 6, 5};
  53. a.merge(b,greater<int>()); // a中元素变为：6,7,8,9,2,1,3,6,5
  55. list<int>a{6,7,8,9};
  56. list<int>b{2, 1, 3, 6, 5};
  57. a.merge(b); // a中元素变为：2,1,3,6,5,6,7,8,9

2 容器的异同

  • vector - 数组
  1. 封装了数组，使用连续内存存储。
  2. 快速查找；但内部插入，删除效率低。
  3. 随机访问方便，支持[]运算符和vector.at()。
  4. 只能在vector的最后进行push和pop，不能在vector的头进行push和pop。
  5. 节省空间。
  6. 当动态添加的数据超过vector默认分配的大小时要进行整体的重新分配、拷贝与释放
  • list - 双向链表
  1. 封装了链表，不支持[]运算符。
  2. 查找慢；内存插入，删除效率高。
  3. 在两端进行push和pop
  4. 占相对于verctor占用内存多
  5. 不能进行内部的随机访问，即不支持[ ]操作符和vector.at()
  • deque - 双端队列
  1. deque是在功能上合并了vector和list。
  2. 随机访问方便，即支持[ ]操作符和vector.at()
  3. 在内部方便的进行插入和删除操作
  4. 可在两端进行push、pop
  5. 占用内存多
  • vector、list、deque 使用区别：
  1. 如果你需要高效的随即存取，而不在乎插入和删除的效率，使用vector
  2. 如果你需要大量的插入和删除，而不关心随即存取，则应使用list
  3. 如果你需要随即存取，而且关心两端数据的插入和删除，则应使用deque
  • map
  1. 属于标准关联容器，使用高效的平衡检索二叉树：红黑树。即封装了二叉树，
  2. 插入键值的元素不允许重复，比较函数只对元素的键值进行比较，元素的各项数据可通过键值检索出来。
  3. key是有顺序的，默认从小到大。
  4. map中的元素是自动按Key升序排序，所以不能对map用sort函数；
  • set
  1. 关联容器，存储同一数据类型的数据类型。
  2. set中每个元素的值是唯一的。有序的。（插入相同的元素，只存一个）
  3. 每次insert之后，以前保存的iterator不会失效。
  • map和set的相同点：
  1. 都属于标准关联容器，使用高效的平衡检索二叉树：红黑树
  2. 插入删除效率高：不需要内存拷贝和内存移动，直接替换指向结点的指针。
  • map和set的区别：
  1. set值只含有key，map有key和value。
  • set和vector区别
  1. set不包含重复的数据
  • map和hash_map的区别：
  1. hash_map使用hash算法来加快查找过程，但需要更多的内存来存放这些hash桶元素。（空间换时间）

（1）为何map和set的插入删除效率比用其他序列容器高？
大部分人说，很简单，因为对于关联容器来说，不需要做内存拷贝和内存移动。说对了，确实如此。set容器内所有元素都是以节点的方式来存储，其节点结构和链表差不多，指向父节点和子节点。结构图可能如下：
　　A
　 /
　 B C
　/ \ /
D E F G
因此插入的时候只需要稍做变换，把节点的指针指向新的节点就可以了。删除的时候类似，稍做变换后把指向删除节点的指针指向其他节点也OK了。这里的一切操作就是指针换来换去，和内存移动没有关系。
（2）为何每次insert之后，以前保存的iterator不会失效？
iterator这里就相当于指向节点的指针，内存没有变，指向内存的指针怎么会失效呢(当然被删除的那个元素本身已经失效了)。相对于vector来说，每一次删除和插入，指针都有可能失效，调用push_back在尾部插入也是如此。因为为了保证内部数据的连续存放，iterator指向的那块内存在删除和插入过程中可能已经被其他内存覆盖或者内存已经被释放了。即使时push_back的时候，容器内部空间可能不够，需要一块新的更大的内存，只有把以前的内存释放，申请新的更大的内存，复制已有的数据元素到新的内存，最后把需要插入的元素放到最后，那么以前的内存指针自然就不可用了。特别时在和find等算法在一起使用的时候，牢记这个原则：不要使用过期的iterator。
（3）当数据元素增多时，set的插入和搜索速度变化如何？
如果你知道log2的关系你应该就彻底了解这个答案。在set中查找是使用二分查找，也就是说，如果有16个元素，最多需要比较4次就能找到结果，有32个元素，最多比较5次。那么有10000个呢？最多比较的次数为log10000，最多为14次，如果是20000个元素呢？最多不过15次。看见了吧，当数据量增大一倍的时候，搜索次数只不过多了1次，多了1/14的搜索时间而已。你明白这个道理后，就可以安心往里面放入元素了。