devbox
小小林熬夜学编程
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C++（18）——适配器概念以及stack、queue、优先队列的模拟实现

作者：小小林熬夜学编程 | 2024-02-21 10:40:53

赞

踩

C++（18）——适配器概念以及stack、queue、优先队列的模拟实现

       上篇文章中，给出了对于list模拟实现中功能的补全，本篇文章将优先介绍一个新的容器deque之后引入什么是适配器，以及适配器的使用方法，再通过适配器的思想来完成对于Stack，queue、优先级队列(priority_queue)的实现。

目录

1. deque:

1.1 什么是deque：

1.2 deque的大致原理以及其特点：

2. 适配器：

2.1 什么是适配器：

3. Stack的模拟实现：

3.1 功能实现：push、pop:

3.2 功能实现：top,size,empty:

3.3 测试：

4. queue的模拟实现：

4.1 queue的功能实现：

4.2 测试：

​编辑5. priority_queue的模拟实现：

5.1 基本框架：

5.2 插入push以及向上调整函数Adjustup:

5.3 向下调整函数Adjustdown以及删除pop:

5.4 其余功能函数：

5.5 测试:

6. 仿函数：

6.1 仿函数的实现：

6.2 测试：

1. deque:

1.1 什么是deque：

       在对deque的相关实现原理进行介绍前，首先来总结之前介绍的两种容器：vector、list的优缺点：

       对于vector，在前面对其进行模拟实现的文章中提到，可以将vector看作之前数据结构中的顺序表，其特点是存储空间在物理以及逻辑上的连续性。因此，借由连续性可以得出，vector的优点在于通过下标可以对空间中的内容进行随机访问。并且缓存命中较高对于其缺点，则是头部或者中间进行插入、删除元素时的效率过低，以及一次性开辟较多空间时带来的损耗

     对于list，同样提到，可以将其看作成带哨兵位头结点的双向循环链表，其特点是存储空间在逻辑上连续，但是在物理上不连续。因此，其优点在于任意位置的插入、删除数据时的效率，以及按需申请空间，不会造成浪费。但是由于其在物理上并不连续，因此不能使用下标来对list中的内容进行访问且缓存命中较低

    不难看出，两者的优点几乎可以看作对于对于二者缺点的补充。而本部分介绍的容器deque，则可以看作是对于二者优点的一种结合。

1.2 deque的大致原理以及其特点：

对于deque，其内存管理方式采用了中控的方法，具体原理如下：

    其中，中控所代表的空间是一个指针数组，里面保存了若干个指针，每个指针指向了一块空间，

对于开辟空间的大小，有相同、不同两种方式，这里采用相同进行解释，即每块空间buff均可以存储10个整型数据。对于上述容器，如果需要进行头插，则首先再开辟一块新的空间，这里命名为buff0，然后在buff0中插入数据即可，具体结构如下：

不过需要注意，deque进行头插时，插入数据的顺序并不是从前向后插入数据，而是从后向前依次插入数据，例如先后向deque插入数据1,0。插入效果如下：

在对上述结构进行尾插时，只需要通过指针数组，找到最后一个buff，进行插入数据即可。即：

 在对于deque进行删除数据时，例如进行头插，假设删除一个数据，效果如下：

 如果再删除一个数据，此时buff0中为空，在删除数据后销毁buff0，效果如下：

不难发现，对于deque，虽然其存储空间在物理上仍然保持一定的连续性，但是其头删却不会向vector一样，需要进行挪动覆盖来完成。

对于deque的尾删，只需要找到最后一个数据所处的位置进行删除即可。

        通过上述例子不难发现，对于deque，其头插、头删、尾插、尾删，均有着不错的效率。并且其存储空间的结构则结合了连续空间以及不连续空间。可以说是综合了vector,list的优点，并且对二者的缺点进行了一定程度的互补。

       不过，deque却并不能彻底代替vector和list。对于vector，其一大优点是可以通过下标来随意访问空间中的内容，对于deque。，虽然也可以实现下标访问，但是其实现方法以及原理相对于 vector过于复杂。下面将对于实现原理进行简单的介绍。

      假设需要利用下标访问第i个位置的内容，则i/10可以算出需要访问的数据在第几块开辟的空间中，再利用i%10就可以计算出，需要访问的内容在空间中的具体位置。但是，如果deque进行过n次头插操作，则计算时，需要先剪掉油茶数据的个数，即利用i-n进行后续的计算。不过需要注意，这种计算方法需要建立在每个buff能存储数据的个数都是相同的。

      不过，在对deque容器中间元素进行删除时，为了保持每个buff的大小都是相同的，并不能直接对于空间进行删除，只能通过逐个挪动数据的方法来完成。这种方法与vector进行头插友删时的弊端一样，效率较低。

     因此，将每个buff的空间保持一样大，可以很好的满足下标访问功能的实现，但是，却不利于实现对于容器中间部分内容的删除以及插入。如果不限制每个存储空间的大小保持一致，有利于实现容器中间部分内容的插入以及删除，但是却不利于实现下标访问。前面矛盾。不过 ，在STL库中，采取的方式是每个存储空间的大小保持一致。具体实现原理过于复杂，本文不再过多叙述。

    总结不难得出，deque的头插，头删，尾插，尾删均有不错的效率，在接下来实现Stack,queue中，将借助deque来完成实现。

2. 适配器：

2.1 什么是适配器：

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

       上述给出的关于适配器的概念中提到了，适配器是一种设计模式，这种模式是将一个类的接口转换成另一个接口。例如对于上面给出的容器deque，可以将其看作一个接口，在对于栈和队列这两种结构的实现中，引入deque这种接口，通过deque中的成员函数来完成对于栈和队列的实现。对于deque中的成员函数，大体如下：



 

3. Stack的模拟实现：

上面说到了，可以利用适配器这种设计模式，将deque作为接口，来完成对于Stack的实现，具体原理如下：

  1. namespace violent1
  2. {
  3. 	template<class T, class Container = deque<T>>
  4. 	class Stack
  5. 	{
  6.  
  7. 	private:
  8. 		Container _con;
  9. 	};
  10. }

在上述代码中，将容器deque作为一种模板引入，在Stack这个类中，通过模板参数来创建成员变量_con。此时，_con具有deque的所有性质，因此，此处也不需要编写额外的构造函数来对于成员变量进行初始化。在后面对于Stack功能的实现中，直接调用deque中的成员函数即可

3.1 功能实现：push、pop:
 

直接调用deque的成员函数即可。

  1. void push(const T& x)
  2. 		{
  3. 			_con.push_back(x);
  4. 		}
  5.  
  6. 		void pop()
  7. 		{
  8. 			_con.pop_back();
  9. 		}

3.2 功能实现：top,size,empty:

  1. const T& top()
  2. 		{
  3. 			return _con.back();
  4. 		}
  5.  
  6. 		size_t size()
  7. 		{
  8. 			return _con.size();
  9. 		}
  10.  
  11. 		bool empty()
  12. 		{
  13. 			return _con.empty();
  14. 		}

3.3 测试：

通过下面的代码对于Stack进行测试：

  1. int main()
  2. {
  3. 	violent1::Stack<int> s;
  4. 	s.push(1);
  5. 	s.push(2);
  6. 	s.push(3);
  7. 	s.push(4);
  8.  
  9. 	while (!s.empty())
  10. 	{
  11. 		cout << s.top() << ' ';
  12. 		s.pop();
  13. 	}
  14.  
  15. 	return 0;
  16. }

运行结果如下:

4. queue的模拟实现：

       原理与实现Stack所用的方法基本相同，只需要注意栈和队列二者本身的不同的性质即可。具体代码如下：

4.1 queue的功能实现：

  1. namespace violent2
  2. {
  3. 	template<class T, class Container = deque<T>>
  4. 	class queue
  5. 	{
  6. 	public:
  7.  
  8. 		void push(const T& x)
  9. 		{
  10. 			_con.push_back(x);
  11. 		}
  12.  
  13. 		void pop()
  14. 		{
  15. 			_con.push_front();
  16. 		}
  17.  
  18. 		const T& front()
  19. 		{
  20. 			return _con.front();
  21. 		}
  22.  
  23. 		const T& back()
  24. 		{
  25. 			return _con.back();
  26. 		}
  27.  
  28. 		size_t size()
  29. 		{
  30. 			return _con.size();
  31. 		}
  32.  
  33. 		bool empty()
  34. 		{
  35. 			return _con.empty();
  36. 		}
  37.  
  38. 	private:
  39. 		Container _con;
  40. 	};
  41. }

4.2 测试：

通过下面的代码对queue的功能进行测试：

  1. void test2()
  2. {
  3. 	violent2::queue<int> q;
  4.  
  5. 	q.push(1);
  6. 	q.push(2);
  7. 	q.push(3);
  8. 	q.push(4);
  9.  
  10. 	cout << "功能测试：队列:";
  11. 	while (!q.empty())
  12. 	{
  13. 		cout << q.front() << ' ';
  14. 		q.pop();
  15. 	}
  16. }

结果如下： 




5. priority_queue的模拟实现：

5.1 基本框架：

对于priority_queue，虽然称之为优先级队列，但是在结构上，更贴近于数据结构中的堆

(注：对于堆的介绍可以在一起学数据结构（8）——二叉树中堆的代码实现_子结点与父结交换位置-CSDN博客查看）

这里不再进行过多的叙述，只给出大体流程：

       对于priority_queue的适配器的选择，vector为最佳。在插入结点时，首先插入到堆最后的叶子结点上，再利用向上调整函数Adjustup对于结点的大小关系进行调整。这里默认为实现大堆，即：任意一个父结点都大于子结点。

       对于结点的删除，由于直接删除根结点可能会破坏堆的结构，因此一般选择交换最后一个叶子结点与根结点，删除此时的最后的叶子结点，利用向下调整函数Adjustdown对此时的根结点进行调整。

       大体框架如下：

  1. #include<iostream>
  2. #include<vector>
  3. using namespace std;
  4.  
  5. namespace violent3
  6. {
  7. 	template<class T, class Container = vector<T>>
  8. 	class priority_queue
  9. 	{
  10. 	public:
  11.  
  12.  
  13. 	private:
  14. 		Container _con;
  15. 	};
  16. }

5.2 插入push以及向上调整函数Adjustup:

  1. void push(const T& x)
  2. 		{
  3. 			_con.push_back(x);
  4. 			Adjustup(_con.size() - 1);
  5. 		}
  1.  
  2. 		void Adjustup(int child)
  3. 		{
  4. 			int parent = (child - 1) / 2;
  5. 			while (child > 0)
  6. 			{
  7. 				if (_con[child] > _con[parent])
  8. 				{
  9. 					swap(_con[child], _con[parent]);
  10. 					child = parent;
  11. 					parent = (child - 1) / 2;
  12. 				}
  13. 				else
  14. 				{
  15. 					break;
  16. 				}
  17. 			}
  18. 		}

5.3 向下调整函数Adjustdown以及删除pop:

  1. void pop()
  2. 		{
  3. 			swap(_con[0], _con[_con.size() - 1]);
  4. 			_con.pop_back();
  5. 			Adjustdown(0);
  6.  
  7. 		}
  1. void Adjustdown(int parent)
  2. 		{
  3. 			size_t child = parent * 2 + 1;
  4. 			while (child < _con.size())
  5. 			{
  6. 				if (child + 1 < _con.size() && _con[child] < _con[child + 1])
  7. 				{
  8. 					child++;
  9. 				}
  10.  
  11. 				if (_con[parent] < _con[child])
  12. 				{
  13. 					swap(_con[child], _con[parent]);
  14. 					parent = child;
  15. 					child = parent * 2 + 1;
  16. 				}
  17. 				else
  18. 				{
  19. 					break;
  20. 				}
  21. 			}
  22. 		}

5.4 其余功能函数：

  1. size_t size()
  2. 		{
  3. 			return _con.size();
  4. 		}
  5.  
  6. 		bool empty()
  7. 		{
  8. 			return _con.empty();
  9. 		}
  10.  
  11. const T& Top()
  12. 		{
  13. 			return _con[0];
  14. 		}

5.5 测试:

利用下面的代码对上述结构进行测试：

  1. void test3()
  2. {
  3. 	violent3::priority_queue<int> pq;
  4. 	pq.push(1);
  5. 	pq.push(2);
  6. 	pq.push(6);
  7. 	pq.push(2);
  8. 	pq.push(3);
  9.  
  10. 	while (!pq.empty())
  11. 	{
  12. 		cout << pq.Top() << ' ';
  13. 		pq.pop();
  14. 	}
  15. }

结果如下：


 

6. 仿函数：

6.1 仿函数的实现：

上面所建立的堆是大堆，如果想建立一个小堆，需要改变Adjustup,Adjustdown中的＞方向，但是，针对于上方的实现方式，每次更改建立的堆的类型时，都需要对符号进行更改，过于繁琐，为了解决这个问题，引入仿函数：

对于仿函数，其并不是一个函数，而是类，例如：文章中需要用于判断建立大小堆的函数，也就是比较函数，因此，建立两个类，分别命名为less,greater即：

  1. template<class T>
  2. 	class less
  3. 	{
  4. 	public:
  5. 		bool operator()(const T& x, const T& y)
  6. 		{
  7. 			return x < y;
  8. 		}
  9. 	};
  10.  
  11. 	template<class T>
  12. 	class greater
  13. 	{
  14. 	public:
  15. 		bool operator()(const T& x, const T& y)
  16. 		{
  17. 			return x > y;
  18. 		}
  19. 	};

在priority_queue的类前，将上面的类作为一个模板参数，假设在没有明确要求的情况下，默认建立大堆，则模板参数如下：

template<class T, class Container = vector<T>, class compare = greater<T>>

在类中，将模板参数compare实例化出一个对象，这里命名为com，在需要对于父、子结点进行比较时，直接将这两个结点放入到com中，具体代码如下：

  1. void Adjustup(int child)
  2. 		{
  3. 			int parent = (child - 1) / 2;
  4. 			compare com;
  5. 			while (child > 0)
  6. 			{
  7. 				if (com(_con[child], _con[parent]))
  8. 				{
  9. 					swap(_con[child], _con[parent]);
  10. 					child = parent;
  11. 					parent = (child - 1) / 2;
  12. 				}
  13. 				else
  14. 				{
  15. 					break;
  16. 				}
  17. 			}
  18. 		}
  19.  
  20. 		void Adjustdown(int parent)
  21. 		{
  22. 			size_t child = parent * 2 + 1;
  23. 			compare com;
  24. 			while (child < _con.size())
  25. 			{
  26. 				if (child + 1 < _con.size() && com(_con[child+1],_con[child]))
  27. 				{
  28. 					child++;
  29. 				}
  30.  
  31. 				if (com(_con[child],_con[parent]))
  32. 				{
  33. 					swap(_con[child], _con[parent]);
  34. 					parent = child;
  35. 					child = parent * 2 + 1;
  36. 				}
  37. 				else
  38. 				{
  39. 					break;
  40. 				}
  41. 			}
  42. 		}

6.2 测试：

利用下面的代码测试仿函数建立大堆小堆：

大堆：

  1. void test3()
  2. {
  3. 	/*violent3::priority_queue<int,deque<int>,greater<int>> pq;*/
  4. 	violent3::priority_queue<int> pq;
  5. 	pq.push(1);
  6. 	pq.push(2);
  7. 	pq.push(6);
  8. 	pq.push(2);
  9. 	pq.push(3);
  10.  
  11. 	while (!pq.empty())
  12. 	{
  13. 		cout << pq.Top() << ' ';
  14. 		pq.pop();
  15. 	}
  16. }

效果如下：


小堆：

  1. void test3()
  2. {
  3. 	violent3::priority_queue<int,deque<int>,less<int>> pq;
  4. 	/*violent3::priority_queue<int> pq;*/
  5. 	pq.push(1);
  6. 	pq.push(2);
  7. 	pq.push(6);
  8. 	pq.push(2);
  9. 	pq.push(3);
  10.  
  11. 	while (!pq.empty())
  12. 	{
  13. 		cout << pq.Top() << ' ';
  14. 		pq.pop();
  15. 	}
  16. }

效果如下：

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/123061
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号