容器适配器是STL中的一种重要组件#xff0c;用于提供不同的数据结构接口#xff0c;以满足特定的需求和限制。

容器适配器是基于其他STL容器构建的#xff0c;通过…1.容器适配器

适配器是一种设计模式该种模式是将一个类的接口转换成客户希望的另外一个接口。

容器适配器是STL中的一种重要组件用于提供不同的数据结构接口以满足特定的需求和限制。

容器适配器是基于其他STL容器构建的通过改变其接口和行为使其适应不同的应用场景。

STL中有三种常见的容器适配器stack、queue和priority_queue。

虽然stack和queue中也可以存放元素但在STL中并没有将其划分在容器的行列而是将其称为容器适配器这是因为stack和队列只是对其他容器的接口进行了包装STL中stack和queue默认使用deque比如

stack是一种容器适配器专门用在具有后进先出操作的上下文环境中其删除只能从容器的一端进行元素的插入与提取操作。

stack是作为容器适配器被实现的容器适配器即是对特定类封装作为其底层的容器并提供一组特定的成员函数来访问其元素将特定类作为其底层的元素特定容器的尾部(即栈顶)被压入和弹出。

stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类这些容器类应该支持以下操作

empty判空操作

标准容器vector、deque、list均符合这些需求默认情况下如果没有为stack指定特定的底层容器

当你使用

将元素压入栈顶myStack.push(10);myStack.push(20);myStack.push(30);std::cout

栈顶元素:

ano***rStack;ano***rStack.push(50);myStack.swap(ano***rStack);

交换后

{_con.swap(st._con);}private:Container

_con;};

队列是一种容器适配器专门用于在FIFO上下文(先进先出)中操作其中从容器一端插入元素另一端

队列作为容器适配器实现容器适配器即将特定容器类封装作为其底层容器类queue提供一组特定的

底层容器可以是标准容器类模板之一也可以是其他专门设计的容器类。

该底层容器应至少支持以下操作:

push_back在队列尾部入队列

标准容器类deque和list满足了这些要求。

默认情况下如果没有为queue实例化指定容器类则使用标

push(const

向队列尾部添加元素myQueue.push(10);myQueue.push(20);myQueue.push(30);std::cout

队列头部元素:

ano***rQueue;ano***rQueue.push(50);myQueue.swap(ano***rQueue);

交换后

{_con.push_back(x);}//队头出队列void

pop()

_con.back();}//获取队列中有效元素个数size_t

size()

{_con.swap(q._con);}private:Container

_con;};

用于实现优先队列数据结构。

优先队列是一种特殊的队列其中的元素按照一定的优先级顺序进行排列而不是按照插入的顺序。

std::priority_queue

使用堆heap数据结构来维护元素的顺序通常用于需要按照一定规则获取最高优先级元素的场景。

在默认情况下std::priority_queue

会以降序排列元素即最大的元素会被放置在队列的前面。

你也可以通过提供自定义的比较函数来改变排序顺序。

构造函数

greater实现最小堆std::priority_queueint,

std::vectorint,

operatorstd::priority_queuestd::string

pq3;//

q;q.push(3);q.push(6);q.push(0);q.push(2);q.push(9);q.push(8);q.push(1);while

(!q.empty()){cout

你可以通过提供自定义的比较函数来改变元素的排序顺序。

比较函数应该返回

struct

priority_queue的底层实际上就是堆结构实现priority_queue之前我们先认识两个重要的堆算法。

下面这两种算法我们均以大堆为例

以大堆为例堆的向上调整算法就是在大堆的末尾插入一个数据后经过一系列的调整使其仍然是一个大堆。

2、若目标结点的值比父结点的值大则交换目标结点与其父结点的位置并将原目标结点的父结点当作新的目标结点继续进行向上调整若目标结点的值比其父结点的值小则停止向上调整此时该树已经是大堆了。

我们先将88与其父结点54进行比较发现88比其父结点大则交换父子结点的数据并继续进行向上调整。

此时将88与其父结点87进行比较发现88还是比其父结点大则继续交换父子结点的数据并继续进行向上调整。

这时再将88与其父结点89进行比较发现88比其父结点小则停止向上调整此时该树已经就是大堆了。

void

以大堆为例使用堆的向下调整算法有一个前提就是待向下调整的结点的左子树和右子树必须都为大堆。

2、若目标结点的值比其较大的子结点的值小则交换目标结点与其较大的子结点的位置并将原目标结点的较大子结点当作新的目标结点继续进行向下调整若目标结点的值比其较大子结点的值大则停止向下调整此时该树已经是大堆了。

例如将该二叉树从根结点开始进行向下调整。

此时根结点的左右子树已经是大堆

将60与其较大的子结点88进行比较发现60比其较大的子结点小则交换这两个结点的数据并继续进行向下调整。

此时再将60与其较大的子结点87进行比较发现60比其较大的子结点小则再交换这两个结点的数据并继续进行向下调整。

这时再将60与其较大的子结点54进行比较发现60比其较大的子结点大则停止向下调整此时该树已经就是大堆了。

void

优先级队列使用vector作为其底层存储数据的容器priority_queue就是堆

iostream

仿函数greater(使内部结构为小堆)templateclass

Tstruct

{_con.push_back(x);AdjustUp(_con.size()

1);//

1]);_con.pop_back();AdjustDown(_con.size(),

0);//

_con.empty();}private:Container

_con;//

1]);_con.pop_back();AdjustDown(_con.size(),

0);//

_con.empty();}private:Container

_con;//