【C++练级之路】【Lv.10】【STL】priority_queue类和反向迭代器的模拟实现

【C++练级之路】【Lv.10】【STL】priority_queue类和反向迭代器的模拟实现



快乐的流畅:个人主页


个人专栏:《C语言》《数据结构世界》《进击的C++》

远方有一堆篝火,在为久候之人燃烧!

一、仿函数

1.1 仿函数的介绍

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

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

1.2 仿函数的优势

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

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

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

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

二、priority_queue

细节:

  1. priority_queue也是容器适配器,默认容器使用vector
  2. 其底层数据结构是,并且默认情况为大堆
    如果不了解堆,可以先看往期【数据结构】【版本2.0】【树形深渊】——二叉树入侵
  3. 为了能方便调整大小堆,增加了仿函数的模板
template<class T, class Container = vector<T>, class ***pare = less<T>>
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)
{
	***pare ***;
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (***(_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)
{
	***pare ***;
	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]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

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<class Iterator, class Ref, class Ptr>
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 T>
class vector
{
public:
	typedef T* iterator;
	typedef const T* const_iterator;

	typedef __reverse_iterator<iterator, T&, T*> reverse_iterator;
	typedef __reverse_iterator<iterator, const T&, const T*> 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 T>
class list
{
public:
	typedef __list_node<T> node;
	typedef __list_iterator<T, T&, T*> iterator;
	typedef __list_iterator<T, const T&, const T*> const_iterator;

	typedef __reverse_iterator<iterator, T&, T*> reverse_iterator;
	typedef __reverse_iterator<iterator, const T&, const T*> 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(优先级队列),实际上就是堆。并且也完美实现了同为适配器的反向迭代器,至此,对于适配器有了更深一步的了解和运用。


真诚点赞,手有余香

转载请说明出处内容投诉
CSS教程_站长资源网 » 【C++练级之路】【Lv.10】【STL】priority_queue类和反向迭代器的模拟实现

发表评论

欢迎 访客 发表评论

一个令你着迷的主题!

查看演示 官网购买