先申明一下本篇总体介绍过程是按照逐步深入去写的,所以可能有些同样类型不在一块!
前言:
写这篇博客的时候,我是边思考边写它!自己其中感觉自己对于list的理解更加的深入,其中提出的很多问题让我明白了list为什么要这么设计,以及代码为啥要这么写!希望我的这篇博客不仅让我受益匪浅,也能对你有所帮助!若您发现了其中有什么地方有问题,希望评论区您能提出来。如果你有更好的理解思路,也希望您能不吝赐教!最后写博客不易,还望给一个赞!
💡💡追着光,跟着光,成为光,发散光!
目录
💡💡3.1.2 返回(非const)迭代器的begin() end()
3.2.1 insert() 任意位置插入 (往指定位置的前面插入)
3.2.2 erase() 任意位置删除结点 ( 迭代器失效问题)
1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。
2. list的底层是带头双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素。
3. 与其他的序列式容器相比(array,vector,deque),list通常在任意位置进行插入、移除元素的执行效率更好。
4. 与其他序列式容器相比,list最大的缺陷是不支持任意位置的随机访问,比如:要访问list的第6个元素,必须从已知的位置(比如头部或者尾部)迭代到该位置,在这段位置上迭代需要线性的时间开销;list还需要一些额外的空间,以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

💡强调一下head是哨兵结点,本身不存储数据,作用只是指向头和尾!
- //结点
- template<class T>
- struct list_node
- {
- //结点构造函数
- list_node(const T& val = T())
- :prev(nullptr)
- , next(nullptr)
- , data(val)
- {}
- public:
- list_node* prev;//接前
- list_node* next;//接后
- T data;//存储数据
- };
这里对于T()说明一下!这里是匿名构造,对于传来的参数类型不确定,可能是内置类型,也可能是类对象!所以不能想当然比如说默认赋值0!
- template<class T,class ref,class ptr>
- struct list_iterator
- {
- typedef list_node<T> node;
- typedef list_iterator<T, ref, ptr> Self;
-
- node* pnode;
- list_iterator(node* p)
- :pnode(p)
- {}
-
-
- ref operator*()
-
- ptr operator->()
-
- //前置
- Self& operator++()
-
- //后置
- Self operator++(int)
-
- //前置
- Self& operator--()
-
- //后置
- Self operator--(int)
-
- bool operator!=(const Self& it)
-
- bool operator==(const Self& it)
-
- };
- class list
- {
-
- public:
- typedef list_node<T> node;
- typedef list_iterator<T,T&,T*> iterator;
- typedef list_iterator<T, const T&,const T*> const_iterator;
- iterator begin()
-
- const_iterator begin()const
-
- const_iterator end()const
-
- iterator end()
-
- void clear()
-
- ~list()
-
- void empty_initialize()
-
- list()
-
- template <class InputIterator>
- list(InputIterator first, InputIterator end)
-
- void swap(list<T>& lt)
-
- list(const list<T>& lt)
-
- list<T>& operator=(list<T> tmp)
-
- void push_back(const T& x)
-
- void push_front(const T& x)
-
- void pop_front()
-
- void pop_back()
-
- void insert(iterator pos,const T& x)
-
- iterator erase(iterator pos)
-
- private:
- node* head;//底层是一个哨兵结点
- };
这里问一个问题,等你看完这篇文章理解很多的时候,回来比较这三个类的是否手动析构,手动写拷贝构造!深入自己想想为啥是上面的结果!
这些函数是后面写的基础!后面会频繁调用,所以先写出来!
💡强调一下head是哨兵结点,本身不存储数据,作用只是指向头和尾!
后面要多次用到这个empty_initialize()内代码 ,所以就用函数了!
- void empty_initialize()
- {
- head = new node;//用new对象,可以直接调用对象的构造函数
- head->next = head;
- head->prev = head;
- }
- list()
- {
- empty_initialize();
- }
首先我们需要将封装的迭代器需要实现的功能函数写好!
❓❓首先我们要问自己一个问题,链表的迭代器能不能像vector string 那样直接单纯地用解引用和++?
我们不妨回顾一下vector string 的迭代器,其底层是指针数组的原生指针!而它们容器的存储空间是连续的,解引用可以直接拿到数组数据,++可以直接加上类型的步长!
而list的呢?list是不连续的!它们通过前后指针链接!直接++不能找到后一个结点!解引用不是直接拿到存储数据,而是一个结点结构体!我们需要的是里面的Data!
怎么办? 系统的* ++ 不能满足我们需要的结果!
💡必须重载运算符!所以我们得将迭代器封装成一个类!
现在再问自己一个问题! 他的类成员变量是谁? 联系一下我们的目的和链表容器结构!
我们想到一个指向node 的指针就可以解决了,++不就是next,--不就是prev *不就是data!
!这里单独将->符号拿出来说明一下! 想用->访问数据,->左边是什么? 是结构体地址!
也就是说如果我们list 存储的数据是结构体或者类!里面有多个变量,那么我们访问数据就不能单纯的解引用!必须使用->来访问数据!
下面上代码~
- template<class T>
- struct list_iterator
- {
- typedef list_node<T> node;//结点类
- typedef list_iterator<T> Self;//迭代器类
-
- node* pnode;//成员变量
-
- //构造函数
- list_iterator(node* p)
- :pnode(p)
- {}
-
- T& operator*()
- {
- return pnode->data;
- }
-
- T* operator->()
- {
- return &pnode->data;//返回结构体地址
- }
-
- Self& operator++()
- {
- pnode = pnode->next;
- return *this;
- }
-
- Self& operator--()
- {
- pnode = pnode->prev;
- return *this;
- }
-
- bool operator!=(const Self& it)
- {
- return pnode != it.pnode;
- }
- };
现在迭代器功能基本完善!我们通过链表函数构建迭代器!
- //再强调一下,迭代器被封装成类!!!
- typedef list_iterator<T> iterator;
-
- iterator begin()
- {
- //匿名对象返回!这里调用了迭代器的构造函数
- return iterator(head->next);
- }
-
- iterator end()
- {
- //这里千万记住,返回的是哨兵结点!不是尾结点!
- return iterator(head);
- }
现在看看如何使用迭代器!

迭代器是一种可以遍历数组的抽象接口!
1.封装底层实现,不暴露底层实现原理
2.有了迭代器,可以不关心底层实现原理,而是注重使用!
我们上面用的*符号,看似简单几个字母,可底层却是返回Data!我们不需要知道它返回的具体是什么,我们只要知道*符号代表着就是获取容器数据的方式!
类封装价值是什么?
1.因为不同容器实现原理不同,vector,list同样是*符号,对于vector,*号是原生指针!解引用可以直接获取数据,但是对于list,解引用实现不了我们直接获取数据的方法!(前面说过)有了类封装,我们就可以重载*号,让它的意义改变!有了封装,让我们使得同样的符号,对于不同实现原理的容器,可以有同样的效果!
2.我们可以注意到,即使是封装了迭代器,它的物理消耗内存仍只有一个指针大小!也就是说即使是类,他没有过多消耗内存!
有了迭代器,它的成员变量是指向结点的指针,所以我们可以用迭代器获取结点位置!
参数为迭代器头尾和要查找的数据!

- void 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;
- }
- iterator erase(iterator pos)
- {
- node* cur = pos.pnode;
- node* prev = cur->prev;
- node* next = cur->next;
- prev->next = next;
- next->prev = prev;
- delete[]cur;//delete会调用结点类的默认析构函数
- //!!!返回下一个位置的迭代器
- return iterator(next);
- }
为什么会有迭代器失效问题? 因为结点空间被释放了,这样迭代器++也就不能找到下一个位置结点,所以返回需要返回下一个结点迭代器!
- void push_back(const T& x)
- {
- insert(end(), x);
- }
这里提一嘴,注意前后两者区别,前面不--end() 因为插入是插在结点前一个!end()返回哨兵结点,插在它的前一个就是尾结点!
这里尾删,删的是尾结点,所以--迭代器重载返回前一个结点,也就是尾结点!
- void pop_back()
- {
- erase(--end());
- }
- void push_front(const T& x)
- {
- insert(begin(), x);
- }
- void pop_front()
- {
- erase(begin());
- }

- template <class InputIterator>
- list(InputIterator first, InputIterator end)
- {
- empty_initialize();//构建哨兵结点
- while (first != end)
- {
- push_back(*first);
- ++first;
- }
- }
1.先构造临时链表tmp(深拷贝!)->> 2. 临时链表与拷贝构造链表交换!
那么如何交换两个链表? 很简单就是交换两个链表的哨兵结点!
- //list<T> lt2(lt1)
- void swap(list<T>& lt)
- {
- std::swap(head, lt.head);//交换地址
- }
- list(const list<T>& lt)
- {
- empty_initialize();//注意我们必须初始化lt2的哨兵结点!这样tmp析构的时候析构的不是野指针!
- list<T> tmp(lt.begin(), lt.end());
- swap(tmp);
- }
首先说明一下,为什么从这里引入const 迭代器,因为注意一下这个拷贝构造的传参,是const list
& ,我们在用迭代器构造tmp的时候,传的 lt 是const的!所以我们要实现const 迭代器!
首先我们得明确一下const迭代器const的作用,这个const保护的是Data!也就是说数据只可读,不可写!迭代器解引用不能算数运算!迭代器本身可以++!
如何实现const迭代器?
先思考一下下面这个写法能不能实现我们要的const迭代器
现在看看这样的 rit 能干什么:
我们看到它不能++,它可以解引用算数运算!它是const迭代器吗?当然不是!通过结果我们不难可以类比原来的内置类型 这样写法相当于 int const * 而我们需要的是 const int* !
所以我们仍需要自己写一个const迭代器!
我们在明确一下const 迭代器与非const 迭代器的主要区别就在* 后是可读可写,还是只可读!也就是返回值一个是const T,一个是T!
💡💡那这就很简单了,那不就是我们在原来普通迭代器基础上重载一个*号运算符重载函数,如下:
template<class T> struct list_iterator { typedef list_node<T> node;//结点类 typedef list_iterator<T> Self;//迭代器类 ..../之前上面写的普通迭代器函数 const T& operator*()const { return pnode->data; } };可是这样真的行吗?这样解决了当前的问题,可是我const迭代器想要调用普通迭代器其他接口函数怎么办?有人又会说了那每一个都重载一下呗!每一个函数都弄一个const!
比如 之前的++,写成如下:
那么请问,如果这样写了会有什么后果!我们来看看!
因为const 修饰了this指针,所以我们不能改变this指向的类对象成员函数 !
可是我们const迭代器只需要对* 做修改!所以这种只在原迭代器补const重载函数,行不通!
那么引入第三种想法(一般人),我们可以重新写一个const迭代器类封装它,类中与原来普通迭代器不同的就是*号 重载函数!
//在list类中定义const迭代器 typedef const_list_iterator<T> const_iterator; //const迭代器类 template<class T> struct const_list_iterator { typedef list_node<T> node;//结点类 typedef const_list_iterator<T> Self;//迭代器类 node* pnode;//成员变量 //构造函数 list_iterator(node* p) :pnode(p) {} //唯一区别地方 const T& operator*() { return pnode->data; } T* operator->() { return &pnode->data;//返回结构体地址 } Self& operator++() { pnode = pnode->next; return *this; } Self& operator--() { pnode = pnode->prev; return *this; } bool operator!=(const Self& it) { return pnode != it.pnode; } };
现在我们看看C++设计者大佬的写法!它们的写法就是一行代码能解决的事绝不用多行!
之前我们先引入一个问题,模板类 类型的问题!
请问list 是类型吗?它不是!它是类明!
什么是类型? 诸如list
的list ! 区别模板类类型的关键在于T!现在再想一想const迭代器不同于普通迭代器什么?不就是重载的*号不同!那么我们是否可以多一个模板参数,区别这两个不同的类!它们是类型 list_iterator
list_iterator 这两个不是同一个迭代器!!! 现在看看大佬写法!
三个模板参数!! 两者区别在于第二个一个是T,一个是const T!
//这里的T*是->返回时的参数 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); } template<class T, class ref, class ptr> struct list_iterator { typedef list_node<T> node; typedef list_iterator<T, ref, ptr> Self; node* pnode; list_iterator(node* p) :pnode(p) {} ref& operator*() { return pnode->data; } ptr operator->() { return &pnode->data; } Self& operator++() { pnode = pnode->next; return *this; } Self& operator--() { pnode = pnode->prev; return *this; } bool operator!=(const Self& it) { return pnode != it.pnode; } };
1.构造tmp--> 2.交换--> 3.出作用域,临时变量调用析构函数,释放this原空间
- //连等可能,所以返回链表!
- //出作用域,被替换的tmp会调用它的析构函数,析构this的原空间
-
- list<T>& operator=(list<T> tmp)
- {
- swap(tmp);
- return *this;
- }
- void clear()
- {
- iterator first = begin();
- while (first != end())
- {
- first = erase(first);//!!!注意考虑迭代器失效
- }
- }
- ~list()
- {
- clear();
- delete head;
- head = nullptr;
- }
这里再引入一个问题!为什么之前的迭代器类,结点类我们没有写析构函数?现在需要写呢?
因为这两个类的成员变量都是内置类型,默认构造会自动释放成员变量。它们的任务都是单个结点!
如果list我们这里不写,默认析构函数只会将我们的头结点释放,那些剩余结点并没有被释放,也就是说list析构任务不仅仅是单个结点,而是所有结点!所以这里我们必须手动写!
- namespace wyz
- {
- template<class T>
- struct list_node
- {
- list_node(const T& val = T())
- :prev(nullptr)
- , next(nullptr)
- , data(val)
- {}
- public:
- list_node* prev;
- list_node* next;
- T data;
- };
- template<class T, class ref, class ptr>
- template<class T, class ref, class ptr>
- struct list_iterator
- {
- typedef list_node<T> node;
- typedef list_iterator<T, ref, ptr> Self;
- node* pnode;
- list_iterator(node* p)
- :pnode(p)
- {}
- ref operator*()
- {
- return pnode->data;
- }
- ptr operator->()
- {
- return &pnode->data;
- }
- //前置
- Self& operator++()
- {
- pnode = pnode->next;
- return *this;
- }
- //后置
- Self operator++(int)
- {
- Self tmp(pnode);
- pnode = pnode->next;
- return tmp;
- }
- //前置
- Self& operator--()
- {
- pnode = pnode->prev;
- return *this;
- }
- //后置
- Self operator--(int)
- {
- Self tmp(pnode);
- pnode = pnode->prev;
- return tmp;
- }
-
- bool operator!=(const Self& it)
- {
- return pnode != it.pnode;
- }
- bool operator==(const Self& it)
- {
- return pnode == it.pnode;
- }
- };
- template<class T>
- class list
- {
-
- public:
- typedef list_node<T> node;
- typedef list_iterator<T, T&, T*> iterator;
- typedef list_iterator<T, const T&, const T*> const_iterator;
- iterator begin()
- {
- //匿名对象返回!
- return iterator(head->next);
- }
- const_iterator begin()const
- {
- return const_iterator(head->next);
- }
- const_iterator end()const
- {
- return const_iterator(head);
- }
- iterator end()
- {
- return iterator(head);
- }
- void clear()
- {
- iterator first = begin();
- while (first != end())
- {
- first = erase(first);//!!!
- }
- }
- ~list()
- {
- clear();
- delete head;
- head = nullptr;
- }
- void empty_initialize()
- {
- head = new node;
- head->next = head;
- head->prev = head;
- }
- list()
- {
- empty_initialize();
- }
- template <class InputIterator>
- list(InputIterator first, InputIterator end)
- {
- empty_initialize();
- while (first != end)
- {
- push_back(*first);
- ++first;
- }
- }
- void swap(list<T>& lt)
- {
- std::swap(head, lt.head);
- }
- list(const list<T>& lt)
- {
- empty_initialize();
- list<T> tmp(lt.begin(), lt.end());
- swap(tmp);
- }
- list<T>& operator=(list<T> tmp)
- {
- swap(tmp);
- return *this;
- }
- void push_back(const T& x)
- {
- insert(end(), x);
- }
- void push_front(const T& x)
- {
- insert(begin(), x);
- }
- void pop_front()
- {
- erase(begin());
- }
- void pop_back()
- {
- erase(--end());
- }
- void 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;
- }
- iterator erase(iterator pos)
- {
- node* cur = pos.pnode;
- node* prev = cur->prev;
- node* next = cur->next;
- prev->next = next;
- next->prev = prev;
- delete[]cur;
- return iterator(next);
- }
- private:
- node* head;//底层是一个哨兵结点
- };