list

C语言库函数的原型,有用的拿去

// list standard header
#pragma once
#ifndef _LIST_
#define _LIST_
#ifndef RC_INVOKED
#include <xfunctional>
#include <memory>
#include <stdexcept>

 #pragma pack(push,_CRT_PACKING)
 #pragma warning(push,3)

_STD_BEGIN
		// TEMPLATE CLASS _List_unchecked_const_iterator
template<class _Mylist, class _Base = _Iterator_base0>
	class _List_unchecked_const_iterator
		: public _Iterator012<bidirectional_iterator_tag,
			typename _Mylist::value_type,
			typename _Mylist::difference_type,
			typename _Mylist::const_pointer,
			typename _Mylist::const_reference,
			_Base>
	{	// unchecked iterator for nonmutable list
public:
	typedef _List_unchecked_const_iterator<_Mylist, _Base> _Myiter;
	typedef bidirectional_iterator_tag iterator_category;

	typedef typename _Mylist::_Nodeptr _Nodeptr;
	typedef typename _Mylist::value_type value_type;
	typedef typename _Mylist::difference_type difference_type;
	typedef typename _Mylist::const_pointer pointer;
	typedef typename _Mylist::const_reference reference;

	_List_unchecked_const_iterator()
		: _Ptr(0)
		{	// construct with null node pointer
		}

	_List_unchecked_const_iterator(_Nodeptr _Pnode, const _Mylist *_Plist)
		: _Ptr(_Pnode)
		{	// construct with node pointer _Pnode
		this->_Adopt(_Plist);
		}

	reference operator*() const
		{	// return designated value
		return (_Mylist::_Myval(_Ptr));
		}

	pointer operator->() const
		{	// return pointer to class object
		return (&**this);
		}

	_Myiter& operator++()
		{	// preincrement
		_Ptr = _Mylist::_Nextnode(_Ptr);
		return (*this);
		}

	_Myiter operator++(int)
		{	// postincrement
		_Myiter _Tmp = *this;
		++*this;
		return (_Tmp);
		}

	_Myiter& operator--()
		{	// predecrement
		_Ptr = _Mylist::_Prevnode(_Ptr);
		return (*this);
		}

	_Myiter operator--(int)
		{	// postdecrement
		_Myiter _Tmp = *this;
		--*this;
		return (_Tmp);
		}

	bool operator==(const _Myiter& _Right) const
		{	// test for iterator equality
		return (_Ptr == _Right._Ptr);
		}

	bool operator!=(const _Myiter& _Right) const
		{	// test for iterator inequality
		return (!(*this == _Right));
		}

	_Nodeptr _Mynode() const
		{	// return node pointer
		return (_Ptr);
		}

	_Nodeptr _Ptr;	// pointer to node
	};

	// TEMPLATE CLASS _List_unchecked_iterator
template<class _Mylist>
	class _List_unchecked_iterator
		: public _List_unchecked_const_iterator<_Mylist>
	{	// unchecked iterator for mutable list
public:
	typedef _List_unchecked_iterator<_Mylist> _Myiter;
	typedef _List_unchecked_const_iterator<_Mylist> _Mybase;
	typedef bidirectional_iterator_tag iterator_category;

	typedef typename _Mylist::_Nodeptr _Nodeptr;
	typedef typename _Mylist::value_type value_type;
	typedef typename _Mylist::difference_type difference_type;
	typedef typename _Mylist::pointer pointer;
	typedef typename _Mylist::reference reference;

	_List_unchecked_iterator()
		{	// construct with null node
		}

	_List_unchecked_iterator(_Nodeptr _Pnode, const _Mylist *_Plist)
		: _Mybase(_Pnode, _Plist)
		{	// construct with node pointer _Pnode
		}

	reference operator*() const
		{	// return designated value
		return ((reference)**(_Mybase *)this);
		}

	pointer operator->() const
		{	// return pointer to class object
		return (&**this);
		}

	_Myiter& operator++()
		{	// preincrement
		++(*(_Mybase *)this);
		return (*this);
		}

	_Myiter operator++(int)
		{	// postincrement
		_Myiter _Tmp = *this;
		++*this;
		return (_Tmp);
		}

	_Myiter& operator--()
		{	// predecrement
		--(*(_Mybase *)this);
		return (*this);
		}

	_Myiter operator--(int)
		{	// postdecrement
		_Myiter _Tmp = *this;
		--*this;
		return (_Tmp);
		}
	};

	// TEMPLATE CLASS _List_const_iterator
template<class _Mylist>
	class _List_const_iterator
		: public _List_unchecked_const_iterator<_Mylist, _Iterator_base>
	{	// iterator for nonmutable list
public:
	typedef _List_const_iterator<_Mylist> _Myiter;
	typedef _List_unchecked_const_iterator<_Mylist, _Iterator_base> _Mybase;
	typedef bidirectional_iterator_tag iterator_category;

	typedef typename _Mylist::_Nodeptr _Nodeptr;
	typedef typename _Mylist::value_type value_type;
	typedef typename _Mylist::difference_type difference_type;
	typedef typename _Mylist::const_pointer pointer;
	typedef typename _Mylist::const_reference reference;

	_List_const_iterator()
		: _Mybase()
		{	// construct with null node pointer
		}

	_List_const_iterator(_Nodeptr _Pnode, const _Mylist *_Plist)
		: _Mybase(_Pnode, _Plist)
		{	// construct with node pointer _Pnode
		}

	typedef _List_unchecked_const_iterator<_Mylist> _Unchecked_type;

	_Myiter& _Rechecked(_Unchecked_type _Right)
		{	// reset from unchecked iterator
		this->_Ptr = _Right._Ptr;
		return (*this);
		}

	_Unchecked_type _Unchecked() const
		{	// make an unchecked iterator
		return (_Unchecked_type(this->_Ptr, (_Mylist *)this->_Getcont()));
		}

	reference operator*() const
		{	// return designated value
 #if _ITERATOR_DEBUG_LEVEL == 2
		if (this->_Getcont() == 0
			|| this->_Ptr == 0
			|| this->_Ptr == ((_Mylist *)this->_Getcont())->_Myhead)
			{	// report error
			_DEBUG_ERROR("list iterator not dereferencable");
			_SCL_SECURE_OUT_OF_RANGE;
			}

 #elif _ITERATOR_DEBUG_LEVEL == 1
		_SCL_SECURE_VALIDATE(this->_Getcont() != 0 && this->_Ptr != 0);
		_SCL_SECURE_VALIDATE_RANGE(this->_Ptr !=
			((_Mylist *)this->_Getcont())->_Myhead);
 #endif /* _ITERATOR_DEBUG_LEVEL */

		return (_Mylist::_Myval(this->_Ptr));
		}

	_Myiter& operator++()
		{	// preincrement
 #if _ITERATOR_DEBUG_LEVEL == 2
		if (this->_Getcont() == 0
			|| this->_Ptr == 0
			|| this->_Ptr == ((_Mylist *)this->_Getcont())->_Myhead)
			{	// report error
			_DEBUG_ERROR("list iterator not incrementable");
			_SCL_SECURE_OUT_OF_RANGE;
			}

 #elif _ITERATOR_DEBUG_LEVEL == 1
		_SCL_SECURE_VALIDATE(this->_Getcont() != 0 && this->_Ptr != 0);
		_SCL_SECURE_VALIDATE_RANGE(this->_Ptr !=
			((_Mylist *)this->_Getcont())->_Myhead);
 #endif /* _ITERATOR_DEBUG_LEVEL */

		this->_Ptr = _Mylist::_Nextnode(this->_Ptr);
		return (*this);
		}

	_Myiter operator++(int)
		{	// postincrement
		_Myiter _Tmp = *this;
		++*this;
		return (_Tmp);
		}

	_Myiter& operator--()
		{	// predecrement
 #if _ITERATOR_DEBUG_LEVEL == 2
		if (this->_Getcont() == 0
			|| this->_Ptr == 0
			|| (this->_Ptr = _Mylist::_Prevnode(this->_Ptr))
				== ((_Mylist *)this->_Getcont())->_Myhead)
			{	// report error
			_DEBUG_ERROR("list iterator not decrementable");
			_SCL_SECURE_OUT_OF_RANGE;
			}

 #elif _ITERATOR_DEBUG_LEVEL == 1
		_SCL_SECURE_VALIDATE(this->_Getcont() != 0 && this->_Ptr != 0);
		this->_Ptr = _Mylist::_Prevnode(this->_Ptr);
		_SCL_SECURE_VALIDATE_RANGE(this->_Ptr !=
			((_Mylist *)this->_Getcont())->_Myhead);

 #else /* _ITERATOR_DEBUG_LEVEL */
		this->_Ptr = _Mylist::_Prevnode(this->_Ptr);
 #endif /* _ITERATOR_DEBUG_LEVEL */

		return (*this);
		}

	_Myiter operator--(int)
		{	// postdecrement
		_Myiter _Tmp = *this;
		--*this;
		return (_Tmp);
		}

	bool operator==(const _Myiter& _Right) const
		{	// test for iterator equality
 #if _ITERATOR_DEBUG_LEVEL == 2
		if (this->_Getcont() == 0
			|| this->_Getcont() != _Right._Getcont())
			{	// report error
			_DEBUG_ERROR("list iterators incompatible");
			_SCL_SECURE_INVALID_ARGUMENT;
			}

 #elif _ITERATOR_DEBUG_LEVEL == 1
		_SCL_SECURE_VALIDATE(this->_Getcont() != 0
			&& this->_Getcont() == _Right._Getcont());
 #endif /* _ITERATOR_DEBUG_LEVEL */

		return (this->_Ptr == _Right._Ptr);
		}

	bool operator!=(const _Myiter& _Right) const
		{	// test for iterator inequality
		return (!(*this == _Right));
		}
	};

template<class _Mylist> inline
	typename _List_const_iterator<_Mylist>::_Unchecked_type
		_Unchecked(_List_const_iterator<_Mylist> _Iter)
	{	// convert to unchecked
	return (_Iter._Unchecked());
	}

template<class _Mylist> inline
	_List_const_iterator<_Mylist>&
		_Rechecked(_List_const_iterator<_Mylist>& _Iter,
			typename _List_const_iterator<_Mylist>
				::_Unchecked_type _Right)
	{	// convert to checked
	return (_Iter._Rechecked(_Right));
	}

	// TEMPLATE CLASS _List_iterator
template<class _Mylist>
	class _List_iterator
		: public _List_const_iterator<_Mylist>
	{	// iterator for mutable list
public:
	typedef _List_iterator<_Mylist> _Myiter;
	typedef _List_const_iterator<_Mylist> _Mybase;
	typedef bidirectional_iterator_tag iterator_category;

	typedef typename _Mylist::_Nodeptr _Nodeptr;
	typedef typename _Mylist::value_type value_type;
	typedef typename _Mylist::difference_type difference_type;
	typedef typename _Mylist::pointer pointer;
	typedef typename _Mylist::reference reference;

	_List_iterator()
		{	// construct with null node
		}

	_List_iterator(_Nodeptr _Pnode, const _Mylist *_Plist)
		: _Mybase(_Pnode, _Plist)
		{	// construct with node pointer _Pnode
		}

	typedef _List_unchecked_iterator<_Mylist> _Unchecked_type;

	_Myiter& _Rechecked(_Unchecked_type _Right)
		{	// reset from unchecked iterator
		this->_Ptr = _Right._Ptr;
		return (*this);
		}

	_Unchecked_type _Unchecked() const
		{	// make an unchecked iterator
		return (_Unchecked_type(this->_Ptr, (_Mylist *)this->_Getcont()));
		}

	reference operator*() const
		{	// return designated value
		return ((reference)**(_Mybase *)this);
		}

	pointer operator->() const
		{	// return pointer to class object
		return (&**this);
		}

	_Myiter& operator++()
		{	// preincrement
		++(*(_Mybase *)this);
		return (*this);
		}

	_Myiter operator++(int)
		{	// postincrement
		_Myiter _Tmp = *this;
		++*this;
		return (_Tmp);
		}

	_Myiter& operator--()
		{	// predecrement
		--(*(_Mybase *)this);
		return (*this);
		}

	_Myiter operator--(int)
		{	// postdecrement
		_Myiter _Tmp = *this;
		--*this;
		return (_Tmp);
		}
	};

template<class _Mylist> inline
	typename _List_iterator<_Mylist>::_Unchecked_type
		_Unchecked(_List_iterator<_Mylist> _Iter)
	{	// convert to unchecked
	return (_Iter._Unchecked());
	}

template<class _Mylist> inline
	_List_iterator<_Mylist>&
		_Rechecked(_List_iterator<_Mylist>& _Iter,
			typename _List_iterator<_Mylist>
				::_Unchecked_type _Right)
	{	// convert to checked
	return (_Iter._Rechecked(_Right));
	}

		// TEMPLATE CLASS _List_nod
template<class _Ty,
	class _Alloc>
	class _List_nod
		: public _Container_base
	{	// base class for _List_val to hold storage
public:
	typedef typename _Alloc::template rebind<_Ty>::other _Alty;
	typedef typename _Alty::size_type size_type;

	struct _Node;
	typedef _Node *_Nodeptr;	// _Node allocator must have ordinary pointers
	typedef _Nodeptr& _Nodepref;

	struct _Node
		{	// list node
		_Nodeptr _Next;	// successor node, or first element if head
		_Nodeptr _Prev;	// predecessor node, or last element if head
		_Ty _Myval;	// the stored value, unused if head

	private:
		_Node& operator=(const _Node&);
		};

 #if _ITERATOR_DEBUG_LEVEL == 0
	_List_nod(_Alloc _Al)
		: _Alnod(_Al), _Alval(_Al)
		{	// construct allocators from _Al
		}

 #else /* _ITERATOR_DEBUG_LEVEL == 0 */
	_List_nod(_Alloc _Al)
		: _Alnod(_Al), _Alval(_Al)
		{	// construct allocators and proxy from _Al
		typename _Alloc::template rebind<_Container_proxy>::other
			_Alproxy(_Alnod);
		this->_Myproxy = _Alproxy.allocate(1);
		_Cons_val(_Alproxy, this->_Myproxy, _Container_proxy());
		this->_Myproxy->_Mycont = this;
		}

	~_List_nod()
		{	// destroy proxy
		typename _Alloc::template rebind<_Container_proxy>::other
			_Alproxy(_Alnod);
		this->_Orphan_all();
		_Dest_val(_Alproxy, this->_Myproxy);
		_Alproxy.deallocate(this->_Myproxy, 1);
		this->_Myproxy = 0;
		}
 #endif /* _ITERATOR_DEBUG_LEVEL == 0 */

	_Nodeptr _Myhead;	// pointer to head node
	size_type _Mysize;	// number of elements

	typename _Alloc::template rebind<_Node>::other
		_Alnod;	// allocator object for nodes
	_Alty _Alval;	// allocator object for element values
	};

		// TEMPLATE CLASS _List_val
template<class _Ty,
	class _Alloc>
	class _List_val
		: public _List_nod<_Ty, _Alloc>
	{	// base class for list to initialize storage
public:
	typedef _List_nod<_Ty, _Alloc> _Mybase;
	typedef typename _Mybase::_Nodeptr _Nodeptr;
	typedef typename _Mybase::_Nodepref _Nodepref;
	typedef typename _Alloc::template rebind<_Ty>::other _Alty;

	typedef typename _Alty::size_type size_type;
	typedef typename _Alty::difference_type difference_type;
	typedef typename _Alty::pointer pointer;
	typedef typename _Alty::const_pointer const_pointer;
	typedef typename _Alty::reference reference;
	typedef typename _Alty::const_reference const_reference;
	typedef typename _Alty::value_type value_type;

	_List_val(_Alloc _Al = _Alloc())
		: _Mybase(_Al)
		{	// construct base, and allocator from _Al
		this->_Mysize = 0;
		this->_Myhead = this->_Alnod.allocate(1);
		this->_Nextnode(this->_Myhead) = this->_Myhead;
		this->_Prevnode(this->_Myhead) = this->_Myhead;
		}

	~_List_val()
		{	// destroy the object
		this->_Alnod.deallocate(this->_Myhead, 1);
		}

	_Nodeptr _Buynode(_Nodeptr _Next,
		_Nodeptr _Prev, const _Ty& _Val)
		{	// allocate a node and set links and value
		_Nodeptr _Pnode = this->_Alnod.allocate(1);

		_TRY_BEGIN
		this->_Nextnode(_Pnode) = _Next;
		this->_Prevnode(_Pnode) = _Prev;
		_Cons_val(this->_Alval, _STD addressof(this->_Myval(_Pnode)), _Val);
		_CATCH_ALL
		this->_Alnod.deallocate(_Pnode, 1);
		_RERAISE;
		_CATCH_END

		return (_Pnode);
		}

	_Nodeptr _Buynode(_Nodeptr _Next,
		_Nodeptr _Prev)
		{	// allocate a node and set links and default value
		_Nodeptr _Pnode = this->_Alnod.allocate(1);

		_TRY_BEGIN
		this->_Nextnode(_Pnode) = _Next;
		this->_Prevnode(_Pnode) = _Prev;
		_Uninitialized_default_fill_n(_STD addressof(this->_Myval(_Pnode)), 1,
			(_Ty *)0, this->_Alval);
		_CATCH_ALL
		this->_Alnod.deallocate(_Pnode, 1);
		_RERAISE;
		_CATCH_END

		return (_Pnode);
		}

	template<class _Valty>
		_Nodeptr _Buynode(_Nodeptr _Next,
		_Nodeptr _Prev, _Valty&& _Val)
		{	// allocate a node and set links and value
		_Nodeptr _Pnode = this->_Alnod.allocate(1);

		_TRY_BEGIN
		this->_Nextnode(_Pnode) = _Next;
		this->_Prevnode(_Pnode) = _Prev;
		_Cons_val(this->_Alval, _STD addressof(this->_Myval(_Pnode)),