文章目录

• • 前言
  • 1. list的介绍及使用
  • • 1.1 list的介绍
    • 1.2 list的使用
    • • 遍历
      • 插入删除数据
      • Operations
      • 迭代器的功能分类
      • list 的sort性能测试
  • 2. list的模拟实现
  • • 2.1 STL_list源码浏览
    • 2.2 基本结构实现
    • 2.3 思考：list迭代器是否可以用原生指针
    • 2.4 list迭代器的实现（重难点）
    • • list_iterator：结点指针的封装
      • `*、前置++ 、!=`的重载
      • begin、end
      • 思考
      • 其它运算符重载
      • const迭代器
      • 代码优化：增加一个模板参数
      • ->的重载
      • 第三个模板参数
    • 2.5 插入删除操作
    • • insert
      • push_back 和 push_front
      • erase、pop_back和pop_front
    • 2.6 clear和析构
    • 2.7 迭代器区间构造和拷贝构造
    • 2.8 赋值重载
  • 3. 源码展示
  • • list.h
    • test.cpp

前言

这篇文章我们来继续STL的学习，今天我们要学习的是list，也是STL中容器的一员。
和之前一样，我们还是先学习它的使用，然后再对它进行一个深度剖析和模拟实现。

1. list的介绍及使用

1.1 list的介绍

list的文档介绍

list的底层实现其实就是我们之前数据结构学过的带头双向循环链表：

遍历

那经过之前的学习，相信大家就可以直接上手使用list的迭代器了：

int main(){list<int> l;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(3);l.push_back(5);for (list<int>::iterator it = l.begin(); it != l.end(); ++it)cout << *it << " ";cout << endl;for (auto e : l)cout << e << " ";cout << endl;for (list<int>::reverse_iterator rit = l.rbegin(); rit != l.rend(); ++rit)cout << *rit << " ";cout << endl;return 0;}

插入删除数据

然后我们来演示一下insert和erase：

我们发现list也没有提供find，所以我们要获取某个位置的迭代器，可以用算法库里面的find：


也是这几个版本，就不给大家全部演示了。
然后erase：


但是注意list的迭代器是双向迭代器：

只能++或者- -，不能+或-：

Operations

然后来看下这几个接口：

那我们来看一下list类的成员变量：

然后我们在看什么呢？

🆗，是不是可以看一下它的构造啊，看明白构造，我们就可以知道它的一个初始状态是怎么样的，然后我们就可以再去看一下它的一些核心的接口，当然对于链表来说无非也就是头插头删、尾插尾删这些，那这样我们对它就差不多了解一个七七八八了。
那构造函数：

我们看到它里面又调了另一个函数empty_initialize，就是空初始化的意思嘛。
那empty_initialize干了什么呢？

我们看到就是创建了一个结点，然后让他的next和prev都指向自己，什么意思呢？
那如果大家看过我之前数据结构的文章，学过里面的带头双向循环链表的话，一看就明白了。
其实就是创建了一个哨兵位的头结点嘛。

然后再来看：

那再来思考：

为什么这个地方浅拷贝但是没有报错呢？
浅拷贝的话这里两个对象不是指向同一块空间了，我们之前遇到这种情况不是都报错了嘛，为什么这里没事呢？
🆗，我们之前浅拷贝造成程序崩溃时因为什么，是不是最后对同一块空间析构了两次，所以才会崩。
但是这里我们的迭代器__list_iterator类我们是不是自己都没写析构函数啊。
那需要写吗？
是不是不需要啊，因为它不需要去释放里面指针指向的结点的空间。
那为什么不需要释放啊？
🆗，它里面虽然有结点的指针，但是它指向的结点属于谁，是不是属于list啊，那结点的释放应该是谁的事情？
是不是list的析构应该干的事情啊。
这里的结点本身就不是你迭代器创建的，也不需要你去释放，你这里拿到结点的指针，只是帮助我去访问和修改链表的。

其它运算符重载

那我们再来重载一下后置++：

后置++和前置++的重载怎么区分，还记得吗？
前置++和后置++都是一元运算符，为了让前置++与后置++形成能正确重载。C++规定：后置++重载时多增加一个int类型的参数，但调用函数时该参数不用传递（它的作用就是为了构成重载），编译器自动传递。（- -也是如此）
那后置++和前置++的区别就是返回值不一样，后置++是先使用，后++，返回++之前的值。

再来实现一个前置- -和后置- -：

很简单，++向后走，–向前走

再来个==：

那在我们的list中，我们可以怎么实现const迭代器呢？

我们现在已经有了一个普通迭代器的类__list_iterator，那我们可以再实现一个const迭代器的类__list_const_iterator:

和普通的迭代器一样，我也可以进行++ - -等操作，唯一的区别就是你只能访问我指向的数据，而不能修改它。

然后，我们list类里面就可以实现const版本的begin和end了：

那可以怎么做呢？

🆗，我们可以这样做：
我们不是要控制operator*的返回值不同情况下不一样（T&或const T&）嘛

现在有一个参数T我们是可以拿到T&的，但是我们现在故意增加一个模板参数ref（reference——引用）。

然后我们再做这样一件事情，在list类模板里面，我们就不再像原来那样搞了，这样：

普通迭代器就传引用，const迭代器就传const引用。


是不是可以啊。
这种写法是不是感觉很牛逼啊，而且是不是就很好的避免了我们上面那样写造成的代码冗余的问题。
那其实库里面就是这样写的：

->的重载

但是呢：

我们看到

库里面有三个模板参数，还有一个Ptr，这个又是干什么的呢？

那我们会发现库里面对于迭代器除了重载*还重载了->

那为什么还要重载->呢，什么场景下会用到呢？

🆗，我们看这种场景：

现在有一个自定义类型AA，我们定义一个list变量l，让他里面存AA类型的数据。
然后我们使用迭代器打印一下：

我们发现报错了，怎么回事？
🆗，我们这里对it进行解引用并打印，但是*it得到的是什么，是不是当前it对应的结点data域里面的数据，是什么？
是不是一个AA类型的变量啊，但是它是自定义类型，并且我们没有重载流插入，所以这里打印不成。

那如何解决呢？

首先我们可能会想到对AA这个类重载流插入，这当然是一个办法。
但是它是struct定义的，所以它的成员默认是公有的，所以我们可以不重载，这样也可以：

那此时list里面放AA类型数据的话，我们的迭代器是不是就相当于是对AA*这个类型的结构体指针（或者说类指针）的封装啊，模拟结构体指针的行为。
但是正常情况下，我们拿到一个结构体指针或类对象的指针去访问它的成员，会先解引用，再通过.去访问吗？
是不是可以直接用->啊。

所以：

基于这样的原因，我们的迭代器也需要重载一下->。
那怎么实现呢？

🆗，去调operator*，operator*返回的是啥？
是结点的data域中的数据，然后再取它的地址返回。这样如果是自定义类型数据是不是返回的就是原生的类对象的指针啊，那就可以用->了。
我们来实现一下：

是不是就这样啊。

就可以用->了。
但是，如果我们仔细观察一下的话，会发现好像有点不对啊，哪里不对呢？
大家看it->_a1，这样写对吗？
it->是不是it去调用operator->这个函数了，那它的返回值是啥？
是不是返回了结点的data域中放的类对象的地址（指针），那我们用这个地址去访问成员变量是不是可以再用->去访问，所以这里正常是不是应该这样写：it->->a1，等同于it.operator->()->a1。
没毛病啊，就是这样。
所以呢：
这个地方本来应该是两个->，但是为了增强代码可读性，省略了一个->，大家也可以认为这个地方进行了一个特殊处理。
就像前面我们讲过的前置++后置++重载的区分那种情况。

第三个模板参数

那现在回到我们上面的那个问题：

push_back 和 push_front

那实现了insert，push_back 和 push_front就可以直接复用了：

3. 源码展示

list.h

#pragma once#include <assert.h>#include <algorithm>namespace yin{template <class T>struct __list_node{__list_node<T>* _next;__list_node<T>* _prev;T _data;__list_node(const T& x = T()):_next(nullptr), _prev(nullptr), _data(x){}};template <class T, class Ref, class Ptr>struct __list_iterator{typedef __list_node<T> node;typedef __list_iterator<T, Ref, Ptr> self;node* _node;__list_iterator(node* n):_node(n){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}self& operator++(){_node = _node->_next;return *this;}self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}self& operator--(){_node = _node->_prev;return *this;}self operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const self& s){return _node != s._node;}bool operator==(const self& s){return _node == s._node;}};/*template <class T>struct __list_const_iterator{typedef __list_node<T> node;typedef __list_const_iterator<T> self;node* _node;__list_const_iterator(node* n):_node(n){}const T& operator*(){return _node->_data;}self& operator++(){_node = _node->_next;return *this;}self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}self& operator--(){_node = _node->_prev;return *this;}self operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const self& s){return _node != s._node;}bool operator==(const self& s){return _node == s._node;}};*/template <class T>class list{typedef __list_node<T> node;public:typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;//typedef __list_const_iterator<T> 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);}void empty_initialize(){_head = new node;_head->_next = _head;_head->_prev = _head;}list(){empty_initialize();}template <class Iterator>list(Iterator first, Iterator last){empty_initialize();while (first != last){push_back(*first);++first;}}/*list(const list<T>& l){empty_initialize();for (auto e : l)push_back(e);}*/void swap(list<T>& l){std::swap(_head, l._head);}list(const list<T>& l){empty_initialize();list<T> tmp(l.begin(), l.end());swap(tmp);}list<T>& operator=(list<T> l){swap(l);return *this;}~list(){clear();delete _head;_head = __nullptr;}void clear(){iterator it = begin();while (it != end()){//it = erase(it);erase(it++);}}void push_back(const T& x){//node* newnode = new node(x);找尾//node* tail = _head->_prev;链接//_head->_prev = newnode;//newnode->_next = _head;//tail->_next = newnode;//newnode->_prev = tail;insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void 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;}iterator erase(iterator pos){assert(pos != end());node* prev = pos._node->_prev;node* next = pos._node->_next;prev->_next = next;next->_prev = prev;delete pos._node;return iterator(next);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}void print_list(const list<T>& l){for (list<T>::const_iterator it = l.begin(); it != l.end(); ++it){//(*it)++;cout << *it << " ";}cout << endl;}private:node* _head;};}

test.cpp

#define _CRT_SECURE_NO_WARNINGS#include <iostream>using namespace std;#include <algorithm>#include "list.h"//int main()//{//list<int> l;//l.push_back(1);//l.push_back(8);//l.push_back(4);//l.push_back(7);//l.push_back(-3);//for (auto e : l)//cout << e << " ";//cout << endl;//l.sort();//sort(l.begin(), l.end());//for (auto e : l)//cout << e << " ";//cout << endl;//return 0;//}//int main()//{//yin::list<int> l;//l.push_back(1);//l.push_back(2);//l.push_back(3);//l.push_back(4);////for (auto e : l)//cout << e << " ";//cout << endl;////l.insert(++l.begin(), 99);//l.push_back(100);//l.push_front(200);////for (auto e : l)//cout << e << " ";//cout << endl;////l.erase(++l.begin());//l.pop_back();//l.pop_front();////for (auto e : l)//cout << e << " ";//cout << endl;//return 0;//}//struct AA//{//int _a1;//int _a2;////AA(int a1 = 0, int a2 = 0)//:_a1(a1)//, _a2(a2)//{}//};//void print(const yin::list<AA>& l)//{//for (yin::list<AA>::const_iterator it = l.begin(); it != l.end(); ++it)//{////cout << (*it)._a1 << " " << (*it)._a2 << " ";//cout << it->_a1 << " " << it->_a2 << " ";//cout << endl;//}//}//int main()//{//yin::list<AA> l;//l.push_back(AA(1, 1));//l.push_back(AA(2, 2));//l.push_back(AA(3, 3));//for (yin::list<AA>::iterator it = l.begin(); it != l.end(); ++it)//{////cout << (*it)._a1 << " " << (*it)._a2 << " ";//cout << it->_a1 << " " << it->_a2 << " ";//cout << endl;//}////print(l);//return 0;//}int main(){yin::list<int> l;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);for (auto e : l)cout << e << " ";cout << endl;yin::list<int> l2;l2.push_back(10);l2.push_back(20);l2.push_back(30);l2.push_back(40);for (auto e : l2)cout << e << " ";cout << endl;l2 = l;for (auto e : l2)cout << e << " ";cout << endl;return 0;}

🆗，那我们关于list的讲解就到这里了，欢迎大家指正！！！