目录

1、简单框架

1、list.h

2、test.cpp

2、list迭代器实现

1、list.h

2、test.cpp

3、思考

1、迭代器中的拷贝构造和赋值重载是否需要自己实现？析构呢？

2、体会类型的力量

3、const迭代器实现

1、list.h

2、test.cpp

4、重载迭代器的operator->

5、insert和erase接口实现

1、insert模拟实现

2、erase模拟实现

6、vector与list对比

1、vector

2、list

7、list拷贝构造、赋值重载问题

1、clear模拟实现

2、析构函数

3、深拷贝

1、传统写法

2、现代写法

8、迭代器区间和n个val初始化的构造函数冲突

1、问题

2、解决方法

9、反向迭代器模拟实现

1、简单框架

list的底层是一个双向带头循环链表

1、list.h

#pragma once
#include
using namespace std;namespace tutu
{templatestruct listNode{listNode* _next;listNode* _prev;T _data;listNode(const T& data=T()):_next(nullptr),_prev(nullptr),_data(data){}};templateclass list{typedef listNode Node;public:list():_head(new Node){_head->_next = _head;_head->_prev = _head;}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;}private:Node* _head;};void test1(){list l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);}
}

2、test.cpp

#include"list.h"int main()
{tutu::test1();return 0;
}

2、list迭代器实现

迭代器是像指针一样的类型，模仿指针的行为，解引用能取数据，++能到下一个位置。

在string和vector中，迭代器就是原生指针，因为他们底层是连续的物理空间；但是list底层物理空间不是连续的，如果还用原生指针，解引用是一个节点，++到不了下一个位置，但是C++提供了类，自定义类型可以对运算符进行重载，所以list底层迭代器的实现就是对节点指针进行封装，重载operator++、operator!=和operator*。

1、list.h

#pragma once
#include
using namespace std;namespace tutu
{templatestruct listNode{listNode* _next;listNode* _prev;T _data;listNode(const T& data=T()):_next(nullptr),_prev(nullptr),_data(data){}};templatestruct __list_iterator{typedef listNode Node;Node* _node;__list_iterator(Node* node):_node(node){}//++it__list_iterator& operator++(){_node = _node->_next;return *this;}//it++__list_iterator operator++(int){__list_iterator tmp(*this);_node = _node->_next;return tmp;}//--it__list_iterator& operator--(){_node = _node->_prev;return *this;}//it--__list_iterator operator--(int){__list_iterator tmp(*this);_node = _node->_prev;return tmp;}T& operator*(){return _node->_data;}bool operator!=(const __list_iterator& it) const{return _node != it._node;}bool operator==(const __list_iterator& it) const{return _node == it._node;}};templateclass list{typedef listNode Node;public:typedef __list_iterator iterator;iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}list():_head(new Node){_head->_next = _head;_head->_prev = _head;}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;}private:Node* _head;};void test1(){list l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);l1.push_back(5);list::iterator it = l1.begin();while (it != l1.end()){cout << *it << " ";++it;}cout << endl;}
}

2、test.cpp

#include"list.h"int main()
{tutu::test1();return 0;
}

3、思考

1、迭代器中的拷贝构造和赋值重载是否需要自己实现？析构呢？

答：都不需要。这里就是需要浅拷贝，默认生成的即可。迭代器中虽然有一个节点指针的成员，但是这个成员不归迭代器管，迭代器的意义就是访问和修改容器的。迭代器是借助节点的指针访问修改链表，节点是属于链表的，不属于迭代器，所以不归它管释放。

2、体会类型的力量

Node*原生指针和一个迭代器对象，它们占用的空间是一样大的，在32位机器上都是4个byte，并且值存的也一样，但是对他们使用运算符的意义和结果是不一样的。

3、const迭代器实现

普通对象调普通迭代器，const对象调const迭代器，目前我们只实现了普通迭代器，const迭代器还需要再写一份，传统的写法是再写一份const版本的迭代器，但是这样会造成代码冗余，这里推荐高手写法，即stl底层实现写法。

比较一下普通迭代器和const迭代器的区别，普通迭代器可读可写，const迭代器只能读不能写，体现到代码层面上就是operator*，一个是返回引用，一个是返回const引用，所以这里用了一个模板参数解决这个问题。

1、list.h

#pragma once
#include
using namespace std;namespace tutu
{templatestruct listNode{listNode* _next;listNode* _prev;T _data;listNode(const T& data=T()):_next(nullptr),_prev(nullptr),_data(data){}};templatestruct __list_iterator{//因为增加了一个模板参数，所以下面的类型都要改，所以增加一个typedeftypedef __list_iterator self;typedef listNode Node;Node* _node;__list_iterator(Node* node):_node(node){}//++itself& operator++(){_node = _node->_next;return *this;}//it++self operator++(int){__list_iterator tmp(*this);_node = _node->_next;return tmp;}//--itself& operator--(){_node = _node->_prev;return *this;}//it--self operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}Ref operator*(){return _node->_data;}bool operator!=(const self& it) const{return _node != it._node;}bool operator==(const self& it) const{return _node == it._node;}};templateclass list{typedef listNode Node;public:typedef __list_iterator iterator;typedef __list_iterator const_iterator;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(){return iterator(_head);}list():_head(new Node){_head->_next = _head;_head->_prev = _head;}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;}private:Node* _head;};void Print_list(const list& lt){list::const_iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;}void test1(){list l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);l1.push_back(5);Print_list(l1);}
}

2、test.cpp

#include"list.h"int main()
{tutu::test1();return 0;
}

4、重载迭代器的operator->

前面都是对list举例，链表中放整形，如果是放一个自定义类型，那么cout<<*it 时就会出问题，例如：list，解引用是一个Date类，需要对流提取进行重载，如果不想重载可以如图：

迭代器是像指针一样的类型，所以可以对operator->进行重载，可以得到如下代码：

在__list_iterator中，对operator->进行重载，如：

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

注意：

然后对于operator->的返回值和operator*有着相同的问题，普通迭代器返回Date*，const迭代器返回const Date*，所以上述不能给T*，这里建议新增模板参数Ptr，传参时，普通迭代器传T*，const迭代器传const T*，如：

#pragma once
#include
using namespace std;namespace tutu
{templatestruct listNode{listNode* _next;listNode* _prev;T _data;listNode(const T& data=T()):_next(nullptr),_prev(nullptr),_data(data){}};templatestruct __list_iterator{//因为增加了一个模板参数，所以下面的类型都要改，所以增加一个typedeftypedef __list_iterator self;typedef listNode Node;Node* _node;__list_iterator(Node* node):_node(node){}//++itself& operator++(){_node = _node->_next;return *this;}//it++self operator++(int){__list_iterator tmp(*this);_node = _node->_next;return tmp;}//--itself& operator--(){_node = _node->_prev;return *this;}//it--self operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const self& it) const{return _node != it._node;}bool operator==(const self& it) const{return _node == it._node;}};templateclass list{typedef listNode Node;public:typedef __list_iterator iterator;typedef __list_iterator const_iterator;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(){return iterator(_head);}list():_head(new Node){_head->_next = _head;_head->_prev = _head;}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;}private:Node* _head;};struct Date{int _year;int _month;int _day;Date(int year = 1,int month = 1,int day=1):_year(year),_month(month),_day(day){}};void Print_list2(const list& lt){list::const_iterator it = lt.begin();while (it != lt.end()){cout << it->_year << "/" << it->_month << "/" << it->_day << endl;++it;}cout << endl;}void test2(){list l1;l1.push_back(Date(2022, 11, 23));l1.push_back(Date(2022, 11, 24));l1.push_back(Date(2022, 11, 25));l1.push_back(Date(2022, 11, 26));Print_list2(l1);}
}

5、insert和erase接口实现

1、insert模拟实现

有了insert，push_back和push_front可以复用：

2、erase模拟实现

有了erase，pop_back和pop_front就可以复用：

6、vector与list对比

1、vector

vector是连续的物理空间，是优势，也是劣势。

优势：支持高效的随机访问。

劣势：1、空间不够要增容，增容代价比较大  2、可能存在一定的空间浪费，按需申请，会导致频繁增容，所以都会扩2倍左右  3、头部或中部插入删除需要挪动数据，效率低下

2、list

list很好解决了vector以上的问题

1、按需申请释放空间  2、list任意位置支持O(1)插入删除

小结：vector和list是互补的两个数据结构。

7、list拷贝构造、赋值重载问题

1、clear模拟实现

2、析构函数

3、深拷贝

1、传统写法

2、现代写法

1、支持迭代器区间初始化的构造函数

2、拷贝构造

3、赋值重载

8、迭代器区间和n个val初始化的构造函数冲突

1、问题

n个val初始化的构造函数：

目前我们的代码中，已经写了支持一段迭代器区间初始化和n个val初始化的构造函数，但是当写以下代码时，编译器会报错：

这就是经典的，迭代器区间初始化和n个val初始化的构造函数的冲突问题：

小结：1、整形的字面常量默认为int类型的，浮点数的字面常量默认为double类型。  2、编译器匹配的原则：只会找更匹配的。

2、解决方法

法一：将size_t  n改为int  n

法二：提供一个int  n的重载版本

9、反向迭代器模拟实现

反向迭代器跟正向迭代器的区别就是++、--的方向是反的，所以反向迭代器封装正向迭代器即可，控制重载++、--的方向。

list库里的底层rbegin、rend跟begin、end是对称的。所以operator*取前一个位置，主要就是为了让反向迭代器开始和结束跟正向迭代器对称。

因为反向迭代器是对正向迭代器的一个封装，所以可以做成模板，iterator是哪个容器的迭代器，reverse_iterator就可以适配出那个容器的反向迭代器，这是复用的体现。

reverse_iterator.h

#pragma once
namespace tutu
{templateclass reverse_iterator{typedef reverse_iterator self;public:reverse_iterator(Iterator it):_it(it){}//++ritself operator++(){--_it;return *this;}//--ritself operator--(){++_it;return *this;}bool operator!=(const self& rit) const{return _it != rit._it;}Ref operator*(){Iterator prev = _it;return *--prev;}Ptr operator->(){return &operator*();}private:Iterator _it;};
}

在list.h中包一下上述头文件，再增加两行typedef，就可以实现反向迭代器

我们这里有三个模板参数，而库里只有一个，这里是做了简化，因为库里的比较麻烦。

注意：

1、一个类里面要取它里面的东西，只能取它的成员变量和内嵌类型，模板参数可通过typedef取到。 

2、要取模板参数中的内嵌类型，编译器这里肯定是通不过的，因为编译器编译到这里还没有实例化，凡是要取一个模板参数里的内嵌类型（内部类或typedef的），加个typename是告诉编译器，它是一个类型，先让它通过，等实例化时，再去找它里面的类型。

3、如果上述按照库中实现，定义一个模板参数，在__list_iterator定义了内嵌类型，但是vector、string就不能直接套，它们底层是原生指针，不是自定义类型，所以还是三个模板参数比较好。vector的迭代器是原生指针，无法取内部类型，那么上面的实现就完了，stl源代码中是使用了一个叫迭代器萃取的技术解决的。