STL¶
前置知识¶
C++基础语法，不需要知道什么是面向对象
A container is a holder object that stores a collection of other objects (its elements). They are implemented as class templates, which allows a great flexibility in the types supported as elements.
目标¶
掌握STL相关的，最少必要知识，并且是进入算法学习的前期，就要掌握。而不是最后掌握
What¶
C++ 的容器（container），用来存储数据的，通常是不同的数据结构。每一种容器，有自己特有的特点。都能存储数据，但是因为优点不同，所以适用在不同的场景。他们有很多的共性操作，基本都是以英文单词字面意思出现，当不知道有没有的时候，可以直接试一下英文单词代表函数名称。
更多的，可以去查C++官网vector - C++ Reference
这个网站特别好用，当然你要会用，才能觉得好用。稍微要动点脑筋，不可死记硬背，英语硬要看下去
vector¶
动态数组
vector<int> a;
vector<int> a(10);
vector<int> a(10, 0);
for (int i = 0; i < 10; i++) cin >> a[i];
a.push_back(10);
a.pop_back();
for (int i = 0; i < 10; i++) {
int x;
cin >> x;
a.push_back(x);
}
sort(a.begin(), a.end());
reverse(a.begin(), a.end());
// 遍历，支持中括号访问
cout << a[0];
for (int i = 0, len = a.size(); i < len; i++) cout << a[i] << ' ';
// 迭代器访问
for (vector<int>::iterator it = a.begin(); it != a.end(); it++) cout << *it << ' ';
// C++11写法
for (auto x : a) cout << x << ' ';
vector<int>::iterator up = upper_bound(a.begin(), a.end(), 10);
vector<int>::iterator low = lower_bound(a.begin(), a.end(), 10);
cout << *low << ' ' << *up << '\n';
cout << low - a.begin() << ' ' << up - a.begin() << '\n';
// 实现vector<int> A的去重，先排序，得到unique的位置，然后把从unique位置往后，全部删除
sort(A.begin(), A.end());
vector<int>::iterator it = unique(A.begin(), A.end());
A.erase(it, A.end());
A.erase(unique(A.begin(), A.end()), A.end()); // 或者这样写
vector<array<int, 3>> e;
// 这样的插入
e.push_back({u, v, i});
// C++17
// 结构化绑定（Structured Bindings）特性
// auto & 表示使用引用类型，避免不必要的拷贝
// [u, v, i] 是结构化绑定
// 将元组中的三个值分别绑定到变量 u、v 和 i 上
for (auto &[u, v, i] : e) {
}
// 关于[结构化绑定]的其他示例
struct Edge {
int to;
int weight;
int index;
};
std::vector<Edge> edges = ...;
for (auto &[u, v, i] : edges) { // u=to, v=weight, i=index }
// 使用 u, v, i...
}
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.
set 就会默认是有序的
set<int> s;
s.insert(3);
s.insert(2);
s.insert(5);
cout << s.count(3) << "\n"; // 1
cout << s.count(4) << "\n"; // 0
s.erase(3);
s.insert(4);
cout << s.count(3) << "\n"; // 0
cout << s.count(4) << "\n"; // 1
set<int> s = {2,5,6,8};
cout << s.size() << "\n"; // 4
for (auto x : s) { //C++11 用法
cout << x << "\n";
}
//set里面，每个元素只存一个
set<int> s;
s.insert(5);
s.insert(5);
s.insert(5);
cout << s.count(5) << "\n"; // 1
//multiset里面，每个元素可以存多个
multiset<int> s;
s.insert(5);
s.insert(5);
s.insert(5);
cout << s.count(5) << "\n"; // 3
//把5这个元素全删了
s.erase(5);
cout << s.count(5) << "\n"; // 0
//只删掉一个5元素
s.erase(s.find(5));
cout << s.count(5) << "\n"; // 2
printf("最小值 %d\n", *st.begin());
printf("最大值 %d\n", *(--st.end()));
printf("最大值 %d\n", *st.rbegin());
set<int>::iterator it;
// 第一个大于等于
it = st.lower_bound(10);
if (it != st.end()) cout << *it << '\n';
// 第一个大于
it = st.upper_bound(10);
if (it != st.end()) cout << *it << '\n';
// 最后一个小于
it = st.lower_bound(10);
if (it != st.begin()){
it--;
cout << *it << '\n';
}
// 注意不要访问不存在的东西，也不要删除不存在的东西
map¶
Maps are associative containers that store elements formed by a combination of a key value and a mapped value, following a specific order.
map<string,int> m;
m["monkey"] = 4;
m["banana"] = 3;
m["apple"] = 9;
cout << m["banana"] << "\n"; // 3
map<string,int> m;
cout << m["aybabtu"] << "\n"; // 0
// 判断是否存在，用count
if (m.count("aybabtu")) {
// key exists
}
// C++11的遍历，我们自己写，要用interator
for (auto x : m) {
cout << x.first << " " << x.second << "\n";
}
//所以，我想问，能不能 map<int, string> 这样定义????
pair¶
This class couples together a pair of values, which may be of different types (T1 and T2). The individual values can be accessed through its public members first and second.
pair<int, int> A, B;
A = make_pair(1, 2); //比赛中可以用这种写法
A = {1, 2}; // C++14写法
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
PII a[N];
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i].first >> a[i].second;
return 0;
}
stack¶
Stacks are a type of container adaptor, specifically designed to operate in a LIFO context (last-in first-out), where elements are inserted and extracted only from one end of the container.
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.
queue¶
queues are a type of container adaptor, specifically designed to operate in a FIFO context (first-in first-out), where elements are inserted into one end of the container and extracted from the other.
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.
queue<int> q;
q.push(3);
q.push(2);
q.push(5);
cout << q.front(); // 3
q.pop();
cout << q.front(); // 2
priority_queue优先队列¶
Priority queues are a type of container adaptors, specifically designed such that its first element is always the greatest of the elements it contains, according to some strict weak ordering criterion.
This context is similar to a heap, where elements can be inserted at any moment, and only the max heap element can be retrieved (the one at the top in the priority queue).
priority_queue<int> q;
q.push(3);
q.push(5);
q.push(7);
q.push(2);
cout << q.top() << "\n"; // 7
q.pop();
cout << q.top() << "\n"; // 5
q.pop();
q.push(6);
cout << q.top() << "\n"; // 6
q.pop();
// 默认是大根堆，如果要写小根堆，就是push x进去的时候，push成-x，
// 取出使用的时候，加个负号再使用。
// 实现大根堆，还有一个方法，如下：
priority_queue<int,vector<int>,greater<int> >q;//这样就可以实现小根堆了
参考：https://www.cnblogs.com/zwfymqz/p/7800654.html, 如何实现自定义结构体的排序
bitset¶
A bitset stores bits (elements with only two possible values: 0 or 1, true or false, ...).
#include <bits/stdc++.h>
using namespace std;
int main() {
bitset<16> a; // 0000000000000000
bitset<16> b(0xfa2); // 0000111110100010
bitset<16> c(string("0101111001")); // 0000000101111001
bitset<4> bt;
bt[1] = 1; // 中括号访问
cout << bt.count() << '\n'; // 输出1的个数
cout << bt.test(1); // 测试第1位是不是1
if (bt.any()) cout << "have ones." << '\n'; // 判断有没有1
if (bt.all()) cout << "all ones." << '\n'; // 判断是不是都是1
bitset<4> foo;
foo.set(); // 都置成1, 1111
foo.set(2, 0); // 把第2位置成0, 1011 (从低位到高位3210，这样位置)
foo.set(2); // 把第2位置成1, 1111
foo.reset(1); // 把第1位置成0
foo.reset(); // 都置成0
foo.flip(2);
foo.flip(); // 翻转所有位置
foo.to_string(); // 转换成字符串
foo.to_ullong(); // 转换成无符号长整型
return 0;
}
// 通过打表预处理，实现输入一个八位有符号二进制，输出对应的十进制
#include<bits/stdc++.h>
using namespace std;
map<string, int> mp;
void init() {
for (int i = -128; i < 128; i++) {
bitset<8> bit(i);
mp[bit.to_string()] = i;
}
}
int main() {
init();
string s;
cin >> s;
cout << mp[s] << '\n';
return 0;
}
array¶
Arrays are fixed-size sequence containers: they hold a specific number of elements ordered in a strict linear sequence.
题单¶
1177：奇数单增序列，使用vector实现
1177：奇数单增序列，使用set实现
1107：校门外的树，使用map实现
1176：谁考了第k名，使用vector, pair实现
1176：谁考了第k名，使用priority_queue实现
总结¶
vector, set, map, pair, stack, queue, priority_queue, bitset