list的模拟实现

• • list的模拟实现
  • • 定义节点
    • 定义迭代器
    • list的常见接口的实现

本质就是双向带头循环链表，模拟实现的重点是它的迭代器，因为list不是一块连续的空间，不能像string和vector一样通过下标来访问，它的迭代器是iterator是 bidirectional iterator双向迭代器(它不支持随机访问),那应该怎么办呢？---->思路：c++的operator可以解决这个问题（运算符重载），可以重载++，–，* 和 ->

在模拟实现之前，我们先来看个问题：

list和vector的区别与联系

• 首先list和vector是互补的，vector是一块连续的地址空间，这是优点同样也是缺点，他不适合频繁的头插头删，但是支持随机访问(可以去实现很多操作)
• vector大部分的编译器扩容一般是在2倍左右，可能会存在部分的空间浪费
• list支持实时申请内存，减少了内存浪费，但是最主要的是支持O(1)的插入和删除，但是不能支持下标的随机访问(空间不连续)

我们知道list是一个双向带头循环的链表，它的节点结构就是一个指向上一个节点的指针，一个指向后一个节点的指针和数据

	template
	struct __list_node //节点
	{
		__list_node* _prev;//指向前一个节点
		__list_node* _next;//指向后一个节点
		T _date;//数据
		
		__list_node(const T& date=T())//构造函数
			:_prev(nullptr)
			,_next(nullptr)
			,_date(date)
		{}
	};

	//给定不同的模板参数可以减少冗余的代码
	//如果只有一个模板参数，那么一个const的迭代器，它如果想要实现读取数据的操作是不被允许的
	template
	struct __list_iterator
	{
		typedef __list_iterator self;
		typedef __list_node list_node;
		//成员变量
		list_node* _node;
        
		__list_iterator(list_node* node)
			:_node(node)
		{}
		// it2 = it1 浅拷贝
		// 拷贝构造和赋值重载是否需要我们自己实现
		// 析构呢？-> 迭代器是借助节点的指针访问修改链表
		// 节点属于链表，不属于迭代器，所以他不管释放
		// 都不需要自己实现，默认生成的即可
		Ref operator*() //指向内置类型可以用解引用
		{
			return _node->_date;
		}
		Ptr* operator->() 
        //如果迭代器指向的是一个结构，要取每一个成员变量就需要重载->
		//所有类型只要想重载->都是这样实现都会自动省略一个->
        //例子如果是日期类为节点类型，返回的就是Date*所以使用应该是it->->
        
		{
			//&的优先级比->低
			//相当于&(_node->_date);
			return &_node->_date;
		}
		//前置++
		self& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		//后置++
		self operator++(int)
		{
			self temp(*this);
			_node = _node->_next;
			return temp;
		}
		//前置--
		self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}
		//后置++
		self operator--(int)
		{
			self temp(*this);
			_node = _node->_prev;
			return temp;
		}
		bool operator==(const self& x) const
		{
			return _node == x._node;
		}
		bool operator!=(const self& x) const
		{
			return _node != x._node;
		}
	};
	//这个是反向迭代器，reverse_iterator
	template
	struct __list_reverse_iterator
	{
		typedef __list_reverse_iterator self;
		InputIterator node;
		__list_reverse_iterator(InputIterator it)
			:node(it)
		{}
		Ref operator*()
		{
			//首先要知道rbegin它指向的是end()也就是list的头结点，然后将node赋给传进来的迭代器，之前的迭代器已经实现了
			//*和--的重载，所以只需要--在解引用得到的就是值
			InputIterator prev = node;
			return *(--prev);
		}
		//operator*()返回的是list_node*，所以取地址复用即可
		Ptr operator->()
		{
			return &operator*();
		}
		self& operator++()
		{
			--node;
			return *this;
		}
		self operator++(int)
		{
			return node--;
		}
		self& operator--()
		{
			++node;
			return *this;
		}
		self operator--(int)
		{
			return node++;
		}
		bool operator!=(const self& rit) const
		{
			return node != rit.node;
		}
		bool operator==(const self& rit) const
		{
			return node == rit.node;
		}
	};

这里有段代码

//这段代码定义在list类里面（当一个测试函数）
fun()
{
    list_node* node=_head->next;
    iterator it=_head->next;
    *node;  //得到的是首元素的那个节点
    *it;	//得到的是首元素的值
    ++node;	//越界
    ++it;	//到了第二个节点位置
}

这段代码中的node和it都是4byte，list_node*是原生指针，而iterator是一个迭代器对象，对他们使用操作符的结果和意义是完全不同的，这就是类型的作用。

template
	class list
	{
		typedef __list_node list_node;
	public:
		typedef __list_iterator iterator;
		//这里的T不能加上const否则在拷贝构造时，用迭代器来构造函数会出错
		//这里是支持读但是不支持写
		typedef __list_iterator const_iterator;

		typedef __list_reverse_iterator reverse_iterator;
		typedef __list_reverse_iterator const_reverse_iterator;
		//构造
		list()
		{
			_head = new list_node();
			_head->_next = _head;
			_head->_prev = _head;
		}
				list(int n, const T& val = T())//改,有现成的不会去匹配模板
		{
			//构造n个T类型的节点
			_head = new list_node();
			for (size_t i = 0; i < n; ++i)
			{
				list_node* newnode = new list_node(val);
				_head->_next = newnode;
				newnode->_prev = _head;
				newnode->_next = _head;
				_head->_prev = newnode;
			}
		}
		list(int n,const T& val= T())//改，有现成的不会去优先匹配模板
		{
			//构造n个T类型的节点
			_head = new list_node();
			for (size_t i = 0; i < n; ++i)
			{
				list_node* newnode = new list_node(val);
				_head->_next = newnode;
				newnode->_prev = _head;
				newnode->_next = _head;
				_head->_prev = newnode;
			}
		}
        //下面两个函数的时候，有时候会出现编译器匹配出错
		//用list 来举例子
		//1的两个参数类型一个是unsigned int，int
		//2的是两个int，会发现下面的更匹配，解决方法实现一个int的版本
		list(size_t n,const T& val= T())//1
		{
			//构造n个T类型的节点
			_head = new list_node();
			for (size_t i = 0; i < n; ++i)
			{
				list_node* newnode = new list_node(val);
				_head->_next = newnode;
				newnode->_prev = _head;
				newnode->_next = _head;
				_head->_prev = newnode;
			}
		}
        //实现用迭代器的构造
		template//2
		list(InputIterator first, InputIterator end)
		{
			_head = new list_node();
			_head->_next = _head;
			_head->_prev = _head;
			while (first != end)
			{
				push_back(*first);
				++first;
			}
		}
		//拷贝构造list lt(lt1);
		list(const list& lt)
		{
			//需要实现用迭代器的构造函数
			_head = new list_node();
			_head->_next = _head;
			_head->_prev = _head;
			list tmp(lt.cbegin(), lt.cend());
			std::swap(_head, tmp._head);
		}
		//赋值拷贝--->直接传值传参，然后交换就好
		list& operator=(list it)
		{
			swap(_head, it._head);
			return *this;
		}
		//有关迭代器的接口
		iterator begin()
		{
			return iterator(_head->_next);
		}
		iterator end()
		{
			return iterator(_head);
		}
		const_iterator cbegin() const
		{
			return const_iterator(_head->_next);
		}
		const_iterator cend() const
		{
			return const_iterator(_head);
		}
		reverse_iterator rbegin()
		{
			return reverse_iterator(end());
		}
		reverse_iterator rend()
		{
			//reverse_iterator(begin());这种就是相当于去调用构造函数，而下面就是直接返回
			return reverse_iterator(begin());
		}
		bool empty() const
		{
			return (_head->_next == _head) ? true : false;
		}
		size_t size() const
		{
			//用迭代器实现
			size_t count = 0;
			list_node* start = _head->_next;
			list_node* end = _head;
			while (start != end)
			{
				++count;
				start = start->_next;
			}
			return count;
		}
		T& front()
		{
			//front返回的是第一个位置的数据
			//这里的*是被重载之后的，可以拿到T _date
			return *(begin());
		}
		const T& front() const
		{
			return *(begin());
		}
		T& back()
		{
			return *(--end());
		}
		const T& back() const
		{
			return *(--end());
		}

		void push_back(const T& val)
		{
			insert(end(), val);
			//list_node* newnode = new list_node(val);
			//list_node* prev = _head->_prev;//指向的最后一个元素
			//newnode->_prev = prev;
			//prev->_next = newnode;
			//newnode->_next = _head;
			//_head->_prev = newnode;
		}
		void push_front(const T& val)
		{
			insert(begin(), val);
		}
		void pop_front(const T& val)
		{
			erase(begin());
		}
		void pop_back(const T& val)
		{
			//尾删的时候end()指向的是最后一个元素的下一个位置，也就是头结点
			erase(--end());
		}
		iterator insert(iterator pos,const T& val=T())
		{
			//不会存在迭代器失效问题，因为迭代器指向位置不会发生改变
			list_node* newnode = new list_node(val);
			list_node* cur = pos._node;
			newnode->_next = cur;
			newnode->_prev = cur->_prev;
			cur->_prev->_next = newnode;
			cur->_prev = newnode;
			return iterator(newnode);
		}
		iterator erase(iterator pos)
		{
			//需要判断不能为头结点
			// 这里erase以后，pos是否失效？一定失效
			assert(pos != end());
			list_node* cur = pos._node;
			list_node* next = cur->_next;
			cur->_prev->_next = next;
			next->_prev = cur->_prev;
			delete cur;
			return iterator(next);
		}
		//删除除头结点以外的节点
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				//erase(it++);
				it=erase(it);
			}
		}
		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}
	private:
		list_node* _head;
	};

list的成员只需要一个头结点就够了