C++学习之list的实现

在了解学习list实现之前我们首先了解一下关于迭代器的分类：

按功能分类：

正向迭代器反向迭代器

const正向迭代器 const反向迭代器

按性质分类：

单向迭代器只能++ 例如单链表

双向迭代器可++，也可-- 例如双链表，map和set

随机迭代器可加加，可减减，可+，可减如顺序表（vector string）,deque(双端队列)

这些都是由容器的底层实现。

可以看到库中提供的list模板是带头双向链表，故此我们实现它就大部分操作都是在数据结构中实现双链表时是一样。

1.成员变量

节点类型的定义：

迭代器

重载前置++/--

重载后置++/--

重载*与->

重载!=与==

const迭代器

迭代器的优化：

成员函数

构造函数

析构函数

拷贝构造函数

容量

size

修饰符

insert()

erase ()

push_front()

pop_front()

push_back()

pop_back()

clear()

1.成员变量

template<class T>class mylist
	{
        typedef list_node<T>  Node;
		typedef _list_iterator<T, T&, T*> iterator;
		typedef _list_iterator<T,const T&,const T*> const_iterator;
private:
		Node* _head;
		size_t _size;
......
}

因为实现的是链表，故此我们的成员变量是链表头节点与链表的大小，这里我们还需要给出

节点类型的定义：

typedef list_node<T>  Node;
template<class T>struct list_node
	{
		//我们给一个缺省值为T的匿名对象
		list_node(const T& x = T())
			:data(x)
			, _next(nullptr)
			, _prev(nullptr)
		{}
		T data;
		list_node<T>* _next;
		list_node<T>* _prev;
	};

迭代器

因为我们实现的是链表，那么迭代器的操作也就是链表节点的操作，节点并非一般的数据类型，

故此我们这里需要封装迭代器，迭代器本质是节点的地址：

//迭代器
	//认真思考的话，迭代器模拟的是一个双链表节点的运动，故我们封装迭代器里面一定是节点，这里放入节点的地址
	//并且重载对应的运算符，封装之后，我们在定义为iterator
	template<class T>struct _list_iterator
	{
		//利用节点的指针实现迭代器
		typedef list_node<T>  Node;
		typedef _list_iterator<T> self;
		Node* _node;
        _list_iterator(Node* node)
			:_node(node)
		{}

	};

封装之后，我们还需要重载对于迭代器的运算符，这些重载都是在迭代器中的，我只是为了吧方法一个个体现出来，分开了。

重载前置++/--

       //重载加加
		self& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

重载后置++/--

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

重载*与->

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

重载!=与==

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

const迭代器

const迭代器对应const对象,指的是内容不能被修改，而非指针（迭代器）本身，因此我们不能直接const iterator去认为是const迭代器,这样反而不能对迭代器进行++等操作，而需要我们去重新定义
定义const迭代器，即内容是无法被修改，由于我们访问内容是通过解引用的方法故我们需要修改访问的的这两个操作符其引用返回为const，即内容无法被修改了。

template<class T>struct _list_const_iterator
	{
		typedef list_node<T>  Node;
		typedef _list_const_iterator<T> self;
		Node* _node;
		_list_const_iterator(Node* node)
			:_node(node)
		{}
		//迭代器的运算符重载
		self& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		self& operator--()
		{
			_node = _node->prev;
			return *this;
		}
		self& operator++(int)
		{
			self tmp(*this);
			_node = _node->_next;
			return tmp;
		}
		self& operator--(int)
		{
			self tmp(*this);
			_node = _node->prev;
			return tmp;
		}
		const T* operator->()
		{
			return &_node->data;
		}
		const T& operator*()
		{
			return &_node->data;
		}
		bool operator!=(const self& s)
		{
			return _node != s._node;
		}
		bool operator==(const self& s)
		{
			return _node == s._node;
		}

	};

由于const迭代器与普通的迭代器区别也就在于访问的内容无法被修改，也就是修改*与->这两个访问内容的操作符，重新实现较为麻烦，库中实现是增加了两个模板参数Ref,Ptr，利用我们传的参数不一样，从而决定用的是哪一个迭代器。

迭代器的优化：

多出两个模板参数之后，我们的*与->返回类型就是到时候传入时候的类型，故这里我们直接用Ref与Ptr代替即可。

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)
		{}
}

        Ptr operator->()
		{
			return _node->data;
		}
		Ref operator*()
		{
			return &_node->data;
		}

在list中，对于模板迭代器我们传参不一样，决定了是const还是普通

typedef _list_iterator<T, T&, T*> iterator;
typedef _list_iterator<T,const T&,const T*> const_iterator;
        iterator begin()
		{
			//return iterator(_head->data);
			return _head->_next;
		}
		iterator end()
		{
			return _head;//哨兵位就是链表的结束标志
		}
		const_iterator begin()const
		{
			return _head->_next;
		}
		const_iterator end()const
		{
			return _head;
		}

成员函数

构造函数

       //通过调用一个初始化链表的函数来实现构造函数
       mylist()
		{
			empty_init();
		}

析构函数

      //通过调用clear函数释放链表的节点，在释放哨兵位，即为析构
 ~mylist()
		{
			clear();
			delete _head;
			_head = nullptr;
		}

拷贝构造函数

//拷贝构造,将节点尾插入新的对象
		mylist(mylist<T>& p)
		{
			empty_init(p);
			for (auto it : p)
			{
				push_back(it);
			}
		}

容量

size

size_t size()
		{
			return _size;
		}

修饰符

insert()

在基于实现insert，我们的其他对list的操作都可以调用insert，不需要都去对链表节点一个个操作，

其次我们设计insert的返回值及参数位置都是迭代器，直接用。

iterator insert(iterator pos, const T x)//插入也会使迭代器失效，原位置节点找不到了
		{
			Node* cur = pos._node;
			Node* newnode = new Node(x);
			Node* prev = cur->_prev;
			//链接节点
			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;
			_size++;
			return iterator(newnode);
		}

erase ()

//删除   这里删除cur节点释放掉，会导致迭代器失效,因此要返回下一节点的迭代器
		iterator erase(iterator pos)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;
			delete cur;
			prev->_next = next;
			next->_prev = prev;
			_size--;
			return iterator(next);
		}

push_front()

void push_front()
		{
			insert(begin());
		}

pop_front()

//头删
		void pop_front()
		{
			erase(begin());
		}

push_back()

//尾插
		void push_back(const T& x)
		{
			//Node* tail = _head->preav;
			//Node* newnode = new Node(x);
			连接节点
			//tail->_next = newnode;
			//newnode->_next = _head;
			//newnode->prev = tail;
			//tail->_prev = newnode;
			//tail = newnode;
			//return (tail);
			insert(end(), x);
		}

pop_back()

//尾删
		void pop_back()
		{
			erase(end());
		}

clear()

//清数据
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
         }

至此我们对list的简单实现就完成了。文章来源地址https://uudwc.com/A/zkdwa