[C++](13)stack && queue && priority

文章目录

• 使用
• • stack 栈
  • queue 队列
  • priority_queue 优先级队列
• 什么是容器适配器？
• deque 容器简单介绍
• 模拟实现
• • stack
  • queue
  • priority_queue
  • • 写死的大堆
    • 仿函数
    • 活的堆
    • 兼容函数指针写法
    • 迭代器范围构造
• 完整代码
• 仿函数其他用法
• • 内置类型排序
  • 自定义类型排序
• 反向迭代器(迭代器适配器)

使用 stack 栈

使用前需包含头文件

stack 和 queue 不支持迭代器，这两种容器不应该让人随意遍历。

• 入栈：push
• 查看栈顶元素：top
• 出栈：pop

例：

void test1()
{
	stack s;
	s.push(1);
	s.push(2);
	s.push(3);
	s.push(4);

	while (!s.empty())
	{
		cout << s.top() << ' ';
		s.pop();
	}
	cout << endl;
}
//结果：4 3 2 1

queue 队列

使用前需要包含头文件

• 入队：push
• 出队：pop
• 查看队头：front
• 查看队尾：back

void test2()
{
	queue q;
	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);

	while (!q.empty())
	{
		cout << q.front() << ' ';
		q.pop();
	}
	cout << endl;
}
//结果：1 2 3 4

priority_queue 优先级队列

priority_queue 就是堆，其默认使用 vector 作为其底层存储数据的容器。

priority_queue 默认是大堆。

• 插入一个值：push
• 查看堆顶元素：top
• 删除堆顶元素：pop

例：

void test3()
{
	priority_queue pq;
	pq.push(1);
	pq.push(6);
	pq.push(5);
	pq.push(9);
	pq.push(8);
	
	while (!pq.empty())
	{
		cout << pq.top() << ' ';
		pq.pop();
	}
	cout << endl;
}
//结果：9 8 6 5 1

改成小堆需要仿函数相关的知识，会在后面讲解，这里演示用法：

需要包含头文件

void test3()
{
	priority_queue, greater> pq; //小堆
	pq.push(1);
	pq.push(6);
	pq.push(5);
	pq.push(9);
	pq.push(8);
	
	while (!pq.empty())
	{
		cout << pq.top() << ' ';
		pq.pop();
	}
	cout << endl;
}

什么是容器适配器？

首先，我们来了解适配器的含义

适配器是一种接口转换器，生活中常见的有电源适配器，它可以将 220V 的交流电转换成适合电器使用的低压直流电。让原本不适用的电变得适用，这便是适配器的作用。

在计算机编程中，容器适配器则是将一个类的接口适配成用户所期待的。

stack，queue，priority_queue 都属于容器适配器，它们都是对其他容器的接口进行了包装。stack 和 queue 底层默认使用deque 容器。注意，其内部使用的基础容器并不是固定的，用户可以在满足特定条件的多个基础容器中自由选择。

deque 容器简单介绍

vector

优点：适合尾插尾删，随机访问，cpu 高速缓存命中高

缺点：

1. 不适合头部或者中部的插入删除，效率低，需要挪动数据
2. 扩容有一定的性能消耗，还可能存在一定程度的空间浪费

list

优点：

1. 任意位置插入删除效率高 O ( 1 ) O(1) O(1)
2. 按需申请释放空间

缺点：

1. 不支持随机访问
2. cpu高速缓存命中低

deque 就是 double-ended queue（双端队列），它结合了 vector 和 list 的设计。

• 基本原理就是由一个中控数组，也就是指针数组，维护多个缓冲区，缓冲区中存放真实数据。

• 缓冲数组满了，就会再开一个，中控数组里也就增加一个指针。

• 中控数组满了，则需要扩容，但是扩容的代价很小。

优点：

1. 头部和尾部的插入删除数据效率不错
2. 支持随机访问
3. 扩容代价小
4. cpu高速缓存命中高

缺点：

1. 中部插入删除效率不行
2. 虽然支持随机访问，但是效率相比 vector 还是有差距，频繁随机访问要小心

比较 vector 排序和 deque 排序：

void testOP()
{
	srand(time(0));
	const int N = 10000000;
	vector v;
	v.reserve(N);
	deque dq1;
	deque dq2;

	for (int i = 0; i < N; ++i)
	{
		auto e = rand();
		v.push_back(e);
		dq1.push_back(e);
		dq2.push_back(e);
	}

	int begin1 = clock();
	sort(v.begin(), v.end());
	int end1 = clock();

	int begin2 = clock();
	vector cp(dq1.begin(), dq1.end());
	sort(cp.begin(), cp.end());
	dq1.assign(cp.begin(), cp.end());
	int end2 = clock();

	int begin3 = clock();
	sort(dq2.begin(), dq2.end());
	int end3 = clock();
	
	cout << "vector sort: " << end1 - begin1 << endl;
	cout << "deque copy vector sort: " << end2 - begin2 << endl;
	cout << "deque sort: " << end3 - begin3 << endl;
}
//结果：
//vector sort: 482
//deque copy vector sort: 540
//deque sort: 1343

可见 deque 的随机访问速度慢一些。把 deque 拷贝到 vector 排序再拷贝回来会快一些。

像 stack 和 queue 这样频繁头尾插入删除，随机访问少的数据结构就非常适合使用 deque 作为基础容器。

模拟实现 stack

模板参数 class Container = deque 表示要使用的基础容器，默认为 deque 容器。

在基础容器上包装一层接口就行了。

template>
class Stack
{
public:
	void push(const T& x)
	{
		_con.push_back(x);
	}

	void pop()
	{
		_con.pop_back();
	}

	const T& top()
	{
		return _con.back();
	}

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

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

private:
	Container _con;
};

我们在创建对象时可以自己传入基础容器的类型，比如 Stack> s;，也可以不传，默认就是 deque 容器

stack支持使用的基础容器有：deque(默认) vector list

queue

template>
class Queue
{
public:
	void push(const T& x)
	{
		_con.push_back(x);
	}

	void pop()
	{
		_con.pop_front();
	}

	const T& front()
	{
		return _con.front();
	}
	
	const T& back()
	{
		return _con.back();
	}

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

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

private:
	Container _con;
};

queue 支持使用的基础容器有：deque(默认) list

priority_queue

堆的操作这里就不细讲了，详细讲解参考：[数据结构](8)二叉树顺序结构之堆|堆实现|堆排序|TOPK_世真的博客-CSDN博客

• 堆比较适合使用 vector 容器，因为堆的调整使用随机访问的频率较高。堆还支持使用 deque，但是不推荐
• 插入删除分别需要向上调整和向下调整，具体算法在之前的文章中有详细讲解。
• 这里实现的是一个写死的大堆。

写死的大堆

template>
class Priority_queue
{
public:
	void AdjustUp(int child)
	{
		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;
			}
		}
	}

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

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

	void pop()
	{
		assert(!_con.empty());
		swap(_con[0], _con[_con.size() - 1]);
		_con.pop_back();
		AdjustDown(0);
	}

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

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

	bool empty()
	{
		return _con.empty();
	}
private:
	Container _con;
};

仿函数

仿函数(functor)，就是使一个类的使用看上去像一个函数。其实现就是类中实现一个 operator()，这个类就有了类似函数的行为，就是一个仿函数类了。

例：

struct Less //仿函数类
{
	bool operator()(int x, int y)
	{
		return x < y;
	}
};

使用：

void test4()
{
	Less LessCom; //函数对象
	cout << LessCom(1, 2) << endl; //当成函数去使用
}

也可以搭配模板去用：

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

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

void test4()
{
	Less LessCom;
	cout << LessCom(1, 2) << endl;
}

活的堆

增加一个模板参数，用于传入仿函数类型，默认为 Less 即表示建大堆，传入 Greater 则表示建小堆。

把原来比较大小的部分改为使用仿函数。

template, class Compare = Less> //仿函数类
class Priority_queue
{
public:
	void AdjustUp(int child)
	{
		Compare comFunc;
		int parent = (child - 1) / 2;
		while (child > 0)
		{
			if (comFunc(_con[parent], _con[child])) //使用仿函数
			{
				swap(_con[parent], _con[child]);
				child = parent;
				parent = (child - 1) / 2;
			}
			else
			{
				break;
			}
		}
	}

	void AdjustDown(int parent)
	{
		Compare comFunc;
		int child = parent * 2 + 1;
		while (child < _con.size())
		{
			if (child + 1 < _con.size() && comFunc(_con[child], _con[child + 1])) //仿函数
			{
				++child;
			}
			if (comFunc(_con[parent], _con[child])) //仿函数
			{
				swap(_con[parent], _con[child]);
				parent = child;
				child = parent * 2 + 1;
			}
			else
			{
				break;
			}
		}
	}
    
    //略。。。
};

---

兼容函数指针写法

仿函数相当于替代了C语言的函数指针，当然，C++依然支持函数指针的写法，这里仅作为了解：

• 首先写好一个回调函数。
• 然后要将该函数指针传入实例化的对象中，即要增加一个成员变量，用于存储函数指针，另外还需要构造函数对其初始化。
• Compare 指定为函数指针类型
• 通过函数指针调用回调函数。

bool ComIntLess(int x, int y) //普通的比较函数
{
	return x > y;
}

template, class Compare = Less> //Compare指定为函数指针类型
class Priority_queue
{
	Compare _comFunc; //存储函数指针
public:
	Priority_queue(const Compare& comFunc = Compare()) //构造函数
		:_comFunc(comFunc)
	{}

	void AdjustUp(int child)
	{
		int parent = (child - 1) / 2;
		while (child > 0)
		{
			if (_comFunc(_con[parent], _con[child])) //回调函数
			{
				swap(_con[parent], _con[child]);
				child = parent;
				parent = (child - 1) / 2;
			}
			else
			{
				break;
			}
		}
	}

	void AdjustDown(int parent)
	{
		int child = parent * 2 + 1;
		while (child < _con.size())
		{
			if (child + 1 < _con.size() && _comFunc(_con[child], _con[child + 1])) //回调函数
			{
				++child;
			}
			if (_comFunc(_con[parent], _con[child])) //回调函数
			{
				swap(_con[parent], _con[child]);
				parent = child;
				child = parent * 2 + 1;
			}
			else
			{
				break;
			}
		}
	}
    //略。。。
};

使用：

void test5()
{
	Priority_queue, bool(*)(int, int)> pq(ComIntLess); //传入函数指针类型和函数指针
	pq.push(1);
	pq.push(5);
	pq.push(3);
	pq.push(7);
	pq.push(9);
	while (!pq.empty())
	{
		cout << pq.top() << ' ';
		pq.pop();
	}
}
//结果：1 3 5 7 9

迭代器范围构造

template 
Priority_queue(InputIterator first, InputIterator last, const Compare& comFunc = Compare())
	:_comFunc(comFunc)
{
	while (first != last)
	{
		_con.push_back(*first++);
	}
	// 向下调整建堆
	for (int i = (_con.size() - 2) / 2; i >= 0; --i)
	{
		AdjustDown(i);
	}
}

完整代码

#pragma once
#include 
#include 
#include 
#include 
using namespace std;

template>
class Queue
{
public:
	void push(const T& x)
	{
		_con.push_back(x);
	}

	void pop()
	{
		_con.pop_front();
	}

	const T& front()
	{
		return _con.front();
	}

	const T& back()
	{
		return _con.back();
	}

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

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

private:
	Container _con;
};

//仿函数/函数对象
template
struct Less
{
	bool operator()(const T& x, const T& y) const
	{
		return x < y;
	}
};

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

bool ComIntLess(int x, int y)
{
	return x > y;
}

template, class Compare = Less>
class Priority_queue
{
	Compare _comFunc;
public:
	Priority_queue(const Compare& comFunc = Compare())
		:_comFunc(comFunc)
	{}

	template 
	Priority_queue(InputIterator first, InputIterator last, const Compare& comFunc = Compare())
		:_comFunc(comFunc)
	{
		while (first != last)
		{
			_con.push_back(*first++);
		}

		for (int i = (_con.size() - 2) / 2; i >= 0; --i)
		{
			AdjustDown(i);
		}
	}

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

	void AdjustDown(int parent)
	{
		int child = parent * 2 + 1;
		while (child < _con.size())
		{
			if (child + 1 < _con.size() && _comFunc(_con[child], _con[child + 1]))
			{
				++child;
			}
			if (_comFunc(_con[parent], _con[child]))
			{
				swap(_con[parent], _con[child]);
				parent = child;
				child = parent * 2 + 1;
			}
			else
			{
				break;
			}
		}
	}

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

	void pop()
	{
		assert(!_con.empty());
		swap(_con[0], _con[_con.size() - 1]);
		_con.pop_back();
		AdjustDown(0);
	}

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

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

	bool empty()
	{
		return _con.empty();
	}
private:
	Container _con;
};

仿函数其他用法 内置类型排序

库里的 sort 函数默认排升序。

传入一个函数对象可以控制排序方式。

void test6()
{
	int a[] = { 1,5,4,8,9,2,3 };
	sort(a, a + 7, greater());
	for (auto e : a)
	{
		cout << e << ' ';
	}
}
//结果：9 8 5 4 3 2 1

：数组的指针就是天然的迭代器，可以直接传参，而后传入一个匿名的函数对象 greater() 。

自定义类型排序

通过仿函数编写不同的排序规则：

struct Fruit
{
	string _name;
	double _price;
	size_t _sales;
};

struct LessPrice
{
	bool operator()(const Fruit& f1, const Fruit& f2) const
	{
		return f1._price < f2._price;
	}
};
struct GreaterPrice
{
	bool operator()(const Fruit& f1, const Fruit& f2) const
	{
		return f1._price > f2._price;
	}
};
struct LessSales
{
	bool operator()(const Fruit& f1, const Fruit& f2) const
	{
		return f1._sales < f2._sales;
	}
};
struct GreaterSales
{
	bool operator()(const Fruit& f1, const Fruit& f2) const
	{
		return f1._sales > f2._sales;
	}
};

void test7()
{
	Fruit gds[4] = { {"苹果", 3.75, 1000}, {"香蕉", 2.98, 200}, {"橙子", 4.62, 300}, {"菠萝", 2.75, 50} };
	sort(gds, gds + 4, LessPrice());
	sort(gds, gds + 4, GreaterPrice());
	sort(gds, gds + 4, LessSales());
	sort(gds, gds + 4, GreaterSales());
}

反向迭代器(迭代器适配器)

反向迭代器++和–的操作和正向迭代器是反的，其它操作一样。

对于已有的正向迭代器类，我们能否像适配器那样直接给它再封装一层呢？

---

当然是可以的，

这里以之前没写完的 list 为例：

template
struct Reverse_iterator
{
	Iterator _it;
	typedef Reverse_iterator Self;

	Reverse_iterator(Iterator it)
		: _it(it)
	{}

	Ref operator*()
	{
		Iterator tmp = _it;
		return *--tmp;
	}

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

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

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

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

反向迭代器的 rbegin 就是正向迭代器的 end，反向迭代器的 rend 就是正向迭代器的 begin

反向迭代器的解引用就是返回反向迭代器指向的元素的前一个。

List 类内：

typedef Reverse_iterator reverse_iterator;
typedef Reverse_iterator 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());
}

任何容器，只要实现了正向迭代器，我们都可以用以上代码封装出反向迭代器，这就是迭代器适配器。