202111051401STL.mp4

大纲要求

•【3】 中 sort 函数

•【4】 栈（stack）、 队列（queue）、链表（list）、向量（vector）等容器

基本概念

有些人会疑惑，为什么会先讲数据结构，先讲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?

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

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

编辑器使用C++11的基本配置

Dev C++ 基本配置

image.png
image.png

VS Code基本配置

新版本的VS Code是自动支持的，无需设置。下面介绍一下，要是设置，在哪设置。

Ctrl + Shift + p，选择Edit Configurations(UI)，当然也可以选择(JSON)，一个东西。
image.png
image.png
image.png

VS Code中使用万能头(适用macOS)

这两个博客中的内容结合使用一下就能搞定
https://blog.csdn.net/BlacKingZ/article/details/113487142
https://www.jianshu.com/p/e10498d2d211

macOS基本配置

  1. g++ -o exe std.cpp -std=c++14
  3. // 修改一下g++命令，方便以后简单使用    
  4. vim ~/.bash_profile
  5. alias vim='/Applications/MacVim.app/Contents/MacOS/Vim'
  6. alias g++='g++ -std=c++14'

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 < (int)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
  19. v.pop_back();
  20. cout << v.back() << "\n"; // 5
  22. // size 10, initial value 0
  23. vector<int> v(10);
  25. // size 10, initial value 5
  26. vector<int> v(10, 5);
  28. // vector的排序
  29. sort(v.begin(), v.end());
  30. reverse(v.begin(), v.end());
  32. sort(v.rbegin(), v.rend());
  34. // int a[N]的排序
  35. sort(a, a+n);
  36. reverse(a, a+n);
  38. // 倒序，这个要注意一下OJ是否支持
  39. sort(a, a + n, greater<int>());
  1. // 【要点】(int)A.size()
  2. // vector中size函数的返回值是一个无符号类型
  3. // 当size是0的时候，对其进行减1，会造成数字的越界溢出
  5. #include <bits/stdc++.h>
  7. using namespace std;
  9. vector<int> A;
  11. int main(){
  12.     cout << A.size() << ' ' << A.size() - 1 << '\n';
  14.     return 0;
  15. }
  17. // 输出 0 18446744073709551615
  19. #include <bits/stdc++.h>
  21. using namespace std;
  23. vector<int> A;
  25. int main(){
  26.     cout << A.size() << ' ' << (int)A.size() - 1 << '\n';
  28.     return 0;
  29. }
  31. // 输出 0 -1
  33. //【注意】for(int i = 0; i < (int)A.size(); i++){} 要写一个强制取整
  1. // 去重
  2. #include <bits/stdc++.h>
  4. using namespace std; 
  6. vector<int> A;
  7. int n;
  9. void print(){
  10.     for (auto x : A) printf("%d ", x);
  11.     puts("");
  12. }
  14. int main()
  15. {
  16.     cin >> n;
  17.     for (int i = 0; i < n; i++){
  18.         int x;  cin >> x;
  19.         A.push_back(x);           // 3 2 1 2 1
  21.     }
  23.     sort(A.begin(), A.end());
  24.     print();                      // 1 1 2 2 3
  26.     vector<int>::iterator it = unique(A.begin(), A.end());
  27.     print();                      // 1 2 3 2 3 
  29.     A.erase(it, A.end());         // 1 2 3
  30.     print();
  32.     return 0;
  33. }
  1. // 重点代码    
  2. vector<int> A;
  3. sort(A.begin(), A.end());
  4. A.erase(unique(A.begin(), A.end()), A.end()); // 这样就可以得到一个去重后的vector
  1. // resizing vector
  2. #include <iostream>
  3. #include <vector>
  5. int main ()
  6. {
  7.   std::vector<int> myvector;
  9.   // set some initial content:
  10.   for (int i=1;i<10;i++) myvector.push_back(i);
  12.   myvector.resize(5);
  13.   myvector.resize(8,100);
  14.   myvector.resize(12);
  16.   std::cout << "myvector contains:";
  17.   for (int i=0;i<myvector.size();i++)
  18.     std::cout << ' ' << myvector[i];
  19.   std::cout << '\n';
  21.   return 0;
  22. }
  25. // myvector contains: 1 2 3 4 5 100 100 100 0 0 0 0

list双向链表

  1. // 双向链表的执行效率比较慢，一般不用这个
  2. // 大纲里出现的，介绍一下
  3. #include <list>
  4. #include <bits/stdc++.h>
  6. using namespace std;
  8. list<int> lst;
  10. void print(){
  11.     for (auto x : lst) cout << x << ' ';
  12.     puts("");
  13. }
  15. int main(){
  16.     lst.push_back(1);
  17.     lst.push_back(2);
  18.     lst.push_back(3);
  19.     print();                  //1 2 3 
  21.     lst.push_front(4);
  22.     lst.push_front(5);
  23.     lst.push_front(6);
  24.     print();                  //6 5 4 1 2 3 
  26.     lst.pop_back();
  27.     print();                  //6 5 4 1 2
  29.     lst.pop_front();
  30.     print();                  //5 4 1 2 
  32.     return 0;
  33. }
  35. /*
  36. 输出
  37. 1 2 3 
  38. 6 5 4 1 2 3 
  39. 6 5 4 1 2 
  40. 5 4 1 2 
  41. */

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. #include <bits/stdc++.h>
  3. using namespace std;
  5. char s1[110];
  6. string s2;
  8. int main(){
  9.     cin >> s2;
  10.     strcpy(s1, s2.c_str());
  12.     printf("%s\n", s1);
  14.     return 0;
  15. }
  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
  1. printf("最小值 %d\n", *st.begin());
  2. printf("最大值 %d\n", *(--st.end()));
  3. printf("最大值 %d\n", *st.rbegin());
  5. set<int>::iterator it;
  7. // 第一个大于等于
  8. it = st.lower_bound(10);
  9. if (it != st.end()) cout << *it << '\n';
  11. // 第一个大于
  12. it = st.upper_bound(10);
  13. if (it != st.end()) cout << *it << '\n';
  15. // 最后一个小于
  16. it = st.lower_bound(10);
  17. if (it != st.begin()){
  18.     it--;
  19.     cout << *it << '\n';
  20. }
  22. // 注意不要访问不存在的东西，也不要删除不存在的东西

std::set::lower_bound 与 std::lower_bound的效率问题

  1. // 两者效率相差大的几乎是天壤之别。
  2. // 在CSP-J2021第二轮认证中，T4小熊的果篮
  3. // 这都是血泪史啊
  5. // 这样写就TLE，只能拿30pts
  6. it = upper_bound(st[p].begin(), st[p].end(), now);
  8. // 这样写就可以AC
  9. it = st[p].upper_bound(now);

image.png

image.png
image.png
我倒是觉得下面那个说的很有道理，应该是set<>::iterator不支持随机访问，所以直接当作普通的序列进行二分的时候就不是O(logn)的复杂度了。所以，一定要使用std::set::lower_bound。
https://blog.csdn.net/CZWin32768/article/details/51752267

std::set

https://www.cplusplus.com/reference/set/set/?kw=set
image.png

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["apple"] = 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> ????

std::map

https://www.cplusplus.com/reference/map/map/?kw=map
image.png
image.png

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会更高效一些。

    unordered_map优缺点

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

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 13. STL模板应用 - 图16 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 13. STL模板应用 - 图17time 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 13. STL模板应用 - 图18 time, and retrieval takes 13. STL模板应用 - 图19 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, 如何实现自定义结构体的排序

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函数用来查下标处的元素是０还是１

std::bitset

https://www.cplusplus.com/reference/bitset/bitset/?kw=bitset
image.png