C++从零开始的打怪升级之路(day38)

这是关于一个普通双非本科大一学生的C++的学习记录贴

在此前，我学了一点点C语言还有简单的数据结构，如果有小伙伴想和我一起学习的，可以私信我交流分享学习资料

那么开启正题

今天分享的是关于适配器了解以及一些简单适配器实现

1.容器适配器

1.1什么是适配器

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

也就是我们常说的复用

1.2deque

虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和queue只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque

deque又叫双端队列，大致性质就是一个指针数组，每个指针对应一段空间，如果数据存满了需要再存数据，只需再开一个指针，如果需要扩容也只是指针数组需要扩容，但是deque的迭代器相当复杂，有四个指针，这里不展开分析

明明我们有vector和list，为什么需要deque这个容器呢

deque的优点：支持随机访问，头插头删效率高，这很好得弥补了list和vector的不足，那deque可以取而代之吗，答案显而易见，我们来看deque的缺点

deque的缺点：【】效率低，由于迭代器复杂，和本身复杂的结构，使deque的大量随机访问效率低，大概是vector时间的4~5倍，但是在stack，queue中并没有体现到他的缺陷，因此STL中的默认容器选择了它

2.stack的模拟实现

根据stack先进后出的性质我们可以借助vector或者deque模拟实现

namespace wkl
{
	template<class T, class Container = deque>
	class stack
	{
		public:
		stack()
		{
			;
		}
 
		void push(const T& x)
		{
			_con.push_back(x);
		}
 
		void pop()
		{
			_con.pop_back();
		}
 
		T& top()
		{
			return _con.back();
		}
 
		size_t size()
		{
			return _con.size();
		}
 
		bool empty()
		{
			return _con.empty();
		}
 
	private:
		Container _con;
	};
 
	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.queue的模拟实现

根据queue先进后出的性质我们可以借助list或者deque模拟实现

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

这是模拟实现代码，以及测试性质函数

4.priority_queue

4.1仿函数

在了解priority_queue之前我们需要先了解仿函数

我们来看下面的代码

namespace wkl
{
	template<class T>
	struct less
	{
		bool operator()(const T& x1, const T& x2)
		{
			return x1 < x2;
		}
	};
 
	void Test_less()
	{
		less<int> l;
		cout << l(1, 2) << endl;
	}
}

cout << l(1, 2) << endl;这一行代码看起来很像函数调用，但实际上不是的

他是根据对象的operator()对（）进行重载，再调用函数，因为看起来像函数，因此被称为仿函数

仿函数属于STL的四大容器之一

4.2priority_queue的模拟实现

优先级队列也是一种适配器，优先级队列的底层实际上是由堆来实现的，我们这里用vector来模拟实现

namespace wkl
{
	//仿函数 函数对象 （对象可以和函数一样调用）
	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 = vector, class Comapre = less>
	class priority_queue  //默认是大堆
	{
	public:
		Comapre com;
 
		void AdjustUp(int child)
		{
			int parent = (child - 1) / 2;
			while (child > 0)
			{
				//if (_con[child] > _con[parent])
				if (com(_con[parent], _con[child]))
				{
					swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}
 
		void push(const T& x)
		{
			_con.push_back(x);
			AdjustUp(_con.size() - 1);
		}
 
		void AdjustDown(int root)
		{
			Comapre com;
			int parent = root;
			int child = parent * 2 + 1;
			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 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> pq;
		pq.push(9);
		pq.push(3);
		pq.push(7);
		pq.push(0);
 
		while (!pq.empty())
		{
			cout << pq.top() << " ";
			pq.pop();
		}
		cout << endl;
	}
}

这是模拟实现代码，以及测试性质函数

 新手写博客，有不对的位置希望大佬们能够指出，也谢谢大家能看到这里，让我们一起学习进步吧！！