deque

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

	size_type insert_n(size_type _Where,
		size_type _Count, value_type _Val)
		{	// insert _Count * _Val at _Where
		if (_Count < 0 || !valid_bias(_Where))
			throw gcnew System::ArgumentOutOfRangeException();

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

			for (; 0 < _Count; --_Count)
				push_front(_Val);
			if (_Oldfirst != _Where)
				{	// insert not at beginning, flip new stuff into place
				reverse_n(_Oldfirst, _Where);
				reverse_n(begin_bias(), _Where);
				}
			return (_Where - 1);
			}
		else
			{	// add elements near end
			size_type _Oldlast = end_bias();
			size_type _Ans = _Where + _Count - 1;

			for (; 0 < _Count; --_Count)
				push_back(_Val);
			if (_Oldlast != _Where)
				{	// insert not at end, flip new stuff into place
				reverse_n(_Where, _Oldlast);
				reverse_n(_Where, end_bias());
				}
			return (_Ans);
			}
		}

	iterator erase(iterator _Where)
		{	// erase element at _Where
		size_type _Bias = get_bias(_Where);

		return (make_iterator(erase_n(_Bias, _Bias + 1)));
		}

	iterator erase(iterator _First, iterator _Last)
		{	// erase [_First, _Last)
		return (make_iterator(
			erase_n(get_bias(_First), get_bias(_Last))));
		}

	size_type erase_n(size_type _First, size_type _Last)
		{	// erase [_First, _Last)
		if (!valid_bias(_First)
			|| !valid_bias(_Last)
			|| _Last < _First)
			throw gcnew System::InvalidOperationException();

		if (_First == _Last)
			return (_First);
		else if (_First - begin_bias() < end_bias() - _Last)
			{	// erase finite sequence closer to front
			size_type _Count = _First - begin_bias();
			size_type _Stride = _Last - _First;

			for (_First = _Last - 1; 0 < _Count; --_Count, --_First)
				at_bias(_First) = at_bias(_First - _Stride);	// copy up
			for (; 0 < _Stride; --_Stride)
				pop_front();
			return (_Last);
			}
		else
			{	// erase finite sequence closer to back
			size_type _Count = end_bias() - _Last;
			size_type _Stride = _Last - _First;

			for (; 0 < _Count; --_Count, ++_Last)
				at_bias(_Last - _Stride) = at_bias(_Last);	// copy down
			for (; 0 < _Stride; --_Stride)
				pop_back();
			return (_First);
			}
		}

	void reverse_n(size_type _First, size_type _Last)
		{	// reverse a subrange
		if (!valid_bias(_First)
			|| !valid_bias(_Last)
			|| _Last < _First)
			throw gcnew System::InvalidOperationException();

		for (; _First != _Last && _First != --_Last; ++_First)
			{	// swap distinct _First and _Last
			value_type _Temp = at_bias(_First);

			at_bias(_First) = at_bias(_Last);
			at_bias(_Last) = _Temp;
			}
		}

	void clear()
		{	// erase all
		for (; !empty(); )
			pop_back();
		}

	void swap(_Mytype_t% _Right)
		{	// exchange contents with _Right
		if ((Object^)this != %_Right)
			{	// worth doing, swap
			_Mymap_t^ _Tmap = _Mymap;
			size_type _Tbias = _Mybias;
			size_type _Tsize = _Mysize;

			_Mymap = _Right._Mymap;
			_Right._Mymap = _Tmap;

			_Mybias = _Right._Mybias;
			_Right._Mybias = _Tbias;

			_Mysize = _Right._Mysize;
			_Right._Mysize = _Tsize;

			++_Mygen;
			++_Right._Mygen;
			}
		}

	// operators
	deque_impl% operator=(deque_impl% _Right)
		{	// assign
		if ((Object^)this != %_Right)
			{	// worth assigning, do it
			clear();
			for (size_type _Idx = 0; _Idx < _Right.size(); ++_Idx)
				push_back(_Right.at(_Idx));
			}
		return (*this);
		}

_STLCLR_FIELD_ACCESS:
	void _Buy(size_type _Capacity)
		{	// allocate map with _Capacity elements
		size_type _Valsize = _Get_sizeof<value_type>::value();

		_Blockshift = _Valsize <= 1 ? 6
			: _Valsize <= 2 ? 5
			: _Valsize <= 4 ? 4
			: _Valsize <= 8 ? 3
			: _Valsize <= 16 ? 2
			: _Valsize <= 32 ? 1
			: 0;	// elements per block is 1 << _Blockshift

		_Mymap = nullptr;
		_Mybias = 0;
		_Mysize = 0;
		_Mygen = 0;
		if (_Capacity < 0)
			throw gcnew System::ArgumentOutOfRangeException();

		size_type _Mapsize = 1 << _Mapshift;
		size_type _Dequesize = _Mapsize << _Blockshift;

		for (; _Dequesize < _Capacity && _Maxsize - _Dequesize < _Dequesize;
			_Mapsize <<= 1, _Dequesize <<= 1)
			;	// double map size until big enough, but not too big
		_Mymap = gcnew _Mymap_t(_Mapsize);
		}

	void _Growmap()
		{	// grow map by doubling its size
		if (_Maxsize - (_Mymap->Length << _Blockshift)
			< (_Mymap->Length << _Blockshift))	// can't double map size
			throw gcnew System::ArgumentOutOfRangeException();

		_Mymap_t^ _Newmap = gcnew _Mymap_t(2 * _Mymap->Length);
		size_type _Count = _Mymap->Length;
		size_type _Block = _Mybias >> _Blockshift;

		for (; 0 < _Count; --_Count, ++_Block)
			_Newmap[_Block % _Newmap->Length] =
				_Mymap[_Block % _Mymap->Length];
		_Mymap = _Newmap;
		}

	// data members
	_Mymap_t^ _Mymap;	// array of array of _Value_t
	int _Blockshift;	// 2 ^ _Blockshift elements per block
	int _Mybias;		// offset of current element zero
	size_type _Mysize;	// number of active elements
	unsigned long _Mygen;	// current change generation

	// interfaces
public:
	virtual System::Object^ Clone()
		{	// clone the deque
		return (gcnew deque_impl(*this));
		}

private:
	property size_type Count
		{	// element count
		virtual size_type get() sealed
			= System::Collections::ICollection::Count::get
			{	// get element count
			return (size());
			}
		};

	property bool IsSynchronized
		{	// synchronized status
		virtual bool get() sealed
			= System::Collections::ICollection::IsSynchronized::get
			{	// test if synchronized
			return (false);
			}
		};

	property System::Object^ SyncRoot
		{	// synchronizer
		virtual System::Object^ get() sealed
			= System::Collections::ICollection::SyncRoot::get
			{	// get synchronizer
			return (this);
			}
		};

	virtual void CopyTo(System::Array^ _Dest_arg, int _First) sealed
		= System::Collections::ICollection::CopyTo
		{	// copy to _Dest_arg, beginning at _First
		cli::array<System::Object^>^ _Dest =
			(cli::array<System::Object ^>^)_Dest_arg;
		for (int _Idx = size(); 0 <= --_Idx; )
			{	// copy back to front
			_Dest[_First + _Idx] = _Mymake_t::make_value(at(_Idx));
			}
		}

	virtual System::Collections::IEnumerator^ GetEnumerator() sealed
		= System::Collections::IEnumerable::GetEnumerator
		{	// get enumerator for the container
		return (gcnew _STLCLR DequeEnumerator<_Value_t>(this, begin_bias()));
		}

	virtual unsigned long get_generation_virtual() sealed
		= _Mycont_it::get_generation
		{	// get underlying container generation
		return (get_generation());
		}

	virtual bool valid_bias_virtual(size_type _Bias) sealed
		= _Mycont_it::valid_bias
		{	// test if _Bias is currently a valid bias
		return (valid_bias(_Bias));
		}

	virtual reference at_virtual(size_type _Pos) sealed
		= _Mycont_it::at
		{	// subscript mutable sequence with checking
		return (at(_Pos));
		}

	virtual reference at_bias_virtual(size_type _Bias) sealed
		= _Mycont_it::at_bias
		{	// subscript mutable sequence with checking, biased
		return (at_bias(_Bias));
		}

	virtual int begin_bias_virtual() sealed
		= _Mycont_it::begin_bias
		{	// get bias of beginning of current sequence
		return (begin_bias());
		}

	virtual int end_bias_virtual() sealed
		= _Mycont_it::end_bias
		{	// get bias of end of current sequence
		return (end_bias());
		}

	virtual reference front_virtual() sealed
		= _Mycont_it::front
		{	// get first element of mutable sequence
		return (front());
		}

	virtual reference back_virtual() sealed
		= _Mycont_it::back
		{	// get last element of mutable sequence
		return (back());
		}

	// iterator generators
	virtual generic_iterator begin_virtual() sealed
		= _Mycont_it::begin
		{	// return iterator for beginning of mutable sequence
		return (begin());
		}
	virtual generic_iterator end_virtual() sealed
		= _Mycont_it::end
		{	// return iterator for end of mutable sequence
		return (end());
		}

	virtual generic_reverse_iterator rbegin_virtual() sealed
		= _Mycont_it::rbegin
		{	// return reverse iterator for beginning of mutable sequence
		return (generic_reverse_iterator(end()));
		}

	virtual generic_reverse_iterator rend_virtual() sealed
		= _Mycont_it::rend
		{	// return reverse iterator for end of mutable sequence
		return (generic_reverse_iterator(begin()));
		}

	// size controllers
//	virtual void reserve_virtual(size_type _Capacity);
//	virtual size_type capacity_virtual();

	virtual void resize_virtual(size_type _Newsize) sealed
		= _Mycont_it::resize
		{	// determine new length, padding with value_type elements
		resize(_Newsize);
		}

	virtual void resize_virtual(size_type _Newsize, value_type _Val) sealed
		= _Mycont_it::resize
		{	// determine new length, padding with _Val elements
		resize(_Newsize, _Val);
		}

	virtual size_type size_virtual() sealed
		= _Mycont_it::size
		{	// return length of sequence
		return (size());
		}

	virtual bool empty_virtual() sealed
		= _Mycont_it::empty
		{	// test if sequence is empty
		return (empty());
		}

	// mutators
	virtual void push_front_virtual(value_type _Val) sealed
		= _Mycont_it::push_front
		{	// insert element at end
		push_front(_Val);
		}

	virtual void pop_front_virtual() sealed
		= _Mycont_it::pop_front
		{	// erase element at end
		pop_front();
		}

	virtual void push_back_virtual(value_type _Val) sealed
		= _Mycont_it::push_back
		{	// insert element at end
		push_back(_Val);
		}

	virtual void pop_back_virtual() sealed
		= _Mycont_it::pop_back
		{	// erase element at end
		pop_back();
		}

	virtual void assign_virtual(size_type _Count, value_type _Val) sealed
		= _Mycont_it::assign
		{	// assign _Count * _Val
		assign(_Count, _Val);
		}

	virtual void assign_virtual(
		_STLCLR Generic::IInputIterator<_Value_t>^ _First,
		_STLCLR Generic::IInputIterator<_Value_t>^ _Last) sealed
		= _Mycont_it::assign
		{	// initialize with [_First, _Last), input iterators
		assign(_First, _Last);
		}

	virtual void assign_virtual(
		System::Collections::IEnumerable^ _Right) sealed
		= _Mycont_it::assign
		{	// initialize with enumeration
		assign(_Right);
		}

	virtual generic_iterator insert_virtual(generic_iterator _Where,
		value_type _Val) sealed
		= _Mycont_it::insert
		{	// insert _Val at _Where
		return (insert(iterator(_Where), _Val));
		}

	virtual void insert_virtual(generic_iterator _Where,
		size_type _Count, value_type _Val) sealed
			= _Mycont_it::insert
		{	// insert _Count * _Val at _Where
		return (insert(iterator(_Where), _Count, _Val));
		}

	virtual void insert_virtual(generic_iterator _Where_iter,
		_STLCLR Generic::IInputIterator<_Value_t>^ _First,
		_STLCLR Generic::IInputIterator<_Value_t>^ _Last) sealed
			= _Mycont_it::insert
		{	// insert [_First, _Last) at _Where, input iterators
		insert(iterator(_Where_iter), _First, _Last);
		}

	virtual void insert_virtual(generic_iterator _Where_iter,
		System::Collections::IEnumerable^ _Right) sealed
			= _Mycont_it::insert
		{	// insert enumeration at _Where, possibly from this container
		insert(iterator(_Where_iter), _Right);
		}

	virtual generic_iterator erase_virtual(generic_iterator _Where) sealed
		= _Mycont_it::erase
		{	// erase element at _Where
		return (erase(iterator(_Where)));
		}

	virtual generic_iterator erase_virtual(generic_iterator _First,
		generic_iterator _Last) sealed
		= _Mycont_it::erase
		{	// erase [_First, _Last)
		return (erase(iterator(_First), iterator(_Last)));
		}

	virtual void clear_virtual() sealed
		= _Mycont_it::clear
		{	// erase all
		clear();
		}

	virtual void swap_virtual(_Mycont_it^ _Right) sealed
		= _Mycont_it::swap
		{	// exchange contents with _Right
		swap(*(_Mytype_t^)_Right);
		}
	};

//
// TEMPLATE REF CLASS deque_base
//
template<typename _Value_t,
	bool _Is_ref>
	ref class deque_base
	:	public deque_impl<_Value_t, _Is_ref>,
			System::Collections::Generic::ICollection<_Value_t>,
			System::Collections::Generic::IEnumerable<_Value_t>,
			System::Collections::Generic::IList<_Value_t>
	{	// double-ended queue of value/handle elements
public:
	// types
	typedef deque_base<_Value_t, _Is_ref> _Mytype_t;
	typedef deque_impl<_Value_t, _Is_ref> _Mybase_t;
//	typedef _STLCLR IDeque<_Value_t> _Mycont_it;
	typedef _Cont_make_value<_Value_t, _Is_ref> _Mymake_t;

//	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;

	// basics
	deque_base()
		:	_Mybase_t()
		{	// construct default
		}

	deque_base(deque_base% _Right)
		:	_Mybase_t(_Right)
		{	// construct by copying a deque
		}

	deque_base% operator=(deque_base% _Right)
		{	// assign
		_Mybase_t::operator=(_Right);
		return (*this);
		}

	operator _Mycont_it^()
		{	// convert to interface
		return (this);
		}

	// constructors
	explicit deque_base(size_type _Count)
		:	_Mybase_t(_Count)
		{	// construct from _Count * value_type()
		}

	deque_base(size_type _Count, value_type _Val)
		:	_Mybase_t(_Count, _Val)
		{	// construct from _Count * _Val
		}

	template<typename _InIt_t>
		deque_base(_InIt_t _First, _InIt_t _Last)
		:	_Mybase_t(_First, _Last)
		{	// construct from [_First, _Last)
		}

	deque_base(_Myenum_it^ _Right)
		:	_Mybase_t(_Right)
		{	// initialize with enumeration
		}

	// mutators
	template<typename _InIt_t>
		void assign(_InIt_t _First, _InIt_t _Last)
		{	// assign [_First, _Last)
		_Assign(_First, _Last, _Iter_category(_First));
		}

	template<typename _InIt_t>
		void _Assign(_InIt_t _Count_arg, _InIt_t _Val,
			_Int_iterator_tag%)
		{	// assign _Count * _Val
		value_type _Count = (value_type)_Count_arg;

		if (_Count < 0)
			throw gcnew System::ArgumentOutOfRangeException();
		clear();
		for (; 0 < _Count; --_Count)
			push_back((value_type)_Val);
		}

	template<typename _InIt_t>
		void _Assign(_InIt_t _First, _InIt_t _Last,
			input_iterator_tag%)
		{	// initialize with [_First, _Last), input iterators
		if (_Iter_container(_First) != this)
			clear();

		size_type _Oldsize = size();

		for (; _First != _Last; ++_First)
			push_back((value_type)*_First);	// append new stuff
		for (; 0 < _Oldsize; --_Oldsize)
			pop_front();	// erase any leftover old stuff
		}

	template<typename _InIt_t>
		void _Assign(_InIt_t _First, _InIt_t _Last,
			random_access_iterator_tag%)
		{	// initialize with [_First, _Last), input iterators
		if (_Last < _First)
			throw gcnew System::ArgumentOutOfRangeException();