当前位置: article > 正文

C++——stack与queue底层理解，优先级队列、仿函数、容器适配器_c++ stack

作者：寸_铁 | 2024-08-12 15:35:08

踩

c++ stack

三、priority_queue的介绍和使用

3.1 priority_queue的介绍

3.2 priority_queue的使用

3.3 priority_queue的模拟实现

四、容器适配器

标准库中stack和queue的底层结构

在前面的C++编程提高学习中，已经初步了解到了stack与queue容器的一些基本接口，但是其底层是什么实现的在下面将进行介绍。

一、 stack栈容器深入理解

1.1 stack概念

1、stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。

2、stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。

3、stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下操作：

empty：判空操作
back：获取尾部元素操作
push_back：尾部插入元素操作
pop_back：尾部删除元素操作

4、标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，默认情况下使用deque。

1.2 stack使用

1、使用默认的适配器

stack<int> s;

2、使用指定的适配器


stack<int, vector<int>> s1;
stack<int, list<int>> s2;

不能用指定string的适配器。

stack<int, string> s3;//存在截断数据丢失的风险

测试


void test_stack()
{
	stack<int> s;
	s.push(1);
	s.push(2);
	s.push(3);
	s.push(4);
	cout << s.size() << endl;//4
	while (!s.empty())
	{
		cout << s.top() << " ";//4 3 2 1
		s.pop();
	}
}

1.3 stack的模拟实现

stack的底层是借助容器适配器来完成的。


namespace cpp
{
	template<class T, class Container = deque<T>>
	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;
	};
}

二、queue队列容器深入理解

2.1 queue的概念

、队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。

2、队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。

3、底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:

empty：检测队列是否为空
size：返回队列中有效元素的个数
front：返回队头元素的引用
back：返回队尾元素的引用
push_back：在队列尾部入队列
pop_front：在队列头部出队列
4、标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。

2.2 queue的使用

1、使用默认的适配器定义队列
queue<int> q1;
2、使用指定的适配器定义队列
queue<int, list<int>> q3;//不能用vector
不能使用vector作为适配器，因为vector不支持头删。

测试：
void test_queue()
{
	queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);
	q.push(40);
	cout << q.size() << endl;//4
	cout << q.back() << endl;//40
	while (!q.empty())
	{
		cout << q.front() << " ";//1 2 3 40
		q.pop();
	}
}

2.3 queue的模拟实现


namespace cpp
{
	template<class T, class Container = deque<T>>
	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;
	};
}

三、priority_queue的介绍和使用

3.1 priority_queue的介绍

1、优先级队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。

2、其底层类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。

3、优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。

4、底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：

empty()：检测容器是否为空
size()：返回容器中有效元素个数
front()：返回容器中第一个元素的引用
push_back()：在容器尾部插入元素
pop_back()：删除容器尾部元素
5、标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。

6、需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。

3.2 priority_queue的使用

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。注意：默认情况下priority_queue是大堆。

priority_queue的定义方式：

1、使用vector作为底层容器，内部构造大堆结构：
priority_queue<int, vector<int>, less<int>> q1;
2、使用vector作为底层容器，内部构造小堆结构：
priority_queue<int, vector<int>, greater<int>> q2;
3、不指定底层容器和内部需要构造的堆结构。（编译器默认大堆处理）
priority_queue<int> pq;
void test_priority_queue()
{
	//priority_queue<int> pq;
	priority_queue<int, vector<int>, greater<int>> pq;
	pq.push(9);
	pq.push(4);
	pq.push(7);
	pq.push(0);
	pq.push(2);
	cout << pq.size() << endl;//5
	while (!pq.empty())
	{
		cout << pq.top() << " ";//0 2 4 7 9 
		pq.pop();
	}
}

优先级队列默认大的优先级高，传的是less仿函数，底层是一个大堆，想控制小的优先级高，传greater仿函数，底层是一个小堆。

仿函数

仿函数概念

仿函数，即函数对象。一种行为类似函数的对象，调用者可以像函数一样使用该对象，其实现起来也比较简单：用户只需要实现一种新类型，在类中重载operator()即可，参数根据用户所要进行的操作选择匹配。

内置类型比较大小关系：
//仿函数/函数对象 --- 对象可以像调用函数一样去使用
struct less
{
	//()运算符重载--用于比较大小
	bool operator()(int x, int y)
	{
		return x < y;
	}
};
自定义类型比较less：
template<class T>
struct less//用于 < 的比较
{
	bool operator()(const T& x, const T& y) const
	{
		return x < y;
	}
};
自定义类型比较greater
template<class T>
struct greater//用于  > 的比较
{
	bool operator()(const T& x, const T& y) const
	{
		return x > y;
	}
};
less和greater的测试
//测试less
less<int> LessCom;
cout << LessCom(1, 2) << endl;//1
//测试greater
greater<int> GreaterCom;
cout << GreaterCom(1, 5) << endl;//0

堆的向上调整算法


//向上调整算法
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
			child = parent;
	    	parent = (child - 1) / 2;
		}
		else
		{
			//此时不需要调整，直接break
			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
			child++;
		}
		//利用仿函数建堆
		if (comFunc(_con[parent], _con[child]))
		{
			//如果为真，交换
			swap(_con[parent], _con[child]);
			//更新child和parent
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			//此时不需要调整，直接break
			break;
		}
	}
}

3.3 priority_queue的模拟实现

借助上文实现好的仿函数，向上建堆，向下建堆。现在可以很好的模拟实现优先级队列了。

总代码如下


namespace cpp
{
    //仿函数/函数对象 --- 对象可以像调用函数一样去使用
	template<class T>
	struct less
	{
		//()运算符重载--用于比较大小
		bool operator()(const T& x, const T& y) const
		{
			return x < y;
		}
	};
	template<class T>
	struct greater
	{
		//()运算符重载--用于比较大小
		bool operator()(const T& x, const T& y) const
		{
			return x > y;
		}
	};
 
	//优先级队列
	template<class T, class Container = vector<T>, class Compare = less<T>>
	class priority_queue
	{
		Compare _comFunc;
	public:
		//构造函数
		priority_queue(const Compare& comFunc = Compare())
			:_comFunc(comFunc)
		{}
		//传迭代器区间构造
		template <class InputIterator>
		priority_queue(InputIterator first, InputIterator last, const Compare& comFunc = Compare())
			: _comFunc(comFunc)
		{
			while (first != last)
			{
				_con.push_back(*first);
				first++;
			}
			//建堆
			for (int i = ((int)_con.size() - 1) / 2; i >= 0; i--)
			{
				//向下调整
				AdjustDown(i);
			}
		}
 
		//向上调整算法
		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
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					//此时不需要调整，直接break
					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
					child++;
				}
				//利用仿函数建堆
				if (comFunc(_con[parent], _con[child]))
				{
					//如果为真，交换
					swap(_con[parent], _con[child]);
					//更新child和parent
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					//此时不需要调整，直接break
					break;
				}
			}
		}
		//插入数据
		void push(const T& x)
		{
			_con.push_back(x);
			//每插入一个数字，都要向上调整键堆
			AdjustUp((int)_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有效数据个数
		size_t size()
		{
			return _con.size();
		}
		//判空
		bool empty()
		{
			return _con.empty();
		}
	private:
		Container _con;
	};
}

测试


void test_priority_queue()
{
	cpp::priority_queue<int> pq;//编译器默认less仿函数
	pq.push(9);
	pq.push(4);
	pq.push(7);
	pq.push(0);
	pq.push(2);
	cout << pq.size() << endl;//5
	while (!pq.empty())
	{
		cout << pq.top() << " ";//9 7 4 2 0
		pq.pop();
	}
}

如果我们把仿函数改成greater

cpp::priority_queue<int, vector<int>, greater<int>> pq;

结果如下：

四、容器适配器

适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。

标准库中stack和queue的底层结构

虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和队列只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque，比如：

deque原理介绍

deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，为了管理这些连续空间，deque 容器用中控数组（数组名假设为 map）存储着各个连续空间的首地址。也就是说，map 数组中存储的都是指针，指向那些真正用来存储数据的各个连续空间（如下图所示）。

通过建立 map 数组，deque 容器申请的这些分段的连续空间就能实现“整体连续”的效果。换句话说，当 deque 容器需要在头部或尾部增加存储空间时，它会申请一段新的连续空间，同时在 map 数组的开头或结尾添加指向该空间的指针，由此该空间就串接到了 deque 容器的头部或尾部。

当中控数组map数组满了的时候，再申请一块更大的连续空间供 map 数组使用，将原有数据（很多指针）拷贝到新的 map 数组中，然后释放旧的空间。

deque的优缺点
与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必vector高的。此外还支持随机访问。cpu高速缓存命中率高。
与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。
但是，deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。deque也不适合中部的插入删除，因为要挪动数据，效率低。
为什么选择deque作为stack和queue的底层默认容器

stack是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的线性结构，都可以作为stack的底层容器，比如vector和list都可以；queue是先进先出的特殊线性数据结构，只要具有push_back和pop_front操作的线性结构，都

可以作为queue的底层容器，比如list。但是STL中对stack和queue默认选择deque作为其底层容器，主要是因为：

stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高。

结合了deque的优点，而完美的避开了其缺陷。

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】