stl 2.0

系统为某一个程序分配空间时,所需时间基本与空间大小无关,与申请次数有关
例 vector最开始就分配了32位空间 不够时再申请64的空间 将之前的copy过来
实际上是一个倍增的思想

[vector与pair] [c++]

vector<int> a(10); //定义长度为10的vector
vector<int> b(10,3); //长度为10且初始化为3的vector

a.size();//a元素个数 所有容器都有 时间复杂度O(1)
a.empty();//返回是否为空
a.clear(); //清空 注意队列没有clear
a.front();//首位
a.back();//末位
push_back(); //末尾添加
pop_back(); //删掉最后一个数
a.erase(a.begin()+2); //删除第3个元素
a.insert(a.begin()+i,b); //在第i+1个元素前面插入b;
begin() end() //迭代器 前者就是a[0] 后者是最后一个数后面的一个数a[a.size]
[] //可以和数组一样

//推荐的遍历方式
1. for(int i=0;i<a.size;i++) cout<<a[i];
2. for(auto x:a) cout<<x;

//常用于多属性 排序 等于一个结构体
pair<int string> p; //定义 中间两个类型参考要求

//也可以存三个属性
pair<int,pair<int,int>>p2;

p.first; //一对pair中第一个元素
p.second;
p={20,"abc"};

用字符数组存不方便 string方便

[string] [c++]

string a="abc";
a+="def"; //可以直接这么加

string b=a.substr(1,2); //从下标为1的元素开始截取长度为2的字串 此处就是bc
//如果长度超过了 那么就输出到最后一个字符为止

queue 队列 先进先出

[队列] [c++]

queue 队列
push() 队尾插入
pop() 弹出队头元素
front()
back()
//注意没有队列clear函数 可以直接
queue<int>q;
q=queue<int>();

priority queue 优先队列 就是堆

[优先队列] [c++]

priority_queue<int> heap; //一定要注意 优先队列默认大根堆

heap.push(-x); // 想弄小根堆 都插负数就行了
priority_queue<int,vector<int>,greater<int> >q1; //或者这样

栈和之前的基本一致 该有的都有

[栈] [c++]

push() //向栈顶插入一个元素
top() //返回栈顶元素
pop() //弹出栈顶元素
size...empty...

双端队列deque 之前没怎么见过
是一种在两端均可以扩展或者收缩的序列化容器 可以在头部和尾部进行插入和删除操作
就是个升级版vector 缺点是速度较慢

[deque] [c++]

size..empty...clear...
push_back()/pop_back() 
push_front()/pop_front() //头尾插入删除

有时可能出现需要去掉重复元素的情况 而且有可能因这些元素比较大或者类型不是int型而不能直接开散列表 在这种情况下就可以用set来保留元素本身而不考虑它的个数
就相当于集合

[set/multiset] [c++]

set<int>S; //set里不会有重复元素 插入重复元素的操作会被忽略
multiset<int>Q; //可以有重复元素
size()..empty()
insert() //插入
find() 查找一个数 不存在返回end迭代器
count() 返回某个数的个数
erase()
      (1) 输入一个数x 删除所有x    O(k+logn)
      (2) 输入一个迭代器,删除这个迭代器(针对有重复元素的multiset)
lower_bound(x) 返回大于等于x的最小的数的迭代器
upper_bound(x) 返回大于x的最小的数的迭代器 如果没有返回end迭代器
例子
int a[] = {1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4};
cout << (lower_bound(a, a + 12, 4) - a) << endl;//输出9即第一个大于等于4的数的下标

map参考stl.map