The use of list and Its Simulation Implementation

One .list iterator Use

1. begin And end Is a forward iterator , Perform... On iterators ++ operation , The iterator moves backwards

2. rbegin(end) And rend(begin) Is a reverse iterator , Perform... On iterators ++ operation , The iterator moves forward

	int ar[] = { 1,2,3,4,5,6,7,8,9,0 };
	int n = sizeof(ar) / sizeof(ar[0]);
	//list<int> mylist(10,5);// Two way circular list with leading node 
	list<int> mylist(ar, ar + n);
	for (const auto& e : mylist)
	{
		cout << e << " ";
	}
	cout << endl;
	list<int>::iterator it = mylist.begin();
	while (it != mylist.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
	list<int>::reverse_iterator rit = mylist.rbegin();
	while (rit != mylist.rend())
	{
		cout << *rit << " ";
		++rit;
	}
	cout << endl;

 3.list Iterator failure problem for

Iterators are like pointers , The iterator fails, that is, the node pointed to by the iterator is invalid , This section The point has been deleted because list The underlying structure of is a two-way circular linked list of leading nodes , therefore stay list When inserting in, it will not lead to list Iteration Failure of , It will be invalid only when deleted , And the only thing that fails is the iterator pointing to the deleted node , Other iterators will not be affected .

mylist.erase(it++);

Two .list Built in functions for

list<int> mylist;

mylist.empty  testing list Is it empty , Is to return true, Otherwise return to false

mylist.size    return list Number of valid nodes in

mylist.front    return list The reference to the value in the first node of

mylist.back    return list Reference to the value of the last node of  

3、 ... and .list Simulation Implementation  

namespace ljx
{
	template<class T>
	struct __list_node
	{
		__list_node<T>* _next;
		__list_node<T>* _prev;
		T _data; 
		__list_node(const T& x=T())
		    :_data(x)
			,_next(nullptr)
			,_prev(nullptr)
		{}
	};
	template<class T,class Ref,class Ptr>
	struct __list_iterator
	{
		typedef __list_node<T>node;
		typedef __list_iterator<T, Ref, Ptr>Self;
		node* _node;
		__list_iterator(node* node)
			:_node(node)
		{}
		T* operator->()
		{
			return &_node->_data;
		}
		T& operator*()
		{
			return _node->_data;
		}
		Self& operator++()
		{  
			_node = _node->_next;
			return *this;
		}
		Self& operator++(int)
		{
			Self tmp(*this);
			//_node = _node->_next;
			++(*this);
			return tmp;
		}
		Self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}
		Self& operator--(int)
		{
			__list_iterator<T>tmp(*this);
			--(*this);
			return tmp;
		}
		bool operator!=(const Self& it)
		{
			return _node != it._node;
		}
		bool operator==(const Self& it)
		{
			return _node == it._node;
		}
	};
	template<class T>
	class list
	{
		typedef __list_node<T> node;
	public:
		typedef __list_iterator<T, T&, T*>iterator;
		typedef __list_iterator<T,const T&,const T*> const_iterator;
		// Take the lead in two-way circular list 
		//typedef __list_iterator<T,const T&,const T * > const_iterator;
		iterator begin()
		{
			return iterator(_head->_next);
		} 
		const_iterator begin()const
		{
			return const_iterator(_head->_next);
		}
		iterator end()
		{
			return iterator(_head);
		}
		const_iterator end()const
		{
			return const_iterator(_head);
		}
		list()
		{
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;
		}
		list(const list<T>& lt)
		{
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;
			//const_iterator it = lt.begin();
			//while (it != lt.end())
			//{
			//	push_back(*it);
			//	++it;
			//}
			for (auto e : lt)
			{
				push_back(e);
			}
		}
		//list <T>& operator=(const list<T>& lt)
		//{
		//	if (this != &lt)
		//	{
		//		clear();
		//		for (auto e : lt)
		//		{
		//			push_back(e);
		//		}
		//	}
		//	return *this;
		//}
		list<T>& operator=(list<T> lt)
		{
			swap(_head, lt._head)
				return *this;
		}
		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}
		void clear()
		{
			node* p = _head->_next;
			while (p != _head)
			{
				delete(p);
			}
		}
		void push_back(const T& x)
		{
			//node* tail = _head->_prev;
			//node* newnode = new node(x);
			//tail->_next = newnode;
			//newnode->_prev = tail;
			//newnode->_next = _head;
			//_head->_prev = newnode;
			insert(end(), x);
		}
		void push_front(const T& x);
		void insert(iterator pos, const T& x)
		{
			node* cur = pos._node;
			node* prev = cur->_prev;
			node* newnode = new node(x);

			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;
		}
		void erase(iterator pos)
		{
			assert(pos != end());
			{
				node* cur = pos._node;
				node* prev = cur->_prev;
				node* next = cur->_next;
				delete cur;
				prev->_next = next;
				next->_prev = prev;
			}
		}
		void pop_back()
		{
			erase(iterator(_head->_prev));
			erase(--end());
		}

	private:
		node* _head;
	};
}