• 【C++】STL — stack和queue的使用 + 适配器和仿函数的使用 + 优先级队列 priority_queue 的模拟实现


    📖前言:

    本章将介绍STL六大组件中的 —— 适配器,在此基础上再学习stack、queue和priority_queue的模拟实现和仿函数的应用场景,最后介绍一下一个新的数据结构deque……


    1. 容器适配器

    1.1 什么是容器适配器:

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

    在这里插入图片描述


    2. stack的介绍和使用 + 模拟实现

    2.1 stack的介绍:

    stack的学习文档:👉 传送门

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

    操作:

    • empty:判空操作
    • back:获取尾部元素操作
    • push_back:尾部插入元素操作
    • pop_back:尾部删除元素操作
    1. 标准容器vector、deque、list均符合这些需求,默认情况下,如果没有为stack指定特定的底层容器,默认情况下使用deque。

    在这里插入图片描述

    2.2 stack的使用:

    stack对其容器的接口进行了包装,默认使用deque:

    在这里插入图片描述
    直接见代码:

    void test_stack()
    	{
    		std::stack<int, vector<int>> s;
    		s.push(1);
    		s.push(2);
    		s.push(3);
    		s.push(4);
    		
    		while (!s.empty())
    		{
    			cout << s.top() << " ";
    			s.pop();
    		}    
    		cout << endl;
    	}
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    运行结果是:4 3 2 1

    注意:

    • stack不支持迭代器了,因为栈让随便遍历是不好的
    • 后进先出不好保证,性质就无法维护了

    2.3 stack的模拟实现:

    直接运用适配器,复用别的容器,stack默认是复用deque这个容器

    namespace Joker
    {
    	//deque,既有vector的优先,又有list的有点
    	template<class T, class Container = deque<T>>
    	class stack
    	{
    	public:
    		void push(const T& x)
    		{
    			_con.push_back(x);
    		}
    
    		void pop()
    		{
    			_con.pop_back();
    		}
    
    		const T& top()
    		{
    			return _con.back();
    		}
    
    		size_t size()
    		{
    			return _con.size();
    		}
    
    		bool empty()
    		{
    			return _con.empty();
    		}
    
    	private:
    		Container _con;
    	};
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36

    我们复用的是deque的功能来实现stack的功能。

    测试一下:

    void test_stack1()
    	{
    		//可以复用以前容器的代码
    		//stack s;
    		stack<int, vector<int>> s;
    		
    		//stack s;
    		s.push(1);
    		s.push(2);
    		s.push(3);
    		s.push(4);
    		
    		while (!s.empty())
    		{
    			cout << s.top() << " ";
    			s.pop();
    		}
    		cout << endl;
    	}
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    运行结果是:4 3 2 1

    测试时候适配器用的是vector的容器,基于queue的结构而去适配合理的容器,因为vector尾插尾删除时间复杂度为〇(1),很方便…

    注意:

    • 这里的适配器类型不能传string的,用string的风险和问题:
    • 可能会溢出或者截断,数据丢失的风险

    3. queue的介绍和使用 + 模拟实现

    3.1 queue的介绍:

    queue的学习文档:👉 传送门

    1. 队列是一种容器适配器,专门用于在FIFO上下文(先进先出)中操作,其中从容器一端插入元素,另一端提取元素。
    2. 队列作为容器适配器实现,容器适配器即将特定容器类封装作为其底层容器类,queue提供一组特定的成员函数来访问其元素。元素从队尾入队列,从队头出队列。
    3. 底层容器可以是标准容器类模板之一,也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:
    • empty:检测队列是否为空
    • size:返回队列中有效元素的个数
    • front:返回队头元素的引用
    • back:返回队尾元素的引用
    • push_back:在队列尾部入队列
    • pop_front:在队列头部出队列
    1. 标准容器类deque和list满足了这些要求。默认情况下,如果没有为queue实例化指定容器类,则使用标准容器deque。
      在这里插入图片描述

    3.2 queue的使用:

    queue对其容器的接口进行了包装,默认使用deque:

    在这里插入图片描述
    直接见代码:

    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;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    运行结果是:1 2 3 4

    • 和之前C语言写的程序queue的逻辑是一致的
    • 使用的方法也是一样的

    3.3 queue的模拟实现:

    直接运用适配器,复用别的容器,queue默认是复用deque这个容器

    namespace Joker
    {
    //队列的实现:
    
    	//deque,既有vector的优点,又有list的有点
    	//队列不支持vector的适配,因为vector是不支持pop_front的接口
    	//用适配器来适配 -- 不用自己实现
    	template<class T, class Container = deque<T>>
    	class queue
    	{
    	public:
    		void push(const T& x)
    		{
    			_con.push_back(x);
    		}
    
    		void pop()
    		{
    			_con.pop_front();
    		}
    
    		const T& front()
    		{
    			return _con.front();
    		}
    
    		const T& back()
    		{
    			return _con.back();
    		}
    
    		size_t size()
    		{
    			return _con.size();
    		}
    
    		bool empty()
    		{
    			return _con.empty();
    		}
    
    	private:
    		Container _con;
    	};
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44

    我们复用的是deque的功能来实现queue的功能。

    测试一下:

    void test_queue()
    {
    	//queue q;
    	queue<int, list<int>> q;
    	//queue> q;
    
    	q.push(1);
    	q.push(2);
    	q.push(3);
    	q.push(4);
    
    	while (!q.empty())
    	{
    		cout << q.front() << " ";
    		q.pop();
    	}
    	cout << endl;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    运行结果:1 2 3 4

    测试时候适配器用的是list,基于queue的结构而去适配合理的容器,因为list头插头删时间复杂度为〇(1),很方便…

    注意:

    • 不要用vector来适配,因为头插和头删的时间复杂度都为〇(n),时间复杂度很高…

    4. 仿函数

    4.1 仿函数的介绍:

    仿函数 – 更高维度的泛型思想(不仅是数据类型的控制,更是逻辑的控制)

    • 在使用仿函数之前,我们要包一下头文件#include< functional > 这个头文件

    什么是仿函数:

    • 仿函数其实是: 看着像函数名,其实是个对象, 可以像调用函数一样去使用,实际上调用的是运算符重载

    仿函数(greater)为例:
    在这里插入图片描述

    • 一起来看一个算法库中的一个排序算法:

    在这里插入图片描述
    这里就用到了仿函数:

    • 默认排的是升序 – 默认传的是less
    • 我们还可以自己写仿函数,然后传过去

    4.2 库中仿函数的使用 + 模拟实现仿函数:

    • 当我们要给一个顺序表排序的时候,当每个元素都是内置类型时,直接用库里的仿函数就可以
    • 但是要排的元素是自定义类型的时候,就需要我们自己写一个仿函数了

    假如我们给一个商品自定义类型:

    //商品
    	struct Goods
    	{
    		string _name;
    		double _price;
    		size_t _saleNum;
    		//...
    
    		/*bool operator<(const Goods& g) const
    		{
    			return _price < g._price;
    		}*/
    	};
    
    	//仿函数 -- 更高维度的泛型思想(不仅是数据类型的控制,更是逻辑的控制)
    	struct LessPrice
    	{
    		bool operator()(const Goods& g1, const Goods& g2) const
    		{
    			return g1._price < g2._price;
    		}
    	};
    
    	struct GreaterPrice
    	{
    		bool operator()(const Goods& g1, const Goods& g2) const
    		{
    			return g1._price > g2._price;
    		}
    	};
    
    	struct LessSaleNum
    	{
    		bool operator()(const Goods& g1, const Goods& g2) const
    		{
    			return g1._saleNum < g2._saleNum;
    		}
    	};
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38

    测试:

    void test_Functional()
    	{
    		//vector v = { 1, 2, 3, 4 }; -- C++11的用法
    		vector<int> v;
    		v.push_back(2);
    		v.push_back(1);
    		v.push_back(4);
    		v.push_back(5);
    		v.push_back(3);
    
    		for (auto e : v)
    		{
    			cout << e << " ";
    		}
    		cout << endl;
    
    		//默认是升序 -- 默认传的是less
    		sort(v.begin(), v.end());
    		for (auto e : v)
    		{
    			cout << e << " ";
    		}
    		cout << endl;
    
    		//greater
    		sort(v.begin(), v.end(), greater<int>());
    		for (auto e : v)
    		{
    			cout << e << " ";
    		}
    		cout << endl;
    
    		//在优先级队列中是按照类的模板参数传的,在这里传的是对象,是函数模板自动推导
    
    		//指向数组的原生指针,本身就是天然迭代器
    		int a[6] = { 1, 2, 5, 2, 5, 7 };
    		sort(a, a + 6);
    		sort(a, a + 6, greater<int>());
    
    		//自定义类型就需要我们写仿函数了
    
    		Goods gds[4] = { { "苹果", 2.1, 1000}, { "香蕉", 3.0, 200}, { "橙子", 2.2,300}, { "菠萝", 1.5,50} };
    
    		sort(gds, gds + 4, LessPrice());
    		sort(gds, gds + 4, GreaterPrice());
    		sort(gds, gds + 4, LessSaleNum());
    		sort(gds, gds + 4, GreaterSaleNum());
    	}
    
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49

    传仿函数的时候,我们只需要传自己写的那个仿函数就可以了…

    补充:

    • 只是一个普通类,重载了括号,可以像函数一样使用所以叫仿函数
    • 是一个空类,只有一个字节

    5. priority_queue优先级队列 的介绍和使用 + 模拟实现

    5.1 priority_queue的介绍:

    priority_queue的学习文档:👉 传送门

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

    底层是一个堆的结构,默认是一个大堆:

    在这里插入图片描述
    数据结构 — 堆 ,还不熟悉的同学看这里👀:👉 堆复习 - 传送门

    5.2 priority_queue的使用:

    在这里插入图片描述
    直接见代码:

    //底层是个堆(默认是个大堆) -- 底层用了vector
    void test_priority_queue()
    {
    	//greater库里写好了的仿函数
    	priority_queue<int, vector<int>, greater<int>> pq;
    	pq.push(2);
    	pq.push(5);
    	pq.push(1);
    	pq.push(6);
    	pq.push(8);
    
    	while (!pq.empty())
    	{
    		cout << pq.top() << " ";
    		pq.pop();
    	}
    	cout << endl;
    
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    运行结果:1 2 5 6 8

    注意:

    默认仿函数传的是less – 应该是是个小于的仿函数

    问题:

    • 优先级队列默认大的优先级高,传的是less仿函数,底层是一个大堆
    • 想控制成小的优先级高,传greater仿函数,底层是一个小堆,这个是反过来的
    • 算是设计的一个失误

    我们有吐槽的权利,但是没有质疑的权利~ 😁😁😁

    5.3 priority_queue的模拟实现:

    1.模拟实现:

    template<class T>
    struct less
    {
    	bool operator()(const T& x, const T& y) const
    	{
    		return x < y;
    	}
    };
    
    template<class T>
    struct greater
    {
    	bool operator()(const T& x, const T& y) const
    	{
    		return x > y;
    	}
    };
    
    //缺省了两个参数,相传第三个参数必须传第三个参数,因为是从右往左缺省
    template<class T, class Container = vector<T>, class Compare = less<T>>
    class priority_queue
    {
    public:
    	priority_queue(const Compare& comFunc = Compare())
    		:_comFunc(comFunc)
    	{}
    
    	//优先级队列的另一个构造函数 -- 用一个区间去构造
    	//兼容使用函数指针
    	template <class InputIterator>
    	priority_queue(InputIterator first, InputIterator last, const Compare& comFunc = Compare())
    		:_comFunc(comFunc)
    	{
    		while (first != last)
    		{
    			_con.push_back(*first);
    			first++;
    		}
    
    		//建堆 -- 向下建堆
    		for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
    		{
    			AdjustDown(i);
    		}
    	}
    
    	//默认做个大堆
    	void AdjustUp(size_t child)
    	{
    		//Compare comFunc;	//是一个仿函数
    		size_t parent = (child - 1) / 2;
    		while (child > 0)
    		{
    			//if (_con[parent] < _con[child])
    			if (_comFunc(_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);
    	}
    
    	void AdjustDown(size_t parent)
    	{
    		//Compare comFunc;
    		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() && _comFunc(_con[child], _con[child + 1]))
    			{
    				//默认认为左孩子大
    				child++;
    			}
    
    			//if (_con[parent] < _con[child])
    			if (_comFunc(_con[parent], _con[child]))
    			{
    				swap(_con[parent], _con[child]);
    				parent = child;
    				child = parent * 2 + 1;
    			}
    			else
    			{
    				break;
    			}
    		}
    	}
    
    	void pop()
    	{
    		assert(!_con.empty());
    		swap(_con[0], _con[_con.size() - 1]);
    		_con.pop_back();
    
    		//向下调整,时间复杂度logN
    		AdjustDown(0);
    	}
    
    	//避免拷贝构造提高效率,加上const是为了不让外部修改 -- 堆是不允许随便修改的
    	const T& top()
    	{
    		return _con[0];
    	}
    
    	size_t size()
    	{
    		return _con.size();
    	}
    
    	bool empty()
    	{
    		return _con.empty();
    	}
    private:
    	Compare _comFunc;
    	Container _con;
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 优先级队列 – 用到堆(大堆用小于 < ,小堆用大于 > )
    • 还是用适配器,不用原生去实现
    • deque的随机访问效率不高,适合在头尾适合在头尾插入删除

    这里用到了堆排序算法,不熟悉的小伙伴还看这里:👉 堆排序复习 - 传送门

    2.测试:

    (1) 不用仿函数,直接通过函数来比较大小,传函数指针:

    在这里插入图片描述

    • 我们在实现的同时,不仅支持仿函数,而且还支持支持了函数指针,因为函数指针也是一种类型。

    (2) 传自己写的 仿函数/函数指针:

    template<class T>
    bool ComInitLess(T x1, T x2)
    {
    	return x1 > x2;
    }
    
    //这里是写死了,只能写降序,不能写升序 -- C++引入了仿函数来解决这个问题
    void test_priority_queue1()
    {
    	//看着像函数名,其实是个对象,可以像调用函数一样去使用,实际上调用的是运算符重载
    	//less LessCom;
    	//cout << LessCom(1, 2) << endl;
    
    	//greater GreaterCom;
    	//cout << GreaterCom(1, 2) << endl;
    
    	//greater库里写好了的仿函数
    	
    	//通过模板类型推导
    	priority_queue<int, vector<int>, greater<int>> pq;
    
    	//通过函数指针调用
    	//priority_queue, bool(*)(int, int)> pq(ComInitLess);
    
    	//priority_queue pq;
    
    	pq.push(2);
    	pq.push(5);
    	pq.push(1);
    	pq.push(6);
    	pq.push(8);
    
    	while (!pq.empty())
    	{
    		cout << pq.top() << " ";
    		pq.pop();
    	}
    
    	cout << endl;
    
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41

    运行结果:1 2 5 6

    (3) 不传仿函数,用默认的缺省值仿函数:

    void test_priority_queue2()
    {
    	int a[] = { 1, 4, 2, 7, 8, 9 };
    	priority_queue<int> pq(a, a + 6);
    
    	while (!pq.empty())
    	{
    		cout << pq.top() << " ";
    		pq.pop();
    	}
    
    	cout << endl;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    运行结果:9 8 7 4 2 1


    6. 适配器的合理选择

    6.1 deque作为stack和queue的底层默认容器的原因:

    • deque(双端队列):
      是一种双开口的"连续"空间的数据结构,双开口的含义是:可以在头尾两端进行插入和删除操作,且时间复杂度为O(1),与vector比较,头插效率高,不需要搬移元素;与list比较,空间利用率比较高。
    • deque的缺陷:
      与vector比较,deque的优势是:头部插入和删除时,不需要搬移元素,效率特别高,而且在扩容时,也不需要搬移大量的元素,因此其效率是必vector高的。与list比较,其底层是连续空间,空间利用率比较高,不需要存储额外字段
      deque有一个致命缺陷:不适合遍历,因为在遍历时,deque的迭代器要频繁的去检测其是否移动到某段小空间的边界,导致效率低下,而序列式场景中,可能需要经常遍历,因此在实际中,需要线性结构时,大多数情况下优先考虑vector和list,deque的应用并不多,而目前能看到的一个应用就是,STL用其作为stack和queue的底层数据结构

    6.2 各种适配器的优劣情况:

    • 适配器是用来适配容器的,那么在不同的场景下需要适配不同的容器,这时候我们就需要根据容器的特点来选择合适的容器了

    适配:

    • stack: 可以用vector、list适配
    • queue: 可以用list适配,不能用vector – 头删效率不高
    • priority_queue: 可以用deque适配,不能用list – 随机访问效率不高

    (1) vector:

    优点: 适合尾插尾删,随机访问,CPU高速缓存命中高
    缺点:
    a. 不适合头部或者中部插入删除,效率低,需要挪动数据
    b. 扩容有一定性能消耗,还存在一定程度空间浪费。-- 因为删除数据不缩容

    (2) list:

    优点:
    a.任意位置插入删除效率高。〇(1)
    b.按需申请释放空间。
    缺点:
    a.不支持随机访问
    b.CPU高速命中低

    (3) deque:

    deque是结合vector和list的优缺点产生的双端队列

    优点:
    a.头部和尾部插入删除数据效率不错
    b.支持随机访问
    c.扩容代价小
    d.cpu高速缓存命中高

    缺点:
    a.中部的插入删除效率不行
    b.虽然支持随机访问,但是效率相比vector而言还是有差距,频繁随机访问要小心

    • deque – 外强中干(很复杂)
    • 它的产生是因为vector和list有共同的缺点
    • 什么场景适合用deque ——> 大量头尾插入删除,偶尔随机访问
    • queue和stack用deque做默认适配容器是OK的
  • 相关阅读:
    书生·浦语大模型全链路开源体系-第6课
    java毕业生设计采购物料质量检验系统计算机源码+系统+mysql+调试部署+lw
    万物生长大会 | 创邻科技再登杭州准独角兽榜单
    Shiro获取登录人数据
    【JavaScript 报错】未捕获的模块错误:Uncaught ModuleError
    R语言绘制精美图形 | 火山图 | 学习笔记
    个人信息保护法vs国家标准,37项标准为个人信息加道“安全锁”~(附整理文档及pdf下载)
    parallelStream并行流性能
    《XSS-Labs》02. Level 11~20
    深入浅出之数组
  • 原文地址:https://blog.csdn.net/m0_63059866/article/details/127107873