STL adapter stack and queue

One 、 The purpose of this article is

1、 Introduce STL One of the six components -- Adapter

2、 use list and vector Realization stack and queue

Two 、 What is an adapter ？

An adapter is a design pattern ( Design patterns are a set of things that are used repeatedly 、 Most people know that 、 Catalogued 、 Total code design experience

junction ), This pattern is to convert the interface of one class into another interface that the customer wants .

Simply speaking , Adapter is actually a good design method when we write code . For example, we need to write a stack , We can use it directly vector perhaps list Do the bottom layer to realize .

3、 ... and 、 Realization stack

    template<class T, class Con = deque<T>>
	class stack
	{
	public:
		void push(const T& x)
		{
			_c.push_back(x);
		}
		void pop()
		{
			assert(!empty());
			_c.pop_back();
		}

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

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

		const T& top()
		{
			return _c.back();
		}

	private:
		Con _c;
	};

Four 、 Implementation queue

    template<class T, class Con = deque<T>>
	class queue
	{
	public:
		void push(const T& x)
		{
			_c.push_back(x);
		}

		void pop()
		{
			_c.pop_front();
		}

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

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

		const T& front()
		{
			return _c.front();
		}

		const T& back()
		{
			return _c.back();
		}
	private:
		Con _c;
	};

5、 ... and 、 It can be used vector Be the bottom of the queue ？

void test1()
{
	queue<int, vector<int>> s;
	s.push(1);
	s.push(2);
	s.push(3);
	s.push(4);

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

  answer ：vector Can't do queue The bottom of the , because queue need pop_front（）, and vector There is no such interface , Only erase Interface .

6、 ... and 、 Why? STL Inside stack and queue It's all default deque Such a container ？

 

  Here we need to introduce the following deque,deque yes double queue Abbreviation , It is often referred to as a double ended queue , Because its insertion and deletion efficiency at both ends is very high , What the queue and stack need is a container with high efficiency of inserting and deleting at both ends , therefore deque Often do stack and queue The bottom container of . About deque How to design and implement the bottom layer of , I will write a special article to explain deque Design and implementation .