title: stl
tags: acm算法
categories: acm算法
begin/end
- begin函数返回指向vector中的第一个元素的迭代器
- *a.begin() == a[0]
- 所有的容器都可以视作一个前闭后开的结构
- end函数返回vector的尾部,即vector数组的末尾的下一个位置
- *a.end() == a[n] 都是越界访问,其中n = a.size()
front/back
- front返回vector的第一个元素,a.front() == a[0] == *a.begin()
- back返回vector的最后一个元素,a.back() == a[a.size()-1] == *a.end()
push_back() / pop_back()
- a.push_back(x)将x插入到vector的尾部
- b.pop_back(),删除vector a的最后一个元素
queue 循环队列
先进先出
priority queue 优先队列
会优先往外弹最大值
声明
queue<int> q;
priority_queue<int> a;//大根堆
priority_queue<int,vector<int>,greater<int>> b;//小根堆
priority_queue<pair<int,int>> a;//定义的是二元组
重载大于号
struct Rec
{
int a,b;
bool operator > (const Rec& t) const{
return a > t.a;
}
}
priority_queue(Rec) d;
循环队列queue
- 如果越界了会从头开始循环
- push //从队尾插入
- pop //从队头弹出
- front //返回队头元素
- back //返回队尾元素
优先队列priority_queue
- push //把元素插入堆
- pop //删除堆顶元素(优先队列中队头即为最大值)
- top //查询堆顶元素
注意:除了队列,栈,其余都有clear函数
- 清空队列直接初始化
- q = queue[HTML_REMOVED]();
栈stack
- 头文件stack,和队列相反,先进后出
stack<int> stk;
stk.push(1);
stk.top();
stk.pop();
双端队列
- 头文件[HTML_REMOVED]
- 支持在两端高效插入或删除元素的连续线性存储空间
- 相当于是一个拓展版的vector
- 二者在队尾插入元素时间复杂度都是O(1)
- 在队头插入,vector是O(n),deque是O(n)
deque<int> a;//定义
a.begin()
a.end()
a.front()
a.back()
a.push_back()//在队尾插入一个元素
a.push_front()//在对头插入一个元素
a[0]//支持取下标随机访问一个元素
a.pop_front()//在对头弹出一个元素
a.pop_back()//在队尾弹出一个一元素
为了避免边界处理问题,都从0开始遍历,存到n-1
循环队列,优先队列,栈,双端队列都没有迭代器
循环队列,优先队列和栈没有clear()函数,其他都有
set
- 包括set和multiset两个容器,分别是有序集合和有序多重集合
- 有序集合(set)的元素不能重复,但是有序多重集合(multiset)可以包含若干个相等的元素
set<int> s;
struct Rec{
...
};
set<Rec> s;//rec中必须重载小于号
multiset<double> s;