【C++】常见的STL容器适配器详解及其模拟实现

qeen87

485人浏览 · 2026-07-27 23:25:13

qeen87 · 2026-07-27 23:25:13 发布

前言：
栈和队列这两个数据结构在前面的文章中已经介绍过了，并且当时也使用C语言分别进行了实现，而优先级队列的底层其实就是堆，关于堆前面同样使用C语言实现过，所以本文就不再花费太多篇幅介绍它们的基本原理了。本篇主要来认识一下STL中的容器适配器，并尝试借助前面介绍过的容器对stack、queue和priority_queue进行简单的模拟实现，后面还会顺便介绍一下deque以及它的迭代器。

1.什么是容器适配器

在STL中，vector、list和deque等容器都有自己完整的一套接口，而stack、queue和priority_queue却没有重新设计一套底层存储结构。其实可以把容器适配器理解成在已有容器外面又套了一层接口，它的内部使用现成的容器保存数据，外部只能通过适配器提供的接口来操作数据。至于内部到底使用vector、list还是deque，只要这个容器能够提供适配器所需要的接口，就可以作为它的底层容器。

在这里插入图片描述

1.1 stack

stack就是我们比较熟悉的栈，它遵循后进先出的原则，只允许在栈顶进行插入、删除和访问。因此它的底层容器至少需要提供push_back、pop_back和back这些接口，vector、list和deque都可以满足这个要求。

需要注意的是，标准库中的std::stack默认使用deque作为底层容器，而本文模拟实现的qen::stack默认使用的是vector。底层容器只是实现上的选择，并不会改变stack对外所表现出来的使用方式。

1.2 queue

queue遵循先进先出的原则，数据从队尾进入，再从队头离开，所以它的底层容器需要同时支持push_back、pop_front、front和back。deque和list都能满足这些要求，而vector没有pop_front接口，所以不能直接作为queue的底层容器。

标准库中的std::queue默认使用的同样是deque。deque既能在尾部插入，又能在头部删除，刚好可以满足queue的需要。
在这里插入图片描述

1.3 priority_queue

priority_queue叫做优先级队列。普通队列按照数据进入的先后顺序出队，而优先级队列每次取出的都是当前优先级最高的元素。它的底层通常使用数组保存一棵完全二叉树，再通过堆的向上调整和向下调整来维护元素之间的关系。

标准库中的priority_queue默认使用vector作为底层容器，并建立大堆，因此top得到的是当前最大的元素；如果把比较方式改为greater，就可以建立小堆，让top得到当前最小的元素。这里需要注意，堆只保证父子结点之间满足对应关系，并不代表底层所有元素已经整体有序。

在这里插入图片描述

2.deque与它的迭代器

deque叫做双端队列，从名字也能看出来它的两端都可以进行插入和删除。vector虽然支持随机访问，但是头部操作的代价比较大；list能够比较方便地插入和删除，却不支持随机访问。deque则同时照顾了这两方面，既能高效地操作两端，又支持随机访问。

在这里插入图片描述

从使用者的角度来看，deque中的元素像是放在一段连续空间中，但它的一种典型实现并不是开辟一整块连续空间，而是由多段定长缓冲区组成，再通过一个中控数组把这些缓冲区的地址组织起来。这个中控数组通常被称为map，不过它和STL中的map容器并不是一回事。

在这里插入图片描述

由于deque的空间是分段的，所以它的迭代器也不能只是一个普通指针。一个典型的deque迭代器通常需要保存下面几个位置：

cur：指向当前访问的元素。
first：指向当前缓冲区的起始位置。
last：指向当前缓冲区的尾后位置。
node：指向中控数组中保存当前缓冲区地址的位置。

迭代器在同一段缓冲区中移动时，直接改变cur就可以了；当cur走到当前缓冲区的边界时，就需要先通过node找到相邻的缓冲区，再让cur指向新缓冲区中的对应位置。随机访问也是在确定跨越了多少个缓冲区之后，再计算最终落在哪一段以及段内的哪个位置。

这也说明了deque虽然支持随机访问，但是它的底层结构并不像vector那样简单连续，它需要借助这些额外的结构把一段段缓冲区组织起来。

3.容器适配器的模拟实现

下面就借助前面介绍过的容器，简单模拟实现一下这三个容器适配器。真正负责保存数据的是成员变量_con，stack、queue和priority_queue只需要根据自己的特点去调用底层容器提供的接口即可。

3.1 stack的模拟实现

#pragma once

#include <vector>
#include <list>



namespace qen
{
	// 实现的是适配器模式, 默认底层为vector
	template<class T, class Container = std::vector<T>>
	class stack
	{
	public:

		// 因为这里我们使用了std的容器模拟栈，会自动
		// 调用他们自己的构造函数所以我们这里
		// 就不用写了， 同理析构也是

		void push(const T& x)
		{
			_con.push_back(x);
		}

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

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

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

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

	private:
		Container _con;
	};



}

这里把底层容器的类型设置成了模板参数Container，默认类型是vector。stack的push、pop和top分别复用了底层容器的push_back、pop_back和back，而size与empty直接使用底层容器对应的接口。

由于_con本身就是一个容器对象，它会自动调用自己对应的构造函数和析构函数，所以这里不需要再单独编写构造和析构。更换底层容器时也不需要修改stack内部的代码，只需要在实例化时传入新的容器类型即可。

3.2 queue的模拟实现

#pragma once
#include <deque>
#include <queue>

namespace qen
{
	//队列这里默认用双端队列
	template<class T, class Container = std::deque<T>>
	class queue
	{
	public:


		void push(const T& x)
		{
			_con.push_back(x);
		}

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

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

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


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

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

	private:
		Container _con;
	};


}

queue和stack的整体结构基本相同，区别主要在于数据进出的方向。push仍然从尾部插入数据，而pop需要从头部删除数据，所以默认底层容器选择了deque。front用来得到队头元素，back用来得到队尾元素，这样就保留了queue先进先出的特点。

3.3 priority_queue的模拟实现与仿函数

#pragma once
#include <vector>

namespace qen
{
	
	template<class T>
	class Less
	{
	public:
		bool operator()(const T& x, const T& y)
		{
			return x < y;
		}
	};

	template<class T>
	class Greater
	{
	public:
		bool operator()(const T& x, const T& y)
		{
			return x > y;
		}
	};

	// 默认是大根堆
	template<class T, class Container = std::vector<T>, class Compare = Less<T>>
	class priority_queue
	{
	public:
		
		void AdjustUp(int child)
		{
			Compare com;
			int parent = (child - 1) / 2;
			while (child > 0)
			{
				//if (_con[child] > _con[parent])
				if (com(_con[parent], _con[child]))
				{
					std::swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}

			}
		}

		void AdjustDown(int parent)
		{

			Compare com;
			int child = (parent * 2) + 1;
			while (child < _con.size())
			{
				// _con[child] < _con[child + 1]
				if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
				{
					++child;
				}

				// _con[child] > _con[parent]
				if (com(_con[parent], _con[child]))
				{
					std::swap(_con[child], _con[parent]);
					parent = child;
					child = (parent * 2) + 1;
				}
				else
				{
					break;
				}
			}
	
		}


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


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

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

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

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

	private:
		Container _con;

	};


}

priority_queue的底层默认使用vector保存堆。插入元素时，先把新元素放到容器尾部，再从新元素所在的位置开始向上调整；删除堆顶元素时，先交换堆顶与最后一个元素，删除尾部元素以后，再从堆顶开始向下调整。top只需要返回下标为0的元素，因为这里始终会把当前堆顶维护在这个位置。

这里还使用了仿函数来决定建立大堆还是小堆。所谓仿函数，其实就是重载了operator()的类，创建出来的对象可以像普通函数一样使用。Less判断第一个元素是否小于第二个元素，Greater则判断第一个元素是否大于第二个元素。

调整函数中的Compare com会根据模板参数创建对应的比较对象。当使用默认的Less时，如果父结点小于子结点就进行交换，最后得到大堆；把比较方式换成Greater以后，如果父结点大于子结点就进行交换，最后得到小堆。这样只需要改变比较方式，就可以让同一份调整代码维护两种不同的堆。

4.简单测试

#include <iostream>
#include "MyStack.h"
#include "MyQueue.h"
#include "Mypriority_queue.h"

void Test1()
{
	//qen::stack<int> st;	
	//你也可以指定的使用底层的容器
	qen::stack<int, std::list<int>> st;
	st.push(1);
	st.push(2);
	st.push(3);
	st.push(4);

	while (!st.empty())
	{
		std::cout << "元素个数-》" << st.size() << std::endl;
		std::cout << st.top() << std::endl;
		st.pop();
	}
	std::cout << "元素个数-》" << st.size() << std::endl;

}

void Test2()
{
	qen::queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);

	std::cout << "front = " << q.front() << std::endl;  // 1
	std::cout << "back = " << q.back() << std::endl;    // 3

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

template <class T, class Container, class Compare>
void std_print_heap(std::priority_queue<T, Container, Compare>& pq)
{
	pq.push(4);
	pq.push(1);
	pq.push(5);
	pq.push(7);
	pq.push(9);
	while (!pq.empty())
	{
		std::cout << pq.top() << " ";
		pq.pop();
	}
	std::cout << std::endl;
}

void Test3()
{
	// 默认是大堆
	std::priority_queue<int> pq1;
	// 也可以通过仿函数指定成小根堆
	std::priority_queue<int, std::vector<int>, std::greater<int>> pq2;
	std_print_heap(pq1);
	std::cout << "===========================" << std::endl;
	std_print_heap(pq2);

}



template <class T, class Container, class Compare>
void qen_print_heap(qen::priority_queue<T, Container, Compare>& pq)
{
	pq.push(4);
	pq.push(1);
	pq.push(5);
	pq.push(7);
	pq.push(9);
	while (!pq.empty())
	{
		std::cout << pq.top() << " ";
		pq.pop();
	}
	std::cout << std::endl;
}


void Test4()
{
	qen::priority_queue<int> pq1;
	qen::priority_queue<int, std::vector<int>, qen::Greater<int>> pq2;
	qen_print_heap(pq1);
	std::cout << "===========================" << std::endl;
	qen_print_heap(pq2);
}

int main()
{
	// Test1();
	// Test2();
	// Test3();
	Test4();

	return 0;
}

Test1把list指定为stack的底层容器，用来说明只要接口满足要求，适配器就可以更换底层容器；Test2验证了queue的队头、队尾以及先进先出的顺序；Test3对标准库中的大堆和小堆进行了测试；Test4则使用相同的数据测试我们自己模拟实现的priority_queue。

当前main函数调用的是Test4，运行结果如下：

9 7 5 4 1
===========================
1 4 5 7 9

可以看到，默认比较方式维护的是大堆，所以元素按照从大到小的顺序离开；换成Greater以后维护的是小堆，元素按照从小到大的顺序离开。模拟实现与预期结果相同。

模拟实现完成以后，再回头看容器适配器其实就很简单了：内部还是借助已有的容器保存数据，只是根据自己的特点把需要的接口重新组合了一下。stack和queue主要处理数据进出的方向，而priority_queue还需要借助堆和仿函数维护元素的优先级。

完

亚马逊云科技技术品牌专区

更多推荐

open-code-review Codex 插件教程：对话式调用评审技能指南

本文是一份面向新手的 **open-code-review Codex 插件教程**，教你在 Codex 中通过对话式方式调用 open-code-review 的 AI 代码评审技能。open-code-review 是阿里巴巴开源的 AI 代码评审工具，采用"确定性流水线 + LLM Agent"混合架构，内置多语言评审规则（NPE、线程安全、XSS、SQL 注入等），可在 Codex 里用一

亚马逊云科技技术品牌专区

OBS Studio 完整指南：免费开源录屏与直播软件从零上手

想做一场像模像样的直播，或者把屏幕内容录成教程视频，但一想到商用软件的订阅费就有些犹豫？其实你不需要花一分钱。OBS Studio 是一款免费开源的直播与录屏软件，支持 Windows、macOS 和 Linux，采集、混音、编码、推流、录制，一条流水线全包了。## 先搞清楚 OBS Studio 是什么OBS Studio 是一个"场景化"的采集合成工具：你把摄像头、窗口、浏览器、图片、

亚马逊云科技技术品牌专区

如何用MediaCrawler爬取小红书抖音数据？7大平台爬虫从安装到实战完整指南

MediaCrawler 是一个支持小红书、抖音、快手、B站、微博、百度贴吧、知乎的开源自媒体数据采集工具。它能按关键词、按帖子、按创作者主页三种方式抓取笔记/视频内容、评论甚至二级评论，并把结果存成 JSON、CSV、Excel 或数据库。适合做市场调研、竞品监控、内容选题的运营人员，以及想要现成爬虫框架而不想从零写 JS 逆向的开发者。## 从一次"手动抄数据"说起想象这个场景：你负责