变长数组vector

自带比较运算，按照字典序进行比较
vector可直接进行复制
vector一旦进行初始化之后，所有的未被赋值默认为0
vector在函数参数传递时与普通数组不同，需要加&才能表示引用传递

#include <vector>
vector<int> a;
vector<int> c({1, 2, 3, 4});    // 初始化
a = c;  // vector也可以直接执行赋值操作 
a.size();
a.empty();
a.clear();
vector<int>::iterator it = a.begin();   // 迭代器，相当于指针，这里it就相当于a[0]的地址
a.end();
*a.begin() == a[0];
a.front() == a[0] == *a.begin();
a.back() == a[a.size() - 1] == *(a.end() - 1);
a.push_back(x);    // 在数组最后添加一个元素x
a.pop_back();      // 删除数组最后一个元素
a.erase(i, j);     // 将vector中从迭代器i到j的所有元素全部删除

// 结构体与vector混用
struct test
{
    int x, y;
};
vector<test> c;

// 遍历vector的三种方式
for (int i = 0; i < a.size(); i ++) cout << a[i] << endl;

for (auto i = a.begin(); i < a.end(); i ++) cout << *i << endl;

for (auto x : a) cout << x << endl;

队列queue

性质：先进先出

#include <queue>
queue<int> q;   // 普通队列
priority_queue<int> a; // 大根堆优先弹出最大值
priority_queue<int, vector<int>, greater<int>> b; // 小根堆优先弹出最小值
priority_queue<pair<int, int>> c;   // 类似于Python中的元组类型

q.push(x); // 在队尾插入一个元素x
q.pop();   // 弹出队头元素
q.front(); // 返回队头
q.back();  // 返回队尾
a.push(x); // 插入一个元素x
a.top();   // 返回最大值
a.pop();   // 删除最大值
// 队列无clear函数，要清空就重新进行初始化
q = queue<int> ();


// 定义结构体类型的大根堆时结构体中要重载小于号，小根堆中要重载大于号

栈stack

性质：先进后出

#include <stack>
stack<int> stk;
stk.push(x)  // 插入一个元素
stk.top()    // 返回栈顶元素
stk.pop()    // 删除栈顶元素

双端队列deque

性质：队头队尾均可插入弹出，与vector一样支持随机访问

#include <deque>
deque<int> a;
a.begin();
a.end();
a.front();
a.back();
a.push_back(x);   // 在队尾插入一个元素
a.push_front(x);  // 在队头插入一个元素
a.pop_back();     // 弹出队尾元素
a.pop_front();    // 弹出队头元素
a.clear();        // 清空队列

集合set

set<int> a;  // 元素不能重复
multiset<int> b;  // 元素可以重复
a.size();
a.empty();
a.clear();
set<int>::iterator it = a.begin();  // set中的迭代器
it ++; it --;   // 有序序列中的前一个元素和后一个元素
++ it; -- it;
a.end();
a.insert(x);    // 往set中插入一个元素x
if (a.find(x) == a.end());   // 判断在集合a中x是否存在，原理是a.find(x)如果找到了会返回x的迭代器，没找到返回a.end()
a.lower_bound(x);    // 找到第一个大于等于x的最小元素的迭代器
a.upper_bound(x);    // 找到第一个大于x的最小元素的迭代器
a.erase(x); a.erase(it);     // 括号中是一个元素表示将这个元素的所有迭代器删除，如果是一个迭代器表示将这个迭代器删除
a.count(x);   // 返回x在集合里面的个数  

// 定义结构体类型的集合时结构体中要重载小于号

映射map

#include <map>
map<int, int> a;
map<string, int> b;
map<string, vector<int>> c;
a[1] = 2;
b["hhh"] = 123;
c["soul"] = vector<int>({1, 2, 3, 4});
a.size();
a.empty();
a.begin();
a.end();
a.clear();
a.insert({1, 2})    // 插入也可以用这种方式
a.erase(x);
if (a.find(x) == a.end());   // 判断在映射a中x是否存在，原理是a.find(x)如果找到了会返回x的迭代器，没找到返回a.end()

无序集合unordered_set和unordered_multiset

无序集合与普通集合所有操作都一样，所有操作的时间复杂度变为了O(1)，但没有lower_bound和upper_bound操作

#include <unordered_set>
unordered_set<int> a;
unordered_multiset<int> b;

无序映射unordered_map

与普通映射所有操作一样，但时间复杂度变为了O(1)

#include <unordered_map>
unordered_map<int, int> a;

位集合bitset

#include <bitset>
bitset<1000> a;     //  支持size等操作，但不支持clear
bitset<1000> b;
a.set(i);    // 将某一位设置为1
a.reset(i);     // 将某一位设置为0
a.count();  // 返回a中1的个数
a &= b;
a != b;

二元组pair

自带比较运算

pair<int, string> a;
// 两种赋值方式
a = {3, "hhh"};
a = make_pair(4, "hyh");
cout << a.first() << ' ' << a.second() << endl;