目录

一、list的介绍

二、list的排序

三、迭代器

1、list的迭代器失效问题

2、迭代器的功能分类

3、list迭代器的模拟实现

3.1普通迭代器

3.2const迭代器

3.3反向迭代器

4、迭代器价值

5、迭代器operator->的重载

四、模拟实现时遇到的困惑及注意点

1、调用拷贝构造时，链表内节点数据为什么已经是深拷贝了？

2、类名和类型的区别

五、vector和list的优缺点

1、vector

2、list

六、模拟实现list整体代码

一、list的介绍

列表是一种顺序容器，它允许在序列中的任何位置执行常量时间插入和删除操作，并允许在两个方向上进行迭代。

它的底层是一个带头双向循环链表。附一篇博主用C语言写的带头双向循环链表：【数据结构】带头双向循环链表的实现

二、list的排序

list不能用算法库的sort进行排序。算法库中的sort的底层是一个快排，需满足三数取中，需要传入随机访问迭代器，所以list并不适用。

当然list中提供了一个自己的sort，它的底层是一个归并排序。但是这个sort比vector使用算法库的sort还慢，甚至比list的数据先push_back到vector到再用算法库的sort还要慢。

三、迭代器

1、list的迭代器失效问题

insert，迭代器不失效

earse失效

2、迭代器的功能分类

1、单向迭代器：只能++，不能–。例如单链表，哈希表；

2、双向迭代器：既能++也能–。例如双向链表；

3、随机访问迭代器：能++–，也能+和-。例如vector和string。

迭代器是内嵌类型（内部类或定义在类里）

3、list迭代器的模拟实现

3.1普通迭代器

迭代器的实现需要支持解引用（为了取数据），支持++–。

博主模拟实现string和vector时，直接将原生指针typedef成迭代器，是因为数组的结构正好满足迭代器的行为（注：string和vector可以用原生指针实现，但是vs中采用自定义类型封装的方式实现），但是list中的节点地址是不连续的，不能使用原生指针，需要使用类进行封装+运算符重载实现。

//用类封装迭代器template struct __list_iterator{typedef list_node node;//用节点的指针进行构造__list_iterator(node* p):_pnode(p){}//迭代器运算符的重载T& operator*(){return _pnode->_data;}__list_iterator& operator++()//返回值不要写成node* operator++()，因为迭代器++肯定返回迭代器啊，你返回节点指针类型不对{ //return _pnode->_next;_pnode=_pnode->_next;return *this;//返回的是迭代器}bool operator!=(const __list_iterator& it){return _pnode != it._pnode;}public:node* _pnode;//封装一个节点的指针};

3.2const迭代器

const迭代器的错误写法：

typedef __list_iterator iterator;const list::iterator it=lt.begin();

因为typedef后，const修饰的是迭代器it，只能调用operator*(),调不了operator++()。（重载operator++()为const operator++()也不行,因为const版本++还是改变不了）

正确写法：想实现const迭代器，不能在同一个类里面动脑筋，需要再写一个const版本迭代器的类。

//用类封装const迭代器template struct __list_const_iterator{typedef list_node node;//用节点的指针进行构造__list_const_iterator(node* p):_pnode(p){}//迭代器运算符的重载const T& operator*()const{return _pnode->_data;}__list_const_iterator& operator++()//返回值不要写成node*，因为迭代器++肯定返回迭代器啊，你返回节点指针类型不对{//return _pnode->_next;//返回类型错误的_pnode = _pnode->_next;return *this;//返回的是迭代器}__list_const_iterator& operator--(){_pnode = _pnode->_prev;return *this;}bool operator!=(const __list_const_iterator& it)const{return _pnode != it._pnode;}public:node* _pnode;//封装一个节点的指针};typedef __list_const_iterator const_iterator;

当然，这样写__list_iterator和__list_const_iterator这两个类会出现代码重复。STL库中是通过类模板多给一个参数来实现，这样，同一份类模板就可以生成两种不同的类型的迭代器（以下为仿STL库的模拟实现）：

//用类封装普通/const迭代器template struct __list_iterator{typedef list_node node;typedef __list_iterator Self;//用节点的指针进行构造__list_iterator(node* p):_pnode(p){}//迭代器运算符的重载Ref operator*(){return _pnode->_data;}Self& operator++()//返回值不要写成node*，因为迭代器++肯定返回迭代器啊，你返回节点指针类型不对{ //return _pnode->_next;//返回类型错误的_pnode=_pnode->_next;return *this;//返回的是迭代器}Self& operator--(){_pnode = _pnode->_prev;return *this;}bool operator!=(const Self& it){return _pnode != it._pnode;}public:node* _pnode;//封装一个节点的指针};typedef __list_iterator iterator;typedef __list_iterator const_iterator;

3.3反向迭代器

1、反向迭代器的底层

反向迭代器的本质就是对正向迭代器的封装，它是一个适配器。

STL源码中的反向迭代器的实现：反向迭代器用正向迭代器进行构造。

reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}

画个图，其实正向迭代器和反向迭代器的位置是对称的。

通过图示，rbegin()迭代器是最后一个数据的下一个位置，但是通过rbegin()访问的数据应该是4，这是通过运算符重载operator*()来解决。

template Ref operator*(){Iterator tmp = _it;return *--(tmp);}typedef ReserveIterator reverse_iterator;typedef ReserveIterator const_reverse_iterator;

2、反向迭代器的实现

namespace jly{template class ReserveIterator{public:ReserveIterator(Iterator it)//使用正向迭代器构造反向迭代器:_it(it){}Ref operator*(){Iterator tmp = _it;return *--(tmp);}Ptr operator->()//operator->()返回数据的地址{return &(operator*());}ReserveIterator& operator++()//返回值不要写成Iterator，因为反向迭代器++返回的是反向迭代器，不是传入的迭代器类型{--_it;return *this;}ReserveIterator& operator--(){++_it;return *this;}bool operator!=(const ReserveIterator& rit)const{return _it != rit._it;}private:Iterator _it;//底层是传入类型的迭代器};}

4、迭代器价值

1、封装底层实现，不暴露底层实现的细节；

2、多种容器提供统一的访问方式，降低使用成本；

C语言没有运算符重载和引用等语法，是实现不了迭代器的。

5、迭代器operator->的重载

迭代器的用法就是模拟指针的行为，如果现在有一个指向结构的指针，那么就需要用到->来解引用。

//*的重载：返回节点的数据Ref operator*(){return _pnode->_data;}//->的重载：返回数据的指针T* operator->(){return &_pnode->_data;}

但是operator->使用T*做返回值类型，这样无论是普通迭代器和const迭代器都能修改，所以operator->的返回值类型应该改为泛型：

template Ptr operator->(){return &_pnode->_data;}typedef __list_iterator iterator;typedef __list_iterator const_iterator;

四、模拟实现时遇到的困惑及注意点

1、调用拷贝构造时，链表内节点数据为什么已经是深拷贝了？

2、类名和类型的区别

普通类：类名等于类型

类模板：类名不等价于类型，例如list类模板类名是list,类型list等。

所以我们平常写函数形参和返回值时，总会带上形参和返回值的类型：

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

但是C++在类模板里面可以用类名代替类型：

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

建议写代码的时候严格区分类型和类名，让自己和别人能够看的很明白。（了解下C++有这种坑语法即可）

五、vector和list的优缺点

vector和list像左右手一样，是互补关系，缺一不可。vector的优点正是list的缺点，list的优点也是vector的缺点，实际选用容器时，按照需求择优选用。

1、vector

vector的优点（结构牛逼）：

1、支持下标的随机访问；

2、尾插尾删效率高（当然扩容的那一次尾插会较慢）；

3、CPU高速缓存命中高（数据从缓存加载至CPU中，会加载连续的一段数据，vector因为结构连续，高速缓存命中高）。

vector的缺点：

1、非尾插尾删效率低；

2、扩容有消耗，并存在一定的空间浪费。

vector迭代器失效问题：

insert/erase均失效。（如果string的insert和erase形参是迭代器，那么也会失效，但是大部分接口是下标传参，不考虑失效问题，只有几个接口是迭代器传参，需要注意迭代器失效问题）

2、list

list的优点：

1、按需申请释放，无需扩容；

2、任意位置插入删除时间O(1)；（这里说的是插入删除，不要加上查找的时间）

list的缺点：

1、不支持下标的随机访问；

2、CPU高速缓存命中率低；

3、每一个节点除了存储数据外，还需要额外存储两个指针。

list迭代器失效问题：

insert不失效，erase失效。

六、模拟实现list整体代码

#pragma once#include #include #include #include using std::cout;using std::endl;namespace jly{//链表节点的类template struct list_node{list_node(const T& x = T())//给一个缺省值，变成默认构造函数:_next(nullptr), _prev(nullptr), _data(x){}list_node* _next;list_node* _prev;T _data;};//用类封装普通/const迭代器template struct __list_iterator{typedef list_node node;typedef __list_iterator Self;//用节点的指针进行构造__list_iterator(node* p):_pnode(p){}//迭代器运算符的重载Ref operator*(){return _pnode->_data;}Ptr operator->(){return &_pnode->_data;}Self& operator++()//返回值不要写成node*，因为迭代器++肯定返回迭代器啊，你返回节点指针类型不对{//return _pnode->_next;//返回类型错误的_pnode = _pnode->_next;return *this;//返回的是迭代器}Self operator++(int)//后置++{_pnode = _pnode->_next;return Self(_pnode->_next);}Self& operator--(){_pnode = _pnode->_prev;return *this;}Self operator--(int)//后置--{_pnode = _pnode->_prev;return Self(_pnode->_prev);}bool operator!=(const Self& it)const{return _pnode != it._pnode;}bool operator==(const Self& it)const{return _pnode == it._pnode;}public:node* _pnode;//封装一个节点的指针};//用类封装const迭代器//template //struct __list_const_iterator//{//typedef list_node node;////用节点的指针进行构造//__list_const_iterator(node* p)//:_pnode(p)//{}////迭代器运算符的重载//const T& operator*()const//{//return _pnode->_data;//}//__list_const_iterator& operator++()//返回值不要写成node*，因为迭代器++肯定返回迭代器啊，你返回节点指针类型不对//{////return _pnode->_next;//返回类型错误的//_pnode = _pnode->_next;//return *this;//返回的是迭代器//}//__list_const_iterator& operator--()//{//_pnode = _pnode->_prev;//return *this;//}//bool operator!=(const __list_const_iterator& it)const//{//return _pnode != it._pnode;//}//public://node* _pnode;//封装一个节点的指针//};//用正向迭代器封装反向迭代器template class ReserveIterator{public:ReserveIterator(Iterator it)//使用正向迭代器构造反向迭代器:_it(it){}Ref operator*(){Iterator tmp = _it;return *--(tmp);}Ptr operator->()//operator->()返回数据的地址{return &(operator*());}ReserveIterator& operator++()//返回值不要写成Iterator，因为反向迭代器++返回的是反向迭代器，不是传入的迭代器类型{--_it;return *this;}ReserveIterator& operator--(){++_it;return *this;}bool operator!=(const ReserveIterator& rit)const{return _it != rit._it;}private:Iterator _it;//底层是传入类型的迭代器};//链表类（控制哨兵位）template class list{public:typedef list_node node;typedef __list_iterator iterator;typedef __list_iterator const_iterator;typedef ReserveIterator reverse_iterator;typedef ReserveIterator const_reverse_iterator;//typedef __list_const_iterator const_iterator;//构造函数void empty_initialize()//用于初始化哨兵位{_head = new node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(){empty_initialize();}template list(InputIterator first, InputIterator last)//迭代器区间构造{empty_initialize();while (first != last){push_back(*first);++first;}}//析构函数~list(){clear();delete _head;_head = nullptr;}//拷贝构造list(const list& lt){先初始化*this//empty_initialize();//for (const auto& e : lt)//取lt的数据给e//{//push_back(e);//}//工具人写法list tmp(lt.begin(),lt.end());empty_initialize();swap(tmp);}void swap(list& lt){std::swap(_head, lt._head);//交换头指针std::swap(_size,lt._size);}赋值运算符重载写法1//list& operator=(const list& lt)//{////防止自己给自己赋值//if (this != &lt)//{//clear();//for (const auto& e : lt)//{//push_back(e);//}//}//return *this;//}// 赋值运算符重载写法2(赋值运算符重载都可以这么干)list& operator=(list lt){swap(lt);//直接交换return *this;}//插入删除void push_back(const T& x){/*node* newNode = new node(x);node* tail = _head->_prev;newNode->_prev = tail;newNode->_next = _head;tail->_next = newNode;_head->_prev = newNode;*/insert(end(), x);}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& x){node* newNode = new node(x);node* prev = pos._pnode->_prev;node* cur = pos._pnode;newNode->_prev = prev;newNode->_next = cur;prev->_next = newNode;cur->_prev = newNode;//return iterator(newNode);pos._pnode = newNode;++_size;return pos;}iterator erase(iterator pos){assert(!empty());node* prev = pos._pnode->_prev;node* next = pos._pnode->_next;prev->_next = next;next->_prev = prev;delete pos._pnode;--_size;//return iterator(next);pos._pnode = next;return pos;}//链表小接口bool empty()const{return _head->_next == _head;}void clear(){/*assert(!empty);node* cur = _head->_next;while (cur != _head){node* next = cur->_next;delete cur;cur = next;}*/iterator it = begin();while (it != end()){it = erase(it);//erase返回删除元素的下一个}}size_t size()const{return _size;}//普通begin(),end()迭代器iterator begin(){//return iterator(_head->_next);return __list_iterator(_head->_next);}iterator end(){return __list_iterator(_head);}//const begin(),end()迭代器const_iterator begin()const{//return const_iterator(_head->_next);return __list_iterator(_head->_next);}const_iterator end()const{return __list_iterator(_head);}reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}private:node* _head;//哨兵位size_t _size;//用于统计节点个数，空间换时间//不加这个私有变量，统计节点个数时间O(N),有这个私有变量，时间O(1),但是每个节点的体积变大};//测试函数struct Pos{int _row;int _col;Pos(int row = 0, int col = 0):_row(row), _col(col){}};void test(){list i;i.push_back(Pos(1, 2));i.push_back(Pos(2, 5));i.push_back(Pos(4, 3));list::iterator it = i.begin();while (it != i.end()){cout <_row;//*it取数据，再取地址、解引用得到_row,多此一举cout <_row;//同第三种写法，编译器为了可读性，省略了一个->cout <()->_row;//it.operator->()是显示调用，->_row是解引用得到_rowit++;}}void test1(){list i;i.push_back(1);i.push_back(2);i.push_back(3);list::iterator it = i.begin();while (it != i.end()){cout << *it << " ";++it;}cout << endl;list::reverse_iterator rit = i.rbegin();while (rit != i.rend()){cout << *rit << " ";++rit;}}}