意外收获 deque

事情一件接一件，原假期计划执行遇到了很严重的突发事件，得调用中断去处理而且处理事件较长。大概需要一周，这一周虽然不能执行假期计划但是正好可以构思一下智慧太阳能上水系统 ！ 等中断执行完了希望构思也能差不多搞定，这样的话回来就可以直接施工。

今天写算法的时候，准备复习一下基本数据结构，无脑打栈实现时突发奇想，咦这个vs的#include<stack>是咋实现的呢？伴随着鼠标选中stack 然后ctrl shift G，打开新世界！

// stack standard header
#pragma once
#ifndef _STACK_
#define _STACK_
#ifndef RC_INVOKED
#include <deque>

 #pragma pack(push,_CRT_PACKING)
 #pragma warning(push,_STL_WARNING_LEVEL)
 #pragma warning(disable: _STL_DISABLED_WARNINGS)
 _STL_DISABLE_CLANG_WARNINGS
 #pragma push_macro("new")
 #undef new
_STD_BEGIN
		// CLASS TEMPLATE stack
template<class _Ty,
	class _Container = deque<_Ty> >
	class stack
	{	// LIFO queue implemented with a container
public:
	typedef _Container container_type;
	typedef typename _Container::value_type value_type;
	typedef typename _Container::size_type size_type;
	typedef typename _Container::reference reference;
	typedef typename _Container::const_reference const_reference;

	static_assert(is_same_v<_Ty, value_type>, "container adaptors require consistent types");

	stack() _NOEXCEPT_COND(is_nothrow_default_constructible_v<_Container>) // strengthened
		: c()
		{	// construct with empty container
		}

	explicit stack(const _Container& _Cont)
		: c(_Cont)
		{	// construct by copying specified container
		}

	template<class _Alloc,
		class = enable_if_t<uses_allocator_v<_Container, _Alloc>>>
		explicit stack(const _Alloc& _Al)
			_NOEXCEPT_COND(is_nothrow_constructible_v<_Container, const _Alloc&>) // strengthened
		: c(_Al)
		{	// construct with allocator
		}

	template<class _Alloc,
		class = enable_if_t<uses_allocator_v<_Container, _Alloc>>>
		stack(const stack& _Right, const _Alloc& _Al)
		: c(_Right.c, _Al)
		{	// construct by copying specified container
		}

	template<class _Alloc,
		class = enable_if_t<uses_allocator_v<_Container, _Alloc>>>
		stack(const _Container& _Cont, const _Alloc& _Al)
		: c(_Cont, _Al)
		{	// construct by copying specified container
		}

	explicit stack(_Container&& _Cont)
			_NOEXCEPT_COND(is_nothrow_move_constructible_v<_Container>) // strengthened
		: c(_STD move(_Cont))
		{	// construct by moving specified container
		}

	template<class _Alloc,
		class = enable_if_t<uses_allocator_v<_Container, _Alloc>>>
		stack(stack&& _Right, const _Alloc& _Al)
			_NOEXCEPT_COND(is_nothrow_constructible_v<_Container, _Container, const _Alloc&>) // strengthened
		: c(_STD move(_Right.c), _Al)
		{	// construct by moving specified container
		}

	template<class _Alloc,
		class = enable_if_t<uses_allocator_v<_Container, _Alloc>>>
		stack(_Container&& _Cont, const _Alloc& _Al)
			_NOEXCEPT_COND(is_nothrow_constructible_v<_Container, _Container, const _Alloc&>) // strengthened
		: c(_STD move(_Cont), _Al)
		{	// construct by moving specified container
		}

	void push(value_type&& _Val)
		{	// insert element at beginning
		c.push_back(_STD move(_Val));
		}

	template<class... _Valty>
		decltype(auto) emplace(_Valty&&... _Val)
		{	// insert element at beginning
#if _HAS_CXX17
		return (c.emplace_back(_STD forward<_Valty>(_Val)...));
#else /* _HAS_CXX17 */
		c.emplace_back(_STD forward<_Valty>(_Val)...);
#endif /* _HAS_CXX17 */
		}

	_NODISCARD bool empty() const
		{	// test if stack is empty
		return (c.empty());
		}

	_NODISCARD size_type size() const
		{	// test length of stack
		return (c.size());
		}

	_NODISCARD reference top()
		{	// return last element of mutable stack
		return (c.back());
		}

	_NODISCARD const_reference top() const
		{	// return last element of nonmutable stack
		return (c.back());
		}

	void push(const value_type& _Val)
		{	// insert element at end
		c.push_back(_Val);
		}

	void pop()
		{	// erase last element
		c.pop_back();
		}

	const _Container& _Get_container() const
		{	// get reference to container
		return (c);
		}

	void swap(stack& _Right) _NOEXCEPT_COND(_Is_nothrow_swappable<_Container>::value)
		{	// exchange contents with _Right
		_Swap_adl(c, _Right.c);
		}

protected:
	_Container c;	// the underlying container
	};

#if _HAS_CXX17
template<class _Container,
	enable_if_t<!_Is_allocator<_Container>::value, int> = 0>
	stack(_Container)
		-> stack<typename _Container::value_type, _Container>;

template<class _Container,
	class _Alloc,
	enable_if_t<conjunction_v<
		negation<_Is_allocator<_Container>>,
		_Is_allocator<_Alloc>,
		uses_allocator<_Container, _Alloc>
	>, int> = 0>
	stack(_Container, _Alloc)
		-> stack<typename _Container::value_type, _Container>;
#endif /* _HAS_CXX17 */

template<class _Ty,
	class _Container,
	class = enable_if_t<_Is_swappable<_Container>::value>> inline
	void swap(stack<_Ty, _Container>& _Left,
		stack<_Ty, _Container>& _Right)
			_NOEXCEPT_COND(_NOEXCEPT_OPER(_Left.swap(_Right)))
	{	// swap _Left and _Right stacks
	_Left.swap(_Right);
	}

template<class _Ty,
	class _Container>
	_NODISCARD inline bool operator==(const stack<_Ty, _Container>& _Left,
		const stack<_Ty, _Container>& _Right)
	{	// test for stack equality
	return (_Left._Get_container() == _Right._Get_container());
	}

template<class _Ty,
	class _Container>
	_NODISCARD inline bool operator!=(const stack<_Ty, _Container>& _Left,
		const stack<_Ty, _Container>& _Right)
	{	// test for stack inequality
	return (!(_Left == _Right));
	}

template<class _Ty,
	class _Container>
	_NODISCARD inline bool operator<(const stack<_Ty, _Container>& _Left,
		const stack<_Ty, _Container>& _Right)
	{	// test if _Left < _Right for stacks
	return (_Left._Get_container() < _Right._Get_container());
	}

template<class _Ty,
	class _Container>
	_NODISCARD inline bool operator>(const stack<_Ty, _Container>& _Left,
		const stack<_Ty, _Container>& _Right)
	{	// test if _Left > _Right for stacks
	return (_Right < _Left);
	}

template<class _Ty,
	class _Container>
	_NODISCARD inline bool operator<=(const stack<_Ty, _Container>& _Left,
		const stack<_Ty, _Container>& _Right)
	{	// test if _Left <= _Right for stacks
	return (!(_Right < _Left));
	}

template<class _Ty,
	class _Container>
	_NODISCARD inline bool operator>=(const stack<_Ty, _Container>& _Left,
		const stack<_Ty, _Container>& _Right)
	{	// test if _Left >= _Right for stacks
	return (!(_Left < _Right));
	}
_STD_END

namespace std {
template<class _Ty,
	class _Container,
	class _Alloc>
	struct uses_allocator<stack<_Ty, _Container>, _Alloc>
		: uses_allocator<_Container, _Alloc>::type
	{	// true_type if container allocator enabled
	};
}	// namespace std

 #pragma pop_macro("new")
 _STL_RESTORE_CLANG_WARNINGS
 #pragma warning(pop)
 #pragma pack(pop)
#endif /* RC_INVOKED */
#endif /* _STACK_ */

/*
 * Copyright (c) by P.J. Plauger. All rights reserved.
 * Consult your license regarding permissions and restrictions.
V6.50:0009 */

#include <deque> 这个头文件啥？ 继续ctrl shift G后发现这货有2013行，瞬间感到这触及了我的知识盲区。

可以大致推断出vs的stack是用一个双端队列实现的？又看了一下queue也引入了这个头文件。得深入理解一下但是template 关键字都忘了，真是糟糕！！

deque头文件主要包括一个双端队列容器。是一个支持在两端插入两端删除的线性储存空间，与vector和queue相似。与vector比起来，deque可以在O(1)的时间内在首端插入元素。与queue比起来，deque又能像数组一样随机访问。

手册这里看