1、vector 基于倍增的思想
(1)操作系统中,分配空间的速度和空间大小无关,和申请时间/申请次数有关;所以为了避免浪费时间,
一次性开较大的空间比较好,竞赛中不怕浪费;
(2)倍增思想:一开始初始化一个vector,系统默认分配32个空间,一旦插入元素超过32个,系统就是
申请一个32×2的空间,然后把之前的元素拷贝到新的空间中;如果超过64了就再申请一个64×2的空间,以此类推;
(3)支持比较运算,按字典序比较 a(4,3)<b(3,3)
(4)支持size() , empty() , clear();
(5)在末尾插入元素的时候尽量使用emplace_back(),效果一样但优于push_back();
2、pair 可以看作是一个自带二元,且自动实现了一种比较的结构体
pair<int,string> p; p=make_pair(123,"asdas"); p={20,"asdas"}
pari<int,pair<int,int>> p; //只要你开心,随便嵌套多少个都行
//也可以比较,first为第一关键字,second为第二关键字,按字典序比较
3、string
(1)支持size() , empty() , clear();
(2)s.substr(i,k); 返回某一字串,i为s中起始字串的下标,k为所要返回字串的长度;如果k大于总长度,
返回到末尾为止
(3)printf("%s",a.c_str()); //返回字符串起始的首地址,也就是把整个字符串输出;
4、queue队列
(1)没有clear,如果要清空 直接重新定义一下 q=queue<int>()
或者 while(!q.empty()) q.pop();
5、优先队列priority_queue (堆,默认为大根堆)
(1)如何创建一个小根堆呢,可以q.push(-x); 就是按x从小打到的顺序排列了
或者 priority_queue<int,vector<int>,greater<int>> heap; 这样就是一个小根堆了
6、stack
size(),empty(),push(),pop(),top();
7、deque 双端队列 加强版vector 速度很慢(所以几乎不用) 支持随机寻址
size(),empty(),clear(),front(),back();
push_back(),pop_back();
push_front(),pop_front();
8、set/multiset set所有操作都是logn 数据是从小到大有序的
(1)、set里面不能有重复元素,如果插入重复元素,这个操作会被忽略掉,但multiset里面可以有重复元素
insert(), find() 查找某个元素,如果没有找到返回end()迭代器 end()指向最后一个元素的后面;
count() 返回元素个数;(在set里面只有0和1的情况,在multiset里面就是有多少个就返回多少个)
erase() 1)如果输入一个数x,就删除所有x;2)如果输入一个迭代器,就仅删除这个迭代器
(2)、核心操作
lower_bound() 返回大于等于x的最小的数的迭代器,如果不存在返回end()
upper_bound() 返回大于x的最小的数的迭代器,如果不存在返回end()
(3)begin(),end() 支持++ --操作 返回前驱和后继元素
9、map\multimap 基于平衡二叉树(红黑树)实现,动态维护有序序列 数据是从小到大有序的
(1)insert()——插入的是一个pair() ,erase()——输入参数是pair或迭代器;支持find()操作
(2)可以像一个数组一样来操作一个map 非常牛 a[1]=5; cout<<a[1]; 但是是logn的
(3)begin(),end() 支持++ --操作 返回前驱和后继元素
(4)同样支持lower_bound() upper_bound()
begin() 返回指向 map 头部的迭代器
clear() 删除所有元素
hash.count(a) 返回指定元素a出现的次数
empty() 如果 map 为空则返回 true
end() 返回指向 map 末尾的迭代器
equal_range() 返回特殊条目的迭代器对
erase() 删除一个元素
hash.find(a) 查找一个元素
get_allocator() 返回map的配置器
insert() 插入元素
key_comp() 返回比较元素key的函数
lower_bound() 返回键值>=给定元素的第一个位置
max_size() 返回可以容纳的最大元素个数
rbegin() 返回一个指向map尾部的逆向迭代器
rend() 返回一个指向map头部的逆向迭代器
size() 返回map中元素的个数
swap() 交换两个map
upper_bound() 返回键值>给定元素的第一个位置
value_comp() 返回比较元素value的函数
10、unodered_set/multiset/map/multimap 基于哈希表实现 数据是无序的
(1)和89中的操作类似,且增删改查的时间复杂度是O1 里面数据是无序的
(2)缺点是不支持lower_bound() upper_bound(); 也不支持迭代器的++ --
unordered_map<int,unordered_map<int,int>> h; //二维数组后面的是下标
h[1][4]=1;
cout<<h[1][4];
unordered_map<int,string> id; //一维数组前面的是下标
11、bitset 压位
(1)定义 bitset<10000> s; 10000是长度;
支持~,&,|,^,>>,<<,==,!=, []支持自由寻址;
(2)count()返回有多少个1; any()判断是否至少有一个1; none() 判断是否全为0;
set()把所有位置成1; set(k,v) 将第k位变成v ; reset()把所有位变成0 ;
flip()把所有位取反等价于~ flip(k)把第k位取反
可以再去看看pbds(