【C++篇】STL适配器（下篇）：优先级队列与反向迭代器的底层奥秘

template<T, vector<T>, less<T>>

#include <vector>
#include <queue>
// greater算法的头文件
#include <functional>

void TestPriorityQueue()
{
	// 默认情况下，创建的是大堆，其底层按照小于号比较
	vector<int> v{3,2,7,6,0,4,1,9,8,5};
	priority_queue<int> q1;
	for (auto& e : v)
		q1.push(e);
	cout << "堆顶为：" << q1.top() << endl;
	// 如果要创建小堆，将第三个模板参数换成greater比较方式
	priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());
	cout <<  "堆顶为："<< q2.top() << endl;
}

Container _con;

void pop()
{

    swap(_con[0], _con[_con.size() - 1]);
    _con.pop_back();

    //向下调整
    AdjustDown(0);
}

void AdjustDown(int parent)
{
	//假设左孩子更大
    int child = parent * 2 + 1;
    while (child < _con.size())
    {
        //右孩子存在且比左孩子大，就指向右孩子
        if (child + 1 < _con.size() && _con[child] < _con[child + 1])
        {
            ++child;
        }
		//父节点小于孩子节点就交换
        if (_con[parent] < _con[child])
        {
            swap(_con[parent], _con[child]);
        }
        else
        {
            break;
        }
		//更新下标，为下一轮循环做准备
        parent = child;
        child = parent * 2 + 1;
    }
}

class MyFunctor {
public:
    // 重载函数调用运算符
    return_type operator()(参数列表) const { 
        // 实现逻辑
    }
};

//仿函数
//控制实例化大小堆

//大堆
template<class T>
class Less
{
public:
    bool operator()(const T& a, const T& b)
    {
        return a < b;
    }
};

//小堆
template<class T>
class Greater
{
public:
    bool operator()(const T& a, const T& b)
    {
        return a > b;
    }
};

namespace zhh
{
template <class T, class Container = vector<T>, class Compare = Less<T> >//设定默认大堆
class priority_queue
{
private:
    void AdjustDown(int parent)
    {
        Compare _com;
        int child = parent * 2 + 1;
        while (child < _con.size())
        {
            if (child + 1 < _con.size() && _com(_con[child], _con[child + 1]))
            {
                ++child;
            }

            if (_com(_con[parent], _con[child]))
            {
                swap(_con[parent], _con[child]);
            }
            else
            {
                break;
            }

            parent = child;
            child = parent * 2 + 1;
        }
    }
    
private:
 	Container _con;
 };

void push(const T& x)
{
    _con.push_back(x);

    //向上调整
    AdjustUp(_con.size() - 1);
}

 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]);
         }
         else
         {
             break;
         }

         child = parent;
         parent = (child - 1) / 2;
     }
 }

//[first, last)
template <class InputIterator>
priority_queue(InputIterator first, InputIterator last)
    :_con(first, last)
{
    //(_con.size() - 1 - 1)/2计算父亲节点的下标
    for (int i = (_con.size() - 1 - 1) / 2; i >= 0; --i)
    {
        AdjustDown(i);
    }
}

#include <iostream>
#include <vector>
#include <iterator> // 包含 reverse_iterator

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};

    // 获取反向迭代器
    auto rbegin = vec.rbegin(); // 指向最后一个元素
    auto rend = vec.rend();     // 指向第一个元素之前的位置

    // 反向遍历
    for (auto rit = rbegin; rit != rend; ++rit) {
        std::cout << *rit << " ";
    }
    // 输出：5 4 3 2 1

    return 0;
}

T& operator*()
{
	Iterator tmp = _it;

	return *--tmp;
}

T* operator->()
{
	return &(operator*());
}

#pragma once

namespace zhh
{
	// 适配器 -- 复用
	template<class Iterator, class Ref, class Ptr>
	struct Reverse_iterator
	{
		typedef Reverse_iterator<Iterator, Ref, Ptr> Self;

		Iterator _it;
		Reverse_iterator(const Iterator& it)
			:_it(it)
		{ }

		Ref operator*()
		{
			Iterator tmp = _it;

			return *--tmp;
		}

		Ptr operator->()
		{
			return &(operator*());
		}

		Self& operator++()
		{
			--_it;
			return *this;
		}

		Self operator++(int)
		{
			Iterator tmp = _it;
			--_it;
			return tmp;
		}

		Self& operator--()
		{
			++_it;
			return *this;
		}

		Self operator--(int)
		{
			Iterator tmp = _it;
			++_it;
			return tmp;
		}

		bool operator==(const Self& s)
		{
			return _it == s._it;
		}

		bool operator!=(const Self& s)
		{
			return _it != s._it;
		}
	};
}

typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;

reverse_iterator rbegin()
{
    return reverse_iterator(end());
}

reverse_iterator rend()
{
    return reverse_iterator(begin());
}

const_reverse_iterator rbegin() const
{
    return const_reverse_iterator(end());
}

const_reverse_iterator rend() const
{
    return const_reverse_iterator(begin());
}