【C++练级之路】【Lv.10】【STL】priority

小明 2025-04-30 01:15:06 4

快乐���流畅：个人主页

个人专栏：《C语言》《数据结构世界》《进击的C++》 远方有一堆篝火，在为久候之人燃烧！

文章目录

  • 一、仿函数
    • 1.1 仿函数的介绍
    • 1.2 仿函数的优势
    • 二、priority_queue
      • 2.1 push
      • 2.2 pop
      • 2.3 top
      • 2.4 size
      • 2.5 empty
      • 三、反向迭代器
        • 3.1 成员变量与默认成员函数
        • 3.2 operator*
        • 3.3 operator->
        • 3.4 operator++
        • 3.5 operator- -
        • 3.6 relational operators
        • 四、反向迭代器的适用
        • 4.1 vector
          • 4.1.1 rbegin
          • 4.1.2 rend
          • 4.2 list
            • 4.2.1 rbegin
            • 4.2.2 rend
            • 总结

              一、仿函数

              1.1 仿函数的介绍

              仿函数，是一种特殊类型的类，它重载了（）运算符，使得这个类的使用看起来像一个函数，因此它又称为函数对象。

              具体来说，仿函数就是将函数的特性赋予到类上，使得这个类有了类似函数的行为。

              1.2 仿函数的优势

              C++设计仿函数之初，其实就是想替代庞杂难懂的函数指针，将函数指针替换为简单易懂的仿函数。

              这里列举两个常用的仿函数——less和greater

              template
struct less
{
	bool operator()(const T& x, const T& y)
	{
		return x  y;
	}
};

              二、priority_queue

              细节：

              1. priority_queue也是容器适配器，默认容器使用vector
              2. 其底层数据结构是堆，并且默认情况为大堆

                如果不了解堆，可以先看往期【数据结构】【版本2.0】【树形深渊】——二叉树入侵

              3. 为了能方便调整大小堆，增加了仿函数的模板
              template
class priority_queue
{
public:
private:
	Container _con;
};

              悄悄说一句：其实容器模板和仿函数模板位置互换，才更加合理！（平时不怎么会换默认容器，但是会经常换仿函数来控制大小堆）

              2.1 push

              入堆

              细节：

              1. 先尾插元素
              2. 再使用向上调整算法
              void push(const T& x)
{
	_con.push_back(x);
	adjust_up(_con.size() - 1);
}

              向上调整算法

              细节：

              • 构造一个仿函数模板对象，再利用重载的（）运算符进行比较（当然，也可以使用匿名对象） 
                void adjust_up(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;
		}
	}
}

                2.2 pop

                出堆

                细节：

                1. 先首尾元素互换
                2. 再尾删元素
                3. 最后使用向下调整算法
                void pop()
{
	swap(_con[0], _con[_con.size() - 1]);
	_con.pop_back();
	adjust_down(0);
}

                向下调整算法

                细节：

                • 构造一个仿函数模板对象，再利用重载的（）运算符进行比较（当然，也可以使用匿名对象） 
                  void adjust_down(int parent)
{
	Compare com;
	int child = parent * 2 + 1;
	while (child  

                  2.3 top
                   

                  获取堆顶元素
                   

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

                   

                  2.4 size
                   

                  获取堆中有效元素个数
                   

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

                   

                  2.5 empty
                   

                  判断堆是否为空
                   

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

                   

                  三、反向迭代器
                   

                  其实，反向迭代器也是一种适配器，它是根据不同容器的正向迭代器，来生成对应的反向迭代器。
                   

                  同时，反向迭代器追求一种对称美，rbegin()在end()，rend()在begin()。
                   

                  3.1 成员变量与默认成员函数
                   

                  细节：
                   

                  1. 仍然使用struct，标明公有属性
                  2. 成员变量是一个正向迭代器
                  3. 提供带参构造函数（其余的默认成员函数不用显式定义，浅拷贝即可）
                  template
struct __reverse_iterator
{
	typedef __reverse_iterator self;
	Iterator _cur;
	__reverse_iterator(Iterator it)
		: _cur(it)
	{}
};

                   

                  3.2 operator*
                   

                  细节：
                   

                  1. 迭代器先自减，再解引用返回
                  2. 返回引用，为了区别普通迭代器和const迭代器
                  Ref operator*()
{
	Iterator tmp = _cur;
	return *--tmp;
}

                   

                  3.3 operator->
                   

                  细节：
                   

                  1. 直接调用operator*()，根据不同容器的数据取地址返回
                  2. 返回指针，为了区别普通迭代器和const迭代器
                  Ptr operator->()
{
	return &(operator*());
}

                   

                  3.4 operator++
                   

                  细节：
                   

                  1. 反向迭代器的++，就是正向迭代器的- -
                  2. 为了区分前置和后置，后置参数加上int（无实际意义，以示区分）
                  3. 前置传引用返回，后置传值返回
                  self& operator++()
{
	--_cur;
	return *this;
}
self operator++(int)
{
	Iterator tmp = _cur;
	--_cur;
	return tmp;
}

                   

                  3.5 operator- -
                   

                  细节：同上
                   

                  self& operator--()
{
	++_cur;
	return *this;
}
self operator--(int)
{
	Iterator tmp = _cur;
	++_cur;
	return tmp;
}

                   

                  3.6 relational operators
                   

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

                   

                  四、反向迭代器的适用
                   

                  4.1 vector
                   

                  template
class vector
{
public:
	typedef T* iterator;
	typedef const T* const_iterator;
	typedef __reverse_iterator reverse_iterator;
	typedef __reverse_iterator const_reverse_iterator;
	iterator begin()
	{
		return _start;
	}
	iterator end()
	{
		return _finish;
	}
	const_iterator begin() const
	{
		return _start;
	}
	const_iterator end() const
	{
		return _finish;
	}
	//...
}

                   

                  4.1.1 rbegin
                   

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

                   

                  4.1.2 rend
                   

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

                   

                  4.2 list
                   

                  template
class list
{
public:
	typedef __list_node node;
	typedef __list_iterator iterator;
	typedef __list_iterator const_iterator;
	typedef __reverse_iterator reverse_iterator;
	typedef __reverse_iterator const_reverse_iterator;
	iterator begin()
	{
		return iterator(_head->_next);
	}
	const_iterator begin() const
	{
		return const_iterator(_head->_next);
	}
	iterator end()
	{
		return iterator(_head);
	}
	const_iterator end() const
	{
		return const_iterator(_head);
	}
	//...
}

                   

                  4.2.1 rbegin
                   

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

                   

                  4.2.2 rend
                   

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

                   

                  总结
                   

                  这次学习了仿函数的概念和基本用法，对于升降序、大小堆等转换具有极大便利。同时实现了新的容器适配器——priority_queue（优先级队列），实际上就是堆。并且也完美实现了同为适配器的反向迭代器，至此，对于适配器有了更深一步的了解和运用。
                   

                  

                   
 
  真诚点赞，手有余香
The End

标签：

微信