C++ ─── List的模拟实现

一， List的模拟实现

List 是一个双向循环链表,由于List的节点不连续，不能用节点指针直接作为迭代器，因此我们要对结点指针封装，来实现迭代器的作用。

迭代器有两种实现方式，具体应根据容器底层数据结构实现：

1. 原生态指针，比如：vector

2. 将原生态指针进行封装，因迭代器使用形式与指针完全相同，因此在自定义的类中必须实现以下方法：

        1. 指针可以解引用，迭代器的类中必须重载operator*()

   2. 指针可以通过->访问其所指空间成员，迭代器类中必须重载oprator->()

        3. 指针可以++向后移动，迭代器类中必须重载operator++()与operator++(int)

至于operator--()/operator--(int)释放需要重载，根据具体的结构来抉择，双向链表可以向前移动，所以需要重载，如果是forward_list就不需要重载--

        4. 迭代器需要进行是否相等的比较，因此还需要重载operator==()与operator!=()

二，代码实现

#pragma once
#include<assert.h>
#include<iostream>
#include <initializer_list>
#include<algorithm>
using namespace std;namespace BMH
{template<class T>struct ListNode{typedef ListNode<T> Node;Node* _prev;Node* _next;T _data;ListNode(const T& data = T()):_prev(nullptr), _next(nullptr), _data(data){}};template<class T, class Ref, class Ptr>struct ListIterator{//正向迭代器typedef ListNode<T> Node;typedef ListIterator<T, Ref, Ptr> Self;// Ref 和 Ptr 类型需要重定义下，实现反向迭代器时需要用到public:typedef Ref Ref;typedef Ptr Ptr;Node* _node;ListIterator(Node* node =nullptr):_node(node){}//++itSelf& operator++(){_node = _node->_next;return *this;//++it 返回自己（迭代器）}//--itSelf& operator--(){_node = _node->_prev;return  *this;}//it++Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}//it--Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}//// 具有指针类似行为//*it  返回值Ref operator*(){return _node->_data;;}//it->  返回指针Ptr operator->(){return &(_node->_data);}////// 迭代器支持比较bool operator == (const Self& it){return _node == it._node;}bool operator != (const Self& it){return _node != it._node;}};template<class T>class List{public:typedef ListNode<T> Node;typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T*> const_iterator;/////初始化创建头结点void empty_init(){_head = new Node();_head->_prev = _head;_head->_next = _head;}//构造函数List(){empty_init();}List(int n, const T& value = T()){empty_init();for (int i = 0; i < n; ++i)push_back(value);}//用下面拷贝构造函数来实现构造函数，拷贝构造函数是构造函数的一种。//List<int> lt2(lt1)//List(const List<T>& lt)//{//	empty_init();//	for (const auto& e : lt)//	{//		Push_Back(e);//	}//}//List<int> lt1 ={1,2,3,4}List(initializer_list<T> il)//不用引用的原因：il本身是两个指针，拷贝代价小{empty_init();for (const auto& e : il){Push_Back(e);}}template<class Inputiterator >List(Inputiterator p1, Inputiterator p2){empty_init();while (p1 != p2){Push_Back(*p1);++p1;}}//拷贝构造//lt2(lt1)List(const List<T>& lt){empty_init();for (const auto& e : lt){Push_Back(e);}}//赋值重载//lt1=lt2List<T>& operator=(List<T> lt){swap(_head, lt._head);return *this;}void clear(){iterator it = begin();while (it != end()){it = erase(it);//用erase时会发生迭代器失效}}~List(){clear();delete _head;_head = nullptr;}/////迭代器iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator begin() const{return const_iterator(_head->_next);}const_iterator end() const{return  const_iterator(_head);}///// 容量相关//尾插void Push_Back(const T& x){Node* tail = _head->_prev;Node* newnode = new Node(x);newnode->_prev = tail;tail->_next = newnode;newnode->_next = _head;_head->_prev = newnode;}void Pop_Back(){erase(--end());}void Push_Front(const T& x){insert(begin(),x);}void Pop_Front(){erase(begin());}//之前插入，无迭代器失效iterator insert(iterator pos ,const T& data ){Node* cur = pos._node;//pos是迭代器，找到其中的节点地址即可Node* newnode = new Node(data);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!= (*this).end());//防止将Node* cur = pos._node;Node* next = cur->_next;Node* prev = cur->_prev;prev->_next = next;next->_prev = prev;delete cur;return iterator(next);}private:Node* _head;};

三、list和vector的区别

        1、任意位置插入删除时：list可以随意插入删除，但是vector任意位置的插入删除效率低，需要挪动元素，尤其是插入时有时候需要异地扩容，就需要开辟新空间，拷贝元素，释放旧空间，效率很低

        2、访问元素时：vector支持随机访问，但是list不支持随机访问
        3、迭代器的使用上：vector可以使用原生指针，但是list需要对原生指针进行封装
        4、空间利用上：vector使用的是一个连续的空间，空间利用率高，而list使用的是零碎的空间，空间利用率低