【C++】STL六大组件之一——适配器（adapters）

---

1. 前言

开篇发问什么是STL?

💭STL全名标准模板库（Standard Template Library）是C++中的一个软件库建立了数据结构和算法的一套标准并降低了其间的耦合性以达到提升各自的独立性、弹性和复用性的目的。

📝 STL提供了六大组件

1. 容器（containers）：如vector、list等数据结构用以存放数据。
2. 算法（algorithms）：如常用的sort、swap算法。
3. 迭代器（iterators）：扮演容器和算法之间的胶合剂是一种”泛型指针“。
4. 空间配置器：负责空间配置与管理。
5. 仿函数：行为类似函数的类。
6. 适配器（adapters）：一种用来修饰容器或仿函数或迭代器接口的东西

本文将着重介绍STL六大组件之一 —— 适配器

---

2. 初始适配器

2.1 适配器的概念

适配器（adapters）在STL组件的灵活组合运用功能上扮演着轴承、转换器的角色。Adapters这个概念事实上是一种设计模式（design pattern）在《Design Patterns》一书中对adapter样式的定义如下：将一个类（class）的接口转换成另一个类（class）的接口使原本因接口不兼容而不能合作的两个类（classes）可以一起运作。

节选自《STL源码剖析》一书

💡 通俗理解如果一个类（class A）（或是函数等）的成员、功能与另一个类（class B）类似但是有一些不同之处可以通过封装class B来实现class A从而将class B的接口转化为class A 的接口。总而言之就是把一个已经存在的东西改成一个我们需要的东西。

2.2 适配器的分类

💨STL所提供的各种适配器大致分为三类：

1. 容器适配器（container adapters）
2. 仿函数适配器（function adapters）
3. 迭代器适配器（iterator adapters）

📝 接下来将逐个介绍

---

3. 容器适配器（container adapters）

💭 其实STL给我们的stack、queue（栈和队列）并不是所谓的容器（如vector、list等）而是容器适配器。stack和queue封装其他容器修饰其接口以满足自身逻辑结构的需求（stack先入后出、queue先入先出）。

💬下面抛出两个问题：

• 问：所谓STL中的stack和queue封装其他容器这个其他容器是什么呢？
  答：是另外一个线性序列容器deque

• 问：为什么要使用deque作为stack和queue的底层容器呢？
  答：想要回答这个问题必须先简单认识deque的结构。

3.1 认识deque

3.1.1 逻辑结构

deque是一种双向开口的连续动态线性空间又称双端队列 （这里的队列没有先进先出的原则）。所谓双向开口就是可以在空间头尾两端分别做元素的插入和删除操作。

💭对比vector虽然vector也是可以在头尾两端进行操作的连续线性空间但是在其头部操作的效率非常低因此无法被接受。

(deque的逻辑结构示意图)

3.1.2 物理结构

⭕一些概念

1. deque并不是真正的连续空间而是由一段一段的定量连续空间构成的这些片段式的小空间称为缓冲区。
2. 缓冲区由一个中控台控制着并且各段小空间以及中控台会根据需要动态变化。缓冲区是deque存储数据的主体。
3. 中控台是一个类似指针数组的空间其中每个元素是一个指针分别指向不同的缓冲区。

(deque的物理结构示意图)

4. deque没有vector和array所谓容量（capacity）的概念因为它是动态增长的。deque的插入、删除会关注操作位置所在缓冲区的元素个数。

💭拿尾插来说若操作位置所在缓冲区尚未满载则直接插入

💭若操作位置所在缓冲区已满则要新开辟一个缓冲区并链接到当前中控台位置的下一位置再插入到新缓冲区的首位。

此外尾删（pop_back）、头插（push_front）、头删（pop_front）也都会关注操作位置所在缓冲区的元素个数。做法与尾插相同这里就不一一演示

3.1.3 deque的迭代器

deque不是真正意义上的连续空间而是分段式的空间为了营造出整体连续的假象满足随机访问的需求STL为deque设计出一个复杂的迭代器。

🔎 deque的迭代器类包含四个指针分别是：cur, first, last, node

(deque的迭代器示意图)

指针	指向
cur	此迭代器所指的当前元素
first	当前元素所在缓冲区的头部
last	当前元素所在缓冲区的尾部
node	中控台内指向当前缓冲区的指针的位置

• deque如何利用这样的迭代器来维护其“连续”的空间？

💭deque的类成员大致如下用了两个迭代器控制空间的首尾。

template <class T>
class deque
{
	// ...
	iterator start;  // cur指向第一个结点
	iterator finish; // cur指向最后一个结点的下一个位置
	map_pointer map; // 指向中控台实际是个二级指针T**（与迭代器中的node指针类型相同）
}

start、finish的指向

💡综上所述：

迭代器中各个指针各司其职cur负责迭代器的首要工作访问所指元素first和last则在告诉迭代器访问的范围当使用迭代器对deque做遍历操作时只要迭代器指向还没脱离当前缓冲区就支持随机访问而当迭代器的cur和last指针相同时若要继续访问下一个元素则要跳到下一个缓冲区恰好node就会帮我们找到下一个（或上一个）缓冲区。

---

3.1.4 选择deque做stack/queue底层容器的原因

💭 简单了解deque的结构后我们就可以解答刚刚提出的问题：为什么要使用deque作为stack和queue的底层容器呢？

先谈谈deque相比vector、list的优缺点

• deque的缺点

1. 随机访问效率低。虽然deque支持随机访问但是其效率远没有vector、array的效率高。因为其分段式的结构使其在跨越不同缓冲区的时候会消耗时间从而降低效率。
2. 不适合遍历。受其结构特性影响对deque遍历时需要频繁检测迭代器是否到达某个缓冲区的边界导致效率低下。

• deque的优点

1. 相比vectordeque减少了空间浪费按需开辟空间。在数据量较少的情况下deque的数据都集中在某几个缓冲区此时可以基本忽略其缺点（随机访问效率低、不适合遍历）性能优于vector。而且deque的头删、头插的效率也远高于vector因为它不用挪动数据最多只需再开一块空间。
2. 相比listdeque支持随机访问。并且其底层是连续空间空间利用率比较高不需要存储额外字段

🔎为什么要使用deque作为stack和queue的底层容器呢？

• stack和queue都是特殊的线性数据结构只在端口处访问数据stack先进先出queue先进后出。都不支持遍历和随机读取所以deque运用于stack和queue中其缺点并不会体现出来。
• 而且deque支持头插尾插、头删尾删（且效率高于vector）提供“整体连续”的空间提高了空间的使用率（vector有空间冗余问题list需要存储额外字段）。
• 所以使用deque作为stack和queue的底层容器可谓是“取其精华、去其糟粕”规避了deque的缺点利用了deque的优点。

---

💭弄清楚STL中stack和queue的底层容器是什么接下来再介绍stack和queue

3.2 stack

🔎stack（栈）是一种容器适配器逻辑结构是后入先出（LIFO）且只能访问栈顶元素。作为容器适配器stack底层容器可以是任何支持push_back、pop_back、empty、back等操作的容器但STL选择了deque原因上文已解释。封装特定容器后再提供一系列特殊的接口以达到其后入先出的效果。

stack文档介绍

（stack的逻辑结构示意图）

💭 stack的结构和使用方法相信大家已经十分熟悉这里就不过多解释重点在于如何基于适配器的设计模式模拟实现一个stack。

⭕下面直接上代码：

namespace ckf // 命名空间封装防止与标准库中的stack命名冲突
{
	template <class T,class Container = deque<T>> //增加一个模板参数用于指定底层容器类型
	class stack
	{
		typedef T value_type;
		
	public:
		// 设计思路：将deque的尾部视为stack的栈顶即可复用deque的接口加以修饰成为stack的接口
		
		void push(value_type val) // 压栈操作
		{
			_st.push_back(val); // 复用deque的push_back
		}

		void pop() // 入栈操作
		{
			_st.pop_back(); // 复用deque的pop_back
		}

		value_type& top() // 取栈顶元素
		{
			return _st.back(); // 复用deque的back取尾部元素
		}

		const value_type& top() const // 取栈顶元素（受const保护的）
		{
			return _st.back();
		}

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

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

💬 测试

void testStack()
{
	ckf::stack<int> st;
	st.push(1);
	st.push(2);
	st.push(3);
	st.push(4);
	st.push(5);
	st.pop();
	st.pop();

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

💡 符合预期

---

3.3 queue

🔎queue（队列）也是一种容器适配器逻辑结构是先入先出（FIFO）可以访问队头元素和队尾元素。 同样使用deque作为底层容器修饰deque接口成为自身的接口以满足自身先入先出（队尾入、队头出）的逻辑。

queue文档介绍

（queue的逻辑结构示意图）

⭕ 基于适配器的设计模式模拟实现一个queue

namespace ckf
{
	template <class T, class Container = deque<T>>
	class queue
	{
		typedef T value_type;
		
	public:
	
		void push(value_type val) // 入队
		{
			_q.push_back(val);
		}

		void pop() // 出队
		{
			_q.pop_front();
		}

		// 取队尾元素
		value_type& back()
		{
			return _q.back();
		}

		const value_type& back() const 
		{
			return _q.back();
		}
		
		// 取队头元素
		value_type& front()
		{
			return _q.front();
		}

		const value_type& front() const
		{
			return _q.front();
		}

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

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

💬 测试

void testQueue()
{
	ckf::queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);
	q.push(5);
	q.pop();
	q.pop();

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

💡 符合预期

---

3.4 另一种容器适配器 —— 优先级队列

3.4.1 认识priority_queue

💭 在STL库中除了stack和queue这两种容器适配器外还存在另一种容器适配器 —— priority_queue即优先级队列。

🔎priority_queue 是一种容器适配器不同于队列它并没有先入先出的逻辑结构而是一种根据元素优先级决定排列顺序的结构且只能读取其头部第一个数据 top不能修改。STL中默认priority_queue第一个元素始终是最大元素。

---

3.4.2 priority_queue的使用

💭 priority_queue和queue在同一个头文件使用时#include <queue>即可

• 构造函数

有全缺省默认构造也有迭代器范围构造根据迭代器区间中的序列生成对应的 priority_queue。

• 其他成员函数

成员函数	功能
push	压入一个新元素
pop	弹出首元素
top	读取首元素
empty	判空
size	获得长度

详见priority_queue文档介绍

⭕ 注意：priority_queue 的push和pop操作在改变其序列后会重新调整顺序保证首元素一定是最大元素。

（优先级队列push数据前后的示意图）

（优先级队列pop数据前后的示意图）

3.4.3 底层实现

🔎事实上priority_queue底层就是一个堆（默认是大堆）因为大堆堆顶元素始终是最大的所以优先级队列首个元素始终是最大的。学习过堆的存储方式我们知道堆用一个数组存储即可。因此priority_queue的底层容器是一个vector通过修饰vector的各种接口实现堆的效果。

关于堆的原理和实现我在《【数据结构】二叉树BinaryTree 》一文中已详细分析这里不再过多赘述直接利用堆的特性模拟实现一个priority_queue。

namespace ckf
{
	// 优先级队列
	template <class T,class Container = vector<T>,class Compare = less<T>>
	class priority_queue
	{
	public:
		priority_queue() // 空构造
		{}

		template <class InputIterator>
		priority_queue(InputIterator first, InputIterator last) // 迭代器范围构造函数
			:_cont(first, last)
		{
			// make heap
			int begin_parent = (_cont.size() - 1 - 1) / 2;
			while (begin_parent >= 0)
			{
				adjust_down(begin_parent--);
			}
		}

		void adjust_up(int child) //向上调整算法
		{
			int parent = 0;
			while (child > 0) // parent >= 0 err!! 当child == 0 parent = (child - 1) / 2 = 0;
			{
				parent = (child - 1) / 2;
				if (_cmp(_cont[parent], _cont[child]))
				{
					swap(_cont[child], _cont[parent]);
					child = parent;
				}
				else
					break;
			}
		}

		void adjust_down(int parent) // 向下调整算法
		{
			int child = parent * 2 + 1;
			while (child < _cont.size())
			{
				if (child + 1 < _cont.size() && _cmp(_cont[child], _cont[child + 1])) // 找大孩子
				{
					++child;
				}

				if (_cmp(_cont[parent], _cont[child]))
				{
					swap(_cont[child], _cont[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
					break;
			}
		}

		void push(const T& val) // 入数据
		{
			_cont.push_back(val);

			adjust_up(_cont.size() - 1);
		}

		void pop() // 出数据
		{
			swap(_cont.front(), _cont.back());
			_cont.pop_back();

			adjust_down(0);
		}

		bool empty() const // 判空
		{
			return _cont.empty();
		}

		const T& top() const // 取堆顶元素且不能修改（修改会破坏堆的结构）
		{
			return _cont[0];
		}

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

	private:
		Container _cont;
		Compare _cmp = Compare(); // 仿函数
	};
}

🔎 模拟priority_queue的大致思路就是封装vector并修饰vector的各个接口以实现堆的逻辑这就是适配器的设计模式。
而从代码中我们看到在对两个元素进行比较时并没有直接用> <去比而是用了一个 Compare类型的对象这个对象是priority_queue的一个成员变量这个对象我们称之为仿函数为什么能用其进行元素比较呢？下面介绍。

---

4. 仿函数适配器（function adapters）

4.1 认识仿函数

💭 引入：很多算法、对象其实都有几个版本举个例子简单的排序算法就有升序、降序两个版本而上面我们模拟实现的priority_queue默认底层是大堆但也可以修改为小堆。先拿排序来说若要控制一个排序算法是升序或是降序应该怎么办呢？从C语言的角度可以为该算法增加应该参数这个参数是一个函数指针我们传入不同的比较函数就可以实现不同方式的比较也就可以控制排序的是升降序。但是在STL中函数指针毕竟不能满足抽象性的要求也无法与其他组件搭配使用。因此STL提供了仿函数。

• 概念
  🔎仿函数是STL中六大组件之一又名函数对象其本质实际就是一个类是一个行为类似函数的类。 为了能够“行为类似函数”仿函数中必须对函数调用操作符进行重载即operator()使我们能够像调用函数一样去调用这个仿函数。

下面简单写一个仿函数less他的功能是判断左参数是否小于右参数。这是STL中提供的我们简单模拟实现一下。

namespace ckf
{
	template <class T>
	class less
	{
		bool operator()(const T& x, const T& y) const // 重载()
		{
			return x < y;
		}
	};
}

💬 测试

void test()
{
	less<int> cmp;

	cout << cmp(1, 100) << endl;
	cout << less<int>()(1, 100) << endl;
}

仿函数的调用方式有两种一是先创建一个仿函数对象在调用二是匿名对象调用。第二种方法较为常见。

⭕ 运行结果

STL中提供了许多的仿函数定义在functional头文件中

详见<functional>的文档介绍

现在我们知道什么是仿函数了也就知道了为什么priority_queue使用仿函数去进行元素大小的比较。若想让priority_queue的底层是小堆则给模板参数Compare传入greater<T>（大于的比较）即可。

greater的文档介绍

---

4.2 什么是仿函数适配器

💭STL中提供了一系列仿函数适配器（functor adapters）这些适配操作包括连结（bind）、否定（negate）、组合（compose）以及对一般函数或成员函数的修饰。

• 仿函数适配器可以封装、修饰一个仿函数变成符合我们需要的仿函数

💭 例如functional库里提供的仿函数适配器bind2nd可以指定某个仿函数的第二个参数。例如我们想要获得一个能够判断一个数是否小于10的仿函数bind2nd<less<T>, 10> （这是一个仿函数） 便能满足需求。

详见bind2nd的文档介绍

---

5. 迭代器适配器（iterator adapters）

💭 STL还为迭代器提供了一系列适配器包括：insert_iterator, reverse_iterator, istream_iterator等定义在头文件<iterator>中。

🔎作用：修饰普通迭代器的接口使其成为另一种迭代器发挥不同的作用。

（STL提供的iterator adapters一览）

💭 学习vector、list时调用rbegin(), rend()接口取出的反向迭代器事实上只是一个迭代器适配器就是这里的reverse_iterator。

reverse_iterator是一个类模板给模板参数传入一个迭代器类它就会将其封装为反向迭代器。

详见reverse_iterator的文档介绍

---

🔎 通过reverse_iterator深入理解迭代器适配器

• 如何实现反向迭代器呢？

反向无非就是迭代器的运动反向与原来的相反。即 ++ 变 ----变++。那么反向迭代器的前进操作只需在 reverse_iterator的operator++中调用Iterator的operator– 即可后退同理。

• 容器之反向迭代器的始末位置稍有不同

学过vector、list我们知道他们的begin接口取出的迭代器指向容器首位end指向最后一个元素的下一个位置。如下图：

（vector的begin,end示意图）

STL中为了配合迭代器区间的“前闭后开”的习惯规定容器的rbegin、rend指向如下：

因此当调用 * 操作时正向迭代器与反向迭代器的取值是不同的反向迭代器会获取指向位置的前一个元素。

（红色箭头代表迭代器的实际指向）

💬 reverse_iterator的模拟实现：

namespace ckf
{
	template <class Iterator, class Ref, class Ptr>
	class reverse_IteratorAdapter
	{
		typedef reverse_IteratorAdapter<Iterator, Ref, Ptr> Self;

	public:
		reverse_IteratorAdapter()
		{}

		explicit reverse_IteratorAdapter(const Iterator& it) // 用正向迭代器构造反向迭代器
			:_it(it)
		{}

		reverse_IteratorAdapter(const Self& otherIter) // 拷贝构造反向迭代器
			:_it(otherIter._it)
		{}

		Self& operator=(const Self& otherIter) // 赋值重载
		{
			if (*this != otherIter)
			{
				_it = otherIter._it;
			}

			return *this;
		}

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

		Self operator++(int) // 后置++
		{
			Self tmp(_it);
			--_it;
			return tmp;
		}

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

		Self operator--(int) // 后置--
		{
			Self tmp(_it);
			++_it;
			return tmp;
		}

		Ref operator*()
		{
			// 访问前一个
			Iterator tmp = _it;
			return *(--tmp);
		}

		Ptr operator->()
		{
			// 重载->就是取地址
			return &(operator*());
		}

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

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

	private:
		Iterator _it; // 底部封装了正向迭代器
	};

	// 容器（以vector为例）内部的类型定义和rbegin()、rend()接口

	template <class T>
	class vector
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;

		typedef reverse_IteratorAdapter<iterator, T&, T*> reverse_iterator;
		typedef reverse_IteratorAdapter<const_iterator, const T&, const T*> const_reverse_iterator;
		//...
		reverse_iterator rbegin()
		{
			return reverse_iterator(end());
		}

		const_reverse_iterator rbegin() const // const的容器就取const的迭代器为了保护容器内部数据
		{
			return const_reverse_iterator(end()); // 此处的end()为 const_iterator 类型传入构造函数构造函数的参数必须也是const_iterator类型才能接收
		}

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

		const_reverse_iterator rend() const
		{
			return const_reverse_iterator(begin());
		}
		//...
	}
}

⭕ 测试

void test_reverse_iterator()
{
	int arr[] = { 1,2,3,4,5 };
	ckf::vector<int> v(arr, arr + sizeof(arr) / sizeof(arr[0]));
	ckf::vector<int>::reverse_iterator rit = v.rbegin();
	while (rit != v.rend())
	{
		cout << *rit << " ";
		++rit;
	}
	cout << endl;
	
	const ckf::vector<int> v2(arr, arr + sizeof(arr) / sizeof(arr[0]));
	ckf::vector<int>::const_reverse_iterator crit = v2.rbegin();
	cout << *(++crit) << endl;
}

💡 符合预期

---

完。