list的模拟实现

目录

1.介绍

2.模拟实现

        2.1先构造Node结点

2.2构造迭代器

2.3构造list容器

2.4const_iterator的实现

 2.5其余函数的实现

---

1.介绍

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。

2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。

3.list iterator与string,vector不同，并不是是一个原生指针，可认为是一个结点的指针。

2.模拟实现

先看listd的实现原理，本质是一个带头双向循环链表。如图

 2.1先构造Node结点

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

		list_node(const T& val = T())//缺省的构造函数
			:_next(nullptr)
			, _prev(nullptr)
			, _data(val)             //存储数据
		{}
	};

2.2构造迭代器

接下来要对结点进行操作，完成遍历，增删查改等等，可再构造一个结构体，存储上面Node的指针。也就是一个迭代器。如图

    template<class T>
	struct __list_iterator
	{
		typedef list_node<T> Node;      //将上面结点重命名Node
		typedef __list_iterator<T> self;//将这个结点命名为self
		Node* _node;                    //存储上面结点的指针

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

对结点进行一些操作，通过迭代器完成。

        T& operator*()  //该迭代器不是原生指针，需重载*
		{
			return _node->_data;//
		}

		self& operator++()  //前置++，返回下一个结点的地址
		{
			_node = _node->_next;
			return *this;
		}

		self operator++(int)//后置++
		{
			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构造list容器

list类中存储有结构体Node的地址

   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是指向首元素的，类型是Node<T>*,用 
                                             itreator接收了
			//return _head->_next;//单参构造函数支持隐式类型的转换
		}

		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;//存储结点的地址
	};

通过上面的代码，就基本完成了一个list了。下面可以验证一下。

 但假设T是自定义类型的话，例如：

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 <<" ";//目前只能这样访问元素
			++it;
		}
		cout << endl;
	}

即使重载了解引用--*，不能直接访问，因为*it 拿到的是 AA类型的数据。所以可以在重载一个->符号。

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

cout << it->_a1 << "-" << it->_a2 << " ";但其实it->是指AA*，it->->本质是这样访问才是正确的，不过编译器做了优化。

2.4const_iterator的实现

例如：

   void print_list(const list<int>& lt)
	{
		list<int>::const_iterator it = lt.begin();
		while (it != lt.end())
		{
			//*it = 10; // 不允许修改
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}

需要在写一个const_iterator的实现，那是不是要重新再写一份struct __list_iterator{}，再对里面内容进行适当修改。其实二者有许多地方相似，可通过模版实现。

对list容器部分代码进行改动

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);
		}
      ...........
      ...........//其余函数实现
      ...........

}

再对迭代器部分代码改动：

   template<class T, class Ref, class Ptr>//Ref是T&，Ptr是T*，或者Ref是const T&，Ptr是 
                                            const T*，根据传过来的类型进行确定
	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;
		}
        ........
        ........//其余函数的实现
        ........

}

 //Ref是T&，Ptr是T*， 或者    Ref是const T&，Ptr是 const T*，根据传过来的类型进行确定

看图分析：

 2.5其余函数的实现

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

		template <class InputIterator>
		list(InputIterator first, InputIterator last)//用一段迭代器区间完成构造
		{
			empty_init();

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

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

		// lt2(lt1) -- 现代写法
		list(const list<T>& lt)
		{
			empty_init();
			list<T> tmp(lt.begin(), lt.end());
			swap(tmp);
		}

		// lt2 = lt1
		list<T>& operator=(list<T> lt)//值传递
		{
			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());
		}

		// 插入在pos位置之前
		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);
        }

补充：由上面代码可知，当插入新元素后，pos依旧指向原来的元素，但函数是返回指向新元素的指针。当删除元素后，当前pos所指向的空间已被销毁，函数返回的是被删除元素的下一个元素的地址。