做网站有什么用出,wordpress 菜单颜色,wordpress验证邮箱验证,网站开发对企业有什么用欢迎来到我的Blog#xff0c;点击关注哦#x1f495;
前言 string vector list 这种线性结构是最基础的存储结构#xff0c;C#xff08;STL#xff09;container很好的帮助我们数据存储的问题。 容器适配器
介绍
容器适配器是C标准模板库#xff08;STL#xff09;中…欢迎来到我的Blog点击关注哦
前言 string vector list 这种线性结构是最基础的存储结构CSTLcontainer很好的帮助我们数据存储的问题。 容器适配器
介绍
容器适配器是C标准模板库STL中的一种设计模式它允许将一个容器的接口转换为另一个接口从而提供不同的操作和行为。容器适配器通常用于封装现有容器以实现特定的数据结构特性如栈后进先出、队列先进先出和优先队列根据优先级排序。
应用 栈stack栈是一种后进先出的数据结构其操作包括入栈push、出栈pop、查看栈顶元素top等。栈适配器可以基于多种底层容器实现如vector、deque或list. 队列queue队列是一种先进先出的数据结构其操作包括入队push、出队pop、查看队首元素front和查看队尾元素back。队列适配器同样可以基于deque或list实现以适应不同的性能需求. 优先队列priority_queue优先队列是一种特殊的队列它根据元素的优先级进行排序。其底层容器通常是vector或deque并通过堆算法维护元素的优先级顺序。优先队列适配器提供了插入和删除具有最高优先级元素的操作.
双重结束队列双端队列deque
特点
双端操作效率支持在两端进行快速的插入和删除操作。随机访问可以通过索引直接访问容器中的元素。无需预先分配固定大小与vector不同deque不需要在创建时指定大小它可以根据需要动态增长。内存分配策略deque不需要像vector那样一次性分配大量内存而是分散在内存中这有助于减少内存碎片。
存储结构
双端队列底层是一段假象的连续空间实际是分段连续的为了维护其“整体连续”以及随机访问的假象落 在了deque的迭代器身上因此deque的迭代器设计就比较复杂如下图所示 List 、vector deque对比
对比维度VectorDequeList内存连续性是否否随机访问性能O(1)O(1) 但可能不如VectorO(n)插入/删除性能非末尾O(n)两端O(1), 中间O(n)两端及中间O(1)内存重用效率扩容时需移动元素两端添加删除不需移动不适用内存分配模式动态数组连续内存分段连续内存非连续内存迭代器失效可能不会不会支持的操作[] 访问、.at() 等[] 访问、.at() 等[] 访问、.at() 等内存管理开销高扩容时中等两端操作低适用场景需要快速随机访问且元素数量稳定需要两端快速插入删除随机访问需求适中频繁插入删除不关心随机访问
栈stack
栈的介绍
函数说明接口说明stack()构造空的栈empty()检测stack是否为空size()返回stack中元素的个数top()返回栈顶元素的引用push()将元素val压入stack中pop()将stack中尾部的元素弹出
栈的模拟实现
利用容器适配器的设计原理很容易实现栈
将栈放mystack的命名空间以防止和库中冲突类模板设计container可以给缺省参数默认deque(容器适配器)在里面利用deque的接口实现
namespace mystack
{templateclass T, class Container std::dequeTclass stack{public:void push_back(const T x){_con.push_back(x);}void pop(){_con.pop_back();}size_t size(){return _con.size();}T top(){return _con.back();}bool empty(){return _con.empty();}private:Container _con;};
}队列
队列介绍
函数声明接口说明queue()构造空的队列empty()检测队列是否为空是返回true否则返回falsesize()返回队列中有效元素的个数front()返回队头元素的引用back()返回队尾元素的引用push()在队尾将元素val入队列pop()将队头元素出队列
队列模拟实现
将栈放myqueue的命名空间以防止和库中冲突类模板设计container可以给缺省参数默认deque(容器适配器)在里面利用deque的接口实现
namespace myqueue
{templateclass T, class Container std::dequeT class queue{public:void push(const T x){_con.push_back(x);}void pop(){_con.pop_front();}size_t size(){return _con.size();}T front(){return _con.front();}bool empty(){return _con.empty();}private:Container _con;};
}优先级队列priority_queue
基本原理
优先级队列通常在内部使用堆数据结构来维护元素的优先级。堆是一种完全二叉树可以是最大堆或最小堆。在最大堆中父节点的值总是大于或等于其子节点的值而在最小堆中父节点的值总是小于或等于其子节点的值。插入操作通过在堆的适当位置插入新元素并进行上调整heapify-up来维持堆的性质。删除操作则涉及到移除堆顶元素优先级最高的元素并进行下调整heapify-down以恢复堆的结构。
priority_queue介绍
函数声明接口说明priority_queue()/priority_queue(first, last)构造一个空的优先级队列empty( )检测优先级队列是否为空是返回true否则返回 falsetop( )返回优先级队列中最大(最小元素)即堆顶元素push(x)在优先级队列中插入元素xpop()删除优先级队列中最大(最小)元素即堆顶元素
优先级模拟实现 可以参考
仿函数
仿函数Functor是C中的一个编程概念它指的是一个类或结构体通过重载函数调用运算符operator()使得这个类或结构体的对象可以像函数一样被调用。仿函数可以包含状态因为它们是对象可以在构造函数中初始化状态并在operator()中使用该状态。仿函数可以作为参数传递给其他函数包括STL算法中的函数从而提供灵活的编程模型.
这个就是一个仿函数
//小于
templateclass Tclass Less{public:bool operator()(const T a,const T b){return a b;}};
//大于
templateclass Tclass Greater{public:bool operator()(const T x, const T y){return x y;}};priority_queue两个关键
向下建堆
确定起始点从最后一个非叶子节点开始向下建堆这个节点也被称为堆的最后一个非叶子节点。在完全二叉树中最后一个非叶子节点的索引可以通过 (n - 1 - 1) / 2 计算得到其中 n 是数组的长度。执行向下调整对每个非叶子节点执行向下调整操作确保该节点与其子节点组成的子树满足堆的性质。向下调整的过程涉及到与子节点的比较和必要时的交换直至到达堆的顶部或直到父节点不再违反堆的性质。迭代过程从最后一个非叶子节点开始逐步向上调整直到根节点。每次调整后更新当前节点的索引以便进行下一次调整。完成建堆重复步骤2和步骤3直到根节点也满足堆的性质此时整个数组就构建成了一个堆。
void AdjustDown(size_t parent)
{compare com;//仿函数size_t child parent * 2 1;//if (child1 _con.size() _con[child] _con[1child])if (child 1 _con.size() com(_con[child] ,_con[1 child]))//和上面等价{child;}while (child _con.size()){if (com(_con[parent], _con[child])){std::swap(_con[child], _con[parent]);parent child;child parent * 2 1;}else{break;}}
}向上建堆
初始化堆大小**设置堆的大小为数组的大小即 n。从最后一个非叶子节点开始向上调整在完全二叉树中最后一个非叶子节点的索引为 floor((n - 1) / 2)。从这个节点开始向上调整确保每个节点都满足大根堆的性质。执行向上调整操作对于每个非叶子节点检查其与子节点的关系并进行必要的交换以确保父节点的值大于或等于其子节点的值。如果子节点中有一个或两个选择较大的子节点与父节点进行比较。如果父节点的值小于子节点的值交换它们的位置并重新设置父节点为当前子节点继续向上调整。重复步骤2和3直到达到根节点即堆的第一个元素。
void AdjustUp(int child)
{compare com;int 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;}}}初始化数据
迭代器初始化 模板嵌套给迭代器初始化 依次push数据在进行堆的建立
templateclass InputIterator
void push_back(InputIterator first, InputIterator last){while (first ! last){_con.push_back(*first);first;}//向下建堆for (int i (_con.size() - 2) / 2; i 0; i--){AdjustDown(i);}}pop数据
将一个个数据和最后一个数据进行交换目的保持当前堆的结构pop出数据将第一个数据进行向下调整
void pop()
{swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);
}push数据
将数据进行尾插入进行向上调整
void push(const T x)
{_con.push_back(x);AdjustUp(_con.size() - 1);
}priority_queue operators
top数据返回首个数据其他常见操作采取容器适配器设计模式的操作
namespace mypriority_queue
{templateclass T, class container std::vectorT,class compare LessTclass priority_queue{public:const T top(){return _con[0];}size_t szie(){return _con.size();}bool empty(){return _con.empty();}private:container _con;};}源码优先级队列
namespace mypriority_queue
{templateclass Tclass Less{public:bool operator()(const T a,const T b){return a b;}};templateclass Tclass Greater{public:bool operator()(const T x, const T y){return x y;}};templateclass T, class container std::vectorT,class compare LessTclass priority_queue{void AdjustDown(size_t parent){compare com;size_t child parent * 2 1;//if (child1 _con.size() _con[child] _con[1child])if (child 1 _con.size() com(_con[child] ,_con[1 child])){child;}while (child _con.size()){if (com(_con[parent], _con[child])){std::swap(_con[child], _con[parent]);parent child;child parent * 2 1;}else{break;}}}void AdjustUp(int child){compare com;int 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;}}}public:templateclass InputIteratorvoid push_back(InputIterator first, InputIterator last){while (first ! last){_con.push_back(*first);first;}//向下建堆for (int i (_con.size() - 2) / 2; i 0; i--){AdjustDown(i);}}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}const T top(){return _con[0];}void push(const T x){_con.push_back(x);AdjustUp(_con.size() - 1);}size_t szie(){return _con.size();}bool empty(){return _con.empty();}private:container _con;};}向下建堆 for (int i (_con.size() - 2) / 2; i 0; i–) { AdjustDown(i); } } void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}const T top(){return _con[0];}void push(const T x){_con.push_back(x);AdjustUp(_con.size() - 1);}size_t szie(){return _con.size();}bool empty(){return _con.empty();}private:container _con;
};}
