概念

有些人会疑惑，为什么会先讲数据结构，先讲STL

因为算法和数据结构是分不开的，在实现算法或者solving problem的时候，会需要不同姿势的存储数据，或者可以更好的存储数据，从而轻松解决问题。所以，先学STL，先学会用。

比如，栈，先学会用stack，以后有时间，再学习一维数组实现栈，再深入学习栈的工作原理。前期需要理解基本原理，理解什么时候需要用栈这种东西，然后能够面对问题的时候，把栈想出来，就是当前的学习目标。

A data structure is a way to store data in the memory of a computer. It is important to choose an appropriate data structure for a problem, because each data structure has its own advantages and disadvantages. The crucial question is: which operations are efficient in the chosen data structure?

我们来介绍一下C++ standard library。STL(Standard Template Library)，C++ 有一个库，里面有很多好东西。是后来出现的，以前不流行，现在很流行的东西。我们学习了很多数据结构，就是那些用来存储数据的东西。在解决问题的时候，我们会选择合适的数据结构来存储这个问题的数据，是因为每个数据结构有优点和缺点。数据结构的相关操作，有一些函数是写好可以直接用的。（记住，你以后还会面临时间复杂度问题，不是所有情况都适合用 STL ，但是前期 STL 非常香）（C++11 现在在 noip 中还不能使用）

It is a good idea to use the standard library whenever possible, because it will save a lot of time.

vector向量(dynamic arrays)

  1. vector<int> v;
  2. v.push_back(3); // [3]
  3. v.push_back(2); // [3,2]
  4. v.push_back(5); // [3,2,5]
  6. cout << v[0] << "\n"; // 3
  7. cout << v[1] << "\n"; // 2
  8. cout << v[2] << "\n"; // 5
  10. for (int i = 0; i < v.size(); i++) {
  11.     cout << v[i] << "\n";
  12. }
  14. vector<int> v;
  15. v.push_back(5);
  16. v.push_back(2);
  17. cout << v.back() << "\n"; // 2
  18. v.pop_back();
  19. cout << v.back() << "\n"; // 5
  21. // size 10, initial value 0
  22. vector<int> v(10);
  24. // size 10, initial value 5
  25. vector<int> v(10, 5);
  27. //vector的排序
  28. sort(v.begin(), v.end());
  29. reverse(v.begin(), v.end());
  32. int a[N];
  34. sort(a, a+n);
  35. reverse(a, a+n);
  37. // 倒序
  38. sort(a, a + n, greater<int>());
  1. vector中size函数的返回值是一个无符号类型，当size是0的时候，对其进行–1，会造成数字的越界溢出
  3. #include <bits/stdc++.h>
  5. using namespace std;
  7. vector<int> A;
  9. int main(){
  10.     cout << A.size() << ' ' << A.size() - 1 << '\n';
  12.     return 0;
  13. }
  15. // 输出 0 18446744073709551615
  18. #include <bits/stdc++.h>
  20. using namespace std;
  22. vector<int> A;
  24. int main(){
  25.     cout << A.size() << ' ' << (int)A.size() - 1 << '\n';
  27.     return 0;
  28. }
  30. // 输出 0 -1
  32. 【注意】for(int i = 0; i < (int)A.size(); i++){} 要写一个强制取整
  1. // 去重
  3. #include <bits/stdc++.h>
  5. using namespace std; 
  7. vector<int> A;
  8. int n;
  10. void print(){
  11.     for (auto x : A) printf("%d ", x);
  12.     puts("");
  13. }
  15. int main()
  16. {
  17.     cin >> n;
  18.     for (int i = 0; i < n; i++){
  19.         int x;  cin >> x;
  20.         A.push_back(x);           // 3 2 1 2 1
  22.     }
  24.     sort(A.begin(), A.end());
  25.     print();                      // 1 1 2 2 3
  27.     vector<int>::iterator it = unique(A.begin(), A.end());
  28.     print();                      // 1 2 3 2 3 
  30.     A.erase(it, A.end());         // 1 2 3
  31.     print();
  33.     return 0;
  34. }

list双向链表

  1. #include <list>
  3. #include <bits/stdc++.h>
  5. using namespace std;
  7. list<int> lst;
  9. void print(){
  10.     for (auto x : lst) cout << x << ' ';
  11.     puts("");
  12. }
  14. int main(){
  15.     lst.push_back(1);
  16.     lst.push_back(2);
  17.     lst.push_back(3);
  18.     print();                  //1 2 3 
  20.     lst.push_front(4);
  21.     lst.push_front(5);
  22.     lst.push_front(6);
  23.     print();                  //6 5 4 1 2 3 
  25.     lst.pop_back();
  26.     print();                  //6 5 4 1 2
  28.     lst.pop_front();
  29.     print();                  //5 4 1 2 
  31.     return 0;
  32. }
  34. /*
  35. 输出
  36. 1 2 3 
  37. 6 5 4 1 2 3 
  38. 6 5 4 1 2 
  39. 5 4 1 2 
  40. */
  1. list<int>lst1;           //创建空list
  2. list<int> lst2(5);       //创建含有5个元素的list
  3. list<int>lst3(3,2);      //创建含有3个元素的list
  4. list<int>lst4(lst2);     //使用lst2初始化lst4
  5. list<int>lst5(lst2.begin(),lst2.end());  //同lst4
  7. Lst1.assign() 给list赋值
  8. Lst1.back() 返回最后一个元素
  9. Lst1.begin() 返回指向第一个元素的迭代器
  10. Lst1.clear() 删除所有元素
  11. Lst1.empty() 如果list是空的则返回true
  12. Lst1.end() 返回末尾的迭代器
  13. Lst1.erase() 删除一个元素
  14. Lst1.front() 返回第一个元素
  15. Lst1.get_allocator() 返回list的配置器
  16. Lst1.insert() 插入一个元素到list中
  17. Lst1.max_size() 返回list能容纳的最大元素数量
  18. Lst1.merge() 合并两个list
  19. Lst1.pop_back() 删除最后一个元素
  20. Lst1.pop_front() 删除第一个元素
  21. Lst1.push_back() 在list的末尾添加一个元素
  22. Lst1.push_front() 在list的头部添加一个元素
  23. Lst1.rbegin() 返回指向第一个元素的逆向迭代器
  24. Lst1.remove() 从list删除元素
  25. Lst1.remove_if() 按指定条件删除元素
  26. Lst1.rend() 指向list末尾的逆向迭代器
  27. Lst1.resize() 改变list的大小
  28. Lst1.reverse() 把list的元素倒转
  29. Lst1.size() 返回list中的元素个数
  30. Lst1.sort() 给list排序
  31. Lst1.splice() 合并两个list
  32. Lst1.swap() 交换两个list
  33. Lst1.unique() 删除list中重复的元素

string类

image.png
The string structure is also a dynamic array that can be used almost like a vector. string类 类型也是一个动态数组，用起来很像 vector ，经常用的s.substr(pos, length) int pos = s.find('c')，还有+用来拼接两个 string

  1. string a = "hatti";
  2. string b = a+a;
  3. cout << b << "\n"; // hattihatti
  4. b[5] = ’v’;
  5. cout << b << "\n"; // hattivatti
  6. string c = b.substr(3,4);
  7. cout << c << "\n"; // tiva
  9. string c = b.substr(3);
  10. cout << c << "\n"; // 这个是什么呢，请实践一下
  12. int pos;
  13. pos = b.find('a');
  14. cout << pos << '\n';  //实践一下
  16. pos = b.find('x');
  17. cout << pos << '\n';  //实践一下
  19. // c_str()
  20. string s;
  21. cin >> s;
  23. char * cstr = new char [s.length()+1];
  24. strcpy(cstr, s.c_str());
  26. printf("%s\n", cstr);
  1. //Note: 我们需要用到不同的头文件
  2. #include <vector>
  3. #include <set>
  4. #include <queue>
  6. //总之，可以用万能头
  7. //无特殊情况，后面的练习过程中，你可以一直使用万能头了
  8. //前提是，你已经了解了不同头文件的作用。比赛的时候认真看比赛要求是否ban掉万能头
  9. //在一些Unix评测环境，万能头不一定好用，不稳定
  10. #include <bits/stdc++.h>

set、multiset

A set is a data structure that maintains a collection of elements. The basic operations of sets are element insertion, search and removal.The benefit of the set structure is that it maintains the order of the elements.

vector 如果要排序，需要 sort 一下； set 就会默认是有序的

  1. set<int> s;
  2. s.insert(3);
  3. s.insert(2);
  4. s.insert(5);
  5. cout << s.count(3) << "\n"; // 1
  6. cout << s.count(4) << "\n"; // 0
  7. s.erase(3);
  8. s.insert(4);
  9. cout << s.count(3) << "\n"; // 0
  10. cout << s.count(4) << "\n"; // 1
  1. set<int> s = {2,5,6,8};
  2. cout << s.size() << "\n"; // 4
  3. for (auto x : s) {        //C++11 用法
  4.     cout << x << "\n";
  5. }
  1. //set里面，每个元素只存一个
  2. set<int> s;
  3. s.insert(5);
  4. s.insert(5);
  5. s.insert(5);
  6. cout << s.count(5) << "\n"; // 1
  1. //multiset里面，每个元素可以存多个
  2. multiset<int> s;
  3. s.insert(5);
  4. s.insert(5);
  5. s.insert(5);
  6. cout << s.count(5) << "\n"; // 3
  1. //把5这个元素全删了
  2. s.erase(5);
  3. cout << s.count(5) << "\n"; // 0
  4. //只删掉一个5元素
  5. s.erase(s.find(5));
  6. cout << s.count(5) << "\n"; // 2

map哈希

A map is a generalized array that consists of key-value-pairs. While the keys in an ordinary array are always the consecutive integers 0, 1 ,... , n−1, where n is the size of the array, the keys in a map can be of any data type and they do not have to be consecutive values.

  1. map<string,int> m;
  2. m["monkey"] = 4;
  3. m["banana"] = 3;
  4. m["harpsichord"] = 9;
  5. cout << m["banana"] << "\n"; // 3

If the value of a key is requested but the map does not contain it, the key is automatically added to the map with a default value.For example, in the following code, the key ”aybabtu” with value 0 is added to the map.

  1. map<string,int> m;
  2. cout << m["aybabtu"] << "\n"; // 0

所以，上述这个操作，不是很好，当查询次数很多，会造成空间问题（我在 CF 现场比赛中，真实遇见…，当时还不熟练这个操作）

  1. //判断是否存在，用count
  2. if (m.count("aybabtu")) {
  3.     // key exists
  4. }
  6. //C++11的遍历，我们自己写，要用interator
  7. for (auto x : m) {
  8.     cout << x.first << " " << x.second << "\n";
  9. }
  1. //所以，我想问，能不能 map<int, string>

unordered_map

unordered_map存储元素时是没有顺序的，只是根据key的哈希值，将元素存在指定位置，所以根据key查找单个value时非常高效，平均可以在常数时间内完成。

与map的区别

  • 运行效率方面：unordered_map最高，而map效率较低但 提供了稳定效率和有序的序列。
  • 占用内存方面：map内存占用略低，unordered_map内存占用略高,而且是线性成比例的。

内部实现机理

map： map内部实现了一个红黑树，该结构具有自动排序的功能，因此map内部的所有元素都是有序的，红黑树的每一个节点都代表着map的一个元素，因此，对于map进行的查找，删除，添加等一系列的操作都相当于是对红黑树进行这样的操作，故红黑树的效率决定了map的效率。
unordered_map: unordered_map内部实现了一个哈希表，因此其元素的排列顺序是杂乱的，无序的

map优缺点

优点：有序性，这是map结构最大的优点，其元素的有序性在很多应用中都会简化很多的操作。红黑树，内部实现一个红黑书使得map的很多操作在lgn的时间复杂度下就可以实现，因此效率非常的高。
缺点：空间占用率高，因为map内部实现了红黑树，虽然提高了运行效率，但是因为每一个节点都需要额外保存父节点，孩子节点以及红/黑性质，使得每一个节点都占用大量的空间
适用处：对于那些有顺序要求的问题，用map会更高效一些。
[

](https://blog.csdn.net/zou_albert/article/details/106983268)

unordered_map优缺点

优点：内部实现了哈希表，因此其查找速度是常量级别的。
缺点：哈希表的建立比较耗费时间
适用处：对于查找问题，unordered_map会更加高效一些，因此遇到查找问题，常会考虑一下用unordered_map

  1. =================迭代器=========================
  2. begin 　　返回指向容器起始位置的迭代器（iterator）
  3. end 　　 返回指向容器末尾位置的迭代器
  4. cbegin　 返回指向容器起始位置的常迭代器（const_iterator）
  5. cend 　　 返回指向容器末尾位置的常迭代器
  6. =================Capacity================
  7. size 　　 返回有效元素个数
  8. max_size 返回 unordered_map 支持的最大元素个数
  9. empty 判断是否为空
  10. =================元素访问=================
  11. operator[] 　　 访问元素
  12. at 　　 　　　　访问元素
  13. =================元素修改=================
  14. insert 　　插入元素
  15. erase　　 删除元素
  16. swap 　　 交换内容
  17. clear　　 清空内容
  18. emplace 　构造及插入一个元素
  19. emplace_hint 按提示构造及插入一个元素
  20. ================操作=========================
  21. find 　　　　　　通过给定主键查找元素,没找到：返回unordered_map::end
  22. count 　　　　　返回匹配给定主键的元素的个数
  23. equal_range 　　返回值匹配给定搜索值的元素组成的范围

pair(typedef pair PII)

image.png

  1. pair<int, int> A, B;
  2. A = make_pair(1, 2);    //比赛中可以用这种写法
  4. //经常的，会这样去用
  5. #include <bits/stdc++.h>
  6. using namespace std;
  8. typedef pair<int, int> PII;
  10. const int N = 110;
  12. PII a[N];
  14. int main()
  15. {
  16.     int n;
  17.     cin >> n;
  18.     for (int i = 0; i < n; i++) cin >> a[i].first >> a[i].second;
  20.     return 0;
  21. }

stack栈

A stack is a data structure that provides two O(1) time operations: adding an element to the top, and removing an element from the top. It is only possible to access the top element of a stack.

  1. stack<int> s;
  2. s.push(3);
  3. s.push(2);
  4. s.push(5);
  5. cout << s.top(); // 5
  6. s.pop();
  7. cout << s.top(); // 2

queue队列

A queue also provides two O(1) time operations: adding an element to the end of the queue, and removing the first element in the queue. It is only possible to access the first and last element of a queue.

  1. queue<int> q;
  2. q.push(3);
  3. q.push(2);
  4. q.push(5);
  5. cout << q.front(); // 3
  6. q.pop();
  7. cout << q.front(); // 2

priority_queue优先队列

A priority queue maintains a set of elements. The supported operations are insertion and, depending on the type of the queue, retrieval and removal of either the minimum or maximum element. Insertion and removal take O(log n) time, and retrieval takes O(1) time.

  1. priority_queue<int> q;
  2. q.push(3);
  3. q.push(5);
  4. q.push(7);
  5. q.push(2);
  6. cout << q.top() << "\n"; // 7
  7. q.pop();
  8. cout << q.top() << "\n"; // 5
  9. q.pop();
  10. q.push(6);
  11. cout << q.top() << "\n"; // 6
  12. q.pop();

默认是大根堆，如果要写小根堆，就是push x进去的时候，push成-x，取出使用的时候，加个负号再使用。实现大根堆，还有一个方法，如下：

  1. priority_queue<int,vector<int>,greater<int> >q;//这样就可以实现小根堆了

参考：https://www.cnblogs.com/zwfymqz/p/7800654.html, 如何实现自定义结构体的排序

struct自定义结构体

自定义结构体，是为了解决一些场景：

  1. 三国英雄，有红，有蓝，有精力值
  2. 班级同学，有语文成绩、数学成绩、英语成绩、总分和学号

对这些情况进行表达，或者，对班级同学按多关键字排序(总分优先，语文优先、数学优先、英语优先、学号优先)，就需要用到结构体存储数据，或者对结构体进行排序。

  1. // 重载小于符号，实现多关键字排序
  2. // eg1
  3. struct node
  4. {
  5.     int s, w;
  7.     bool operator< (const node &W)const
  8.     {
  9.         return w > W.w;
  10.     }
  11. }a[N];
  14. // eg2
  15. struct Node
  16. {
  17.     int x, y;
  19.     bool operator< (const Node& W)const
  20.     {
  21.         if (x != W.x) return x > W.x;
  22.         else return y > W.y;
  23.     }
  24. }a[N], b[N];  //a存机器，b存任务
  27. // 用cmp函数来处理自定义排序
  28. struct Film
  29. {
  30.     int l, r;
  31. }a[N];
  33. bool cmp(Film &a, Film &b)
  34. {
  35.     return a.r < b.r;
  36. }
  38. sort(a, a + n, cmp);
  1. // 构造函数，就是方便后面的出事后
  2. struct node
  3. {
  4.     int x;
  6.     node(){}
  8.     node(int a)
  9.     {
  10.         x = a;
  11.     }
  13.     bool operator< (const node& W)const
  14.     {
  15.         return pos[x] > pos[W.x];  //按权值，进行小根堆
  16.     }
  17. };
  19. // 调用
  20.     priority_queue<node> q;
  21.     for (int i = 1; i <= n; i++)
  22.         if (!deg[i]) q.push(node(i)); //处理叶子结点  这里就可以直接node(i)
  24. // 要么，就得这样
  25.     priority_queue<node> q;
  26.     for (int i = 1; i <= n; i++)
  27.         if (!deg[i]){
  28.             node t;
  29.             t.a = i;
  30.             q.push(t);
  31.         }

iterator迭代器

Many functions in the C++ standard library operate with iterators. An iterator is a variable that points to an element in a data structure. 用 iterator 来写遍历，遍历不同的容器，都可以用 iterator，但是只有部分容器支持下标访问，比如 vector。

  1. //set的遍历
  2. set<int>::iterator it;
  3. for (it = s.begin(); it != s.end(); it++) {
  4.     cout << *it << "\n";
  5. }
  7. //输出最大元素
  8. it = s.end(); it--;
  9. cout << *it << "\n";
  11. //查找元素是否存在
  12. it = s.find(x);
  13. if (it == s.end()) {
  14.     //x is not found
  15. }
  1. //示例
  2. //set<pair<int, int> > 
  3. //不能写成set<pair<int, int>>，这也是不建议用#define宏定义的原因
  4. #include <bits/stdc++.h>
  6. using namespace std;
  8. typedef pair<int, int> PII;
  10. set<PII> s;
  12. int main()
  13. {
  14.     s.insert(make_pair(3, 5));
  15.     s.insert(make_pair(7, 9));
  16.     s.insert(make_pair(11, 13));
  18.     set<PII>::iterator it;
  19.     for (it = s.begin(); it != s.end(); it++)
  20.         printf("%d %d\n", (*it).first, (*it).second);
  22.     return 0;
  23. }

bitset

A bitset is an array whose each value is either 0 or 1. For example, the following code creates a bitset that contains 10 elements:

  1. bitset<10> s;
  2. s[1] = 1;
  3. s[3] = 1;
  4. s[4] = 1;
  5. s[7] = 1;
  6. cout << s[4] << "\n"; // 1
  7. cout << s[5] << "\n"; // 0

The benefit of using bitsets is that they require less memory than ordinary arrays, because each element in a bitset only uses one bit of memory. For example, if n bits are stored in an int array, 32n bits of memory will be used, but a corresponding bitset only requires n bits of memory. In addition, the values of a bitset can be efficiently manipulated using bit operators, which makes it possible to optimize algorithms using bit sets.

  1. bitset<10> s(string("0010011010")); // from right to left
  2. cout << s[4] << "\n"; // 1
  3. cout << s[5] << "\n"; // 0
  5. bitset<10> s(string("0010011010"));
  6. cout << s.count() << "\n"; // 4
  8. bitset<10> a(string("0010110110"));
  9. bitset<10> b(string("1011011000"));
  10. cout << (a&b) << "\n"; // 0010010000
  11. cout << (a|b) << "\n"; // 1011111110
  12. cout << (a^b) << "\n"; // 1001101110
  1. foo.size() 返回大小（位数）
  2. foo.count() 返回1的个数
  3. foo.any() 返回是否有1
  4. foo.none() 返回是否没有1
  5. foo.set() 全都变成1
  6. foo.set(p) 将第p + 1位变成1
  7. foo.set(p, x) 将第p + 1位变成x
  8. foo.reset() 全都变成0
  9. foo.reset(p) 将第p + 1位变成0
  10. foo.flip() 全都取反
  11. foo.flip(p) 将第p + 1位取反
  12. foo.to_ulong() 返回它转换为unsigned long的结果，如果超出范围则报错
  13. foo.to_ullong() 返回它转换为unsigned long long的结果，如果超出范围则报错
  14. foo.to_string() 返回它转换为string的结果
  16. foo.test(0) test函数用来查下标处的元素是０还是１