deque

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

// deque stl/clr header
#ifndef _CLI_DEQUE_
 #define _CLI_DEQUE_
#include <cliext/iterator>

namespace cliext {
	namespace impl {
//
// TEMPLATE CLASS _Get_sizeof
//
template<typename _Value_t>
	value struct _Get_sizeof
	{	// get size of a type
	static int value()
		{	// return size
		try
			{	// try to determine size of type
			return (System::Runtime::InteropServices::Marshal::
				SizeOf(_Value_t::typeid));
			}
		catch (System::Object^)
			{	// failed, assume int
			return (4);
			}
		}
	};

template<typename _Value_t>
	value struct _Get_sizeof<_Value_t^>
	{	// get size of a handle type
	static int value()
		{	// return size
		return (System::Runtime::InteropServices::Marshal::
			SizeOf(System::IntPtr::typeid));
		}
	};

//
// TEMPLATE CLASS deque_impl
//
template<typename _Value_t,
	bool _Is_ref>
	ref class deque_impl
	:	public _STLCLR IDeque<_Value_t>
	{	// double-ended queue of elements
public:
	// types
	typedef deque_impl<_Value_t, _Is_ref> _Mytype_t;
	typedef _STLCLR IDeque<_Value_t> _Mycont_it;
	typedef System::Collections::Generic::IEnumerable<_Value_t> _Myenum_it;
	typedef cli::array<_Value_t> _Myarray_t;
	typedef cli::array<_Myarray_t^> _Mymap_t;
	typedef _Cont_make_value<_Value_t, _Is_ref> _Mymake_t;

	typedef RandomAccessIterator<_Mytype_t>
		iterator;
	typedef ConstRandomAccessIterator<_Mytype_t>
		const_iterator;
	typedef ReverseRandomAccessIterator<_Mytype_t>
		reverse_iterator;
	typedef ReverseRandomAccessIterator<_Mytype_t>
		const_reverse_iterator;

	typedef int size_type;
	typedef int difference_type;
	typedef _Value_t value_type;
	typedef value_type% reference;
	typedef value_type% const_reference;

	typedef _Mycont_it generic_container;
	typedef value_type generic_value;
	typedef _STLCLR Generic::ContainerRandomAccessIterator<_Value_t>
		generic_iterator;
	typedef _STLCLR Generic::ReverseRandomAccessIterator<_Value_t>
		generic_reverse_iterator;

	// constants
	static const int _Maxsize = MAX_CONTAINER_SIZE;
	static const int _Mapshift = 5;	// minimum map size is 1 << _Mapshift

	// constructors
	deque_impl()
		{	// construct empty deque
		_Buy(0);
		}

	deque_impl(_Mytype_t% _Right)
		{	// construct by copying _Right
		size_type _Count = _Right.size();
		size_type _Idx = 0;

		for (_Buy(_Count); _Idx < _Count; ++_Idx)
			push_back(_Right.at(_Idx));
		}

	explicit deque_impl(size_type _Count)
		{	// construct from _Count * value_type()
		for (_Buy(_Count); 0 < _Count; --_Count)
			push_back(value_type());
		}

	deque_impl(size_type _Count, value_type _Val)
		{	// construct from _Count * _Val
		for (_Buy(_Count); 0 < _Count; --_Count)
			push_back(_Val);
		}

	template<typename _InIt_t>
		deque_impl(_InIt_t _First, _InIt_t _Last)
		{	// construct from [_First, _Last)
		_Construct(_First, _Last, _Iter_category(_First));
		}

	template<typename _InIt_t>
		void _Construct(_InIt_t _Count, _InIt_t _Val,
			_Int_iterator_tag)
		{	// initialize with _Count * _Val
		if (_Count < 0)
			throw gcnew System::ArgumentOutOfRangeException();
		for (_Buy((size_type)_Count); 0 < _Count; --_Count)
			push_back((value_type)_Val);
		}

	template<typename _InIt_t>
		void _Construct(_InIt_t _First, _InIt_t _Last,
			input_iterator_tag)
		{	// initialize with [_First, _Last), input iterators
		for (_Buy(0); _First != _Last; ++_First)
			push_back((value_type)*_First);
		}

	template<typename _InIt_t>
		void _Construct(_InIt_t _First, _InIt_t _Last,
			forward_iterator_tag)
		{	// initialize with [_First, _Last), forward iterators
		size_type _Size = cliext::distance(_First, _Last);

		if (_Size < 0)
			throw gcnew System::ArgumentOutOfRangeException();
		for (_Buy(_Size); 0 < _Size; --_Size, ++_First)
			push_back((value_type)*_First);
		}

	deque_impl(System::Collections::Generic::IEnumerable<_Value_t>^ _Right)
		{	// initialize with enumeration
		_Buy(0);
		for each (value_type _Val in _Right)
			push_back(_Val);
		}

	// destructor
	~deque_impl()
		{	// destroy the object
		clear();
		_Mymap = nullptr;
		_Mybias = 0;
		_Mysize = 0;
		++_Mygen;
		}

	// accessors
	unsigned long get_generation()
		{	// get underlying container generation
		return (_Mygen);
		}

	size_type get_bias(iterator _Where)
		{	// get offset from valid iterator
		if (_Where.container() != this)
			throw gcnew System::ArgumentException();
		return (_Where.get_bias());
		}

	bool valid_bias(size_type _Bias)
		{	// test if _Bias is currently a valid bias
		return ((unsigned int)_Bias - begin_bias()
			<= (unsigned int)size());	// unsigned to handle bias wraparound
		}

	reference at(size_type _Pos)
		{	// subscript mutable sequence with checking
		return (at_bias(begin_bias() + _Pos));
		}

	reference at_bias(size_type _Bias)
		{	// subscript mutable sequence with checking, biased
		if ((unsigned int)size() <= (unsigned int)_Bias - begin_bias())
			throw gcnew System::ArgumentOutOfRangeException();

		int _Blocksize = 1 << _Blockshift;

		_Bias &= (_Mymap->Length << _Blockshift) - 1;
		return (_Mymap[_Bias >> _Blockshift][_Bias & (_Blocksize - 1)]);
		}

	int begin_bias()
		{	// get bias of beginning of current sequence
		return (_Mybias);
		}

	int end_bias()
		{	// get bias of end of current sequence
		return (begin_bias() + size());
		}

	property value_type default[size_type]
		{	// get or set subscripted element
		virtual value_type get(size_type _Pos)
			{	// get _Pos element
			return (at(_Pos));
			}

		virtual void set(size_type _Pos, value_type _Val)
			{	// set _Pos element
			at(_Pos) = _Val;
			}
		};

	property value_type front_item
		{	// get or set first element
		virtual value_type get()
			{	// get first element
			return (front());
			}

		virtual void set(value_type _Val)
			{	// set first element
			front() = _Val;
			}
		};

	property value_type back_item
		{	// get or set last element
		virtual value_type get()
			{	// get last element
			return (back());
			}

		virtual void set(value_type _Val)
			{	// set last element
			back() = _Val;
			}
		};

	reference front()
		{	// get first element of mutable sequence
		if (empty())
			throw gcnew System::NullReferenceException();
		return (at(0));
		}

	reference back()
		{	// get last element of mutable sequence
		if (empty())
			throw gcnew System::NullReferenceException();
		return (at(size() - 1));
		}

	// converters
	_Myarray_t^ to_array()
		{	// convert to array
		_Myarray_t^ _Ans = gcnew _Myarray_t(size());

		for (int _Idx = size(); 0 <= --_Idx; )
			_Ans[_Idx] = _Mymake_t::make_value(at(_Idx));
		return (_Ans);
		}

	// iterator generators
	iterator make_iterator(size_type _Bias)
		{	// return iterator for offset
		return (iterator(this, _Bias));
		}

	iterator begin()
		{	// return iterator for beginning of mutable sequence
		return (make_iterator(begin_bias()));
		}

	iterator end()
		{	// return iterator for end of mutable sequence
		return (make_iterator(end_bias()));
		}

	reverse_iterator rbegin()
		{	// return reverse iterator for beginning of mutable sequence
		return (reverse_iterator(end()));
		}

	reverse_iterator rend()
		{	// return reverse iterator for end of mutable sequence
		return (reverse_iterator(begin()));
		}

	// size controllers
//	void reserve(size_type _Capacity);
//	size_type capacity();

	virtual void resize(size_type _Newsize)
		{	// determine new length, padding with value_type elements
		resize(_Newsize, value_type());
		}

	void resize(size_type _Newsize, value_type _Val)
		{	// determine new length, padding with _Val elements
		if (_Newsize < 0)
			throw gcnew System::ArgumentOutOfRangeException();

		difference_type _Count = _Newsize - size();

		for (; 0 < _Count; --_Count)
			push_back(_Val);
		for (; _Count < 0; ++_Count)
			pop_back();
		}

	size_type size()
		{	// return length of sequence
		return (_Mysize);
		}

	bool empty()
		{	// test if sequence is empty
		return (size() == 0);
		}

	// mutators
	void push_front(value_type _Val)
		{	// insert element at beginning
		int _Blocksize = 1 << _Blockshift;

		if ((_Mybias & (_Blocksize - 1)) == 0
			&& _Mymap->Length <= (_Mysize + _Blocksize) / _Blocksize)
			_Growmap();	// starting new block and no spare block
		--_Mybias;

		size_type _Newoff = _Mybias
			& ((_Mymap->Length << _Blockshift) - 1);
		size_type _Block = _Newoff >> _Blockshift;

		if (_Mymap[_Block] == nullptr)
			_Mymap[_Block] = gcnew _Myarray_t(_Blocksize);
		_Mymap[_Block][_Newoff & (_Blocksize - 1)] =
			_Mymake_t::make_value(_Val);
		++_Mysize;
		++_Mygen;
		}

	void pop_front()
		{	// erase element at beginning
		if (empty())
			throw gcnew System::InvalidOperationException();

		_Mymake_t::unmake_value(front());
		++_Mybias;
		--_Mysize;
		++_Mygen;
		}

	void push_back(value_type _Val)
		{	// insert element at end
		int _Blocksize = 1 << _Blockshift;

		if (((_Mybias + _Mysize) & (_Blocksize - 1)) == 0
			&& _Mymap->Length <= (_Mysize + _Blocksize) / _Blocksize)
			_Growmap();	// starting new block and no spare block

		size_type _Newoff = (_Mybias + _Mysize)
			& ((_Mymap->Length << _Blockshift) - 1);
		size_type _Block = _Newoff >> _Blockshift;

		if (_Mymap[_Block] == nullptr)
			_Mymap[_Block] = gcnew _Myarray_t(_Blocksize);
		_Mymap[_Block][_Newoff & (_Blocksize - 1)] =
			_Mymake_t::make_value(_Val);
		++_Mysize;
		++_Mygen;
		}

	void pop_back()
		{	// erase element at end
		if (empty())
			throw gcnew System::InvalidOperationException();

		_Mymake_t::unmake_value(back());
		--_Mysize;
		++_Mygen;
		}

	void assign(size_type _Count, value_type _Val)
		{	// assign _Count * _Val
		if (_Count < 0)
			throw gcnew System::ArgumentOutOfRangeException();
		clear();
		for (; 0 < _Count; --_Count)
			push_back(_Val);
		}

	void assign(_STLCLR Generic::IInputIterator<_Value_t>^ _First,
		_STLCLR Generic::IInputIterator<_Value_t>^ _Last)
		{	// initialize with [_First, _Last), input iterators
		if (_Iter_container(_First) != this)
			clear();

		size_type _Oldsize = size();

		for (; !_First->equal_to(_Last); _First->next())
			push_back((value_type)_First->get_cref());	// append new stuff
		for (; 0 < _Oldsize; --_Oldsize)
			pop_front();	// erase any leftover old stuff
		}

	void assign(_Myenum_it^ _Right)
		{	// initialize with enumeration
		size_type _Oldsize = size();

		for each (value_type _Val in _Right)
			push_back(_Val);	// append new stuff
		for (; 0 < _Oldsize; --_Oldsize)
			pop_front();	// erase any leftover old stuff
		}

	void assign(System::Collections::IEnumerable^ _Right)
		{	// initialize with enumeration
		size_type _Oldsize = size();

		for each (value_type _Val in _Right)
			push_back(_Val);	// append new stuff
		for (; 0 < _Oldsize; --_Oldsize)
			pop_front();	// erase any leftover old stuff
		}

	iterator insert(iterator _Where, value_type _Val)
		{	// insert _Val at _Where
		return (make_iterator(
			insert_n(get_bias(_Where), 1, _Val)));
		}

	void insert(iterator _Where,
		size_type _Count, value_type _Val)
		{	// insert _Count * _Val at _Where
		insert_n(get_bias(_Where), _Count, _Val);
		}

	void insert(iterator _Where_iter,
		_STLCLR Generic::IInputIterator<_Value_t>^ _First,
		_STLCLR Generic::IInputIterator<_Value_t>^ _Last)
		{	// insert [_First, _Last) at _Where, input iterators
		size_type _Where = get_bias(_Where_iter);

		if (!valid_bias(_Where))
			throw gcnew System::InvalidOperationException();

		if (_First->equal_to(_Last))
			;
		else if (_Where - begin_bias() < end_bias() - _Where)
			{	// add elements near beginning
			size_type _Oldfirst = begin_bias();

			for (; !_First->equal_to(_Last); _First->next())
				push_front((value_type)_First->get_cref());	// prepend flipped

			if (_Oldfirst != _Where)
				{	// insert not at beginning, flip new stuff into place
				reverse_n(_Oldfirst, _Where);
				reverse_n(begin_bias(), _Where);
				}
			else
				reverse_n(begin_bias(), _Oldfirst);	// flip new stuff in place
			}
		else
			{	// add elements near end
			size_type _Oldlast = end_bias();

			for (; !_First->equal_to(_Last); _First->next())
				push_back((value_type)_First->get_cref());	// append
			if (_Oldlast != _Where)
				{	// insert not at end, flip new stuff into place
				reverse_n(_Where, _Oldlast);
				reverse_n(_Oldlast, end_bias());
				reverse_n(_Where, end_bias());
				}
			}
		}

	void insert(iterator _Where_iter,
		System::Collections::Generic::IEnumerable<_Value_t>^ _Right)
		{	// insert enumeration at _Where, possibly from this container
		size_type _Where = get_bias(_Where_iter);

		if (!valid_bias(_Where))
			throw gcnew System::InvalidOperationException();

		if (_Where - begin_bias() < end_bias() - _Where)
			{	// add elements near beginning
			size_type _Oldfirst = begin_bias();

			for each (value_type _Val in _Right)
				push_front(_Val);	// flipped
			if (_Oldfirst != _Where)
				{	// insert not at beginning, flip new stuff into place
				reverse_n(_Oldfirst, _Where);
				reverse_n(begin_bias(), _Where);
				}
			else
				reverse_n(begin_bias(), _Oldfirst);	// flip new stuff in place
			}
		else
			{	// add elements near end
			size_type _Oldlast = end_bias();

			for each (value_type _Val in _Right)
				push_back(_Val);	// not flipped
			if (_Oldlast != _Where)
				{	// insert not at end, flip new stuff into place
				reverse_n(_Where, _Oldlast);
				reverse_n(_Oldlast, end_bias());
				reverse_n(_Where, end_bias());
				}
			}
		}

	void insert(iterator _Where_iter,
		System::Collections::IEnumerable^ _Right)
		{	// insert enumeration at _Where, possibly from this container
		size_type _Where = get_bias(_Where_iter);

		if (!valid_bias(_Where))
			throw gcnew System::InvalidOperationException();

		if (_Where - begin_bias() < end_bias() - _Where)
			{	// add elements near beginning
			size_type _Oldfirst = begin_bias();

			for each (value_type _Val in _Right)
				push_front(_Val);	// flipped
			if (_Oldfirst != _Where)
				{	// insert not at beginning, flip new stuff into place
				reverse_n(_Oldfirst, _Where);
				reverse_n(begin_bias(), _Where);
				}
			else
				reverse_n(begin_bias(), _Oldfirst);	// flip new stuff in place
			}
		else
			{	// add elements near end
			size_type _Oldlast = end_bias();

			for each (value_type _Val in _Right)
				push_back(_Val);	// not flipped
			if (_Oldlast != _Where)
				{	// insert not at end, flip new stuff into place
				reverse_n(_Where, _Oldlast);
				reverse_n(_Oldlast, end_bias());
				reverse_n(_Where, end_bias());
				}
			}
		}