C++ 之 【模拟实现 list（节点、迭代器、常见接口）】(将三个模板放在同一个命名空间就实现 list 啦)

1.前提准备

(1) list 的底层结构一般是带头双向循环链表

(1)为避免命名冲突，需要创建一个命名空间来存放模拟实现的 list

(2)下面模拟实现list时，声明和定义不分离(具体原因后续讲解)

2.完整实现

2.1 链表节点

template<class T>//节点写成类模板，适合不同的数据类型
struct __list_node//带头双向循环链表的节点，因为下面会使用，用struct
{typedef __list_node<T> Node;//起个别名，谨防忘记实例化(即指定参数)Node* _next;Node* _prev;T _val;__list_node(const T& val = T()):_next(nullptr),_prev(nullptr),_val(val){}
};

(1)将链表节点写成一个类模板，将数据类型指定为模板参数T，以支持不同类型的数据

(2)使用 struct 定义节点类，原因有二

1.后续所实现的链表,迭代器需要用到节点，使用 struct 方便暴露节点成员

2.用户使用链表时，并不知晓节点的名称等消息，强行使用而出错的锅不用实现者背

(3)不要将类模板名直接写为node，因为后续还有树等数据结构也有节点，

所以命名时通常加 list 前缀来区分

(1)节点包含指向前后的两个指针，指针类型是节点类型，注意

类模板中，__list_node是类模板名，__list_node<T>是类型

谨防忘记，为类型起个别名

typedef __list_node<T> Node;//起个别名，谨防忘记实例化(即指定参数)Node* _next;Node* _prev;

(2)节点初始化，将指针置空，数据依用户传递为主，缺省值为辅

__list_node(const T& val = T()):_next(nullptr),_prev(nullptr),_val(val){}

(1)后续实现链表时才会在堆上申请节点

节点内部并没有申请其他资源，就没必要在节点中写析构函数等其他默认成员函数

等链表使用完毕，再在链表中进行资源释放即可

2.2 链表中的迭代器

迭代器可以被理解为 抽象化的指针，它模拟指针的行为(遍历和操作元素)，

使用方式与指针一致，但它的适用范围更广

(1)vector是动态顺序表，内存连续分布，指针可以遍历和操作元素

所以在vector中，指针就是一种迭代器

但是 list 的内存分布一般不连续，节点指针不可以遍历和操作元素，

所以，我们定义一个迭代器类来封装节点指针，通过运算符重载来模拟指针的行为，

此时，该迭代器类的对象就是链表的迭代器

	template<class T, class Ref, class Ptr>//节点指针类型是__list_node<T>*struct __list_iterator//list中需要使用迭代器，使用struct供下面使用{typedef __list_node<T> Node;typedef __list_iterator<T, Ref, Ptr> Self;Node* _node;//用节点指针构造迭代器__list_iterator(Node* node):_node(node){}//it1 != it2bool operator!=(const Self& it)const{return _node != it._node;}bool operator==(const Self& it)const{return _node == it._node;}//*Ref operator*()const//Ref是引用的意思，用来控制普通迭代器与const迭代器{return _node->_val;}Self& operator++(){_node = _node->_next;return *this;}Self operator++(int){iterator 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;}Ptr operator->()const{return &(_node->_val);}};

2.2.1 迭代器的细节点

迭代器类的成员变量就是节点指针

(1)节点类型为：__list_node<类型>，为了支持不同类型的数据，将类型指定为参数T，

同时为了简便，为节点起个别名 Node 

typedef __list_node<T> Node;

所以指针类型就是 Node*，

Node* _node;//用节点指针构造迭代器

(1)使用 struct 定义迭代器类，原因有二

1.后续所实现的链表中的常用接口需要用到迭代器，使用struct暴露成员直接供其使用

2.用户使用链表时，并未知晓迭代器的完整信息，强行使用而导致出错的锅不用实现者背

(2)命名迭代器类时通常加 list 前缀来区分

(3)迭代器对象名字太长，起个别名Self，self 就是 自己的意思

typedef __list_iterator<T, Ref, Ptr> Self;

2.2.2 迭代器的构造函数

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

(1)后续实现链表时，显示传递一个节点指针以构造一个迭代器

(2)迭代器内部并没有申请其他资源，就没必要在迭代器类中写析构函数等其他默认成员函数

2.2.3 迭代器间的比较

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

(1)迭代器之间的比较实际上就是 节点指针之间的比较，运算符重载即可

2.2.4 迭代器访问数据

Ref operator*()//Ref是引用的意思，用来控制普通迭代器与const迭代器
{return _node->_val;
}

(1)指针解引用可以访问到它所指向的数据，迭代器模拟指针

通过运算符重载，使得解引用迭代器就是 获取 节点指针指向的数据

(2)Ref是引用的意思，用来控制普通迭代器与const迭代器,下面来仔细讲解

2.2.5 普通迭代器与const迭代器的主要区别

不加const修饰的链表包含的是 普通迭代器，const 修饰的链表包含的是 const迭代器。

不加const修饰的链表中，节点的数据可以被修改，const 修饰的链表则相反

所以普通迭代器与const迭代器的主要区别就是，二者访问数据的权限间的区别

普通迭代器 可读可修改数据， const 迭代器 只可读 数据

Ref operator*()//Ref是引用的意思，用来控制普通迭代器与const迭代器
{return _node->_val;
}

所以，将解引用返回值类型指定为模板参数

后续通过显示传递不同解引用返回值类型(T&, const T&)(T为数据类型)，

就可以实现普通迭代器和const迭代器

2.2.6 迭代器的遍历

Self& operator++()
{_node = _node->_next;return *this;
}Self operator++(int)
{iterator 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;
}

(1)前置++，重载运算符，让节点指针指向后一个节点，同时返回自己的引用即可

(2)后置++，重载运算符，让节点指针指向后一个节点，同时返回自己的拷贝即可

(1)前置--，重载运算符，让节点指针指向前一个节点，同时返回自己的引用即可

(2)后置--，重载运算符，让节点指针指向前一个节点，同时返回自己的拷贝即可

2.2.7 重载 -> 运算符

Ptr operator->()const
{return &(_node->_val);
}

struct A
{int _a1;int _a2;A(int a1 = 0, int a2 = 0):_a1(a1),_a2(a2){}
};
void test_list2()
{list<A> lt;lt.push_back(A(1, 1));lt.push_back(A(2, 2));lt.push_back(A(3, 3));lt.push_back(A(4, 4));list<A>::iterator it = lt.begin();while (it != lt.end()){//cout << (*it)._a1 << ' ' << (*it)._a2 << endl;cout << it->_a1 << ' ' << it->_a2 << endl;//it->->_a1有省略++it;}cout << endl;
}

当节点存储的是一个自定义类型的数据的时候，想要访问自定义类型的数据有两个方法

//cout << (*it)._a1 << ' ' << (*it)._a2 << endl;
cout << it->_a1 << ' ' << it->_a2 << endl;//it->->_a1有省略

(1)解引用迭代器：(*it)._a1，通过 operator* 获取对象，再用 . 操作符访问成员。

(2)调用 operator->：it->_a1，通过 operator-> 获取对象的指针（或类指针对象），

再用 -> 访问成员

cout << it->_a1 << ' ' << it->_a2 << endl;//it->->_a1有省略

虽然访问数据时省略了一个 ->

但是这行代码是能正常运行并访问数据的，实际上，为了简洁，迭代器访问自定义类型的数据时，只需要一个->即可，你可以认为编译器能够自动识别并补充这里的省略

重载->运算符返回的是自定义类型对象的地址(用指针接收)，

将指针类型指定为模板参数Ptr，

后续通过显示传递不同解引用返回值类型(T*, const T*)(T为数据类型)，

就可以实现普通迭代器和const迭代器

2.3 链表中的常见接口

	template<class T>class list{typedef __list_node<T> Node;public:typedef __list_iterator<T, T&, T*> iterator;//迭代器需要放到外面使用，所以别名也要在public中typedef __list_iterator<T, const T&, const T*> const_iterator;//迭代器需要放到外面使用，所以别名也要在public中iterator begin(){return _head->_next;//单参数返回，调用构造函数生成临时对象}iterator end(){return _head;}const_iterator begin()const{return _head->_next;}const_iterator end()const{return _head;}//构造函数void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(){empty_init();}//lt(lt1)list(const list<T>& lt){empty_init();for (auto& e : lt){push_back(e);}}//lt1 = lt2void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}list<T>& operator=(list<T> lt){swap(lt);return *this;}//析构函数~list(){clear();delete _head;_head = nullptr;}void clear(){auto it = begin();while (it != end()){it = erase(it);}_size = 0;}//尾插void push_back(const T& val){先找尾//Node* tail = _head->_prev;创造尾插节点//Node* newnode = new Node(val);_head tail newnode//_head->_prev = newnode;//newnode->_next = _head;//tail->_next = newnode;//newnode->_prev = tail;insert(end(), val);}void push_front(const T& val){insert(begin(), val);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}//insert\eraseiterator insert(iterator pos, const T& val){//创建新节点Node* newnode = new Node(val);//使用结点指针而不是迭代器进行链接Node* cur = pos._node;//prev newnode curNode* prev = cur->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;++_size;return newnode;}iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;//prev cur nextNode* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;cur = nullptr;--_size;return prev;}size_t size()const{return _size;}private:Node* _head;size_t _size;};

2.3.1 链表中的细节点

(1)链表同样是一个类模板，模板参数就是节点数据类型

(2)成员变量包含 哨兵位节点的指针_head 和 链表的大小_size (不包含头节点的节点个数)

(1)使用 class 定义 list

不同于上述的节点和迭代器， list 需要实现封装，只提供相应接口供外部使用

(1)节点类型为：__list_node<类型>，为了支持不同类型的数据，将类型指定为参数T，

同时为了简便，为节点起个别名 Node 

typedef __list_node<T> Node;

注意，为了防止外部使用 Node, 需要将这行代码写在访问限定符private的作用域之内

(2)迭代器对象名字太长，为符合日常使用习惯起别名如下：

typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;

基于上述"普通迭代器与const迭代器的区别"，指定相应参数即可达到

注意，为了外部可以使用迭代器iterator, 

所以需要将这行代码写在访问限定符public的作用域之内

2.3.2 链表中迭代器的接口

		iterator begin(){return _head->_next;//单参数返回，调用构造函数生成临时对象}iterator end(){return _head;}const_iterator begin()const{return _head->_next;}const_iterator end()const{return _head;}

(1)begin函数返回的是指向第一个有效节点(哨兵位的下一个位置)的迭代器

函数内部直接返回相应指针即可，

因为迭代器的构造函数是单参数类型，编译器会用该指针构造出相应迭代器

(2)其他函数按要求返回相应指针即可

(3)注意，const迭代器相关函数只有const对象才能调用，所用需要用const修饰

2.3.3 链表的构造函数

		//构造函数void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(){empty_init();}

(1)初始化一个链表就是创建一个头节点，使其前后指针指向自己(起到双向循环的作用)，

并把链表的大小置为0的过程，将这个过程抽象为一个函数，以供后续拷贝构造函数的使用

2.3.4 insert、erase函数

		iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);prev->_next = newnode;newnode->_next = cur;cur->_prev = newnode;newnode->_prev = prev;++_size;return newnode;}

insert 通常是指 在 pos位置之前插入

(1)只实现的单元素的插入，插入位置 pos 的类型是迭代器，返回的是新插入节点的位置

(2)插入时只需要注意 插入节点，插入节点前一个节点与新节点之间的关系

因为迭代器改变指向有点麻烦，使用节点指针完成上述关系的链接

因为链表由哨兵位节点，不用考虑头插为空

(3)插入一个节点，_size++

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;--_size;return next;}

(1)不能删除哨兵位节点，同时注意 _size--

(1)erase函数存在迭代器失效问题，返回被删除节点的下一个节点的迭代器

(2)删除时注意提前保存上一个节点和下一个节点即可

2.3.5 尾插尾删头插头删 

实现好了insert、erase函数以及迭代器的接口之后，

直接调用函数即可

		void push_back(const T& x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}

2.3.6 clear 与 析构函数 

        void clear(){iterator it = begin();while (it != end()){it = erase(it);}_size = 0;}~list(){clear();delete _head;_head = nullptr;}	

 (1)clear函数的作用是清理有效节点，不包含哨兵位，

直接迭代器遍历链表并删除节点即可，注意将_size 置空

(2)析构函数就是在 clear 之后， 清理头节点

2.3.7 拷贝构造函数

		list(const list<T>& lt){empty_init();for (auto& e : lt){push_back(e);}}

拷贝构造一个链表，被构造对象首先需要进行初始化，

然后遍历链表进行尾插即可

2.3.8 赋值重载函数

		void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}//lt1 = lt2list<T>& operator=(list<T> lt){swap(lt);return *this;}

现代写法，不用自己开空间，直接传值传参，

lt 是 lt2 的深拷贝(拷贝构造实现的是深拷贝)，然后交换两个链表，传引用返回

2.3.9 size函数

		size_t size(){return _size;}

前面的insert 、erase、clear函数已经对_size变量进行了相应操作

这里直接返回即可