初学者：《C++ STL容器入门：手把手教你使用常用容器》
🎬 博主名称：个人主页
🔥 个人专栏: 《算法通关》，《Java讲解》
⛺️心简单，世界就简单
目录
unordered_set, unordered_map, unordered_multiset, unordered_multimap
序言
我们今天来讲一下
vector
string
queue, priority_queue,
stack
set, map, multiset, multimap
unordered_set, unordered_map, unordered_multiset, unordered_multimap
vector倍增思想：
系统为某一程序分配空间时，所需的时间，基本上与空间大小无关，与申请次数有关
所以，我们申请一个数组大小为1000的数组，和申请1000个大小为1的数组，时间差别就是1000倍，就是因为有这样一个特点，所以我们变长数组要尽量减小申请空间的次数
我们在申请长度后，如果我们空间不够，我们就将长度*2再次申请一，初始化常用函数遍历方式黑科技
vector是支持比较运算的，按字典序大小排序比较
pair
存储一个二元组，可以看成有两个变量的结构体，并且内部有比较函数定义方式
这两个数据类型放什么都行取出元素方式
这个是支持比较运算的，排序时候也是按字典序来排，以 first 为第一关键字，，以第second为第二关键字构造一个pair用来干嘛
最常用就是说，有一个东西有两种不同属性，我们就可以用一个pair来存，我们需要按照一种属性来排序，我们把需要排序的属性放在first。
当然如果有三个属性，我们也可以用pair来存，就pair<int, pair<int, int>> p;这样就行了
string
c++把字符串进行了封装常用函数操作
queue队列
priority_queue优先队列
他的原理就是拿堆来实现的，默认是大根堆常用函数如何构造小根堆
1，q.push()时直接插入负值
2，定义时就直接定义为小根堆
stack 栈常用函数
deque 双端队列
其实时一个加强版的vector，功能很强大，但是由于时间很慢，我们不常用
set，multiset
set里面不能包含任何重复元素，multiset里可以有重复元素常用函数
set里的所有操作都是O( logn)时间复杂度
map，multimap
unordered_set, unordered_map, unordered_multiset, unordered_multimap
这些和上面的操作都是几乎一样的
不支持lower_bound， ++ ，--他里面时无序的，因为他是unordered，好处就是他的增删改查复杂度都是O( 1 )
这个yxc的stl总结，可以也看看
vector, 变长数组，倍增的思想 size() 返回元素个数 empty() 返回是否为空 clear() 清空 front()/back() push_back()/pop_back() begin()/end() [] 支持比较运算，按字典序 pair<int, int> first, 第一个元素 second, 第二个元素 支持比较运算，以first为第一关键字，以second为第二关键字（字典序） string，字符串 size()/length() 返回字符串长度 empty() clear() substr(起始下标，(子串长度)) 返回子串 c_str() 返回字符串所在字符数组的起始地址 queue, 队列 size() empty() push() 向队尾插入一个元素 front() 返回队头元素 back() 返回队尾元素 pop() 弹出队头元素 priority_queue, 优先队列，默认是大根堆 size() empty() push() 插入一个元素 top() 返回堆顶元素 pop() 弹出堆顶元素 定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q; stack, 栈 size() empty() push() 向栈顶插入一个元素 top() 返回栈顶元素 pop() 弹出栈顶元素 deque, 双端队列 size() empty() clear() front()/back() push_back()/pop_back() push_front()/pop_front() begin()/end() [] set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列 size() empty() clear() begin()/end() ++, -- 返回前驱和后继，时间复杂度 O(logn) set/multiset insert() 插入一个数 find() 查找一个数 count() 返回某一个数的个数 erase() (1) 输入是一个数x，删除所有x O(k + logn) (2) 输入一个迭代器，删除这个迭代器 lower_bound()/upper_bound() lower_bound(x) 返回大于等于x的最小的数的迭代器 upper_bound(x) 返回大于x的最小的数的迭代器 map/multimap insert() 插入的数是一个pair erase() 输入的参数是pair或者迭代器 find() [] 注意multimap不支持此操作。 时间复杂度是 O(logn) lower_bound()/upper_bound() unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表 和上面类似，增删改查的时间复杂度是 O(1) 不支持 lower_bound()/upper_bound()， 迭代器的++，-- bitset, 圧位 bitset<10000> s; ~, &, |, ^ >>, << ==, != [] count() 返回有多少个1 any() 判断是否至少有一个1 none() 判断是否全为0 set() 把所有位置成1 set(k, v) 将第k位变成v reset() 把所有位变成0 flip() 等价于~ flip(k) 把第k位取反 之后要开图论的系列了。球球三连，码字不易，谢谢谢谢大家
