C++ 容器的两把利器之优先级队列与反向迭代器实现原理解析_C/C++

-------------反向迭代器------------

1、适配器模式

要实现反向迭代器，就不得不提到适配器模式

在上一篇内容中，我们学习的 stack 和 queue 就是典型的容器适配器；而今天要讲的反向迭代器，则是一种迭代器适配器

2、反向迭代器原理

反向迭代器是一个迭代器适配器，它包装了一个正向迭代器，把 ++ 操作映射成原迭代器的 --，把 -- 操作映射成原迭代器的 ++，从而实现反向遍历的效果

反向迭代器在容器中的指向：

3、反向迭代器的实现

namespace ljh
{
	//typedef iterator<iterator, t& , t*> iterator;
	//typedef iterator<iterator, const t& , const t*> iterator;
	template<class iterator, class ref, class ptr>
	struct reverseiterator
	{
		typedef reverseiterator<iterator, ref, ptr> self;
		iterator _it;
		reverseiterator(iterator it)
			:_it(it)
		{
		}
		ref operator*()
		{
			iterator tmp = _it;
			return *(--tmp);
		}
		ptr operator->()
		{
			return &(operator*());
		}
		self& operator++()
		{
			--_it;
			return *this;
		}
		//由于没写析构函数，所以不用担心拷贝构造是浅拷贝
		self operator++(int)
		{
			self tmp(*this); 
			--_it;//正向迭代器--，反向迭代器++
			return tmp;
		}
		self& operator--()
		{
			++_it;
			return *this;
		}
		self operator--(int)
		{
			self tmp(*this);
			++_it;
			return tmp;
		}
		bool operator!=(const self& s) const
		{
			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 reverse_iterator(end());
	}
	const_reverse_iterator rend() const
	{
		return reverse_iterator(begin());
	}
}

3.1 模板参数解析

template<class iterator, class ref, class ptr>
struct reverseiterator

iterator：被适配的正向迭代器类型（比如 vector::iterator）

ref：迭代器取值（*it）时返回的引用类型（比如 t& 或 const t&）

ptr：迭代器箭头访问（it->）时返回的指针类型（比如 t* 或 const t*）

3.2 类型别名与成员变量

typedef reverseiterator<iterator, ref, ptr> self;
iterator _it;

self：简化自身类型的书写，避免重复写长模板名

_it：内部持有的正向迭代器，是反向迭代器的 “核心数据”

3.3 构造函数

reverseiterator(iterator it) : _it(it) {}

用一个正向迭代器来初始化反向迭代器，把传入的迭代器保存到 _it 中。

3.4 取值运算符operator*

ref operator*()
{
    iterator tmp = _it;
    return *(--tmp);
}

这是反向迭代器的核心适配逻辑。

它先拷贝一份内部迭代器 _it，对拷贝做 -- 移动到前一个位置，再取值返回。

这样保证了 rbegin() 能正确指向容器的最后一个元素。

3.5 箭头运算符operator->

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

复用 operator* 的结果，取其地址返回，支持 it->member 这样的指针访问语法。

3.6 前置 ++ 运算符operator++

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

反向迭代器的 ++ 对应内部正向迭代器的 --，实现 “向后移动”（在反向遍历中是向前走）。

3.7 后置 ++ 运算符operator++(int)

self operator++(int)
{
    self tmp(*this);
    --_it;
    return tmp;
}

先创建一个当前对象的副本，再移动内部迭代器，最后返回副本。

这是后置 ++ 的标准实现，保证返回的是 “移动前” 的迭代器。

3.8 前置 -- 运算符operator--

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

反向迭代器的 -- 对应内部正向迭代器的 ++，实现 “向前移动”（在反向遍历中是向后退）。

3.9 后置 -- 运算符operator--(int)

self operator--(int)
{
    self tmp(*this);
    ++_it;
    return tmp;
}

逻辑同后置 ++，先拷贝再移动，返回移动前的迭代器。

3.10 不等比较运算符operator!=

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

直接比较两个反向迭代器内部持有的正向迭代器，判断它们是否指向不同位置。

// 先定义反向迭代器的类型别名（依赖之前的 reverseiterator 适配器）
typedef reverseiterator<iterator, t&, t*> reverse_iterator;
typedef reverseiterator<const_iterator, const t&, const t*> const_reverse_iterator;
// 1. 普通版 rbegin()：可读写反向迭代器起点
reverse_iterator rbegin()
{
    // 核心：用正向迭代器的 end() 初始化反向迭代器，指向容器最后一个元素
    return reverse_iterator(end());
}
// 2. 普通版 rend()：可读写反向迭代器终点
reverse_iterator rend()
{
    // 核心：用正向迭代器的 begin() 初始化反向迭代器，指向第一个元素之前
    return reverse_iterator(begin());
}
// 3. const版 rbegin() const：只读反向迭代器起点
const_reverse_iterator rbegin() const
{
    // 核心：逻辑同普通版，但返回 const 版本，仅支持读操作
    return const_reverse_iterator(end());
}
// 4. const版 rend() const：只读反向迭代器终点
const_reverse_iterator rend() const
{
    // 核心：逻辑同普通版，但返回 const 版本，仅支持读操作
    return const_reverse_iterator(begin());
}

-------------优先级队列------------

1、仿函数

仿函数（functor）是 c++ 中一种特殊的类对象，核心特点是重载（重载）了 operator() 运算符，使得对象可以像函数一样被调用（用对象名(参数) 的形式）。

简单说：仿函数是 “像函数的对象”，本质是带 operator() 的类实例。

template<class t>
class small
{
public:
	bool operator()(const t& x,const t& y)
	{
         return x < y;
	}
};
template<class t>
class big
{
public:
	bool operator()(const t& x,const t& y)
	{
		return x > y;
	}
};
int main()
{ 
    small<int> s;
    big<int> b;
    cout << s(1,2) << endl;
	cout << b(1, 2) << endl;
	return 0;
}

对初次接触的读者来说，仿函数的调用方式（比如 s(1,2)）确实显得有些陌生，和我们熟悉的 +、= 等运算符重载的写法很不一样。你可能暂时会疑惑它的实际价值，这很正常 —— 当我们后续用它来定制优先级队列的比较规则时，这种设计的灵活性和必要性就会清晰地展现出来。

2、优先级队列介绍

priority_queue 是 c++ 标准库中的一个容器适配器，底层默认用 vector 存储数据，内部维护一个堆结构，确保队首元素始终是优先级最高的（默认是最大值）。

核心特点：

只能访问队首的最大元素，不能遍历或随机访问其他元素。

插入新元素时，会自动调整堆结构以维持优先级顺序。

弹出队首元素后，剩余元素也会自动重新调整。

底层原理：通过调用 make_heap、push_heap、pop_heap 等算法函数来维护堆的特性。

默认行为：默认是大顶堆（最大元素优先），可以通过传入仿函数（如 greater<t>）改为小顶堆。

3、优先级队列的实现

namespace ljh
{
    // 仿函数/函数对象
    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;
	    }
    };
	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]))
					//if (child + 1 < _con.size() && _con[child] < _con[child + 1])
				{
					++child;
				}
				if (com(_con[parent], _con[child]))
				{
					swap(_con[child], _con[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}
		//向上调整算法
		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;
				}
			}
		}
	public:
        //默认构造
		priority_queue()
		{
		}
		//范围构造
		template<class inputiterator>
		priority_queue(inputiterator first,inputiterator last)
		{
			while (first!=last)
			{
				_con.push_back(*first);
				first++;
			}
			//建堆-向下调整建堆（默认建立大堆）
            //n
			for (int i = (_con.size() - 2) / 2; i >= 0; i--)
			{
				//向下调整算法
				adjustdown(i);
			}
		}
		void pop()
		{
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			adjustdown(0);
		}
		void push(const t& x)
		{
			_con.push_back(x);
			adjustup(_con.size() - 1);
		}
		const t& top()
		{
			return _con[0];
		}
		bool empty()
		{
			return _con.empty();
		}
		size_t size()
		{
			return _con.size();
		}
	private:
		container _con;
	};
}

3.1 类模板定义

template<class t, class container = vector<t>, class compare = less<t>>
class priority_queue

这是整个优先级队列的模板定义，有三个模板参数：

t：队列中存储的元素类型。

container：底层存储数据的容器，默认用 vector，也可以换成 deque 等支持随机访问的容器。

compare：比较规则的仿函数，默认是 less<t>（大顶堆），可以换成 greater<t> 实现小顶堆。

3.2adjustdown向下调整算法

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[child], _con[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}

这是维护堆结构的核心函数，用来在堆顶元素被移除后，把新的堆顶向下调整到正确位置：

先创建一个比较规则的仿函数对象 con。

从 parent 的左孩子 child = parent*2+1 开始。

先在左右孩子中，用 com 比较出优先级更高的那个，作为真正要交换的 child。

然后用 com 比较父节点和这个孩子节点，如果父节点优先级更低，就交换它们，并继续向下调整。

如果父节点优先级已经更高，说明调整完成，直接跳出循环。

3.3adjustup向上调整算法

void adjustup(int child)
{
    compare com;
    int parent = (child - 1) / 2;
    while (child > 0)
    {
        if (com(_con[parent], _con[child]))
        {
            swap(_con[child], _con[parent]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
            break;
        }
    }
}

这个函数用来在新元素插入堆尾后，把它向上调整到正确位置：

创建比较规则的仿函数对象 con。

计算当前 child 节点的父节点 parent = (child-1)/2。

用 con 比较父节点和孩子节点，如果父节点优先级更低，就交换它们，并继续向上调整。

如果父节点优先级已经更高，说明调整完成，跳出循环。

3.4 默认构造函数

priority_queue()
{}

空的默认构造函数，底层容器 _con 会自己调用默认构造，不需要额外操作。

3.5 范围构造函数

template<class inputiterator>
priority_queue(inputiterator first, inputiterator last)
{
    while (first != last)
    {
        _con.push_back(*first);
        first++;
    }
    for (int i = (_con.size() - 2) / 2; i >= 0; i--)
    {
        adjustdown(i);
    }
}

这个构造函数可以用一段迭代器区间来初始化队列：

先把区间里的所有元素都插入到底层容器 _con 中。

然后从最后一个非叶子节点开始，依次调用 adjustdown，把整个容器调整成一个合法的堆结构。

3.6 pop弹出堆顶元素

void pop()
{
    swap(_con[0], _con[_con.size() - 1]);
    _con.pop_back();
    adjustdown(0);
}

弹出堆顶元素的步骤：

先把堆顶元素（_con[0]）和堆尾元素交换。

然后删除堆尾元素（也就是原来的堆顶）。

最后对新的堆顶元素调用 adjustdown，重新维护堆的结构。

3.7push插入新元素

void push(const t& x)
{
    _con.push_back(x);
    adjustup(_con.size() - 1);
}

插入新元素的步骤：

先把新元素插入到底层容器的尾部。

然后对这个新插入的元素调用 adjustup，把它向上调整到正确的位置，以维持堆的性质。

3.8top获取堆顶元素

const t& top()
{
    return _con[0];
}

直接返回底层容器的第一个元素，也就是堆顶元素。因为堆顶始终是优先级最高的元素。

3.9empty判断队列是否为空

bool empty()
{
    return _con.empty();
}

直接调用底层容器的 empty() 方法，判断队列是否为空。

3.10size获取队列元素个数

size_t size()
{
    return _con.size();
}

直接返回底层容器的大小，也就是队列中元素的个数。

到此这篇关于c++ 容器的两把利器之优先级队列与反向迭代器实现原理解析的文章就介绍到这了,更多相关c++ 优先级队列与反向迭代器内容请搜索代码网以前的文章或继续浏览下面的相关文章希望大家以后多多支持代码网！

C++ 容器的两把利器之优先级队列与反向迭代器实现原理解析

2026年01月26日 • C/C++ •我要评论