前言

容器适配器是一个封装了序列容器的类模板,它在一般序列容器的基础上提供了一些不同的功能,之所以称之为容器适配器,是因为它可以通过适配容器的现有接口来提供不同的功能

简单的理解容器适配器,其就是将不适用的序列式容器(包括 vector、deque 和 list)变得适用。

STL中的三大容器适配器:stack、queue、priority_queue。

一:deque(双端队列)

在学习容器适配器之前我们首先了解一个叫做deque的序列容器。

deque(双端队列): 是一个双端操作,任意位置O(1)插入删除加上随机访问的序列容器,并且不需要增容,deque集合了vector和list的优点,但是deque随机访问的效率低(排序)

  • 双端队列的底层:

双端队列底层是一段假想的连续空间,实际是分段连续的 ,由一段段连续的小空间组成。

问题一: deque怎么管理这一段段连续的小空间呢?

这里deque通过中控映射的方式管理这一段段连续的小空间,中控映射其实就是一个指针数组,通过指针指向一段段连续的小空间,如果扩容,只需要考虑指针数组的扩容,这样代价就会小很多。

问题二: deque如何实现随机访问呢?

需要计算访问的数据在哪个小空间中,数据量较大的场景下耗时会比较长。

问题三: deque的迭代器结构?

first指向一段小空间的开始,last指向一段小空间的结束,cur指向迭代器当前位置,node指向中控指针数组中的结点用于切换小空间。

注意:双端队列并不符合先进先出的序列特点。

  • 双端队列的应用:

双端队列被用于STL容器stack和queue的默认底层数据结构

1.stack和queue不需要遍历,只需要在固定的一端或者两端进行操作。

2.在stack中元素增长时,deque比vector的效率高(扩容时不需要搬移大量数据);queue中的元素增长
时,deque不仅效率高,而且内存使用率高。

二:stack(栈)

stack类的基本使用这里就不多做讲解,我们主要来研究一下stack类的模拟实现。

stack是一个封装了deque< T >容器的适配器类模板,默认实现的是一个后入先出(Last-In-First-Out,LIFO)的压入栈。stack< T > 模板定义在头文件 stack 中。

#pragma once
#include<vector>
#include<list>

// 用STL容器封装适配转换实现出来的stack(复用性)
namespace WJL{
	// Container:容器
	template<class T, class Container>
	class Stack{
	public:
		void push(const T& x){
			_con.push_back(x);
		}

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

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

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

		T& top(){
			return _con.back();
		}
	private:
		Container _con;
	};
	
	void Test(){
		Stack<int, vector<int>> st;
		//Stack<int, list<int>> st;
		st.push(1);
		st.push(2);
		st.push(3);
		st.push(4);
		st.push(5);

		while (!st.empty()){
			cout << st.top() << " ";
			st.pop();
		}
		cout << endl;
	}
}

输出结果:5 4 3 2 1

三:queue(队列)

queue类的基本使用这里就不多做讲解,我们主要来研究一下queue类的模拟实现。

queue是一个封装了deque< T >容器的适配器类模板,默认实现的是一个先入先出(First-In-First-Out,LIFO)的队列。queue< T > 模板定义在头文件queue中。

注意:vector不提供支持头部操作的接口,所以vector不能作为queue的适配容器。

#pragma once
#include<list>

// 用STL容器封装适配转换实现出来的queue(复用性)
namespace WJL{
	// Container:容器
	template<class T, class Container>
	class Queue{
	public:
		void push(const T& x){
			_con.push_back(x);
		}

		void pop(){
			// vector不提供pop_front()接口
			_con.pop_front();
		}

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

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

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

		T& back(){
			return _con_back();
		}
	private:
		Container _con;
	};


	void Test(){
		Queue<int, list<int>> q;

		q.push(1);
		q.push(2);
		q.push(3);
		q.push(4);
		q.push(5);

		while (!q.empty()){
			cout << q.front() << " ";
			q.pop();
		}
		cout << endl;
	}
}

输出结果:1 2 3 4 5

四:priority_queue(优先级队列)

优先级队列是一种容器适配器,它的第一个元素总是它包含元素中优先级最高的。

4.1 优先级队列的使用

优先级队列默认使用vector作为其底层存储数据的容器,在vector上又使用了堆算法将vector中元素构造成堆的结构,默认情况下priority_queue是大堆

#include<iostream>
#include<queue>
#include<functional> // 仿函数头文件
using namespace std;

void test_priority_queue(){
	1. 默认大的优先级高,优先级队列底层实际是一个大堆
	//priority_queue<int> pq;
	2. 应用仿函数使小的优先级高
	priority_queue<int, vector<int>, greater<int>> pq;
	pq.push(3);
	pq.push(1);
	pq.push(9);
	pq.push(4);
	pq.push(2);

	注:容器适配器不支持迭代器,容器适配器通常包含特殊的性质,迭代器会破坏容器适配器原有性质
	while (!pq.empty()){
		cout << pq.top() << " ";
		pq.pop();
	}
}

int main(){
	test_priority_queue();
	return 0;
}
4.2 优先级队列的模拟实现

优先级队列运用仿函数控制优先级大小(大小堆)。

#include<vector>
namespace WJL{
	// 仿函数(函数对象)
	template<class T>
	// class:成员部分公有 部分私有
	// struct:成员全部公有
	struct less{
		bool operator()(const T& x1, const T& x2){
			return x1 < x2;
		}
	};

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

	// 默认大堆
	template<class T,class Container = vector<T>,class Compare = less<T>>
	class priority_queue{
	public:
		// 向上调整算法
		void AdjustUp(int child){
			Compare com;
			int parent = (child - 1) / 2;
			while (child > 0){
				// child > parent
				if (com(_con[parent], _con[child])){
					swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else{
					break;
				}
			}
		}
		void push(const T& x){
			_con.push_back(x);
			AdjustUp(_con.size() - 1);
		}

		//向下调整算法
		void AdjustDown(int root){
			Compare com;
			size_t parent = root;
			size_t child = parent * 2 + 1;
			while (child < _con.size()){
				// 选出左右孩子中较大的
				if (child+1 < _con.size()&&com(_con[child],_con[child + 1])){
					child++;
				}
				// child > parent
				if (com(_con[parent], _con[child])){
					swap(_con[parent], _con[child]);
					parent = child;
					child = parent * 2 + 1;
				}
				else{
					break;
				}
			}
		}

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

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

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

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

	void test_priority(){
		//priority_queue<int> pq;
		priority_queue<int,vector<int>,greater<int>> pq;

		pq.push(3);
		pq.push(1);
		pq.push(9);
		pq.push(4);
		pq.push(2);
		while (!pq.empty()){
			cout << pq.top() << " ";
			pq.pop();
		}
		cout << endl;
	}
}
运行结果:1 2 3 4 9
小结

STL中的容器适配器都是通过基础序列容器适配转换而来的,并不是原生实现的 , 提高了代码的复用性。

需要注意的是,STL 中的容器适配器,其内部使用的基础序列容器并不是固定的,用户可以在满足特定条件的多个基础容器中自由选择。并且,容器适配器不支持迭代器,因为支持迭代器会导致适配器的性质改变。

Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐