vector变长数组, 倍增的思想
string字符串,substr(),c_str()
queue队列,push(),front(),pop()
priority_queue优先队列,push(),top(),pop()
stack栈,push(),top(),pop()
deque双端队列
set,map,multiset,multimap基于平衡二叉树(红黑树), 动态维护有序序列
unordered_set,unordered_map,unordered_multiset,unordered_multimap哈希表
bitset压位
vector
初始化:
vector <int> a (10)长度为10的数组
vector <int> a (10,3)长度为10的数组, 每一个数为3
vector <int> a [10]定义了10个vector
vector支持的函数:
a.size()返回元素个数
a.empty()空返回true, 非空返回false
a.clear()清空
a.front()/a.back()返回第一个数/ 最后一个数
a.push_back()在最后插入一个数
a.pop_back()删除最后一个数
a.begin()返回a的第一个元素的迭代器
a.end()返回a的最后一个元素的下一个元素的迭代器
a[]vector支持随机寻址
vector的遍历:
for(int i = 0 ; i < a.size() ; i++) cout << a[i] << ' ';用数组下标遍历
for(vector<int>::iterator i = a.begin() ; i != a.end() ; i++) cout << *i << ' ';用迭代器遍历
for(auto x : a) cout << x << ' ';C++的范围遍历
倍增思想: 系统为某一程序分配空间时所需时间, 与空间大小无关, 与申请次数有关.
vector每一次数组长度不够时, 将数组长度扩大一倍.
pair
初始化:
pair <int,int> p
pair <int,pair <int,int>> p
pair支持的操作:
p.first返回第一个元素
p.second返回第二个元素
string
初始化:
string a
string支持的函数:
a.length()返回字符串长度
a.size()返回元素个数
a.empty()空返回true, 非空返回false
a.clear()清空
a.find('x')返回字符x在字符串中下标
a.substr(,)返回某个子串第一个参数表示子串起点下标, 第二个参数表示子串长度.
若第二个参数过大(或无第二个参数), 返回从第一个参数开始的整个子串.
若用
printf输出string要用a.c_str()
queue
初始化:
queue <int> a
queue支持的函数:
a.size()返回元素个数
a.empty()空返回true, 非空返回false
a.push(x)向队尾插入一个元素x
a.front()返回队头元素
a.back()返回队尾元素
a.pop()弹出队头元素
注意:
queue没有clear函数
a = queue <int> ();相当于clear功能
priority_queue
初始化:
priority_queue <int> heap优先队列, 默认是大根堆
priority_queue <int,vector<int>,greater<int>> heap定义小根堆
priority_queue支持的函数:
heap.push(x)插入一个元素x
heap.top()返回堆顶元素
heap.pop()弹出堆顶元素
注意:
priority_queue没有clear元素
stack
初始化:
stack <int> a
stack支持的函数:
a.size()返回元素个数
a.empty()空返回true, 非空返回false
a.push(x)向栈顶插入一个元素x
a.top()返回栈顶元素
a.pop()弹出栈顶元素
注意:
stack没有clear函数
deque
初始化:
deque <int> q
deque支持的函数:
q.size()返回元素个数
q.empty()空返回true, 非空返回false
q.clear()清空
q.front()返回队头元素
q.back()返回队尾元素
q.push_back()向队尾插入一个元素x
q.pop_back()弹出队尾元素
q.push_front()向队头插入一个元素x
q.pop_front()弹出队头元素
q[]deque支持随机访址
q.begin()返回第一个元素的迭代器
q.end()返回最后一个元素下一个元素的迭代器
set / multiset
set 元素不能重复, multiset 元素可以重复
初始化:
set <int> s
multiset <int> ms
set/multiset支持的函数:
s.size()返回元素个数
s.empty()空返回true, 非空返回false
s.clear()清空
s.insert(x)插入一个数x
s.find(x)查找一个数x, 存在返回x的迭代器, 不存在返回end()的迭代器
s.count(x)返回某一个数x的个数
s.erase()输入的是一个数x, 则删除所有x; 输入的是一个迭代器, 则删除这个迭代器
s.lower_bound(x)返回大于等于x的最小的数的迭代器, 不存在则返回end()
s.upper_bound(x)返回大于x的最小的数的迭代器, 不存在则返回end()
++/--返回前驱/ 后继的迭代器
map / multimap
初始化:
map <string,int> a
a ["xt"] = 666
cout << a ["xt"] <<endl;输出"1"可将第一个参数作为数组下标
map/multimap支持的函数:
a.size()返回元素个数
a.empty()空返回true, 非空返回false
a.clear()清空
a.begin()返回第一个元素的迭代器
a.end()返回最后一个元素下一个元素的迭代器
++/--返回前驱/ 后继的迭代器
a.insert()插入的数需要是一个pair
a.erase()输入的参数需要是一个pair或迭代器
a.find()
a[]
unordered_set / unordered_map / unordered_multiset / unordered_multimap
允许存在重复元素的
set和map增删查改的时间复杂度是 O(1)
除不支持
lower_bound()和upper_bound()外, 其余支持函数与set和map相同
bitset
初始化:
bitset <10000> S
bitset只能存储0和1,< >内参数表示长度
bitset支持的操作:
~S取反
&,|,^与、或、异或
>>,<<位运算
==,!=等于、不等于
S.count()返回有多少个1
S.any()判断是否至少有一个1
S.none()判断是否全为0
S.set()把所有位置成1
S.set(k,v)把第k位变成v
S.reset()把所有位置成0
S.flip()把所有位取反
S.flip(k)把第k位取反