C++容器适配与栈的实现及dequeque和优先级详解

C/C++
199
0
0
2023-06-02
详解C++中动态内存管理和泛型编程
上一篇
C语言中花式退出程序的方式总结
下一篇
目录
  • 容器适配器
  • 栈的实现
  • queque实现
  • dequeque
  • dequeque的缺陷
  • 优先级队列
  • 习题
  • 优先级队列模拟实现
  • 仿函数

容器适配器

我们可以看出，栈中没有空间配置器（内存池），而是适配器

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

栈的实现

#include<vector>
#include<iostream>
using namespace std;
namespace myspace
{
	template<class T>
	class Stack
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}
		void pop()
		{
			_con.pop_back();
		}
		T& top()
		{
			return _con.back();//back接口访问尾部的数据
		}
		T& top()const
		{
			return _con.back();//back接口访问尾部的数据
		}
		bool empty()
		{
			return _con.empty();
		}
		size_t size()const
		{
			return _con.size();
		}
	private:
		vector<T> _con;
	};
}

此时这个栈并不是适配器，因为底层被写死了，底层是用vector实现的，如果想让它适配，加上适配器即可

此时就是适配器

list

注意队列不能用vector，编译会报错，因为不支持头删，没有pop_front

queque实现

namespace myspace
{
	template<class T, class Container = deque<T>>
	class queue
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}
		void pop()
		{
			_con.pop_front();
		}
		T& back()
		{
			return _con.back();
		}
		T& front()
		{
			return _con.front();
		}
		const T& back() const
		{
			return _con.back();
		}
		const T& front() const
		{
			return _con.front();
		}
		bool empty()  const
		{
			return _con.empty();
		}
		size_t size() const
		{
			return _con.size();
		}
	private:
		Container _con;
	};
}

dequeque

我们发现栈和队列都有一个dequeque

dequeque不是队列，是vector和list的结合体

1.支持任意位置的插入删除

2.支持随机访问

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

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

dequeque的缺陷

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

与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。 但是，deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下（中间的插入删除效率很低），

而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构

测试之后，dequeque显然效率低

void test_op()
{
	srand(time(0));
	const int N = 100000;
	vector<int> v;
	v.reserve(N);
	deque<int> dp;
	for (int i = 0; i < N; ++i)
	{
		auto e = rand();
		v.push_back(e);
		dp.push_back(e);
	}
	int begin1 = clock();
	sort(v.begin(), v.end());
	int end1 = clock();
	int begin2 = clock();
	sort(dp.begin(), dp.end());
	int end2 = clock();
	printf("vector sort:%d\n", end1 - begin1);
	printf("deque sort:%d\n", end2 - begin2);
}

优先级队列

priority_queque

优先级队列的底层是堆（二叉树的堆）

第二个参数容器适配器，第三个参数仿函数，less是大的优先级高

后面俩个参数给缺省值，测试优先级队列，默认大的优先级高

也可以用一个区间去初始化

把第三个参数改为greater，就是小的优先级高

习题

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int>  pq(nums.begin(),nums.end());
       while(--k)
       {
           pq.pop();
       }
       return pq.top();
    }
};

215. 数组中的第K个最大元素 - 力扣（LeetCode）

优先级队列模拟实现

namespace myspace
{
	//大堆
	template<class T,class Container=vector<T>>
	class priority_queque
	{
	public:
		template<class InputerIterator>
		priority_queque(InputerIterator first, InputerIterator last)//迭代器区间
		{
			while (first < last)
			{
				_con.push_back(*first);
				++first;
			}
			//建堆
			for (int i = (_con.size() - 1 - 1)/2;i>=0;--i)
			{
				adjust_down(i);
		   }
		}
		priority_queque()//默认构造，不然会报错，因为上面的迭代器区间这个函数跟构造函数同名
		{}
		void adjust_up(size_t child)
		{
			size_t parent = (child - 1) / 2;
			while (child>0)
			{
				if (_con[parent] < _con[child])
				{
					std::swap(_con[parent], _con[child]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}
		void adjust_down(size_t parent)
		{
			size_t child = parent * 2 + 1;
			while (child < _con.size())
			{
				if (child + 1 < _con.size() && _con[child + 1] > _con[child])
				{
					++child;
				} //选出最大的孩子
				if (_con[child] > _con[parent])
				{
					std::swap(_con[child],_con[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}
		void push(const T& x)//（大堆）堆的插入
		{
			_con.push_back(x);
			adjust_up(_con.size()-1);//尾插后向上跳转
		}
		void pop()//删除堆顶数据
		{
			std::swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			adjust_down(0);
		}//对顶数据和最后一个数据交换，之后删除最后一个数据，然后向下调整堆
		const T& top()
		{
			return _con[0];
		}
		bool empty()
		{
			return _con.empty();
		}
		size_t size()const
		{
			return _con.size();
		}
	private:
		Container _con;
	};
}
int main()
{
	int a[]= { 156,132,156,156,31,5,15,31,364,15 };
	myspace::priority_queque<int> pq(a,a+sizeof(a)/sizeof(int));
	while (!pq.empty())
	{
		cout << pq.top() << " ";
		pq.pop();
	}
	return 0;
}

优先级队列要控制比较大小的逻辑，上面的写法我们以大堆为例但是这样把优先级队列给写死了，如果把里面的>改为<则会变成小堆，但是这样比较麻烦。上面我们只传了俩个参数，还有一个参数没传，第三个参数是仿函数

仿函数

仿函数/函数对象——是个类，重载的是operator（），类对象可以像函数一样去使用，本质就是重载

（）也是一个运算符

跟sort不同，sort传的是函数模板，传的是对象，而这里传的是类模板，传的是类型

这里的lsFunc不是函数名，而是一个类对象

这俩个等价

不仅有less，还有greater

namespace myspace
{
	template<class T>
	class less
	{
	public:
		bool operator()(const T& l, const T& r)const
		{
			return l < r;
		}
	};
	template<class T>
	class greater
	{
	public:
		bool operator()(const T& l, const T& r)const
		{
			return l > r;
		}
	};
}

我们将这里全部改成小于号

传入仿函数

这样就可以去替换小于号

小堆

大堆

完整代码

namespace myspace
{
	//大堆
	template<class T,class Container=vector<T>,class Compare=less<T>>
	class priority_queque
	{
	public:
		template<class InputerIterator>
		priority_queque(InputerIterator first, InputerIterator last)//迭代器区间
		{
			while (first < last)
			{
				_con.push_back(*first);
				++first;
			}
			//建堆
			for (int i = (_con.size() - 1 - 1)/2;i>=0;--i)
			{
				adjust_down(i);
		   }
		}
		priority_queque()//默认构造，不然会报错，因为上面的迭代器区间这个函数跟构造函数同名
		{}
		Compare com;
		void adjust_up(size_t child)
		{
			size_t parent = (child - 1) / 2;
			while (child>0)
			{
				if (com(_con[parent] , _con[child]))
				{
					std::swap(_con[parent], _con[child]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}
		void adjust_down(size_t parent)
		{
			size_t child = parent * 2 + 1;
			while (child < _con.size())
			{
				if (child + 1 < _con.size() &&  com(_con[child],_con[child + 1]) )
				{
					++child;
				} //选出最大的孩子
				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);
			adjust_up(_con.size()-1);//尾插后向上跳转
		}
		void pop()//删除堆顶数据
		{
			std::swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			adjust_down(0);
		}//对顶数据和最后一个数据交换，之后删除最后一个数据，然后向下调整堆
		const T& top()
		{
			return _con[0];
		}
		bool empty()
		{
			return _con.empty();
		}
		size_t size()const
		{
			return _con.size();
		}
	private:
		Container _con;
	};
}
namespace myspace
{
	template<class T>
	class less
	{
	public:
		bool operator()(const T& l, const T& r)const
		{
			return l < r;
		}
	};
	template<class T>
	class greater
	{
	public:
		bool operator()(const T& l, const T& r)const
		{
			return l > r;
		}
	};
}
int main()
{
	int a[]= { 156,132,156,156,31,5,15,31,364,15 };
	myspace::priority_queque<int,vector<int>,less<int>> pq(a,a+sizeof(a)/sizeof(int));
	while (!pq.empty())
	{
		cout << pq.top() << " ";
		pq.pop();
	}
	return 0;
}
详解C++中动态内存管理和泛型编程
上一篇
C语言中花式退出程序的方式总结
下一篇