vector
变长数组,倍增思想
基本函数
size() //返回元素个数,时间复杂度为o(1)
empty() //返回a是否为空,时间复杂度为o(1)
clear() //清空
front()/back() //返回第一个数/最后一个数
push_back() //最后插入一个数
pop_back() //删掉最后一个数
begin() / end() //第0个数/最后一个数的后面一个数
[]支持随机寻址(与数组相同)
支持比较运算, 按字典序
定义
//vector 定义
vector<int> a(10, 3);//定义一个长度为10,全为3
三种遍历方式
for (int i = 0; i < a.size(); i++) cout << a[i] << ' ';
cout << endl;
for (vector<int>::reverse_iterator i = a.begin(); i != a.end(); i++) cout << *i << ' ';
cout << endl;
for (auto x : a) cout << x << ' ';
cout << endl;
pair<int, int>
first,第一个元素
sencond,第二个元素
支持比较运算,以first为第一关键字,以second为第二关键字(字典序)
pair<int,pair<int,int>>p; //pair存储3个元素
//pair初始化
pair<int,string>p;
p=make_pair(10,"C++");
string 字符串
基本函数
size()/length() 返回个数
empty() 是否为空
clear() 清空
string1+string2 字符串相加
string a="hello";
string b="world";
string c=a+b;
substr(i,j) //返回某一字串,从下标i开始,共返回j个字符
c_str(a) //返回字符串a的地址
queue 队列
push() 相对为插入一个元素
front() 返回队头元素
back() 返回队尾元素
pop() 弹出队头元素
无clear()函数
priority_queue 优先队列
默认是大根堆
push() 插入一个元素
top() 返回堆顶元素
pop() 弹出堆顶元素
stack 栈
size()
empty()
无clear()
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() ++/--
set(元素不重复)/multiset(可重复)
inset() 插入一个数
find() 查找一个数
count() 返回某一个数的个数
erase()
1.输入一个数x,删除所有x
2.输入一个迭代器,则删除这个迭代器
核心操作
lower_bound(x) 返回大于等于x的最小的数
upper_bound(x) 返回大于x的最小的数
map/multimap
inset() 插入的数是一个pair
find() 查找一个数
erase() 输入的参数是pair或者迭代器
[ ] 时间复杂度o(logn)
lower_bound(x)
upper_bound(x)
unordered_set,unorderd_map,unordered_muliset,unordered_multimap
基于哈希表
和上述类似,增删改查的时间为o(1)
但不支持lower_bound(x),upper_bound(x),迭代器的++,--等与排序相关的操作
bitset 压位
~,&,|,^
>>,<<
==,!=
[]
count() 返回有多少个1
any() 判断是否至少有一个1
none() 判断是否全为0
set() 把所有位置成1
set(k,v) 将第k位变成v
reset() 把所有为位变为0
flip() 等价于~
flip(k) 把第k位取反