C++ STL容器适配器使用指南

目录
  • 适配器
  • stack容器适配器
    • ️stack的介绍
      • ️stack的使用
      • ️stack的模拟实现
  • queue
    • ️queue的介绍
      • ️queue的使用
      • ️queue的模拟实现
  • deque容器
  • priority-queue
    • ️priority-queue的使用
      • ️priority-queue的模拟实现

适配器

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

容器适配器让一种已存在的容器类型采用另一种不同的抽象类型的工作方式实现。也就是对一种容器封装来实现其他的容器。知道了容器适配器接下来先来讲stack。

stack容器适配器

️stack的介绍

1.stack应用在后进先出的上下文环境中,只能在容器的一端进行入数据和出数据。

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

empty:判空操作

back:获取尾部元素操作

push_back:尾部插入元素操作

pop_back:尾部删除元素操作

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

️stack的使用

主要的接口

有了string,vector,list的基础再玩这个stack就会很简单。

数据结构有栈的详细讲解,这里就不详细使用了。

stack<int> st;
	//入栈
	st.push(1);
	st.push(2);
	st.push(3);
	st.push(4);
	st.pop();//出栈
	cout << st.top() << endl;//取栈顶数据
	cout << st.empty() << endl;//判空

️stack的模拟实现

我们可以用vector来模拟实现。

namespace gpy
{
	template<class T>
	class stack
	{
	public:
		stack(){}
		void push(const T& x)
		{
			_v.push_back(x);
		}
		void pop()
		{
			_v.pop_back();
		}
		T& top()
		{
			return _v.back();
		}
		size_t size()const
		{
			return _v.size();
		}
		bool empty()const
		{
			return _v.empty();
		}
	private:
		std::vector<T> _v;
	};
}

queue

️queue的介绍

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

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

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

  • empty:检测队列是否为空
  • size:返回队列中有效元素的个数
  • front:返回队头元素的引用
  • back:返回队尾元素的引用
  • push_back:在队列尾部入队列
  • pop_front:在队列头部出队列

标准容器类deque和list满足了这些要求。默认情况下,如果没有为queue实例化指定容器类,则使用标准容器deque。

️queue的使用

跟stack差不多这里就简单的使用一下

️queue的模拟实现

stack可以使用vector实现,但是不能实现queue。vector的头插头删需要挪动数据效率会变低所以标准库中没有提供头插头删的接口。queue就可以用list来模拟实现。

namespace gpy
{
	template <class T>
	class queue
	{
	public:
		queue(){}
		void push(const T& x)
		{
			_lt.push_back(x);//queue的push就是list的尾插
		}
		void pop()
		{
			_lt.pop_front();//queue的pop就是list的头删
		}
		T& front(){return _lt.front();}
		const T& front()const{ return _lt.front(); }
		T& back(){ return _lt.back(); }
		const T& back()const{ return _lt.back(); }
		size_t size()const{ return _lt.size(); }
		bool empty()const{ return _lt.empty(); }
	private:
		std::list<T> _lt;
	};
}

deque容器

vector优点:尾插尾删的效率高,支持随机访问,cpu高速缓存命中率很高缺点:空间不够,增容代价大,一般增2倍,但增容后我只用了很少的一段空间那其他的空间就浪费了。中间和头部的插入删除效率低O(N),需要挪动数据,list优点:

1.按需申请空间,不会造成空间浪费

2.任意位置的插入删除效率都高

缺点:不支持随机访问, CPU高速缓存命中率低

改进:用中控数组-指针数组

这就是deque,双端队列和队列没有关系。在deque中,中控数组叫map,开的数组叫缓冲区。 deque(双端队列):是一种双开口的"连续"空间的数据结构,双开口的含义是:可以在头尾两端进行插入和删除操作,且时间复杂度为O(1),与vector比较,头插效率高,不需要搬移元素;与list比较,空间利用率比较高。

它不是正真连续的空间,底层结构如上图。deque要支持随机访问叫要实现迭代器,它的迭代器很复杂简单了解。

这里就不多讲解,感兴趣的可以看侯捷老师的《stl源码剖析》。

deque却没有那么牛逼优缺点:

1.它最大优点就是做stack和queue的默认适配器,stack和queue只在头尾操作,

2.它中间插入删除还是要挪动数据,很麻烦效率低

3.deque是糅合了vector和list,它没有vector随机访问效率高,任意位置的插入删除效率没有list高。

priority-queue

️priority-queue的使用

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

    priority_queue<int> pq;//默认是大堆
	pq.push(10);
	pq.push(5);
	pq.push(13);
	pq.push(4);
	pq.push(9);
	while (!pq.empty())
	{
		cout << pq.top() << " ";
		pq.pop();
	}
	cout << endl;

默认是大的优先级高,如果要变成小的优先级高,需要再传一个模板参数greater

️priority-queue的模拟实现

初始结构,下面都是按大堆实现的

namespace gpy
{
	template <class T,Container =vector<T>>
	class  priority_queue
	{
	public:
		priority_queue(){}

	private:
		Containter _con;
	};
}

首先实现尾插

当插入一个数就和parent比较,比parent大就向上调整.

标准库给的“<”是大堆,我们在模拟的时候也用“<”.

void AdjustUp(size_t child)
		{
			size_t 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 push(const T& x)
		{
			_con.push_back(x);
			//从尾开始调
			AdjustUp(_con.size()-1);
		}

pop,如果直接pop就不能还保持是堆的结构,先把堆顶的数和最后一个数交换在删除这个数,此时2边都还满足堆这是在向下调整

先从0处开始,选出左右2个孩子中大的和parent比较,比parent大的就交换。

void AdjustDown(size_t parent)
		{
			size_t 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 pop()
		{
			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();
		}

测试一下

那如果要是按低的优先级来该怎么办呢?这是就要用到仿函数了。

仿函数就是像函数一样可以使用。

template<class T>
struct Less
{
	bool operator()(const T& l, const T& r)
	{
		return l < r;
	}
};

bool Less1(int l, int r)
{
	return l < r;
}

就是类里面重载了运算符。有了仿函数就可以把上面的代码在改进改进,在多传一个模板参数

namespace gpy
{
	template<class T>
	struct less
	{
		bool operator()(const T& l, const T& r)
		{
			return l < r;
		}
	};

	template<class T>
	struct greater
	{
		bool operator()(const T& l, const T& r)
		{
			return l > r;
		}
	};
	template <class T,  class Container = vector<T>,class Compare = less<T>>
	class  priority_queue
	{
	public:
		Compare com;
		void AdjustUp(size_t child)
		{
			size_t parent = (child - 1) / 2;
			while (child > 0)
			{
				//if (_con[parent] < _con[child])
				if (com(_con[parent],_con[child]))
				{
					swap(_con[parent], _con[child]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}
		void AdjustDown(size_t parent)
		{
			size_t child = parent * 2 + 1;

			while (child<_con.size())
			{
				//选出大的孩子
				//if (child + 1 < _con.size() && _con[child] < _con[child + 1])
				if (child+1 < _con.size() && com(_con[child],_con[child+1]))
				{
					++child;
				}
				//if (_con[parent] < _con[child])
				if (com(_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()
		{
			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;
	};
}

本篇文章到这就结束了,欢迎大家一起交流!

到此这篇关于C++ STL容器适配器使用指南的文章就介绍到这了,更多相关C++ STL容器适配器内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • c++ STL库容器之集合set代码实例

    set 简介 set是STL中一种标准关联容器,其键值就是实值,实值就是键值,不可以有重复,所以我们不能通过set的迭代器来改变set的元素的值.它底层使用平衡的搜索树--红黑树实现,插入删除操作时仅仅需要指针操作节点即可完成,不涉及到内存移动和拷贝,所以效率比较高.set,顾名思义是"集合"的意思,在set中元素都是唯一的,而且默认情况下会对元素自动进行升序排列,支持集合的交(set_intersection),差(set_difference) 并(set_union),对称差(s

  • C++ STL中的容器适配器实现

    1 stack 1.1 stack 介绍 stack是一种容器适配器,专门用在具有后进先出操作的上下文环境中,其删除只能从容器的一端进行元素的插入与提取操作. stack是作为容器适配器被实现的,容器适配器即是对特定类封装作为其底层的容器,并提供一组特定的成员函数来访问其元素,将特定类作为其底层的,元素特定容器的尾部(即栈顶)被压入和弹出. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类,这些容器类应该支持以下操作:empty:判空操作.back:获取尾部元素操作.pus

  • 深入解析C++ STL中的常用容器

    STL是C/C++开发中一个非常重要的模板,而其中定义的各种容器也是非常方便我们大家使用.下面,我们就浅谈某些常用的容器.这里我们不涉及容器的基本操作之类,只是要讨论一下各个容器其各自的特点.STL中的常用容器包括:顺序性容器(vector.deque.list).关联容器(map.set).容器适配器(queue.stac). 1.顺序性容器 (1)vectorvector是一种动态数组,在内存中具有连续的存储空间,支持快速随机访问.由于具有连续的存储空间,所以在插入和删除操作方面,效率比较慢

  • C++ STL入门教程(1) vector向量容器使用方法

    一.简介 Vectors 包含着一系列连续存储的元素,其行为和数组类似. 访问Vector中的任意元素或从末尾添加元素都可以在O(1)内完成,而查找特定值的元素所处的位置或是在Vector中插入元素则是O(N). 二.完整程序代码 /*请务必运行以下程序后对照阅读*/ #include <vector> #include <iostream> #include <algorithm> #include <stdexcept> using namespace

  • C++ STL 序列式容器与配接器的简单使用

    目录 容器概述 序列式容器 array vector list deque forward_list Adapter(配接器) stack queue priority_queue 容器概述 C++标准里提供了以下容器或容器配接器: 序列式容器 配接器 关联式容器 不定序关联容器 array stack set unordered_set vector queue map unordered_map list priority_queue multiset unordered_multiset

  • C++ STL容器stack和queue详解

    stack是一个比较简单的容器,它的使用也很简单,stack是LIFO容器,就是后进先出,最后添加进去的元素,第一个取出来 stack初始化 std::stack<int> first; std::stack<int> second(first); std::stack<int, std;:vector<int>> third; //使用vector初始化stack ### stack常用方法### empty();//判断是否为空 push(Elem e)

  • C++语言 STL容器list总结

    在使用std::list<>链表时,难免会对数据进行添加删除操作.而遍历链表则有两种方式:通过索引访问,象数组一样处理:通过std::list<>::iterator链表遍历器进行访问 STL 中的list 就是一 双向链表,可高效地进行插入删除元素. list不支持随机访问.所以没有 at(pos)和operator[]. list 对象list1, list2 分别有元素list1(1,2,3),list2(4,5,6) .list< int>::iterator

  • C++ 标准模板库 STL 顺序容器详解

    C++ 标准模板库 STL 顺序容器 容器 数据结构 顺序性 重复性 支持迭代器 vector 动态数组 无序 可重复 随机访问迭代器 deque 双向队列 无序 可重复 随机访问迭代器 list 双向链表 无序 可重复 双向迭代器 动态数组 vector ​ vector #include <vector> 动态数组:其元素在内存中是连续存放的,随机存取任何元素都可以在常数时间内完成,在该容器的尾部增删元素也几乎能够在常数时间内完成具有较好的性能. ​ 一个 vector 常用函数使用实例如

  • C++ STL关联式容器自定义排序规则的2种方法

    前面在讲解如何创建 map.multimap.set 以及 multiset 容器时,遗留了一个问题,即如何自定义关联式容器中的排序规则? 实际上,为关联式容器自定义排序规则的方法,已经在 <STL priority_queue自定义排序方法>一节中做了详细的讲解.换句话说,为 Priority_queue 容器适配器自定义排序规则的方法,同样适用于所有关联式容器. 总的来说,为关联式容器自定义排序规则,有以下 2 种方法. 1) 使用函数对象自定义排序规则 在掌握此方法之前,读者必须对函数对

  • C++ STL容器适配器使用指南

    目录 适配器 stack容器适配器 ️stack的介绍 ️stack的使用 ️stack的模拟实现 queue ️queue的介绍 ️queue的使用 ️queue的模拟实现 deque容器 priority-queue ️priority-queue的使用 ️priority-queue的模拟实现 适配器 适配器是一种设计模式(设计模式是一套被反复使用的.多数人知晓的.经过分类编目的.代码设计经验的总结),该种模式是将一个类的接口转换成客户希望的另外一个接口.例如: 容器适配器让一种已存在的容

  • C++实现STL容器的示例

    各大容器的特点: 1.可以用下标访问的容器有(既可以插入也可以赋值):vector.deque.map: 特别要注意一下,vector和deque如果没有预先指定大小,是不能用下标法插入元素的! 2. 序列式容器才可以在容器初始化的时候制定大小,关联式容器不行: 3.注意,关联容器的迭代器不支持it+n操作,仅支持it++操作. 适配器的概念 适配器的意思就是将某些已经存在的东西进行限制或者组合变成一个新的东西,这个新的东西体现一些新的特性,但底层都是由一些已经存在的东西实现的. STL中的容器

  • C++常见的stl容器与相关操作 示例解析

    目录 sort排序 vector map unordered_map set queue stack 创建容器时指定排序规则 sort排序 针对含有迭代器的容器,可以用#include<algorithm>中的sort函数进行排序. 默认排序是从小到大,可以自己写仿函数,也可以用greater<int>()或者less<int>(). #include <vector> #include <algorithm> #include <iost

  • C++容器适配器的概念与示例

    目录 一. 什么是适配器与容器适配器? 二. 理解容器适配器 stack的模拟实现 queue的模拟实现 一. 什么是适配器与容器适配器? 适配器是一种设计模式(设计模式是一套被反复使用的,多数人知晓的,经过分类编目的,代码设计经验的总结),该种模式将一个类的接口转换成用户需要的另外一个接口. 举个例子:在日常生活中,当手机没电了,我们需要给手机充电,给手机充电的方式很多,可以插到电源上,也可以用充电宝,还可以直接连着电脑充.而我们并不关心用什么给它充电,我们关心的只是能否给手机充上电.适配器充

  • c++ STL容器总结之:vertor与list的应用

    STL提供六大组件,彼此可以组合套用 1.容器(containers):各种数据结构,如vertor,list,deque,set,map.从实现的角度来看,STL容器是一种class template 2.算法(algorithms):各种算法如sort,search,copy,earse.STL算法是一种 function template. 3.迭代器(iterators):扮演容器与算法之间的胶合剂,是所谓的"泛型指针".所有STL容器都有自己的专属的迭代器. 4.仿函数(fu

  • C++ 容器适配器priority_queue的使用及实现代码

    优先级队列(Priority Queue) 队列是一种特征为FIFO的数据结构,每次从队列中取出的是最早加入队列中的元素.但是,许多应用需要另一种队列,每次从队列中取出的应是具有最高优先权的元素,这种队列就是优先级队列(Priority Queue),也称为优先权队列. 1. 优先级队列的概念 优先级队列的定义 优先级队列是不同于先进先出队列的另一种队列.每次从队列中取出的是具有最高优先权的元素. 优先级队列的特点 优先级队列是0个或多个元素的集合,每个元素都有一个优先权或值. 当给每个元素分配

  • C++ STL容器详解之红黑树部分模拟实现

    目录 一.红黑树的概念 二.红黑树的性质 三.红黑树节点的定义 四.红黑树结构  五. 红黑树的插入操作 六.代码 总结 一.红黑树的概念 红黑树(Red Black Tree),是在计算机科学中用到的一种数据结构,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black. 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的. 二.红黑树的性质 1. 每个结点不是红色就是黑色: 2. 根节点是黑色的:

  • 利用C++模拟实现STL容器:list

    目录 一.list的介绍 二.list的排序 三.迭代器 1.list的迭代器失效问题 2.迭代器的功能分类 3.list迭代器的模拟实现 4.迭代器价值 5.迭代器operator->的重载 四.模拟实现时遇到的困惑及注意点 五.vector和list的优缺点 1.vector 2.list 六.模拟实现list整体代码 一.list的介绍 列表是一种顺序容器,它允许在序列中的任何位置执行常量时间插入和删除操作,并允许在两个方向上进行迭代. 它的底层是一个带头双向循环链表.附一篇博主用C语言写

  • C++ STL容器与函数谓词示例分析讲解

    目录 1.C++ vector向量 2.C++ stack 栈 3.C++ queue 队列 4.优先级队列 5.C++ list 6.c++ set 集合 7.C++ map函数 8.C++ multimap容器 9.C++ 谓词 10.C++内置预定义函数 C++ STL(Standard Template Library标准模板库),相当于java的集合模块, STL 有很多的容器. 1.C++ vector向量 (内部:封装动态大小数组作为容器,能够存放任意的动态数组) #include

随机推荐