做网站要找什么软件,建一个自己的网站价格,凡科网站是骗子,做实验教学视频的网站目录
一、详解 C STL 容器适配器
1.1 - 什么是容器适配器#xff1f;
1.2 - 容器适配器的种类
二、详解 C STL deque 容器
2.1 - deque 的原理介绍
2.2 - deque 的优缺点
三、详解 stack 容器适配器
3.1 - stack 的基本介绍
3.2 - stack 的成员函数
3.3 - stack 的模…目录
一、详解 C STL 容器适配器
1.1 - 什么是容器适配器
1.2 - 容器适配器的种类
二、详解 C STL deque 容器
2.1 - deque 的原理介绍
2.2 - deque 的优缺点
三、详解 stack 容器适配器
3.1 - stack 的基本介绍
3.2 - stack 的成员函数
3.3 - stack 的模拟实现
四、详解 queue 容器适配器
4.1 - queue 的基本介绍
4.2 - queue 的成员函数
4.3 - queue 的模拟实现
五、详解 priority_queue 容器适配器
5.1 - priority_queue 的基本介绍
5.2 - priority_queue 的成员函数
5.3 - priority_queue 的模拟实现 一、详解 C STL 容器适配器
1.1 - 什么是容器适配器
在详解什么是容器适配器之前初学者首先要理解适配器的含义。
其实容器适配器中的 适配器和生活中常见的电源适配器中的 适配器 的含义非常接近。我们知道无论是电脑、手机还是其它电器充电时都无法直接使用 220V 的交流电为了方便用户使用各个电器厂商都会提供一个适用于自己产品的电源适配器它可以将 220V 的交流电转换成适合电器使用的低压直流电。
具有多种功能的电源适配器可以满足多种需求 因此简单理解容器适配器就是将不适用的序列式容器包括 vector、deque 和 list变得适用。容器适配器的底层即通过封装某个序列式容器并重新组合该容器中包含的成员函数使其满足特定场景的需要。
容器适配器本质上还是容器只不过此容器类模板的实现利用了大量其他基础容器类模板中已经写好的成员函数。当然如果必要的话容器适配器中也可以自创新的成员函数。
需要注意的是STL 中的容器适配器其内部使用的基础容器并不是固定的用户可以在满足特定条件的多个基础容器中自由选择。 1.2 - 容器适配器的种类
STL 提供了 3 种容器适配器分别为 stack 栈适配器、queue 队列适配器以及 priority_queue 优先权队列适配器
容器适配器基础容器需要包含的成员函数满足条件的基础容器默认使用的基础容器stackempty()、size()、back()、push_back()、pop_back()vector、deque、listdequequeueempty()、size()、front()、back()、push_back()、pop_front()deque、listdequepriority_queueempty()、size()、front()、push_back()、pop_back()vector、dequevector 因为删除 vector 容器的头部元素需要移动大量元素效率较低所以 vector 容器没有提供 pop_front 成员函数因此其不能作为 queue 的基础容器。 因为 list 容器不支持随机访问所以其不能作为 priority_queue 的基础容器。 由于不同的序列式容器其底层采用的数据结构不同因此容器适配器的执行效率也不尽相同但通常情况下使用默认的基础容器即可。 二、详解 C STL deque 容器
2.1 - deque 的原理介绍
deque 是 double-ended queue 的缩写又称双端队列容器。
deque 容器和 vector 容器有很多相似的地方例如deque 容器也擅长在序列尾部插入或删除元素时间复杂度为 O(1) 常数阶而不擅长在序列中间添加或删除元素。和 vector 不同的是deque 还擅长在序列头部插入或删除元素时间复杂度也为 O(1) 常数阶并且更重要的一点是deque 并不是连续的空间而是由一段段小空间拼接而成的实际 deque 类似于一个动态二维数组其底层结构如下图所示
‘ 双端队列底层是一段假象的连续空间实际是分段连续的为了维护其 整体连续 以及随机访问的假象重任就落在了 deque 的迭代器身上因此 deque 的迭代器设计就比较复杂如下图所示 那 deque 是如何借助其迭代器维护其假象连续的结构呢 2.2 - deque 的优缺点
和 vector 相比deque 的优点在头部插入和删除元素时不需要移动元素效率较高而且在扩容时也不需要移动大量的元素。
和 list 相比deque 的优点空间利用率较高不需要存储额外字段。
但是deque 有一个致命缺点不适合遍历因为在遍历时deque 的迭代器要频繁地去检测是否移动到某段小空间的边界导致效率低下而序列式场景中可能需要经常遍历因此在实际中需要线性结构时大多数情况下优先考虑 vector 和 listdeque 的应用场景并不多而目前看到的一个应用就是STL 用其作为 stack 和 queue 的默认基础容器因为 stack 和 queue 不需要遍历因此 stack 和 queue 没有迭代器只需要在固定的一端或两端进行操作 在 stack 元素增长时deque 比 vector 的效率高扩容时不需要移动大量元素queue 中的元素增长时deque 不仅效率高而且空间利用率高。
即利用了 deque 的优点而完美地避开了其缺点。 三、详解 stack 容器适配器
3.1 - stack 的基本介绍
stack 以类模板的形式定义在 stack 头文件中并位于 std 命名空间中。
template class T, class Container dequeT class stack;
stack 是一种容器适配器专门设计用于在后进先出LIFOlast-in first-out的环境中使用元素只能从容器的一端进行插入和删除。 3.2 - stack 的成员函数
构造函数
explicit stack(const container_type ctnr container_type()); 注意container_type 等价于 Container。 构造一个 stack 容器适配器对象。 empty
bool empty() const;
size
size_type size() const;
top value_type top();
const value_type top() const;
push
void push(const value_type val);
pop
void pop();
示例
#include iostream
#include stack
using namespace std;
int main()
{stackint st;st.push(1);st.push(2);st.push(3);st.push(4);cout st.size() endl; // 4while (!st.empty()){cout st.top() ;st.pop();}// 4 3 2 1cout endl;return 0;
} 3.3 - stack 的模拟实现
#pragma once
#include deque
namespace yzz
{templateclass T, class Container std::dequeTclass stack{public:bool empty() const{return _ctnr.empty();}
size_t size() const{return _ctnr.size();}
T top(){return _ctnr.back();}
const T top() const{return _ctnr.back();}
void push(const T val){_ctnr.push_back(val);}
void pop(){_ctnr.pop_back();}private:Container _ctnr;};
} 四、详解 queue 容器适配器
4.1 - queue 的基本介绍
queue 以类模板的形式定义在 queue 头文件中并位于 std 命名空间中。
template class T, class Container dequeT class queue;
queue 是一种容器适配器专门设计用于在先进先出FIFOfirst-in first-out的环境中使用元素只能从容器的一端插入并从另一端删除。 4.2 - queue 的成员函数
构造函数
explicit queue(const container_type ctnr container_type());
empty
bool empty() const;
size
size_type size() const;
front value_type front();
const value_type front() const;
back value_type back();
const value_type back() const;
push
void push(const value_type val);
pop
void pop();
示例
#include iostreamm
#include queue
using namespace std;
int main()
{queueint q;q.push(1);q.push(2);q.push(3);q.push(4);cout q.size() endl; // 4cout q.front() q.back() endl; // 1 4while (!q.empty()){cout q.front() ;q.pop();}// 1 2 3 4cout endl;return 0;
} 4.3 - queue 的模拟实现
#pragma once
#include deque
namespace yzz
{templateclass T, class Container std::dequeTclass queue{public:bool empty() const{return _ctnr.empty();}
size_t size() const{return _ctnr.size();}
T front(){return _ctnr.front();}
const T front() const{return _ctnr.front();}
T back(){return _ctnr.back();}
const T back() const{return _ctnr.back();}
void push(const T val){_ctnr.push_back(val);}
void pop(){_ctnr.pop_front();}private:Container _ctnr;};
} 五、详解 priority_queue 容器适配器
5.1 - priority_queue 的基本介绍
priority_queue 以类模板的形式定义在queue 头文件中并位于 std 命名空间中。
template class T, class Container vectorT, class Compare lessT
class priority_queue;
priority_queue 是一种容器适配器其模拟的也是队列这种存储结构即使用此容器适配器存储元素只能从一进称为队尾从另一端出称为队头且每次只能访问 priority_queue 中位于队头的元素。
但是priority_queue 容器适配器中元素的存和取遵循的并不是 first-in first-out先进先出原则而是 first-in largest-out 原则即先进队列的元素不一定先出队列而是优先级最大的元素先出队列。
priority_queuue 容器适配器的 first-in largest-out 特性和它底层采用堆heap结构存储数据是分不开的注意priority_queue 默认情况下是大根堆。 5.2 - priority_queue 的成员函数
构造函数
initialize (1) explicit priority_queue(const Compare Cmp Compare(), const Container ctnr Container());range (2) template class InputIteratorpriority_queue(InputIterator first, InputIterator last,const Compare Cmp Compare(), const Container ctnr Container()));
empty
bool empty() const;
size
size_type size() const;
top
const value_type top() const;
push
void push(const value_type val);
pop
void pop();
示例一
#include iostream
#include queue
using namespace std;
int main()
{priority_queueint pq;pq.push(30);pq.push(100);pq.push(25);pq.push(40);cout pq.size() endl; // 4while (!pq.empty()){cout pq.top() ;pq.pop();}// 100 40 30 25cout endl;return 0;
}
示例二 - 如果 priority_queue 中存储的是自定义类型的数据用户则需要在自定义类型中提供 和 的重载
#include iostream
#include queue
using namespace std;
class Date
{friend ostream operator(ostream out, const Date d);
public:Date(int year 1949, int month 10, int day 1): _year(year), _month(month), _day(day){ }
bool operator(const Date d) const{return (_year d._year)|| (_year d._year _month d._month)|| (_year d._year _month d._month _day d._day);}
bool operator(const Date d) const{return (_year d._year)|| (_year d._year _month d._month)|| (_year d._year _month d._month _day d._day);}
private:int _year;int _month;int _day;
};
ostream operator(ostream out, const Date d)
{return out d._year - d._month - d._day;
}
int main()
{priority_queueDate, vectorDate, greaterDate pq;pq.push(Date(2023, 5, 1));pq.push(Date(2023, 7, 1));pq.push(Date(2023, 6, 1));pq.push(Date(2023, 4, 1));cout pq.size() endl; // 4while (!pq.empty()){cout pq.top() ;pq.pop();}// 2023-4-1 2023-5-1 2023-6-1 2023-7-1cout endl;return 0;
} 5.3 - priority_queue 的模拟实现
#pragma once
#include vector
#include assert.h
namespace yzz
{// 函数对象仿函数类templateclass Tstruct less{bool operator()(const T left, const T right){return left right;}};
templateclass Tstruct greater{bool operator()(const T left, const T right){return left right;}};
// priority_queue 容器适配器templateclass T, class Container std::vectorT, class Compare lessTclass priority_queue{private:void AdjustUp(int child){Compare cmp;int parent (child - 1) / 2;while (child 0){if (cmp(_ctnr[parent] ,_ctnr[child])){std::swap(_ctnr[parent], _ctnr[child]);child parent;parent (child - 1) / 2;}else{break;}}}
void AdjustDown(int parent){Compare cmp;int sz _ctnr.size();int child 2 * parent 1; // 双亲节点默认和其左孩子进行比较while (child sz){if (child 1 sz cmp(_ctnr[child] ,_ctnr[child 1])){child; // 改为让双亲节点和其右孩子进行比较}
if (cmp(_ctnr[parent] ,_ctnr[child])){std::swap(_ctnr[parent], _ctnr[child]);parent child;child 2 * parent 1;}else{break;}}}
public:priority_queue() { }
templateclass InputIteratorpriority_queue(InputIterator first, InputIterator last){while (first ! last){push(*first);first;}}
bool empty() const{return _ctnr.empty();}
size_t size() const{return _ctnr.size();}
const T top() const{return _ctnr.front();}
void push(const T val){_ctnr.push_back(val);AdjustUp(_ctnr.size() - 1);}
void pop(){assert(!_ctnr.empty()); // 前提是 _ctnr 非空std::swap(_ctnr[0], _ctnr[_ctnr.size() - 1]);_ctnr.pop_back();AdjustDown(0);}private:Container _ctnr;};
}
