C++语法（12）---- 模拟实现queue和stack_哈里沃克的博客-CSDN博客https://blog.csdn.net/m0_63488627/article/details/130068637

目录

1.使用

2.模拟实现

1.数据元素

 2.数据建立

3.函数实现

4.向上调整和向下调整

3.仿函数（函数对象）介绍 

1.使用

封装在queue库文件中

 默认是大堆

想要变成小堆需要传入仿函数2.

int main()
{//小堆的实现priority_queue<int,vector<int>,greater<int>> pq;pq.push(1);pq.push(5);pq.push(8);pq.push(6);pq.push(4);while (!pq.empty()){cout << pq.top() << endl;pq.pop();}return 0;
}
/
int main()
{//大堆的实现priority_queue<int,vector<int>,less<int>> pq;pq.push(1);pq.push(5);pq.push(8);pq.push(6);pq.push(4);while (!pq.empty()){cout << pq.top() << endl;pq.pop();}return 0;
}

2.模拟实现

1.数据元素

后面会用到仿函数，用到再介绍

template<class T, class Container = vector<T>,class Compare=less<T>>
private:
Container _con; //存储结构是vector的指针，vector实现堆的数据结构

 2.数据建立

1.实现一个空构造，具体内容push来实现

2.根据迭代器位置拷贝构造，通过插入的数随后向上调整实现出一个拷贝的堆

3.优先级队列自己不需要迭代器，因为其特殊的访问逻辑（只看头尾）

template<class InputIterator>
priority_queue()
{}template<class InputIterator>
priority_queue(InputIterator first, InputIterator last):_con(first, last)
{for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--){adjust_down(i);}
}

3.函数实现

1.push即先尾插，随后尾部数据向上调整

2.pop就是头尾互换，随后头部数据向下调整

3.查数据个数，数据内容等函数不一一介绍

4.具体实现下面再说

void push(const T& x)
{_con.push_back(x);adjust_up(_con.size() - 1);
}void pop()
{swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);
}const T& top() const
{return _con[0];
}bool empty() const
{return _con.emoty();
}size_t size() const
{return _con.size();
}

4.向上调整和向下调整

1.注释中的其实是原来的比较，即为逻辑的大小比较

2.目前实现是通过仿函数实现的

void adjust_up(size_t child)
{Compare com;size_t parent = (child - 1) / 2;while (child > 0){//if (_con[parent] < _con[child])if (com(_con[parent]), _con[child]){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}elsebreak;}
}void adjust_down(size_t parent) 
{Compare com;size_t child = parent * 2 + 1;while (child < _con.size()){//if (child + 1 < _con.size() && _con[child] > _con[child + 1])if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){++child;}//if (_con[parent] < _con[child])if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}elsebreak;}
}

仿函数的使用

template<class T>
class less
{
public:bool operator()(const T& x, const T& y) const{return x < y;}
};template<class T>
class greater
{
public:bool operator()(const T& x, const T& y) const{return x < y;}
};

3.仿函数（函数对象）介绍 

1.仿函数是一个类，这个类的函数叫仿函数

2.class或者struct都可以，函数调用前提是属性为公有函数

3.仿函数重写了一个operator()，即重写了函数的访问

4.原理如图

在其中的代码其实没什么实际用处，因为跟调用函数没什么区别，反而减低了可读性；但是仿函数并不是这样用的。

5.仿函数更广泛用于泛型编程，即把仿函数中的类传递给函数，使得编译器自动推演。

举个例子，如果是一个有一个类如果想适用不同类型，需要实现不同模板的比较大小，但是如果只是><=的逻辑比较，好像又缺乏的很，因为int可以这样比，但是如果我需要一个指定日期类的比较呢？这样好像光大小比较实现不了，那么我们可以传入仿函数，默认缺省是><=的比较，随后我们在函数外实现日期类的仿函数比较，只要日期类比较，在指定类生成时改变默认的仿函数，那么我们就可以实现日期类的比较了。