C++入门容器适配器 / stack && queue模拟实现

2024-07-07 07:04:21

容器适配器

deque的原理介绍

stack模拟实现

queue模拟实现

priority_queue模拟实现

仿函数

容器适配器

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

可以这样理解：通过适配器模式，可以将不兼容的接口正常运作。

STL标准库中stack和queue的底层结构

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

那么这里的deque是什么东西呢？

deque的原理介绍

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

deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组。

我们假设一个buff是10个int大小的空间数组，map中存放了每个buff数组的地址，buff数组用来存放数据，可以理解他从中间开始利用空间，向左右扩容。

我们可以理解为他在map中间进行插入删除操作：

与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必vector高的。
与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。

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

为什么选择deque作为stack和queue的底层默认容器？我们给出了以下两点原因：

stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高。

stack模拟实现

目前为止，我们已经了解了两种模式：

适配器模式 -- 封装转换
迭代器模式 -- 封装统一访问方式（数据结构访问都可以用）

接下来试着通过运用适配器来模拟实现stack和queue：

//Stack.h
#pragma once

namespace bit
{
	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();
		}

		bool empty()
		{
			return _con.empty();
		}

		size_t size()
		{
			_con.size();
		}
	private:
		Container _con;
	};
}

我们只需要定义一个适配器类型的成员变量_con，他默认可以使用push_back，pop_back等常规接口，直接利用接口实现操作即可。stack用vector和list都可以实现，测试代码如下：

void test_stack()
{
	//bit::stack<int, vector<int>> s;
	//bit::stack<int, list<int>> s; 
	bit::stack<int, deque<int>> s;  

	//bit::stack<int> s; //不传第二个参数默认使用deque

	s.push(1);
	s.push(2);
	s.push(3);
	s.push(4);

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

queue模拟实现

//Queue.h
#pragma once

namespace bit
{
    // deque list
    // 不支持vector
    template<class T, class Container = deque<T>>
    class queue
    {
    public:
        void push(const T& x)
        {
            _con.push_back(x);
        }

        void pop()
        {
            _con.pop_front();
			// 这样就可以支持vector了，但是效率就很低了
			//_con.erase(_con.begin());
        }

        T& back()
        {
            return _con.back();
        }

        T& front()
        {
            return _con.front();
        }

        bool empty()
        {
            return _con.empty();
        }

        size_t size()
        {
            _con.size();
        }
    private:
        Container _con;
    };
}

注意：queue不支持vector适配器，原因是vector没有pop_front的接口，如果要实现要用erase接口，但是头删完后面所有数据要往前挪，消耗时间太大，不建议这样做。测试代码如下：

void test_queue()
{
	bit::queue<int> q;
	//bit::queue<int,list<int>> q;

	// 不支持
	//bit::queue<int, vector<int>> q;

	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);

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

priority_queue模拟实现

仿函数

在实现之前先了解仿函数的概念：重载了operator（）的类

特点：参数个数和返回值根据需求确定，不固定，很灵活

通过这个概念可以实现STL库里的greater和less同等效果的仿函数。

//priority_queue.h
#pragma once

namespace bit
{
	template<class T>
	class myless
	{
	public:
		bool operator()(const T& x, const T& y)
		{
			return x < y;
		}
	};

	template<class T>
	class mygreater
	{
	public:
		bool operator()(const T& x, const T& y)
		{
			return x > y;
		}
	};

	template<class T, class Container = vector<T>, class Comapre = myless<T>>
	class priority_queue
	{
	public:
		priority_queue() = default;

		template <class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
		{
			while (first != last)
			{
				_con.push_back(*first);
				++first;
			}

			for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
			{
				adjust_down(i);
			}
		}

		void adjust_up(int child)
		{
			Comapre comfunc;
			int parent = (child - 1) / 2;
			while (child > 0)
			{
				//if (_con[parent] < _con[child])
				if (comfunc(_con[parent], _con[child]))
				//if (comfunc.operator()(_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);
			adjust_up(_con.size() - 1);
		}

		void adjust_down(int parent)
		{
			Comapre 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()
		{
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();

			adjust_down(0);
		}

		const T& top()
		{
			return _con[0];
		}

		size_t size()
		{
			return _con.size();
		}

		bool empty()
		{
			return _con.empty();
		}
	private:
		Container _con;
	};
}

我们可以通过显式调用greater仿函数来实现小堆，测试代码如下：

void test_priority_queue()
{
	//vector<int> v = { 3,2,7,6,0,4,1,9,8,5 };
	//priority_queue<int> q1(v.begin(), v.end());

	int a[] = { 3,2,7,6,0,4,1,9,8,5 };
	// 默认是大堆
	//bit::priority_queue<int> q1(a, a+sizeof(a)/sizeof(int));
	// 小堆
	bit::priority_queue<int, vector<int>, bit::mygreater<int>> q1(a, a + sizeof(a) / sizeof(int));

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

码农公寓

容器适配器

deque的原理介绍

stack模拟实现

queue模拟实现

priority_queue模拟实现

仿函数

相关文章