目录
1.容器适配器
1.1 什么是适配器
1.2 STL标准库中stack和queue底层结构
1.3 deque
1.3.1 deque原理介绍(了解)
1.3.2 deque优点和缺点
1.3.3 为什么选择deque作为stack和queue的底层默认容器
2. stack介绍和使用
2.1 stack介绍
2.2 stack使用
2.3 stack模拟实现
3. queue介绍和使用
3.1 queue的介绍
3.2 queue的使用
3.3 queue模拟实现
4. priority_queue
4.1 priority_queue的介绍
4.2 priority_queue的使用
4.3 priority_queue模拟实现
1.容器适配器
1.1 什么是适配器
1.2 STL标准库中stack和queue底层结构
1.3 deque
1.3.1 deque原理介绍(了解)
那deque是如何借助其迭代器维护其假想连续的结构呢?
1.3.2 deque优点和缺点
deque:1.operator[ ]计算稍显复杂,大量使用,性能下降(相比vector)
2.中间插入删除效率不高
3. 底层角度迭代器会很复杂
1.3.3 为什么选择deque作为stack和queue的底层默认容器
1.头尾插入删除非常适合,相比vector和List而言,很适合去做stack和queue的默认适配容器
2.中间插入删除多用list
3.随机访问多用vector
2. stack介绍和使用
2.1 stack介绍
- stack是一种容器适配器,专门用在具有后进先出操作的上下文环境中,其删除只能从容器的一端进行元素的插入与提取操作。
- stack是作为容器适配器被实现的,容器适配器即是对特定类封装作为其底层的容器,并提供一组特定的成员函数来访问其元素,将特定类作为其底层的,元素特定容器的尾部(即栈顶)被压入和弹出。
- stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类,这些容器类应该支持以下操作:
empty:判空操作
size: 返回栈中有效元素的个数
back:获取尾部元素操作
push_back:尾部插入元素操作
pop_back:尾部删除元素操作
- 标准容器vector、deque、list均符合这些需求,默认情况下,如果没有为stack指定特定的底层容器,默认情况下使用deque。
2.2 stack使用
函数说明 | 接口说明 |
stack() | 构造空的栈 |
empty() | 检测stack是否为空 |
size() | 返回stack中元素的个数 |
top() | 返回栈顶元素的引用 |
push() | 将元素val压入stack中 |
pop() | 将stack中尾部的元素弹出 |
2.3 stack模拟实现
template<class T,class Container=deque<T>>class stack{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}T& top(){return _con.back();}const T& top() const{return _con.back();}bool empty() const{return _con.empty();}size_t size() const{return _con.size();}private:Container _con;};
3. queue介绍和使用
3.1 queue的介绍
- 队列是一种容器适配器,专门用于在FIFO上下文(先进先出)中操作,其中从容器一端插入元素,另一端提取元素。
- 队列作为容器适配器实现,容器适配器即将特定容器类封装作为其底层容器类,queue提供一组特定的成员函数来访问其元素。元素从队尾入队列,从队头出队列。
- 底层容器可以是标准容器类模板之一,也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:
empty:检测队列是否为空size:返回队列中有效元素的个数front:返回队头元素的引用back:返回队尾元素的引用push_back:在队列尾部入队列pop_front:在队列头部出队列
- 标准容器类deque和list满足了这些要求。默认情况下,如果没有为queue实例化指定容器类,则使用标准容器deque。
3.2 queue的使用
函数声明 | 接口说明 |
queue() | 构造空的队列 |
empty() | 检测队列是否为空,是返回true,否则返回false |
size() | 返回队列中有效元素的个数 |
front() | 返回队头元素的引用 |
back() | 返回队尾元素的引用 |
push() | 在队尾将元素val入队列 |
pop() | 将队头元素出队列 |
3.3 queue模拟实现
template<class T,class Container=deque<int>>class queue{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_front();}T& back(){return _con.back();}T& front(){return _con.front();}const T& back() const{return _con.back();}const T& front() const{return _con.front();}bool empty() const{return _con.empty();}size_t size() const{return _con.size();}private:Container _con;};
4. priority_queue
4.1 priority_queue的介绍
仿函数(Functor)又称为函数对象(Function Object)是一个能行使函数功能的类。
仿函数的语法几乎和我们普通的函数调用一样,不过作为仿函数的类,都必须重载 operator() 运算符。因为调用仿函数,实际上就是通过类对象调用重载后的 operator() 运算符。
- 优先队列是一种容器适配器,根据严格的弱排序标准,它的第一个元素总是它所包含的元素中最大的。
- 此上下文类似于堆,在堆中可以随时插入元素,并且只能检索最大堆元素(优先队列中位于顶部的元素)。
- 优先队列被实现为容器适配器,容器适配器即将特定容器类封装作为其底层容器类,queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出,其称为优先队列的顶部。
- 底层容器可以是任何标准容器类模板,也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问,并支持以下操作:
empty():检测容器是否为空size():返回容器中有效元素个数front():返回容器中第一个元素的引用push_back():在容器尾部插入元素pop_back():删除容器尾部元素
- 标准容器类vector和deque满足这些需求。默认情况下,如果没有为特定的priority_queue类实例化指定容器类,则使用vector。
- 需要支持随机访问迭代器,以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数 make_heap、push_heap和pop_heap来自动完成此操作。
4.2 priority_queue的使用
函数声明 | 接口说明 |
priority_queue() priority_queue(first,last) | 构造一个空的优先级队列 |
empty() | 检测优先级队列是否为空,是返回true,否则返回false |
top() | 返回优先级队列中最大(最小元素),即堆顶元素 |
push() | 在优先级队列中插入元素val |
pop() | 删除优先级队列中最大(最小)元素,即堆顶元素 |
//构造一个空的优先队列(此优先队列默认为大顶堆)
priority_queue<int> big_heap; //另一种构建大顶堆的方法
priority_queue<int,vector<int>,less<int> > big_heap2;
小顶堆(升序)
//构造一个空的优先队列,此优先队列是一个小顶堆
priority_queue<int,vector<int>,greater<int> > small_heap;
注意:
如果使用less和greater,需要头文件:
#include <functional>
如果在priority_queue中放自定义类型的数据,用户需要在自定义类型中提供> 或者< 的重载。
4.3 priority_queue模拟实现
template<class T, class Container = vector<T>,class Compare=std::less<T>>class priority_queue{public:priority_queue(){}template<class InputIterator>priority_queue(InputIterator first, InputIterator last){while (first != last){_con.push_back(*first);++first;}//建堆,(_con.size()-1-1)/2为末尾节点的父节点所在位置for (int i = ((_con.size() - 1 - 1) / 2); i >= 0; i--){//向下建堆logNadjust_down(i);}}//向上建堆void adjust_up(size_t child){/*size_t parent = (child - 1) / 2;while (child > 0){//建大堆if (_con[parent] < _con[child]){std::swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}*/Compare com;//仿函数,类对象像函数一样使用,重载operator()size_t parent = (child - 1) / 2;while (child > 0){//建大堆if (com(_con[parent],_con[child])){std::swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}void push(const T& x){//先vector插入,再向上调整_con.push_back(x);adjust_up(_con.size() - 1);}//向下建堆void adjust_down(size_t parent){/*size_t child = parent * 2 + 1;while (child < _con.size()){//选出左右孩子大的那一个if (child + 1 < _con.size() && _con[child] < _con[child + 1]){++child;}//建大堆if (_con[parent] < _con[child]){std::swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;}}*/Compare com;//仿函数,类对象像函数一样使用,重载operator()size_t child = parent * 2 + 1;while (child < _con.size()){//选出左右孩子大的那一个if (child + 1 < _con.size() && com(_con[child] , _con[child + 1])){++child;}//建大堆if (com(_con[parent] , _con[child])){std::swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;}}}void pop(){//根与最右下边的孩子交换,vector尾删,再下调整std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}const T& top() const{return _con[0];}bool empty() const{return _con.empty();}size_t size() const{return _con.size();}private:Container _con;};
这里就不赘述建堆过程,小伙伴可自行搜索数据结构内容复习。