stack_queue的底层,模拟实现,deque和priority_queue详解

适配器

适配器是一种模式，这种模式将类的接口转化为用户希望的另一个接口
可以类比为充电器，将220V转化为你需要的伏数

Stack的模拟实现

函数参数传的是类型和值
模版参数传的是类型

类模版实例化时，按需实例化，你调了哪些函数，就实例化哪些函数，不会全实例化

namespace wbc
{// Container适配转化出Stack,类模版的缺省参数是类型template<class T, class Container = vector<T>>class 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
{template<class T,class Container = list<T>>class 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,还有一个指向中控的node
• start和finish两个迭代器：
  
• 两个迭代器的图

• deque头插头删，尾插尾删效率很高，比vector的效率高，比list开空间上不需要开大量的细碎的空间，空间利用率更高

• 下标的随机访问还行，比vector稍微差一些，vector是直接+数字到达相应的位置，deque是需要进行10几次运算才能到相应的位置，比如可能头插了，数据需要减去，要计算

• 中间的插入和删除效率很低，需要挪动数据，是O(N)
  

• operator++的源码

priority_queue

优先级队列也不是先进先出的，priority_queue也是一个容器适配器,在queue的头文件下

默认是大的数优先级更高，底层是堆
堆的底层是vector

priority_queue的使用

int main()
{// less < 大的优先极高 大堆// greater > 小的优先级高 小堆// priority_queue<int,vector<int>,less<int>> pq;priority_queue<int, vector<int>, greater<int>> 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(),它的对象可以像函数一样使用
template<class T>
class Less
{
public:bool operator()(const T& x, const T& y){return x < y;}
};template<class T>
class Greater
{
public:bool operator()(const T& x, const T& y){return x > y;}
};int main()
{Less<int> A;// 函数对象cout << A(2, 3) << endl;// 底层是cout << A.operator()(2,3) << endl;
}

仿函数的作用

在排序中可以用仿函数不用写两个（一个用于升序，一个用于降序的排序），仿函数的函数对象传参，对象是一个类，用模版参数接收，函数模版要传对象自动推导这个类型，优先级队列的那里是类模版传类型

// < 升序
// > 降序
template<class 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()
{Less<int> A;Greater<int> 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, Less<int>());Bubblesort(a, 8, Greater<int>());
}

priority_queue模拟实现

#pragma once
#include<vector>template<class T>
class Less
{
public:bool operator()(const T& x, const T& y){return x < y;}
};template<class T>
class Greater
{
public:bool operator()(const T& x, const T& y){return x > y;}
};namespace wbc
{template<class T, class Container = vector<T>,class Compare = Less<T>>class 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[child+1]if (child + 1 < _con.size() && com(_con[child],_con[child+1])){++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;};
}