系统为某一程序分配空间时,所需时间与空间大小无关,与申请次数有关
vector
变长数组,倍增思想:先申请1,再申请2(copy)(x2)
n:申请空间次数logn,copy O(1)
vector<int> a(),b(10),c(10,3),d[10];//c:10个3
a.clear();
a.size();//O(1)
a.empty();//O(1)
a.front();
a.back();
a.push_back();
a.pop_back();
a.begin();//a[0]
a.end();//a[size()];
a.erase();O(n);
for(int i=0;i<a.size();i++){}
for(vector<int>::iterator it=a.begin();i<a.end();i++){}
for(auto it:a){}//c++11
//支持比较运算,大小按字典序比
pair
pair<int,string>p;
pair<int,pair<int,int>>pp;
p=make_air(10,"szh");
p={20,"abc"};//c++11
p.first;
p.second;
//支持比较运算,大小按字典序比
string 字符串
string s="sch";
s+="def";
s+='c';
cout<<a.substr(1,10);//第一个字符起10个字符,输完即止,c++中第二个数是长度,其他语言是截止位置
cout<<a.substr(1);//第一个字符开始的字符串
printf("%s\n",s.c_str());//存储字符串的起始地址
//substr()返回子串,c_str()返回头指针
s.size();
s.length();
s.empty();
s.clear();
queue 队列
//没有clear();
queue<int> q;
q=queue<int>();//清空
q.push();
q.front();
q.back();
q.pop();
q.empty();
priority_queue 优先队列,堆,默认大根堆
//无clear();
priority_queue<int> heap;
q.push();
q.top();
q.pop();
//定义小根堆:
heap.push(-x);//1
priority_queue<int,vector<int>,greater<int>>heap;//2
stack 栈
//无clear();
stack<int> s;
s.empty();
s.push();
s.pop();
s.top();
s.size();
deque 双端队列
//缺点:速度稍慢
deque<int> d;
d.size();
d.empty();
d.clear();
d.front();
d.back();
d.push_back();
d.pop_back();
d.push_front();
d.pop_front();
支持随机选取;
set,multiset
set 没有重复元素
multiset 可以有重复元素
size();
empty();
clear();//除了这三个都是O(logn)
begin();
end();
//++,--返回前驱和后继,O(logn)
set/multiset
insert();
find();//没有返回end()
count();//返回某一个数的个数
erase();
(1)输入时一个数x,删除所有x, O(k+logn)k:x个数
(2)输出一个迭代器,删除这个迭代器
lower_bound();//返回大于等于x的最小的迭代器
upper_bound();//返回大于x的最小的迭代器
//没有返回end();
map,multimap
基于平衡二叉树(红黑树),动态维护有序序列
size();
empty();
clear();
begin();
end();
//++,--;
insert();//插入的数是一个pair
erase();//输入的参数是pair或者迭代器
find();
lower_bound();
upper_bound();
[]//像数组一样使用map;
map<string,int>m;
m["szh"]=1;//时间复杂度:O(logn)
cout<<m["szh"]<<endl;
unordered_set,unordered_map,unordered_multiset,unordered_multimap
哈希表
//和上面类似,但增删改查的时间复杂度是O(1)
//不支持lower_bound(),upper_bound(),迭代器的++,--;
bitset 压位
//bool:1字节,8位
//bitset:一位
//8分之一bool
//常用于存大量bool值
bitset<10000> b;
~b;
//&,|,^
//>>,<< 与感知方向相反
//==,!=
//[]
count();//返回有多少个1
any();//返回是否至少有一个1
none();//是否全为0
set();//把所有位变成1
set(k,v);//将第k位变成1
reset();//把所有位变成0
flip();//所有位取反
flip(k);//第k位取反
//c++ reference