首页 > 编程语言 >C++STL容器适配器——stack和queue

C++STL容器适配器——stack和queue

时间：2024-11-10 18:15:18浏览次数：3  
标签：容器 STL 适配器 C++ queue child push size con

目录

一.stack介绍及使用

1.stack介绍

2.stack的使用

3.模拟实现stack

二.queue的介绍及使用

1.queue介绍

2.queue的使用

3.模拟实现queue

三.deque的了解

1.deque的介绍

2.deque的缺陷

四.priority_queue的介绍及使用

1.priority_queue介绍

2.priority_queue的使用

3.模拟实现priority_queue

五.整体代码

1.stack.h

2.queue.h

3.priority_queue.h

4.test.cpp

一.stack介绍及使用

1.stack介绍

stack文档介绍

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

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

2.stack的使用

void test_stack()
{
	stack<int> st;
	st.push(1);
	st.push(2);
	st.push(3);
	st.push(4);
	//没有迭代器
	while (!st.empty())
	{
		cout << st.top() << " ";
		st.pop();
	}
	cout << endl;
}

3.模拟实现stack

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;
};

二.queue的介绍及使用

1.queue介绍

queue文档介绍

  1. 队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素
  2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列
  3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:
  • empty：检测队列是否为空
  • size：返回队列中有效元素的个数
  • front：返回队头元素的引用
  • back：返回队尾元素的引用
  • push_back：在队列尾部入队列
  • pop_front：在队列头部出队列

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

2.queue的使用

void test_queue()
{
	queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);

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

3.模拟实现queue

template<class T, class Container>
class queue
{
public:
	void push(const T& x) { _con.push_back(x); }
	void pop() { _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;
};

三.deque的了解

1.deque的介绍

deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高

deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，其底层结构如下图所示：

双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，落在了deque的迭代器身上，因此deque的迭代器设计就比较复杂，如下图所示：

那deque是如何借助其迭代器维护其假想连续的结构呢？

2.deque的缺陷

与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必vector高的。

与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。

但是，deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构

我们可以用下面的函数来测试大量数据排序时deque的缺点

void test_deque()
{
	deque<int> d;
	vector<int> v;
	const int n = 100000;
	srand(time(0));
	for (size_t i = 0; i < n; ++i)
	{
		int x = rand();
		d.push_back(x);
		v.push_back(x);
	}

	size_t begin1 = clock();
	sort(d.begin(), d.end());
	size_t end1 = clock();

	size_t begin2 = clock();
	sort(v.begin(), v.end());
	size_t end2 = clock();

	cout << end1 - begin1 << endl;
	cout << end2 - begin2 << endl;
}

四.priority_queue的介绍及使用

1.priority_queue介绍

priority_queue文档介绍

  1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的
  2. 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)
  3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部
  4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类
  5. 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector
  6. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数 make_heap、push_heap和pop_heap来自动完成此操作

2.priority_queue的使用

//容器适配器都不支持迭代器遍历,因为通常都包含一些特殊的性质
//如果可以遍历,那么无法保持他们很好的性质
void test_priority_queue()
{
	//priority_queue<int> pq;//默认大的优先级高
	priority_queue<int, vector<int>, greater<int>> pq;//想让小的优先级高->仿函数
	pq.push(3);
	pq.push(1);
	pq.push(5);
	pq.push(4);
	pq.push(2);
	pq.push(7);

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

3.模拟实现priority_queue

仿函数

template<class T>
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 = 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[parent] < _con[child])
			if (com(_con[parent], _con[child]))
			{
				swap(_con[parent], _con[child]);
				child = parent;
				parent = (child - 1) / 2;
			}
			else
			{
				break;
			}
		}
	}

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

			//if (_con[child] > _con[parent])
			if (com(_con[parent], _con[child]))
			{
				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()
	{
		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;
};

五.整体代码

1.stack.h

#pragma once
#include<vector>
#include<list>
#include<deque>
namespace wzyl
{
	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()
	{
		//stack<int, vector<int>> st;
		//stack<int, list<int>> st;
		stack<int, deque<int>> st;
		st.push(1);
		st.push(2);
		st.push(3);
		st.push(4);
		while (!st.empty())
		{
			cout << st.top() << " ";
			st.pop();
		}
		cout << endl;
	}
}

2.queue.h

#pragma once
//#include<vector>
#include<list>
#include<deque>
namespace wzyl
{
	template<class T, class Container>
	class queue
	{
	public:
		void push(const T& x) { _con.push_back(x); }
		void pop() { _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()
	{
		//queue<int, vector<int>> q;//不能用vector,因为没有提供pop_front
		//queue<int, list<int>> q;
		queue<int, deque<int>> q;
		q.push(1);
		q.push(2);
		q.push(3);
		q.push(4);
		while (!q.empty())
		{
			cout << q.front() << " ";
			q.pop();
		}
		cout << endl;
	}
}

3.priority_queue.h

#pragma once
#include<vector>
namespace wzyl
{
	template<class T>
	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 = 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[parent] < _con[child])
				if (com(_con[parent], _con[child]))
				{
					swap(_con[parent], _con[child]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}

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

				//if (_con[child] > _con[parent])
				if (com(_con[parent], _con[child]))
				{
					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()
		{
			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_queue()
	{
		//priority_queue<int,vector<int>,greater<int>> pq;
		priority_queue<int> pq;
		pq.push(1);
		pq.push(3);
		pq.push(7);
		pq.push(4);
		pq.push(2);
		pq.push(6);

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

4.test.cpp

#include<iostream>
using namespace std;

#include"stack.h"
#include"queue.h"
#include"priority_queue.h"

#include<time.h>
#include<algorithm>
#include<queue>
#include<functional>


void test_deque()
{
	deque<int> d;
	vector<int> v;
	const int n = 100000;
	srand(time(0));
	for (size_t i = 0; i < n; ++i)
	{
		int x = rand();
		d.push_back(x);
		v.push_back(x);
	}

	size_t begin1 = clock();
	sort(d.begin(), d.end());
	size_t end1 = clock();

	size_t begin2 = clock();
	sort(v.begin(), v.end());
	size_t end2 = clock();

	cout << end1 - begin1 << endl;
	cout << end2 - begin2 << endl;
}

//容器适配器都不支持迭代器遍历,因为通常都包含一些特殊的性质
//如果可以遍历,那么无法保持他们很好的性质
void test_priority_queue()
{
	//priority_queue<int> pq;//默认大的优先级高
	priority_queue<int, vector<int>, greater<int>> pq;//想让小的优先级高->仿函数
	pq.push(3);
	pq.push(1);
	pq.push(5);
	pq.push(4);
	pq.push(2);
	pq.push(7);

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

int main()
{
	/*wzyl::test_stack();
	wzyl::test_queue();*/
	//test_deque();
	//test_priority_queue();
	wzyl::test_priority_queue();
	wzyl::less<int> lessfunc;
	cout << lessfunc(1, 2) << endl;
	return 0;
}

标签：容器,STL,适配器,C++,queue,child,push,size,con
From： https://blog.csdn.net/w200514/article/details/143663619

相关文章

  • C/C++语言基础--C++模板与元编程系列五(可变惨模板，形参包展开，折叠表达式)
    本专栏目的更新C/C++的基础语法，包括C++的一些新特性前言模板与元编程是C++的重要特点，也是难点，本人预计将会更新10期左右进行讲解，这是第五期，讲解可变惨模板，形参包展开，折叠表达式等，本人感觉这一部分内容还是比较复杂的；C语言后面也会继续更新知识点，如内联汇编；欢迎收藏+关......
  • 【最新原创毕设】基于移动端的助农电商系统+08655（免费领源码）可做计算机毕业设计JAVA、
    基于移动端的助农电商系统的设计与实现摘要近年来，电子商务的快速发展引起了行业和学术界的高度关注。基于移动端的助农电商系统旨在为用户提供一个简单、高效、便捷的农产品购物体验，它不仅要求用户清晰地查看所需信息，而且还要求界面设计精美，使得功能与页面完美融合，从而提升......
  • （2024最新毕设合集）基于SpringBoot的梓锦社区疫苗接种服务系统+42529|可做计算机毕业设
    目 录摘要1绪论1.1选题背景与意义1.2开发现状1.3论文结构与章节安排2 梓锦社区疫苗接种服务系统系统分析2.1可行性分析2.1.1技术可行性分析2.1.2 经济可行性分析2.1.3法律可行性分析2.2系统功能分析2.2.1功能性分析2.2.2非功能性分析2.......
  • 封装红黑树实现mymap和myset--C++
    源码及框架分析SGI-STL30版本源代码，map和set的源代码在map/set/stl_map.h/stl_set.h/stl_tree.h等几个头文件中。map和set的实现结构框架核心部分截取出来如下：//set#ifndef__SGI_STL_INTERNAL_TREE_H#include<stl_tree.h>#endif#include<stl_set.h>#include<st......
  • 【C++】验证STL容器线程不安全
    文章目录概要整体架构流程技术名词解释技术细节示例代码代码现象分析代码来验证一下vector的扩容解决方法小结概要在并发编程中，线程安全是确保多个线程在同时访问共享资源时，不会引起数据竞争或意外的行为。在C++中，std::vector通常并不是线程安全的，因此在多线程环境......
  • C++笔记---lambda表达式
    1.简单介绍及语法Lambda表达式是C++11引入的一种便捷的匿名函数定义机制。lambda表达式本质是一个匿名函数对象，跟普通函数不同的是他可以定义在函数内部。lambda表达式语法使用层而言没有类型，所以我们一般是用auto或者模板参数定义的对象去接收lambda对象。Lambda表达......
  • C++程序设计大作业-学生管理系统-计算机自考实践
    目录源码C++程序设计报告开发环境系统运行导入初始数据显示信息输入记录编辑记录删除记录批量导出数据源码#include<iostream>#include<string>#include<fstream>#include<sstream>#include<list>#include<map>//定义最大值#defineMAX100using......
  • c++中的顺序表结构
     顺序表是简单的一种线性结构，逻辑上相邻的数据在计算机内的存储位置也是相邻的（就类似于数组），可以快速定位第几个元素，中间不允许有空值，插入、删除时需要移动大量元素顺序表有三个要素1.用elems记录存储位置的基地址2.分配一段连续的存储空间size3.用length记录实际的元素......
  • C++类中的静态成员
    目录1.静态成员变量：2.静态成员函数在C++中类中的静态成员分为两类，一类是静态成员变量，一类是静态成员函数。什么是静态成员变量和静态成员函数呢？就是在前面加static关键字。1.静态成员变量：它具有以下几个特点：    1.所有的对象共享同一份数据    2.在编......
  • C++的基础学习5
    //四、变量的作用域与生命周期////1.作用域：那里起作用那里就是变量的作用域//局部变量的作用域：就是变量所在的局部范围。//全局变量的作用域：整个工程。////#define_CRT_SECURE_NO_WARNINGS1//#include<stdio.h>//intg=2021;//全局变量////intmain()//{// print......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99