网站架构软件,网站上线多久才能百度,vi设计公司有哪些,wordpress 外链转内链1.容器适配器
适配器是一种设计模式#xff0c;该种模式是将一个类的接口转换成客户希望的另外一个接口。
容器适配器是STL中的一种重要组件#xff0c;用于提供不同的数据结构接口#xff0c;以满足特定的需求和限制。容器适配器是基于其他STL容器构建的#xff0c;通过…1.容器适配器
适配器是一种设计模式该种模式是将一个类的接口转换成客户希望的另外一个接口。
容器适配器是STL中的一种重要组件用于提供不同的数据结构接口以满足特定的需求和限制。容器适配器是基于其他STL容器构建的通过改变其接口和行为使其适应不同的应用场景。
STL中有三种常见的容器适配器stack、queue和priority_queue。
虽然stack和queue中也可以存放元素但在STL中并没有将其划分在容器的行列而是将其称为容器适配器这是因为stack和队列只是对其他容器的接口进行了包装STL中stack和queue默认使用deque比如 而priority_queue默认使用vector 2.stack的介绍和使用
stack的介绍 stack是一种容器适配器专门用在具有后进先出操作的上下文环境中其删除只能从容器的一端进行元素的插入与提取操作。 stack是作为容器适配器被实现的容器适配器即是对特定类封装作为其底层的容器并提供一组特定的成员函数来访问其元素将特定类作为其底层的元素特定容器的尾部(即栈顶)被压入和弹出。 stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类这些容器类应该支持以下操作 empty判空操作 back获取尾部元素操作 push_back尾部插入元素操作 pop_back尾部删除元素操作 标准容器vector、deque、list均符合这些需求默认情况下如果没有为stack指定特定的底层容器 默认情况下使用deque。 stack的使用
当你使用 std::stack 时你可以使用以下一些重要的成员函数
push(const T value): 将元素 value 压入栈顶。pop(): 弹出栈顶元素不返回其值。top(): 返回栈顶元素的引用但不将其从栈中移除。size(): 返回栈中元素的数量。empty(): 检查栈是否为空返回布尔值。swap(stack other): 将当前栈与另一个栈 other 进行交换。
#include iostream
#include stackint main() {std::stackint myStack;// 将元素压入栈顶myStack.push(10);myStack.push(20);myStack.push(30);std::cout 栈顶元素: myStack.top() std::endl; // 输出30std::cout 栈的大小: myStack.size() std::endl; // 输出3myStack.pop(); // 弹出栈顶元素if (!myStack.empty()) {std::cout 弹出元素后的栈顶元素: myStack.top() std::endl; // 输出20}std::stackint anotherStack;anotherStack.push(50);myStack.swap(anotherStack); // 交换两个栈的内容std::cout 交换后 myStack 的大小: myStack.size() std::endl; // 输出1return 0;
}stack的模拟实现
#pragma once
#include dequenamespace phw {templateclass T, class Container std::dequeTclass 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();}size_t size() const {return _con.size();}bool empty() const {return _con.empty();}void swap(stackT, Container st) {_con.swap(st._con);}private:Container _con;};
}// namespace phw3.queue的介绍和使用
queue的介绍 队列是一种容器适配器专门用于在FIFO上下文(先进先出)中操作其中从容器一端插入元素另一端 提取元素。 队列作为容器适配器实现容器适配器即将特定容器类封装作为其底层容器类queue提供一组特定的 成员函数来访问其元素。元素从队尾入队列从队头出队列。 底层容器可以是标准容器类模板之一也可以是其他专门设计的容器类。该底层容器应至少支持以下操作: empty检测队列是否为空 size返回队列中有效元素的个数 front返回队头元素的引用 back返回队尾元素的引用 push_back在队列尾部入队列 pop_front在队列头部出队列 标准容器类deque和list满足了这些要求。默认情况下如果没有为queue实例化指定容器类则使用标 准容器deque。
queue的使用
push(const T value): 将元素 value 添加到队列的尾部。pop(): 弹出队列的头部元素不返回其值。front(): 返回队列头部元素的引用。back(): 返回队列尾部元素的引用。size(): 返回队列中元素的数量。empty(): 检查队列是否为空。swap(queue other): 交换两个队列的内容。
示例
#include iostream
#include queueint main() {std::queueint myQueue;// 向队列尾部添加元素myQueue.push(10);myQueue.push(20);myQueue.push(30);std::cout 队列头部元素: myQueue.front() std::endl; // 输出10std::cout 队列尾部元素: myQueue.back() std::endl; // 输出30std::cout 队列大小: myQueue.size() std::endl; // 输出3myQueue.pop(); // 弹出队列头部元素std::cout 弹出元素后的队列头部元素: myQueue.front() std::endl; // 输出20std::queueint anotherQueue;anotherQueue.push(50);myQueue.swap(anotherQueue); // 交换两个队列的内容std::cout 交换后 myQueue 的大小: myQueue.size() std::endl; // 输出1return 0;
}queue的模拟实现
#pragma once
#include dequenamespace phw//防止命名冲突
{templateclass T, class Container std::dequeTclass queue {public://队尾入队列void push(const T x) {_con.push_back(x);}//队头出队列void pop() {_con.pop_front();}//获取队头元素T front() {return _con.front();}const T front() const {return _con.front();}//获取队尾元素T back() {return _con.back();}const T back() const {return _con.back();}//获取队列中有效元素个数size_t size() const {return _con.size();}//判断队列是否为空bool empty() const {return _con.empty();}//交换两个队列中的数据void swap(queueT, Container q) {_con.swap(q._con);}private:Container _con;};
}// namespace phw4.priority_queue的介绍和使用
priority_queue的介绍
std::priority_queue 用于实现优先队列数据结构。优先队列是一种特殊的队列其中的元素按照一定的优先级顺序进行排列而不是按照插入的顺序。
std::priority_queue 使用堆heap数据结构来维护元素的顺序通常用于需要按照一定规则获取最高优先级元素的场景。在默认情况下std::priority_queue 会以降序排列元素即最大的元素会被放置在队列的前面。你也可以通过提供自定义的比较函数来改变排序顺序。
priority_queue的使用
构造函数
默认构造函数 创建一个空的优先队列。
std::priority_queueT pq; // 创建一个空的优先队列T 是元素类型带有比较函数的构造函数 可以指定一个自定义的比较函数用于确定元素的优先级顺序。
std::priority_queueT, Container, Compare pq;T 是元素类型。Container 是底层容器类型默认情况下使用 std::vector。Compare 是比较函数类型用于确定元素的顺序。默认情况下使用 operator 来比较元素。
示例
#include iostream
#include queueint main() {// 构造一个默认的优先队列元素类型为 int使用默认比较函数 operatorstd::priority_queueint pq1;// 构造一个优先队列元素类型为 int使用自定义的比较函数 greater实现最小堆std::priority_queueint, std::vectorint, std::greaterint pq2;// 构造一个优先队列元素类型为 std::string使用默认比较函数 operatorstd::priority_queuestd::string pq3;// 构造一个优先队列元素类型为 double使用 lambda 表达式作为比较函数实现最大堆auto cmp [](double a, double b) { return a b; };std::priority_queuedouble, std::vectordouble, decltype(cmp) pq4(cmp);return 0;
}成员函数 push() 向优先队列中插入元素。 pq.push(value); // 插入元素 valuepop() 移除队列顶部的元素即最高优先级元素。 pq.pop(); // 移除队列顶部元素top() 获取队列顶部的元素即最高优先级元素。 T highestPriority pq.top(); // 获取最高优先级元素empty() 检查队列是否为空。 bool isEmpty pq.empty(); // 如果队列为空则返回 true否则返回 falsesize() 获取队列中的元素数量。 int numElements pq.size(); // 获取队列中的元素数量示例
#include iostream
#include functional
#include queue
using namespace std;
int main(){priority_queueint 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 q.top() ;q.pop();}cout endl; //9 8 6 3 2 1 0return 0;
}自定义比较函数
你可以通过提供自定义的比较函数来改变元素的排序顺序。比较函数应该返回 true如果第一个参数应该排在第二个参数之前。
struct MyComparator {bool operator()(const T a, const T b) {// 自定义比较逻辑}
};std::priority_queueT, Container, MyComparator pq;priority_queue的模拟实现
priority_queue的底层实际上就是堆结构实现priority_queue之前我们先认识两个重要的堆算法。下面这两种算法我们均以大堆为例
堆的向上调整算法 以大堆为例堆的向上调整算法就是在大堆的末尾插入一个数据后经过一系列的调整使其仍然是一个大堆。
调整的基本思想如下 1、将目标结点与其父结点进行比较。 2、若目标结点的值比父结点的值大则交换目标结点与其父结点的位置并将原目标结点的父结点当作新的目标结点继续进行向上调整若目标结点的值比其父结点的值小则停止向上调整此时该树已经是大堆了。 例如现在我们在该大堆的末尾插入数据88。 我们先将88与其父结点54进行比较发现88比其父结点大则交换父子结点的数据并继续进行向上调整。 此时将88与其父结点87进行比较发现88还是比其父结点大则继续交换父子结点的数据并继续进行向上调整。 这时再将88与其父结点89进行比较发现88比其父结点小则停止向上调整此时该树已经就是大堆了。 堆的向上调整算法代码
void AdjustUp(int child) {int parent (child - 1) / 2;while (child 0) {// 默认less 也就是parentchildif (_comp(_con[parent], _con[child]))// 通过所给比较方式确定是否需要交换结点位置{// 将父结点与孩子结点交换swap(_con[child], _con[parent]);// 继续向上进行调整child parent;parent (child - 1) / 2;} else// 已成堆{break;}}
}堆的向下调整算法
以大堆为例使用堆的向下调整算法有一个前提就是待向下调整的结点的左子树和右子树必须都为大堆。 调整的基本思想如下 1、将目标结点与其较大的子结点进行比较。 2、若目标结点的值比其较大的子结点的值小则交换目标结点与其较大的子结点的位置并将原目标结点的较大子结点当作新的目标结点继续进行向下调整若目标结点的值比其较大子结点的值大则停止向下调整此时该树已经是大堆了。 例如将该二叉树从根结点开始进行向下调整。此时根结点的左右子树已经是大堆 将60与其较大的子结点88进行比较发现60比其较大的子结点小则交换这两个结点的数据并继续进行向下调整。 此时再将60与其较大的子结点87进行比较发现60比其较大的子结点小则再交换这两个结点的数据并继续进行向下调整。 这时再将60与其较大的子结点54进行比较发现60比其较大的子结点大则停止向下调整此时该树已经就是大堆了。 堆的向下调整算法代码
void AdjustDown(int n, int parent) {int child 2 * parent 1;while (child n) {//_comp(_con[child], _con[child 1])表示childchild1if (child 1 n _comp(_con[child], _con[child 1])) {child;}// parentchildif (_comp(_con[parent], _con[child]))// 通过所给比较方式确定是否需要交换结点位置{// 将父结点与孩子结点交换swap(_con[child], _con[parent]);// 继续向下进行调整parent child;child 2 * parent 1;} else// 已成堆{break;}}
}模拟实现代码
// 优先级队列使用vector作为其底层存储数据的容器priority_queue就是堆
// 默认情况是大堆#include iostream
#include vector
using namespace std;
namespace phw {// 仿函数less(使内部结构为大堆)templateclass Tstruct less {bool operator()(const T x, const T y) {return x y;}};// 仿函数greater(使内部结构为小堆)templateclass Tstruct greater {bool operator()(const T x, const T y) {return x y;}};// 优先级队列templateclass T, class Container vectorT, class Compare greaterTclass priority_queue {public:// 堆的向上调整void AdjustUp(int child) {int parent (child - 1) / 2;while (child 0) {// 默认less 也就是parentchildif (_comp(_con[parent], _con[child]))// 通过所给比较方式确定是否需要交换结点位置{// 将父结点与孩子结点交换swap(_con[child], _con[parent]);// 继续向上进行调整child parent;parent (child - 1) / 2;} else// 已成堆{break;}}}// 堆的向下调整void AdjustDown(int n, int parent) {int child 2 * parent 1;while (child n) {//_comp(_con[child], _con[child 1])表示childchild1if (child 1 n _comp(_con[child], _con[child 1])) {child;}// parentchildif (_comp(_con[parent], _con[child]))// 通过所给比较方式确定是否需要交换结点位置{// 将父结点与孩子结点交换swap(_con[child], _con[parent]);// 继续向下进行调整parent child;child 2 * parent 1;} else// 已成堆{break;}}}// 插入元素到队尾并排序void push(const T x) {_con.push_back(x);AdjustUp(_con.size() - 1);// 将最后一个元素进行一次向上调整}// 弹出队头元素堆顶元素void pop() {swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(_con.size(), 0);// 将第0个元素进行一次向下调整}// 访问队头元素堆顶元素T top() {return _con[0];}const T top() const {return _con[0];}// 获取队列中有效元素个数size_t size() const {return _con.size();}// 判断队列是否为空bool empty() const {return _con.empty();}private:Container _con;// vector容器Compare _comp; // 比较方式};
}// namespace phw
(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(_con.size(), 0);// 将第0个元素进行一次向下调整}// 访问队头元素堆顶元素T top() {return _con[0];}const T top() const {return _con[0];}// 获取队列中有效元素个数size_t size() const {return _con.size();}// 判断队列是否为空bool empty() const {return _con.empty();}private:Container _con;// vector容器Compare _comp; // 比较方式};
}// namespace phw
