list

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

		return (--_Where);
		}

	void insert(iterator _Where,
		size_type _Count, value_type _Val)
		{	// insert _Count * _Val at _Where
		insert_node(get_node(_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
		node_type^ _Where = get_node(_Where_iter);

		if (_First->container() == this)
			_Insert_safe(_Where, _First, _Last);
		else
			for (; !_First->equal_to(_Last); _First->next())
				insert_node(_Where, 1, (value_type)_First->get_cref());
		}

	void insert(iterator _Where_iter,
		_Myenum_it^ _Right)
		{	// insert enumeration at _Where, possibly from this container
		node_type^ _Where = get_node(_Where_iter);
		node_type^ _Oldfirst = front_node();

		try
			{	// try to build insert list
			for each (value_type _Val in _Right)
				insert_node(_Oldfirst,	// insert new at beginning
					1, _Val);
			}
		catch (System::Object^)
			{	// failed, discard new stuff
			for (; front_node() != _Oldfirst; )
				pop_front();
			throw;
			}
		splice_node(_Where, this,
			front_node(), _Oldfirst);	// splice new into place
		}

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

		try
			{	// try to build insert list
			for each (value_type _Val in _Right)
				insert_node(_Oldfirst,	// insert new at beginning
					1, _Val);
			}
		catch (System::Object^)
			{	// failed, discard new stuff
			for (; front_node() != _Oldfirst; )
				pop_front();
			throw;
			}
		splice_node(_Where, this,
			front_node(), _Oldfirst);	// splice new into place
		}

	void _Insert_safe(_Mynode_t^ _Where,
		_STLCLR Generic::IInputIterator<_Value_t>^ _First,
		_STLCLR Generic::IInputIterator<_Value_t>^ _Last)
		{	// insert [_First, _Last] at _Where, possibly from this container
		node_type^ _Oldfirst = front_node();

		try
			{	// try to build insert list
			for (; !_First->equal_to(_Last); _First->next())
				insert_node(_Oldfirst,
					1, (value_type)_First->get_cref());	// insert at beginning
			}
		catch (System::Object^)
			{	// failed, discard new stuff
			for (; front_node() != _Oldfirst; )
				pop_front();
			throw;
			}
		splice_node(_Where, this,
			front_node(), _Oldfirst);	// splice new into place
		}

	template<typename _InIt_t>
		void _Insert_safe(_Mynode_t^ _Where, _InIt_t _First, _InIt_t _Last)
		{	// insert [_First, _Last] at _Where, possibly from this container
		node_type^ _Oldfirst = front_node();

		try
			{	// try to build insert list
			for (; _First != _Last; ++_First)
				insert_node(_Oldfirst,
					1, (value_type)*_First);	// insert new at beginning
			}
		catch (System::Object^)
			{	// failed, discard new stuff
			for (; front_node() != _Oldfirst; )
				pop_front();
			throw;
			}
		splice_node(_Where, this,
			front_node(), _Oldfirst);	// splice new into place
		}

	void insert_node(node_type^ _Where,
		size_type _Count, value_type _Val)
		{	// insert _Count * _Val at _Where
		size_type _Added = 0;

		if ((System::Object^)_Where->container() != this)
			throw gcnew System::ArgumentException();

		if (_Count < 0 || _Maxsize - size() < _Count)
			throw gcnew System::ArgumentOutOfRangeException();
		try
			{	// try to insert _Count copies
			for (; _Added < _Count; ++_Added)
				{	// insert a node at _Where
				node_type^ _Node = _Buynode(_Where, _Where->_Prev, _Val);

				_Where->_Prev = _Node;
				_Node->_Prev->_Next = _Node;
				++_Mysize;
				}
			}
		catch (System::Object^)
			{	// failed, discard new stuff
			for (; 0 < _Added; --_Added)
				erase_node(_Where->prev_node());
			}

		if (0 < _Added)
			++_Mygen;
		}

	node_type^ insert_node(node_type^ _Where,
		node_type^ _First, node_type^ _Last)
		{	// insert copy of list subrange
		size_type _Added = 0;

		if (_Where->container() != this)
			throw gcnew System::ArgumentException();

		try
			{	// try to insert _Count copies
			for (; _First != _Last; _First = _First->next_node(), ++_Added)
				insert_node(_Where, 1, _First->_Myval);
			}
		catch (System::Object^)
			{	// failed, discard new stuff
			for (; 0 < _Added; --_Added)
				erase_node(_Where->prev_node());
			}

		if (0 < _Added)
			++_Mygen;
		return (_Where);
		}

	iterator erase(iterator _Where)
		{	// erase element at _Where
		node_type^ _Node = get_node(_Where);

		return (make_iterator(erase_node(_Node)));
		}

	iterator erase(iterator _First, iterator _Last)
		{	// erase [_First, _Last)
		return (erase_node(get_node(_First), get_node(_Last)));
		}

	node_type^ erase_node(node_type^ _Where)
		{	// erase node at _Where
		if (_Where->container() != this || _Where->is_head())
			throw gcnew System::InvalidOperationException();

		_Mymake_t::unmake_value(_Where->_Myval);
		_Where->_Head = nullptr;	// orphan corresponding iterators
		_Where->_Prev->_Next = _Where->_Next;
		_Where = _Where->_Next;
		_Where->_Prev = _Where->_Prev->_Prev;
		--_Mysize;
		++_Mygen;
		return (_Where);
		}

	iterator erase_node(node_type^ _First, node_type^ _Last)
		{	// erase nodes in [_First, _Last)
		if (_First == nullptr || _First->container() != this)
			throw gcnew System::ArgumentException();

		for (; _First != _Last; )
			_First = erase_node(_First);
		return (make_iterator(_First));
		}

	void clear()
		{	// erase all
		for (; front_node() != head_node(); )
			erase_node(front_node());
		}

	void swap(_Mytype_t% _Right)
		{	// exchange contents with _Right
		if ((Object^)this != %_Right)
			{	// worth doing, swap
			node_type^ _Oldfirst = front_node();

			splice_node(_Oldfirst, %_Right,
				_Right.front_node(), _Right.head_node());
			_Right.splice_node(_Right.head_node(), this,
				_Oldfirst, head_node());

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

	// special functions
	void splice(iterator _Where, _Mytype_t% _Right)
		{	// splice all of _Right at _Where
		splice_node(get_node(_Where), %_Right,
			_Right.front_node(), _Right.head_node());
		}

	void splice(iterator _Where, _Mytype_t% _Right, iterator _First)
		{	// splice _Right [_First, _First + 1) at _Where
		node_type^ _Node = _Right.get_node(_First);

		splice_node(get_node(_Where), %_Right,
			_Node, _Node->next_node());
		}

	void splice(iterator _Where, _Mytype_t% _Right,
		iterator _First, iterator _Last)
		{	// splice _Right [_First, _First + 1) at _Where
		splice_node(get_node(_Where), %_Right,
			_Right.get_node(_First), _Right.get_node(_Last));
		}

	void splice_node(node_type^ _Where, _Mytype_t^ _Right,
		node_type^ _First, node_type^ _Last)
		{	// splice _Right [_First, _Last) before _Where
		if (_Where->container() != this
			|| _First->container() != _Right)
			throw gcnew System::ArgumentException();

		if (_First == _Last)
			;	// nothing to do
		else if ((Object^)this != _Right)
			{	// get sublist from another list
			node_type^ _Nlast = _Last->_Prev;

			_Mysize += _Right->unsplice_node(this, _First, _Last);
			_Nlast->_Next = _Where;
			_Where->_Prev->_Next = _First;
			_First->_Prev = _Where->_Prev;
			_Where->_Prev = _Nlast;
			++_Mygen;
			}
		else if (_First != _Where && _Where != _Last)
			{	// worth splicing, do it
			node_type^ _Node = _Where->_Prev;

			_First->_Prev->_Next = _Last;
			_Last->_Prev->_Next = _Where;
			_Where->_Prev->_Next = _First;
			_Where->_Prev = _Last->_Prev;
			_Last->_Prev = _First->_Prev;
			_First->_Prev = _Node;
			++_Mygen;
			}
		}

	size_type unsplice_node(_Mytype_t^ _Left,
		node_type^ _First, node_type^ _Last)
		{	// unsplice [_First, _Last) to give to _Left
		if (_First->container() != this)
			throw gcnew System::InvalidOperationException();

		size_type _Count = 0;
		node_type^ _Node = _First;

		for (; _Node != _Last && !_Node->is_head();
			_Node = _Node->_Next, ++_Count)
			_Node->_Head = _Left->head_node();	// change ownership

		if (_Node != _Last || _Maxsize - _Left->size() < _Count)
			{	// invalid splice, back out
			for (; _First != _Node; _First = _First->_Next)
				_Node->_Head = _Myhead;	// revert ownership

			if (_Node != _Last)
				throw gcnew System::InvalidOperationException();
			else
				throw gcnew System::ArgumentOutOfRangeException();
			}

		_First->_Prev->_Next = _Last;	// remove sublist
		_Last->_Prev = _First->_Prev;
		_Mysize -= _Count;
		++_Mygen;
		return (_Count);
		}

	void remove(value_type _Val)
		{	// erase each element matching _Val
		for (node_type^ _First = front_node(); _First != head_node(); )
			{	// point past element and test it
			_First = _First->next_node();
			if (_First->prev_node()->_Myval == _Val)
				erase_node(_First->prev_node());
			}
		}

	void remove_if(_Valtest_dt^ _Pred)
		{	// erase each element satisfying _Pred
		for (node_type^ _First = front_node(); _First != head_node(); )
			{	// point past element and test it
			_First = _First->next_node();
			if (_Pred(_First->prev_node()->_Myval))
				erase_node(_First->prev_node());
			}
		}

	template<typename _Pr1_t>
		void remove_if(_Pr1_t _Pred)
		{	// erase each element satisfying _Pred
		for (node_type^ _First = front_node(); _First != head_node(); )
			{	// point past element and test it
			_First = _First->next_node();
			if (_Pred(_First->prev_node()->_Myval))
				erase_node(_First->prev_node());
			}
		}

	void unique()
		{	// erase each element matching previous
		_Unique(equal_to<value_type>());
		}

	void unique(_Valcomp_dt^ _Pred)
		{	// erase each element satisfying _Pred with previous
		_Unique(_Pred);
		}

	template<typename _Pr2_t>
		void unique(_Pr2_t _Pred)
		{	// erase each element satisfying _Pred with previous
		_Unique(_Pred);
		}

	template<typename _Pr2_t>
		void _Unique(_Pr2_t _Pred)
		{	// erase each element satisfying _Pred with previous
		if (2 <= size())
			{	// worth doing, do it
			for (node_type^ _First = front_node();
				_First->next_node() != head_node(); )
				if (_Pred(_First->_Myval, _First->next_node()->_Myval))
					erase_node(_First->next_node());
				else
					_First = _First->next_node();
			}
		}

	void merge(_Mytype_t% _Right)
		{	// merge in elements from _Right, both ordered by operator<
		_Merge(_Right, less<value_type>());
		}

	void merge(_Mytype_t% _Right, _Valcomp_dt^ _Pred)
		{	// merge in elements from _Right, both ordered by _Pred
		_Merge(_Right, _Pred);
		}

	template<typename _Pr3_t>
		void merge(_Mytype_t% _Right, _Pr3_t _Pred)
		{	// merge in elements from _Right, both ordered by _Pred
		_Merge(_Right, _Pred);
		}

	template<typename _Pr3_t>
		void _Merge(_Mytype_t% _Right, _Pr3_t _Pred)
		{	// merge in elements from _Right, both ordered by _Pred
		if ((Object^)this != %_Right)
			{	// safe to merge, do it
			node_type^ _First1 = front_node();
			node_type^ _First2 = _Right.front_node();

			for (; _First1 != head_node() && _First2 != _Right.head_node(); )
				if (_Pred(_First2->_Myval, _First1->_Myval))
					{	// splice in an element from _Right
					_First2 = _First2->next_node();
					splice_node(_First1, %_Right,
						_First2->prev_node(), _First2);
					}
				else
					_First1 = _First1->next_node();

			splice_node(head_node(), %_Right, _First2,
				_Right.head_node());
			}
		}

	void sort()
		{	// order sequence, using operator<
		_Sort(less<value_type>());
		}

	void sort(_Valcomp_dt^ _Pred)
		{	// order sequence, using _Pred
		_Sort(_Pred);
		}

	template<typename _Pr3_t>
		void sort(_Pr3_t _Pred)
		{	// order sequence, using _Pred
		_Sort(_Pred);
		}

	template<typename _Pr3_t>
		void _Sort(_Pr3_t _Pred)
		{	// order sequence, using _Pred
		if (2 <= size())
			{	// worth sorting, do it
			const size_type _Maxbins = 30;
			typedef cli::array<list_impl^> _Myarray_t;

			list_impl^ _Templist = gcnew list_impl;
			_Myarray_t^ _Binlist = gcnew _Myarray_t(_Maxbins);
			int _Maxbin = 0;
			int _Bin;
			for (; !empty(); )
				{	// sort another element, using bins
				_Templist->splice_node(_Templist->front_node(), this,
					front_node(),
					front_node()->next_node());	// pick an element
				for (_Bin = 0; _Bin < _Maxbin && !_Binlist[_Bin]->empty();
					++_Bin)
					{	// merge into ever larger bins
					_Binlist[_Bin]->merge(*_Templist, _Pred);
					_Binlist[_Bin]->swap(*_Templist);
					}
				if (_Bin == _Maxbins)
					_Binlist[_Bin - 1]->merge(*_Templist, _Pred);
				else
					{	// spill to empty or new bin, while they last
					if (_Bin == _Maxbin)
						{	// start a new bin
						_Binlist[_Bin] = gcnew list_impl;
						++_Maxbin;
						}
					_Binlist[_Bin]->swap(*_Templist);
					}
				}
			for (_Bin = 1; _Bin < _Maxbin; ++_Bin)
				_Binlist[_Bin]->merge(*_Binlist[_Bin - 1], _Pred);
			splice_node(head_node(), _Binlist[_Maxbin - 1],
				_Binlist[_Maxbin - 1]->front_node(),
				_Binlist[_Maxbin - 1]->head_node());
			}
		}