但事实上，我们在C/C++中有另一种方式：->即直接it->_row;下面的Ptr就是。

因此我们也需要考虑如何将这样的运算符也重载进去，只需要在类中再加一个模板参数，到现在三个模板参数，已经齐了。这也是我们最终的迭代器的类：

//typedef __list_iterator iterator;
//typedef __list_iterator const_iterator; 
template//模仿大佬在STL中的写法，能避免副本造成的代码冗余
struct __list_iterator//封装成类的迭代器
{typedef list_node node;typedef __list_iterator Self;node* _pnode;__list_iterator(node* p):_pnode(p){}// iterator it// *it// ++itRef operator*()//const迭代器看这个{return _pnode->_data;}Ptr operator->()//const迭代器看这个{return &_pnode->_data;}Self& operator++()//前置{_pnode = _pnode->_next;return *this;}Self& operator++(int)//后置  //自己加的，这里写成T对于自己加的Pos会报错{//Self it = *this;Self it(*this);_pnode = _pnode->_next;return it;}Self& operator--()//前置{_pnode = _pnode->_prev;return *this;}bool operator!=(const Self& it) const{return _pnode != it._pnode;}bool operator==(const Self& it) const{return _pnode == it._pnode;}
};

但意的是，->返回的值仍然是一个指针，那我们调用时确是一个函数：那返回时不应该是it->->_row吗？

这是因为编译器做了一定程度的优化，将两个->变成了一个，因此，我们直接写成两个->也是对的。

这样就完成了我们整个迭代器类的封装。

3. list模拟实现完整代码

下面就看看整体的代码，个人感觉只有这样整体观察才能理解更多·。因为一些比如push_back、push_front、pop_back、pop_front我们在实现string、vector的时候已经描述过，都是以复用的形式出现的，整体看才会明白。

3.1 list.h

#pragma oncenamespace cfy
{templatestruct list_node{list_node* _next;//不加也没错，但是写上好一些list_node* _prev;T _data;list_node(const T& x)//构造:_next(nullptr), _prev(nullptr), _data(x){}};//typedef __list_iterator iterator;//typedef __list_iterator const_iterator; template//模仿大佬在STL中的写法，能避免副本造成的代码冗余struct __list_iterator//封装成类的迭代器{typedef list_node node;typedef __list_iterator Self;node* _pnode;__list_iterator(node* p):_pnode(p){}// iterator it// *it// ++itRef operator*()//const迭代器看这个{return _pnode->_data;}Ptr operator->()//const迭代器看这个{return &_pnode->_data;}那么能不能重载一个T&？ 像下面： const iterator*it++it 不能调++了，因为const不能调用非const，那这个时候可不可以将++的运算符继续重载？ 不能，++是写的函数，不可能把他变成const， 因此像下面这样重载，可以解引用，但是不能++， 所以换思路，可以将迭代器这整个类再写一个const版本的出来，就是会产生代码冗余//const T& operator*() const//{//	return _pnode->_data;//}Self& operator++()//前置{_pnode = _pnode->_next;return *this;}Self& operator++(int)//后置  //自己加的，这里写成T对于自己加的Pos会报错{//Self it = *this;Self it(*this);_pnode = _pnode->_next;return it;}Self& operator--()//前置{_pnode = _pnode->_prev;return *this;}bool operator!=(const Self& it) const{return _pnode != it._pnode;}bool operator==(const Self& it) const{return _pnode == it._pnode;}};templateclass list{typedef list_node node;public:typedef __list_iterator iterator;typedef __list_iterator const_iterator; //虽然是一个类模板，但是T不同就不是一个类const_iterator begin() const{return const_iterator(_head->_next);}const_iterator end() const{return const_iterator(_head);}iterator begin(){return iterator(_head->_next);}iterator end(){//iterator it(_head);//return it;//直接利用匿名对象更为便捷return iterator(_head);}void empty_initialize(){_head = new node(T());_head->_next = _head;_head->_prev = _head;_size = 0;//实现计算动态大小}list() // 不是list的原因：构造函数和类名相同，和类型list不同{empty_initialize();}~list(){clear();delete _head;_head = nullptr;}lt2(lt1)  传统写法//list(const list& lt)//实现const迭代器之后就没有错误了//{//	empty_initialize();//	for (const auto& e : lt)//	{//		push_back(e);//	}//}//list& operator=(const list& lt)//实现const迭代器之后就没有错误了//{//	if (this != <)//	{//		clear();//		for (const auto& e : lt)//		{//			push_back(e);//		}//	}//	return *this;//}void swap(list& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}template list(InputIterator first, InputIterator last)//迭代器区间构造，和vector的对应{empty_initialize();while (first != last){push_back(*first);++first; //first++;}}// 拷贝构造的现代写法list(const list& lt)//list(const list& lt) 官方库是这样写的，也可以，语法设计问题，但是不建议自己这样写{empty_initialize();//初始化头结点，防止交换后tmp野指针不能正常的调用析构 list tmp(lt.begin(), lt.end());swap(tmp);}//lt3 = ltlist& operator=(list lt)//不能加引用，lt是调用拷贝构造生成的//list& operator=(list lt) 官方库是这样写的，也可以{swap(lt);return *this;}size_t size() const//增加一个计数的成员，以空间换时间{return _size;}bool empty(){return _size == 0;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}_size = 0;}void push_back(const T& x){/*node* newnode = new node(x);node* tail = _head->_prev;tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;*/insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_front(){erase(begin());}void pop_back(){erase(--end());}iterator insert(iterator pos, const T& x){node* newnode = new node(x);node* cur = pos._pnode;node* prev = cur->_prev;prev->_next = newnode;newnode->_prev = prev;cur->_prev = newnode;newnode->_next = cur;++_size;return iterator(pos);}iterator erase(iterator pos){assert(pos != end());node* prev = pos._pnode->_prev;node* next = pos._pnode->_next;prev->_next = next;next->_prev = prev;delete pos._pnode;--_size;return iterator(next);}private:node* _head;size_t _size;};void test_list1(){list lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.insert(++lt.begin(), 10);//iterator 1、内嵌类型 2、像指针一样list::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;for (auto e : lt){cout << e << " ";}cout << endl;}void test_list2(){list lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_front(10);lt.push_front(20);lt.push_front(30);lt.pop_back();lt.pop_back();lt.pop_back();lt.pop_front();lt.pop_front();for (auto e : lt){cout << e << " ";}cout << endl;}void test_list3(){list lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);for (auto e : lt){cout << e << " ";}cout << endl;list lt1(lt);//默认是浅拷贝,指向同一块lt.pop_back();lt.pop_back();for (auto e : lt1){cout << e << " ";}cout << endl;list lt3 = lt1;for (auto e : lt3){cout << e << " ";}}//const T* p1//T* const p2;//const迭代器类似p1的行为，保护指向的对象不被修改，迭代器本身可以修改//void print_list(const list& lt)//{//	//const list::iterator cit = lt.begin();//	//不符合const迭代器的行为，因为他保护迭代器本省不能修改，那么我们也就不能用++迭代器//}//void print_list(const list& lt)//{//	list::const_iterator it = lt.begin(); //重载了，找的另一个类的迭代器//	while (it != lt.end())//	{//		(*it) += 2;//不能写//		cout << *it << " ";//		++it;//	}//	cout << endl;//}void test_list4(){list lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list::iterator it = lt.begin();while (it != lt.end()){(*it) += 2;cout << *it << " ";++it;//it++;}cout << endl;//print_list(lt);list lt1(lt);for (auto e : lt1){cout << e << " ";}cout << endl;list lt2 = lt;for (auto e : lt2){cout << e << " ";}cout << endl;cout << lt.size() << endl;}struct Pos{int _row;int _col;Pos(int row=0, int col=0):_row(row),_col(col){}};void print_list(const list& lt){list::const_iterator it = lt.begin(); //重载了，找的另一个类的迭代器while (it != lt.end()){//it->_row++;  增加第三个模板参数cout << it->_row << ":" << it->_col << endl;++it;}cout << endl;}void test_list5(){list lt;Pos p1(1, 1);lt.push_back(p1);lt.push_back(p1);lt.push_back(p1);lt.push_back(Pos(2, 3));lt.push_back(Pos(2, 3));list::iterator it = lt.begin();while (it != lt.end()){//cout << (*it)._row << ":" << (*it)._col << endl;cout << it->_row << ":" << it->_col << endl;//编译器为了可读性，做了特殊处理，省略了一个->,//那么省略之前应该是it->->_row//cout << it.operator->()->_col << ":" << it.operator->()->_row << endl;++it;}cout << endl;print_list(lt);}
}//实现const迭代器的两种方法：
// 1. 重新写一个类，里面只有一个函数是不一样的，目的为了const
// 2. 利用模板！// 类名和类型的问题：
// 普通类  类名 等价于 类型
// 类模板  类名 不等价于 类型
// 如： list模板 类名list 类型list
// 类模板里面可以用类名代表类型，但是不建议那么用//vector和list对比：
//vector优点：
//1、下标随机访问
//2、尾插尾删效率高（但不明显）
//3、CPU高速缓存命中率高：因为物理空间连续
//
//vector缺点：
//1、前面部分插入删除效率低
//2、扩容有消耗，还存在一定空间浪费，扩容开多了浪费，开少了频繁扩容
//
//list优点：
//1、按需申请释放，无需扩容
//2、任意位置插入删除O(1)，前提是已经知道这个位置了，查找是O(n)
//
//list缺点：
//1、不支持下标的随机访问
//2、CPU高速缓存命中率低
//
//
//总结：vector和list不是敌对关系，而是互补配合//总结迭代器失效问题：
//vector -> insert/erase
//list   -> erase
//
//string有没有迭代器失效？->insert/erase失效，和vector类似
//但一般不关注string的迭代器失效，因为string insert/erase常用接口函数都是下标支持，迭代器支持用的很少

3.2 Test.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include
#include
#include
#include
#include
using namespace std;
#include"list.h"void test_list1()
{list lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";it++;}cout << endl;lt.push_front(10);lt.push_front(20);lt.push_front(30);lt.push_front(40);for (auto e : lt){cout << e << " ";}cout << endl;lt.pop_back();lt.pop_back();lt.pop_front();lt.pop_front();for (auto e : lt){cout << e << " ";}cout << endl;
}void test_list2()
{list lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);auto pos = find(lt.begin(), lt.end(), 3);if (pos != lt.end()){//insert之后pos是否失效呢？不失效,因为链表不存在挪动空间和扩容的问题lt.insert(pos, 30);}cout << *pos << endl;//(*pos)++;for (auto e : lt){cout << e << " ";}cout << endl;lt.erase(pos);//erase之后，pos就失效了，因为空间都被干掉了//cout << *pos << endl;for (auto e : lt){cout << e << " ";}cout << endl;}//Operations:
void test_list3()
{list lt;lt.push_back(1);lt.push_back(2);lt.push_back(5);lt.push_back(3);lt.push_back(4);lt.push_back(4);lt.push_back(4);lt.push_back(5);lt.push_back(6);lt.push_back(7);lt.push_back(6);for (auto e : lt){cout << e << " ";}cout << endl;lt.remove(3);lt.remove(30);for (auto e : lt){cout << e << " ";}cout << endl;lt.sort();//迭代器·功能分类//1、单向 ++ //2、双向 ++ -- list//3、随机 + -for (auto e : lt){cout << e << " ";}cout << endl;//去重：建立在有序的基础上lt.unique();for (auto e : lt){cout << e << " ";}cout << endl;}void test_op()
{srand(time(0));const int N = 10000000;vector v;v.reserve(N);list lt1;list lt2;for (int i = 0; i < N; ++i){auto e = rand();//v.push_back(e);lt1.push_back(e);lt2.push_back(e);}// 拷贝到vector排序，排完以后再拷贝回来int begin1 = clock();for (auto e : lt1){v.push_back(e);}sort(v.begin(), v.end());size_t i = 0;for (auto& e : lt1){e = v[i++];}int end1 = clock();int begin2 = clock();// sort(lt.begin(), lt.end());lt2.sort();int end2 = clock();printf("vector sort:%d\n", end1 - begin1);printf("list sort:%d\n", end2 - begin2);
}int main()
{//test_op();cfy::test_list5();return 0;
}

下面也是上述代码实现的链接。

C++/list模拟实现最终版 · 蓝桉/CPP - 码云 - 开源中国 (gitee.com)

4. 模拟实现的注意事项

4.1 深拷贝的问题

对于vector，我们知道有深浅拷贝的问题，即浅拷贝会造成析构两次导致出现错误，但我们此次的list实现方式，则不存在这种问题：

4.2 类名和类型的问题

普通类： 类名等价于类型

类模板： 类名不等于类型

举例：list模板类名为list，但是实际上的类型是list，这两个在具体函数返回值还是有区别的，但是在类模板里面可以直接用类名来代替类型，不过不建议这么用，因为对其他人不好理解。举个例子看看。

例1：

就是我们节点类这里，指针直接不写也是可以的。

例2： 这个就看代码吧

// 赋值运算符重载
list& operator=(list lt)
{swap(lt);return *this;
}

也就是说这个在类中也可以变成这样，这也是正确的：

// 赋值运算符重载写法2(赋值运算符重载都可以这么干)
list& operator=(list lt)
{swap(lt);return *this;
}

5. vector与list的优缺点

1. vector优点与缺点

优点：

• 支持下标随机访问。
• 尾删尾插效率高（但不明显）。
• CPU高速缓存命中率高：因为物理空间连续。

缺点：

• 前面部分插入删除效率低。
• 扩容有消耗，还存在一定的空间浪费，扩容开多了浪费，开少了浪费空间。

2. list优点与缺点

优点：

• 按需申请释放，无需扩容。
• 任意位置插入删除是O(1)，前提是已经知道这个位置了，查找是O(n)。

缺点：

• 不支持下标的随机访问
• CPU高速缓存命中率低

因此vector与list不是相互替代的关系，而是互补配合。