/*
vector,变长数组,倍增的思想
size() 返回元素个数
empty() 返回是否为空
clear() 清空(队列无清空函数)
front()/back()
push_back()/pop_back()
begin()/end() //end()取最后一个数的后面的数
支持比较运算
pair<int,int>
first,第一个元素
second,第二个元素
支持比较运算,以first为第一关键字,以second为第二关键字(字典序)
string,字符串,substr()-返回某一个子串,c_str()-返回字符数组的头指针
size()/length() 返回字符串长度
empty()
clear()
queue,队列
size()
empty()
push() 向队尾插入一个元素
front() 返回队头元素
back() 返回队尾元素
pop() 弹出队头元素
无clear()函数
priority_queue,优先队列,默认为大根堆
push() 插入一个元素
top() 返回堆顶元素
pop() 弹出堆顶元素
定义成小根堆的方式:priority_queue<int,vector<int>,greater<int>> q;
stack,栈
push() 向栈顶插入一个元素
top() 返回栈顶元素
pop() 弹出栈顶元素
无clear()函数
deque,双端队列(队头队尾都可以插入删除),支持随机访问-加强版的vector
size()
empty()
clear()
front()
back()
push_back()/pop_back()
push_front()/pop_front()
begin()/end()
[]
效率非常低,比一般的数组慢好几倍
set,map,multiset,multimap,multimap,基于平衡二叉树(红黑树-平衡二叉树的一种),动态维护有序序列
size()
empty()
clear()
begin()/end() ++,--返回前驱和后继,时间复杂度O(logn)
set/multiset
insert() 插入一个数
find() 查找一个数
count() 返回某一个数的个数
erase()
(1)输入是一个数x,删除所有x O(k+logn) k是x的个数
(2)输入一个迭代器,删除这个迭代器
lower_bound()/upper_bound()
lower_bound(x) 返回大于等于x的最小的数的迭代器
upper_bound(x) 返回大于x的最小的数的迭代器
map/multimap
insert() 插入的数是一个pair
erase() 输入的参数是pair或者迭代器
find()
[] 时间复杂度是O(logn)
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位取反
*/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;
int main()
{
//vector<int> a(10,-3); //定义一个长度为10的vector,并且初始化为3
//vector<int> a[10];
vector<int> a;
for(int i=0;i<10;i++) a.push_back(i);
for(int i=0;i<a.size();i++) cout<<a[i]<<' ';
cout<<endl;
for(auto /*vector<int>::iterator*/ i=a.begin();i!=a.end();i++) cout<<*i<<' '; //迭代器可以看作指针
cout<<endl;
a[0],a[a.size()];
for(auto x:a) cout<<x<<' ';
a.size(); //所有容器都有,时间复杂度O(1)
a.empty(); //所有容器都有,时间复杂度O(1)
vector<int> a(4,3),b(3,4); //vector支持比较运算
if(a<b) puts("a<b"); //比较字典序
pair<int,string>p;
p=make_pair(10,"yxc");
p={20,"abc"};
pair<int,pair<int,int>>p;
string a="yxc";
a+="def";
a+='c';
cout<<a<<endl;
cout<<a.substr(1,2)<<endl; //从下标1开始,返回2个字符
//当后面的数字很大超过字符串长度时,输完字符串就会停止
//cout<<a.substr(1)<<endl;
//省略第二个数字也会输出到字符串末端
printf("%s\n",a.c_str());
queue<int> q;
q=queue<int>(); //重新构造一个队列以达到clear()函数的效果
priority_queue<int> heap; //默认为大根堆
heap.clear(-x);
priority_queue<int,vector<int>,greater<int>> heap; //小根堆
map<string,int> a;
a["yxc"]=1;
cout<<a["yxc"]<<endl;
unordered_multimap<string,int> a;
return 0;
}