【C++】STL——list深度剖析 及 模拟实现
list的模拟实现
那接下来我们就来对list进行一个深度剖析和模拟实现，那首先我们还是先来简单的浏览一下STL中list的源码：
2.1 STL_list源码浏览
首先我们可以看到：
它里面有三个模板类
第一个类是结点；
第二个是迭代器；
最后一个就是链表对应的类模板。
但是我们发现结点和迭代器的类他都是用struct定义的，那用struct就说明他想把类里面的所有成员都对外开放出去，因为struct的默认访问权限为public。
那我们来看一下list类的成员变量：
🆗，我们会发现它只有一个成员变量link_type node，那它的类型link_type 是啥呢？
我们找一下：
我们看到link_type其实就是结点的指针。
然后我们在看什么呢？
🆗，是不是可以看一下它的构造啊，看明白构造，我们就可以知道它的一个初始状态是怎么样的，然后我们就可以再去看一下它的一些核心的接口，当然对于链表来说无非也就是头插头删、尾插尾删这些，那这样我们对它就差不多了解一个七七八八了。
那构造函数：
我们看到它里面又调了另一个函数empty_initialize，就是空初始化的意思嘛。
那empty_initialize干了什么呢？
我们看到就是创建了一个结点，然后让他的next和prev都指向自己，什么意思呢？
那如果大家看过我之前数据结构的文章，学过里面的带头双向循环链表的话，一看就明白了。
其实就是创建了一个哨兵位的头结点嘛。
然后再来看：
头插push_front和尾插push_back，那头插就是在begin的位置插入一个元素，尾插就是在end的位置插入一个元素。
那对于list来说，begin和end应该在哪呢？
🆗，那剩下的接口我们就可以不用看了，本身我们之前也学过，已经比较了解它的结构了，后面有需要的地方我们再来看。
那接下来我们就可以开始模拟实现了。
2.2 基本结构实现
那首先我们写一下结点的结构：
namespace yin
{
template <class T>
struct list_node
{
list_node<T>* _next;
list_node<T>* _prev;
T _data;
//构造
list_node(const T& x)
:_next(nullptr)
, _prev(nullptr)
, _data(x)
{}
};
}
这里还是放到我们自己的命名空间里。
然后写一下list的结构，迭代器我们先放到后面在搞：
然后先来给一个默认构造：
然后我们先写一个push_back：
尾插要怎么写，想一下？
很简单，首先拿要插入的数据创建一个新结点，找尾然后改变指针指向链接就行了嘛
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;
}
测试一下：
🆗，我们的链表就成形了。
2.3 思考：list迭代器是否可以用原生指针
那接下来我们来搞一下list的迭代器：
大家回想一下，我们之前模拟实现string和vector的时候，它们的迭代器我们是不是都使用了原生指针去实现啊，因为使用指针完全是可行的嘛。
那现在list的迭代器我们还可以使用指针来搞吗？
🆗，string和vector的迭代器之所以能使用原生指针去实现，最主要的原因是不是因为它们底层的物理空间是连续的啊，那连续的话，用指针是不是很方便啊，++就往后走正好访问到下一个元素。
那list呢？list的迭代器用原生指针实现可行吗？或者说用原生指针实现有没有什么问题呢？
🆗，list里面是一个一个的结点，如果我们用结点的指针node*的话，首先它解引用是啥？
是不是对应的结点啊，但是我们访问链表，取的应该是每个结点里面data域的数据吧。
其次，结点的指针++，得到的是下一个结点的指针吗？
是不是大概率不是啊，因为每个结点的空间都不一定是连续的啊。
那怎么办呢？我们可以来看一下库里面怎么实现的：
那其实刚才开始我们在浏览源码的时候也提到了，库里面是不是把迭代器也实现成一个类模板了，那这个类模板是啥呢？
我们发现迭代器这个类模板其实就是对结点的指针进行了一个封装。
但是，迭代器要能++找到下一个结点位置的迭代器，还要能够解引用取到结点里面的值等等一系列操作，怎么办？
我们看到，它在类模板里面对++，–，解引用这些操作进行了重载。
++怎么实现的？
就是让node走到下一个结点。
解引用呢？
就是去取结点里data域的数据。
这样是不是就满足迭代器的需求了。
2.4 list迭代器的实现（重难点）
list_iterator：结点指针的封装
那接下来我们就来实现一下list的迭代器：
就是对结点的指针进行一个封装：
*、前置++ 、!=的重载
那我们先来重载一下迭代器的++，*和！=，这三个重载完就可以使用迭代器遍历了
首先解引用就是返回当前结点的data：
然后++（先写一下前置），就是让结点的指针走到下一个结点，前置++返回++之后的值。就是他自己嘛
当然这个类型比较长，我们可以typedef一下：
然后！=：
begin、end
然后我们在list里面加一个begin和end就可以用迭代器了：
那begin就是返回第一个元素位置（即头结点后面）的迭代器，end就是返回最后一个元素的下一个位置（即头结点位置）的迭代器：
那现在我们就可以用迭代器遍历list了：
🆗，是不是就可以了。
当然范围for也就支持了：
那学到这个地方，我们其实可以得到一个结论：
迭代器要么就是原生指针，要么就是自定义类型对原生指针进行封装，模拟指针的行为
思考
然后，大家来思考一下问题：
大家看，这个地方把begin的返回值赋值给it，发生了什么？
🆗，这个地方是不是会调用迭代器__list_iterator这个类的拷贝构造啊。
但是，我们自己并没有实现拷贝构造，所以这个地方回调用默认生成的拷贝构造。
但是默认生成的是浅拷贝，那这个地方浅拷贝有问题吗？
是不是没问题啊，这个地方是不是就应该是浅拷贝啊。begin返回的迭代器里面有一个结点的指针，指向list的第一个元素，然后把它拷贝给it，it里面的结点指针也指向第一个元素，这样后面++是不是才能正确找到后续的元素啊。
所以这个地方就应该是浅拷贝。
那再来思考：
为什么这个地方浅拷贝但是没有报错呢？
浅拷贝的话这里两个对象不是指向同一块空间了，我们之前遇到这种情况不是都报错了嘛，为什么这里没事呢？
🆗，我们之前浅拷贝造成程序崩溃时因为什么，是不是最后对同一块空间析构了两次，所以才会崩。
但是这里我们的迭代器__list_iterator类我们是不是自己都没写析构函数啊。
那需要写吗？
是不是不需要啊，因为它不需要去释放里面指针指向的结点的空间。
那为什么不需要释放啊？
🆗，它里面虽然有结点的指针，但是它指向的结点属于谁，是不是属于list啊，那结点的释放应该是谁的事情？
是不是list的析构应该干的事情啊。
这里的结点本身就不是你迭代器创建的，也不需要你去释放，你这里拿到结点的指针，只是帮助我去访问和修改链表的。
其它运算符重载
那我们再来重载一下后置++：
后置++和前置++的重载怎么区分，还记得吗？
前置++和后置++都是一元运算符，为了让前置++与后置++形成能正确重载。C++规定：后置++重载时多增加一个int类型的参数，但调用函数时该参数不用传递（它的作用就是为了构成重载），编译器自动传递。（- -也是如此）
那后置++和前置++的区别就是返回值不一样，后置++是先使用，后++，返回++之前的值。
再来实现一个前置- -和后置- -：
很简单，++向后走，–向前走
再来个==：
那就实现的差不多了。
const迭代器
假如现在我们要写一个打印链表的函数：
然后我们调用该函数：
发现报错了，为什么，是不是又是权限放大的问题啊？
怎么解决？
🆗，我们是不是要实现const迭代器，提供const版本的begin和end啊。
那在我们的list中，我们可以怎么实现const迭代器呢？
我们现在已经有了一个普通迭代器的类__list_iterator，那我们可以再实现一个const迭代器的类__list_const_iterator:
和普通的迭代器一样，我也可以进行++ - -等操作，唯一的区别就是你只能访问我指向的数据，而不能修改它。
然后，我们list类里面就可以实现const版本的begin和end了：
那这样的话，我们的print_list函数里面：
这个地方换成const_iterator就行了。
这下就可以了。
当然const_iterator就不能修改了：
代码优化：增加一个模板参数
但是：
这样写的话：
我们看到这两个类除了名字不同之外，唯一的区别就是operator*的返回值类型不同，一个返回引用，一个返回const引用。
那这样是不是太冗余了呀，那我们能不能想想办法，只写一个类，就搞定这两种情况呢，其实就是控制一下这里operator*的返回值，const对象调用就返回const引用，普通对象调用就返回引用。
那可以怎么做呢？
🆗，我们可以这样做：
我们不是要控制
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。
没毛病啊，就是这样。
所以呢：
这个地方本来应该是两个->，但是为了增强代码可读性，省略了一个->，大家也可以认为这个地方进行了一个特殊处理。
就像前面我们讲过的前置++后置++重载的区分那种情况。
第三个模板参数
那现在回到我们上面的那个问题：
为什么还有第三个模板参数
Ptr？再看我们重载的->：
现在它的返回值是
T*，但是如果是const对象调用的话，是不是应该返回const T*啊，所以呢？和
operator*，我们增加一个模板参数来控制不同情况下返回不同类型的返回值。
这样const对象也可以使用->了：
反向迭代器我们学到后面一点再讲。
2.5 插入删除操作
那接下来我们来实现一下insert和erase：
insert和erase实现好，头插头删、尾插尾删就可以直接复用了。
那这些东西呢也很简单，没什么新东西，都是我们数据结构阶段玩过的，所以这个部分的重点其实就是迭代器的实现，大家要好好看一看。
insert
那我们先来搞一下insert：
创建新结点链接就行了。
测试 一下：
没问题。
那大家来思考一个问题，list的insert会导致迭代器失效吗？
🆗，是不会的。
list的底层结构为带头结点的双向循环链表，在list中进行插入操作是不会导致list的迭代器失效的。
之前学到vector进行插入会导致迭代器失效是因为vector插入数据可能会扩容，扩容之后原来的迭代器就指向一块被释放的空间了，而且就算没有扩容，由于插入元素要挪动数据，那插入之后pos位置的就不在是原来的数据了。但是对于链表来说不存在这些问题。
插入前后，pos始终指向同一个结点，不会发生改变，因此在list中进行插入操作是不会导致list的迭代器失效的。
push_back 和 push_front
那实现了insert，push_back 和 push_front就可以直接复用了：
试一下：
没问题。
erase、pop_back和pop_front
再来实现一下erase：
然后pop_back和pop_front直接复用：
来测试一下：
那大家思考一下，erase会导致迭代器失效吗？
是不是会啊！
进行erase这些删除操作之后，当前迭代器指向的结点都被释放了，那它肯定失效了。
那失效了我们还想继续用怎么办？
那erase正常情况下是有返回值的：
返回指向被删除元素后面元素的迭代器，如果被删除的是最后一个元素，则返回的是end()。
那我们想继续用的话，接收一下返回值就行了。
2.6 clear和析构
那接下来我们写一下析构：
不过写析构之前我们可以先写一下clear，然后析构可以复用一下clear。
那clear是啥？
是不是清空list里面所有的元素啊，当然头结点不能清除。
来写一下：
这样是不是就行了啊，直接复用erase，但是erase会导致迭代器失效，所以我们接收一下返回值。
来试一下：
除此之外呢，这个地方还可以这样写：
大家看这样写可以吗？
🆗，这样也是可以的，我们看后置++是怎么实现的：
上来先++，迭代器已经更新到下一个位置了，然后这里返回的是++之前的迭代器的拷贝，所以不会导致迭代器失效，这样也是可以的。
但是这样写肯定是错误的：
那然后我们来写析构：
那析构就是释放所有资源，包括头结点。
就完成了。
2.7 迭代器区间构造和拷贝构造
我们再来实现一下迭代器区间的构造：
很简单，我们vector就写过嘛，来写一下，
但是现在这样写有没有什么问题？
🆗，直接尾插的话是不是的有头结点啊。
那我们可以学一下库里：
搞一个这个函数empty_initialize（空初始化）：
这样在好多地方都可以直接复用。
测试一下：
没问题。
不过呢，顺便提一下
在这个地方有的老铁可能会提出这样的疑惑，就是这里empty_initialize是非const成员函数，那要是定义const对象是不是调不了啊？
🆗，肯定是可以调的，要是这样认为的话，那我们的构造函数也都是非const的，那我们是不是就定义不了const对象了啊。
那为什么可以呢？
补充一个小知识点：
问大家一个问题，const变量在定义的时候有const属性吗？
是没有的，否则它还怎么初始化呢？
111行这句代码可以通过吗，它可以通过那110行就也没问题。
所以大家也可以认为这是一个特殊处理，const变量在定义的时候是不具有const属性的，定义完成之后才有。
所以是可以调的，没问题。
然后来搞一下拷贝构造：
这样是不是就可以啊。
试一下：
当然也可以用现代写法：
但是呢？
有问题啊，怎么回事？
🆗，是不是忘了初始化了，就直接跟tmp交换了。
好了。
2.8 赋值重载
再来搞一个赋值重载：
那这个用现代写法也很easy：
两句代码就搞定了。
测试一下：
注意：
参数不能传引用，传引用的话就会把给它赋值的对象给改变了。
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的讲解就到这里了，欢迎大家指正！！！
- 点赞
- 收藏
- 关注作者
评论（0）