从C语言到C++_17(list的模拟实现)list不是原生指针的迭代器（上）：https://developer.aliyun.com/article/1521329
2.7 operator--
前面实现了operator++，现在实现下operator--，把++的_next换成_prev就行：
iterator& operator--() { _node = _node->_prev; return *this; // 返回减减后的值 } iterator operator--(int) { iterator tmp(*this); // 拷贝构造一个tmp存储原来的值 _node = _node->prev; return tmp; // 返回减减前的值 }
2.8 const 迭代器
不用范围 for 的前提下去用迭代器遍历打印似乎挺麻烦的，我们可以把它放到一个函数里，
这里考虑到减少拷贝，使用引用返回，之前也说过这种情况能用 const 就用 const。
所以这里就成 const_iterator 了，而刚才实现的是普通迭代器，会导致没法遍历：
普通迭代器访问普通对象，可读可写；const 迭代器访问 const 对象，可读但不可写。
所以这里自然是需要实现 const 迭代器，即实现一个 "可读但不可写" 的迭代器。
（可以 ++ 可以解引用，但解引用的时候不能修改）
所以直接在 __list_iterator 里面重载一个 const 类型的 operator* 解决不了问题，
我们得重新实现一个 __const_list_iterator 出来。（更好的方法后面讲）
传统的方法是把 list_iterator 这个类CV一下，然后把名称改成 __const_list_iterator
这种实现方式可以是可以，但是这么实现好像有点拉胯，代码是很冗余的，
这个 const 迭代器和普通迭代器也就是类型名称和返回值不一样而已……
有没有办法可以优化一下呢？
可以通过加一个额外的模板参数去控制 operator 的返回值，能想到吗？
我们来看看巨佬是怎么做的 ：在定义 template 模板的时增加两个参数：
template<class T, class Ref, class Ptr> struct __list_iterator // 定义迭代器 { typedef list_node<T> Node; typedef __list_iterator<T, Ref, Ptr> iterator; // 在list类里面： // typedef __list_iterator<T, T&, T*> iterator; // typedef __list_iterator<T, const T&, const T*> const_iterator;
再加上const begin和const end我们的遍历打印函数就能跑出来了：
list.h
#pragma once #include<iostream> #include<assert.h> using namespace std; namespace rtx { template<class T> struct list_node // 定义结点 { T _data; list_node* _prev; list_node* _next; list_node(const T& x = T()) :_data(x) ,_prev(nullptr) ,_next(nullptr) {} }; template<class T, class Ref, class Ptr> struct __list_iterator // 定义迭代器 { typedef list_node<T> Node; typedef __list_iterator<T, Ref, Ptr> iterator; // 在list类里面： // typedef __list_iterator<T, T&, T*> iterator; // typedef __list_iterator<T, const T&, const T*> const_iterator; Node* _node; __list_iterator(Node* node) :_node(node) {} bool operator!=(const iterator& it) { return _node != it._node; } //T& operator*() Ref operator*() { return _node->_data; // 返回结点的数据 } //T* operator->() Ptr operator->() { return &(operator*()); //即 return &(_node->_data); } iterator& operator++() { _node = _node->_next; return *this; // 返回加加后的值 } iterator operator++(int) { iterator tmp(*this); // 拷贝构造一个tmp存储原来的值 _node = _node->_next; return tmp; // 返回加加前的值 } iterator& operator--() { _node = _node->_prev; return *this; // 返回减减后的值 } iterator operator--(int) { iterator tmp(*this); // 拷贝构造一个tmp存储原来的值 _node = _node->prev; return tmp; // 返回减减前的值 } }; template<class T> class list // 定义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()// begin是实际数据的第一个，_head 是哨兵位头结点 { return iterator(_head->_next); } iterator end()// end是实际数据的下一个 { return iterator(_head); } list() { _head = new Node; _head->_prev = _head; _head->_next = _head; } void push_back(const T& x) { Node* tail = _head->_prev; Node* NewNode = new Node(x); // 思路图：head tail NewNode tail->_next = NewNode; NewNode->_prev = tail; _head->_prev = NewNode; NewNode->_next = _head; } private: Node* _head; // 哨兵位头结点 }; }
Test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "list.h" namespace rtx { void Test_arrow() { struct Pos { int _a1; int _a2; Pos(int a1 = 0, int a2 = 0) :_a1(a1) , _a2(a2) {} }; Pos aa; Pos* p2 = &aa; p2->_a1; p2->_a2; list<Pos> lt; lt.push_back(Pos(10, 20)); lt.push_back(Pos(10, 21)); list<Pos>::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; void print_list(const list<int>& lt) { list<int>::const_iterator it = lt.begin(); while (it != lt.end()) { cout << *it << " "; it++; } cout << endl; } void Test_push_back() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); list<int>::iterator it = lt.begin(); print_list(lt); for (const auto& e : lt) { cout << e << " "; } cout << endl; } } int main() { rtx::Test_push_back(); //rtx::Test_arrow(); return 0; }
前面实现的迭代器都是原生指针。，写到 list 这才是涉及到了迭代器的精华。
3. list 的增删查改
在以前数据结构实现的时候说过，双向带头循环链表，
这个结构的优势就是只要实现insert和erase其它大多函数都能复用了
3.1 insert和头插尾插
在 pos 位置插入，我们通过 pos 去找到前驱 prev，之后创建新结点，再进行 "缝合" 操作，
这个我们也用C语言实现过了，这里不再细说。
iterator insert(iterator pos, const T& x) { Node* cur = pos._node; Node* prev = cur->_prev; Node* NewNode = new Node(x); prev->_next = NewNode; NewNode->_prev = prev; NewNode->_next = cur; cur->_prev = NewNode; return iterator(NewNode); } void push_back(const T& x) { //Node* tail = _head->_prev; //Node* NewNode = new Node(x); 思路图：head tail NewNode //tail->_next = NewNode; //NewNode->_prev = tail; //_head->_prev = NewNode; //NewNode->_next = _head; insert(end(), x); } void push_front(const T& x) { insert(begin(), x); }
测试：
void Test_insert() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); //list<int>::iterator pos = find(lt.begin(), lt.end(), 2);// 涉及其它问题，先不这样写 //if (pos != lt.end()) //{ // lt.insert(pos, 20); //} lt.insert(++lt.begin(), 20); lt.push_front(0); lt.push_front(-1); print_list(lt); }
3.2 erase和头删尾删
只需注意别删掉哨兵位头结点：
iterator erase(iterator pos) { assert(pos != end()); Node* cur = pos._node; // 删cur Node* prev = cur->_prev; prev->_next = cur->_next; // cur前一个指向cur后一个 cur->_next->_prev = prev; // cur后一个指回cur前一个 delete cur; return iterator(prev->_next); // 返回删除位置下一个 } void pop_back() { erase(begin()); } void pop_front() { erase(--end()); }
测试：
void Test_erase() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); lt.erase(++++lt.begin());//发现个好玩的，（删除3） lt.pop_back(); lt.pop_front(); print_list(lt); }
4. list 的深浅拷贝
list 的同样涉及深浅拷贝问题，下面的拷贝构造是深拷贝还是浅拷贝？
void Test_copy() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); list<int> lt2(lt); print_list(lt); print_list(lt2); }
程序没有崩，是深拷贝吗？不是的，这里默认生成的拷贝构造，还是浅拷贝，
有同学就会问了：难道是没有写数据？也不是，这里没崩仅仅是因为我们还没设计析构。
这里依然要自己去实现一个拷贝构造，去完成 "深拷贝" 。下面先实现一下析构：
4.1 clear 和析构
写析构之前为了方便清空，我们先实现一下 clear ，然后复用一下，clear又可以复用erase，
实现了 clear 后，我们再去实现 list 的析构函数就很简单了。
我们只需要把哨兵位头结点 _head 给干掉就行了，并且记得要置成空指针。
~list() { clear(); delete _head; _head = nullptr; } void clear() { iterator it = begin(); while (it != end()) { it = erase(it); // 返回删除位置的下一个结点 } }
再运行一下程序就崩溃了，虽然没报错，但是调试一下就报错了：
自动生成的拷贝构造是浅拷贝，为了解决这个问题，我们需要手动实现一个深拷贝的拷贝构造：
从C语言到C++_17(list的模拟实现)list不是原生指针的迭代器(下 ）：https://developer.aliyun.com/article/1521350
