Simulation Implementation of list

Catalog

1. Introduce

2. Simulation Implementation

        2.1 First construct Node node

2.2 Construct iterators

2.3 structure list Containers

2.4const_iterator The implementation of the

 2.5 Implementation of other functions

---

1. Introduce

1. list It is a sequential container that can be inserted and deleted anywhere within the constant range , And the container can iterate back and forth .

2. list The bottom layer of is a two-way linked list structure , Each element in a two-way linked list is stored in independent nodes that are not related to each other , In a node, point to its previous element and the next element through a pointer .

3.list iterator And string,vector Different , It's not a native pointer , It can be regarded as a pointer to a node .

2. Simulation Implementation

First look at listd Implementation principle of , In essence, it is a leading two-way circular linked list . Pictured

 2.1 First construct Node node

template<class T>
	struct list_node
	{
		list_node<T>* _next;
		list_node<T>* _prev;
		T _data;

		list_node(const T& val = T())// The default constructor 
			:_next(nullptr)
			, _prev(nullptr)
			, _data(val)             // Store the data 
		{}
	};

2.2 Construct iterators

Next, operate the node , Complete the traversal , Add, delete, check, modify, etc , You can construct another structure , Store it Node The pointer to . It's an iterator . Pictured

    template<class T>
	struct __list_iterator
	{
		typedef list_node<T> Node;      // Rename the above node Node
		typedef __list_iterator<T> self;// Name this node self
		Node* _node;                    // Store the pointer of the above node 

		__list_iterator(Node* node)
			:_node(node)
		{}
    };

Perform some operations on nodes , Through iterators .

        T& operator*()  // This iterator is not a native pointer , Heavy load required *
		{
			return _node->_data;//
		}

		self& operator++()  // In front of ++, Return the address of the next node 
		{
			_node = _node->_next;
			return *this;
		}

		self operator++(int)// After ++
		{
			self tmp(*this);
			_node = _node->_next;
			return tmp;
		}

		self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

		self operator--(int)
		{
			self tmp(*this);
			_node = _node->_prev;
			return tmp;
		}


		bool operator!=(const self& it)
		{
			return _node != it._node;
		}

		bool operator==(const self& it)
		{
			return _node == it._node;
		}

2.3 structure list Containers

list Class stores structures Node The address of

   template<class T>
	class list
	{
	public:
		typedef __list_iterator<T> iterator;
        typedef list_node<T> Node;

		list() 
		{
			_head = new Node();
			_head->_next = _head;
			_head->_prev = _head;
		}
        iterator begin()//
		{
			return iterator(_head->_next);//_head->next It points to the first element , The type is Node<T>*, use  
                                             itreator To receive the 
			//return _head->_next;// One parameter constructors support implicit type conversions 
		}

		iterator end()
		{
			return iterator(_head);
		}

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

	private:
		Node* _head;// The address of the storage node 
	};

Through the code above , Basically completed a list 了 . The following can be verified .

  But suppose T If it is a custom type , for example ：

struct AA
	{
		AA(int a1 = 0, int a2 = 0)
			:_a1(a1)
			, _a2(a2)
		{}

		int _a1;
		int _a2;
	};

	void test_list2()
	{
		list<AA> lt;
		lt.push_back(AA(1, 1));
		lt.push_back(AA(2, 2));
		lt.push_back(AA(3, 3));
		lt.push_back(AA(4, 4));

		
		list<AA>::iterator it = lt.begin();
		while (it != lt.end())
		{
			cout << (*it)._a1 << "-"<< (*it)._a2 <<" ";// Currently, you can only access elements in this way 
			++it;
		}
		cout << endl;
	}

Even overloads know references --*, No direct access , because *it Get is AA Data of type . So you can reload a -> Symbol .

       T* operator->()
		{ 
			//return &(operator*());
			return &_node->_data;
		}

cout << it->_a1 << "-" << it->_a2 << " "; But in fact it-> Refer to AA*,it->-> The essence is that access is correct , But the compiler is optimized .

2.4const_iterator The implementation of the

for example ：

   void print_list(const list<int>& lt)
	{
		list<int>::const_iterator it = lt.begin();
		while (it != lt.end())
		{
			//*it = 10; //  No modification allowed 
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}

Need to write one const_iterator The implementation of the , Is it necessary to write another one struct __list_iterator{}, Then make appropriate modifications to the contents . In fact, there are many similarities between the two , It can be realized by template .

Yes list Change the code of the container

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;

		const_iterator begin() const
		{
	
			return const_iterator(_head->_next);
		}
		const_iterator end() const
		{
			return const_iterator(_head);
		}


        iterator begin()
		{
			return iterator(_head->_next);
			//return _head->_next;
		}
		iterator end()
		{
			return iterator(_head);
		}
      ...........
      ...........// Other functions are implemented 
      ...........

}

Then make some code changes to the iterator ：

   template<class T, class Ref, class Ptr>//Ref yes T&,Ptr yes T*, perhaps Ref yes const T&,Ptr yes  
                                            const T*, Determine according to the type of transmission 
	struct __list_iterator
	{
		typedef list_node<T> Node;
		typedef __list_iterator<T, Ref, Ptr> self;
		Node* _node;

		__list_iterator(Node* node)
			:_node(node)
		{}
	

		Ref operator*()
		{
			return _node->_data;
		}

		Ptr operator->()
		{ 
			//return &(operator*());
			return &_node->_data;
		}
        ........
        ........// Implementation of other functions 
        ........

}

 //Ref yes T&,Ptr yes T*, perhaps     Ref yes const T&,Ptr yes  const T*, Determine according to the type of transmission

Look at the picture ：

 2.5 Implementation of other functions

       void empty_init()
		{
			_head = new Node();
			_head->_next = _head;
			_head->_prev = _head;
		}

		template <class InputIterator>
		list(InputIterator first, InputIterator last)// Complete the construction with an iterator interval 
		{
			empty_init();

			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

		void swap(list<T>& lt)
		{
			std::swap(_head, lt._head);
		}

		// lt2(lt1) --  Modern writing 
		list(const list<T>& lt)
		{
			empty_init();
			list<T> tmp(lt.begin(), lt.end());
			swap(tmp);
		}

		// lt2 = lt1
		list<T>& operator=(list<T> lt)// Value passed 
		{
			swap(lt);
			return *this;
		}

		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}

		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}

		void push_back(const T& x)
		{
			//Node* tail = _head->_prev;
			//Node* newnode = new Node(x);

			 _head       tail  newnode
			//tail->_next = newnode;
			//newnode->_prev = tail;
			//newnode->_next = _head;
			//_head->_prev = newnode;

			insert(end(), x);
		}

		void push_front(const T& x)
		{
			insert(begin(), x);
		}

		void pop_back()
		{
			erase(--end());
		}

		void pop_front()
		{
			erase(begin());
		}

		//  Insert in pos Before the position 
		iterator insert(iterator pos, const T& x)
		{
			Node* newNode = new Node(x);
			Node* cur = pos._node;
			Node* prev = cur->_prev;

			prev->_next = newNode;
			newNode->_prev = prev;
			newNode->_next = cur;
			cur->_prev = newNode;

			return iterator(newNode);
		}

		iterator erase(iterator pos)
		{
			assert(pos != end());

			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;

			prev->_next = next;
			next->_prev = prev;
			delete cur;

			return iterator(next);
        }

Add ： From the above code, we can see , When a new element is inserted ,pos Still point to the original element , But a function returns a pointer to a new element . When the element is deleted , At present pos The space pointed to has been destroyed , The function returns the address of the next element of the deleted element .