ps企业网站模板,做网站 工资高吗,互联网推广培训,wordpress短代码大全文章目录 适配器Stack的模拟实现Queue的模拟实现vector和list的对比dequedeque的框架deque的底层 priority_queuepriority_queue的使用priority_queue的底层仿函数的使用仿函数的作用priority_queue模拟实现 适配器 适配器是一种模式#xff0c;这种模式将类的接口转化为用户希… 文章目录 适配器Stack的模拟实现Queue的模拟实现vector和list的对比dequedeque的框架deque的底层 priority_queuepriority_queue的使用priority_queue的底层仿函数的使用仿函数的作用priority_queue模拟实现 适配器 适配器是一种模式这种模式将类的接口转化为用户希望的另一个接口 可以类比为充电器将220V转化为你需要的伏数 Stack的模拟实现
函数参数传的是类型和值 模版参数传的是类型
类模版实例化时按需实例化你调了哪些函数就实例化哪些函数不会全实例化
namespace wbc
{// Container适配转化出Stack,类模版的缺省参数是类型templateclass T, class Container vectorTclass stack{public:void push(const T x){_con.push_back(x);}void pop(){_con.pop_back();}const T top() const {return _con.back();}bool empty() const {return _con.empty();}size_t size() const {return _con.size();}private:Container _con;// Container会自动调用它的默认构造对于自定义类型来说// 所以不用写};void print_container(){cout hello world endl;}
}Queue的模拟实现 队列是先进先出的用list实现更好vector只支持尾插和尾删不能直接进行队头的删除 // 队列是队尾进数据队头出数据namespace wbc
{templateclass T,class Container listTclass Queue{public:void push(const T x){_con.push_back(x);}void pop(){_con.pop_front();}const T front() const{return _con.front();}const T back() const{return _con.back();}bool empty() const{return _con.empty();}size_t size() const {return _con.size();}private:Container _con;};
}vector和list的对比 vector 优点 1.尾插尾删不错支持高效的下标随机访问 2.物理空间连续所以高速缓存利用率高 缺点 1.头部和中间的插入和删除效率低 2.空间需要扩容扩容有一定的代价效率和空间浪费 list 优点 1.按需申请释放空间不需要扩容 2.支持任意位置的插入和删除 缺点 1.不支持下标随机访问
deque deque不是先进先出是任意位置插入删除的容器 deque的框架 deque是vector和list的缝合 这里的扩容是需要扩容指针数组让中控的指针更多指向的buff数组更多如果buff数组不够的话也要增加buff数组new buff[ ] deque的底层
底层是两个迭代器,map和map_size start和finish的迭代器 都有指向当前buff数组的cur,指向开始位置的first,指向数据结束位置的下一个位置的last,还有一个指向中控的nodestart和finish两个迭代器 两个迭代器的图 deque头插头删尾插尾删效率很高比vector的效率高比list开空间上不需要开大量的细碎的空间空间利用率更高 下标的随机访问还行比vector稍微差一些vector是直接数字到达相应的位置deque是需要进行10几次运算才能到相应的位置比如可能头插了数据需要减去要计算 中间的插入和删除效率很低需要挪动数据是O(N) operator的源码 priority_queue 优先级队列也不是先进先出的priority_queue也是一个容器适配器,在queue的头文件下 默认是大的数优先级更高底层是堆 堆的底层是vector priority_queue的使用
int main()
{// less 大的优先极高 大堆// greater 小的优先级高 小堆// priority_queueint,vectorint,lessint pq;priority_queueint, vectorint, greaterint pq;pq.push(1);pq.push(2);pq.push(3);pq.push(10);pq.push(9);while (!pq.empty()){cout pq.top() ;pq.pop();}cout endl;return 0;
}priority_queue的底层
仿函数的使用 仿函数本质是一个类这个类重载了operator(),它的对象可以像函数一样使用 仿函数是一个类可以像模版参数一样使用 仿函数很多都是空类没有成员变量的类对象大小为1 仿函数控制大堆和小堆,就不需要写一个大堆和一个小堆了 // 仿函数本质是一个类,它重载了operator(),它的对象可以像函数一样使用
templateclass T
class Less
{
public:bool operator()(const T x, const T y){return x y;}
};templateclass T
class Greater
{
public:bool operator()(const T x, const T y){return x y;}
};int main()
{Lessint A;// 函数对象cout A(2, 3) endl;// 底层是cout A.operator()(2,3) endl;
}仿函数的作用 在排序中可以用仿函数不用写两个一个用于升序一个用于降序的排序仿函数的函数对象传参对象是一个类用模版参数接收函数模版要传对象自动推导这个类型优先级队列的那里是类模版传类型 // 升序
// 降序
templateclass compare
void Bubblesort(int* a, int n, compare com)
{for (int i 0; i n; i){// 单趟int flag 0;for (int j 1; j n-i; j){if(com(a[j],a[j-1]))// if (a[j] a[j - 1]){swap(a[j], a[j - 1]);flag 1;}}if (flag 0) break;}
}
int main()
{Lessint A;Greaterint B; 函数对象//cout A(2, 3) endl;// // 底层是//cout A.operator()(2,3) endl;int a[] { 9,1,2,5,7,4,6,3 };// 有名对象Bubblesort(a, 8, A);Bubblesort(a, 8, B);// 匿名对象Bubblesort(a, 8, Lessint());Bubblesort(a, 8, Greaterint());
} priority_queue模拟实现
#pragma once
#includevectortemplateclass T
class Less
{
public:bool operator()(const T x, const T y){return x y;}
};templateclass T
class Greater
{
public:bool operator()(const T x, const T y){return x y;}
};namespace wbc
{templateclass T, class Container vectorT,class Compare LessTclass priority_queue{public:// 默认是大堆void AdjustUp(int child){Compare com;int parent (child - 1) / 2;while (child 0){if (com(_con[parent],_con[child])){swap(_con[parent], _con[child]);child parent;parent (child - 1) / 2;}else{break;}}}void push(const T x){_con.push_back(x);// 插入数据之后建堆,保证是堆// 向上调整建堆AdjustUp(_con.size() - 1);}// 向下调整建堆void AdjustDown(int parent){// 找出左右孩子中大的那个// 假设左孩子大size_t child parent * 2 1;Compare com;while (child _con.size()){// _con[child] _con[child1]if (child 1 _con.size() com(_con[child],_con[child1])){child;}if(com(_con[parent],_con[child])){swap(_con[parent], _con[child]);parent child;child parent * 2 1;}else{break;}}}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();// 向下调整建堆AdjustDown(0);}const T top(){// 如果为空,容器底层会检查不用管return _con[0];}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};
}
