手撕STL：list底层结构与迭代器实现

本文代码已同步Github

一、底层源码分析

1、源码剖析

通过上一篇对vector的学习，我们知道其底层是通过三个指针来充当迭代器；

下面我们来看一下list的底层是怎么设计的；

同样使用g++中的SGI版本来观察

先来看说明文档，发现依据是多个头文件配合的形式； 那么核心文件便是<stl_list.h>

我们来看一看

发现和vector不同的是，list里面有多个类，比如list_node ,list_iterator,这些；

简单看一下类的名称及成员变量就会知道：

list_node是节点，存储的是节点的信息，看来底层确实是由一个双向链表来实现的 list_iterator就是迭代器，有一个list_node*的指针

我们再往下看看还有没有其他的类

还有一个类，类名为list，里面有一个list_node*的指针；

2、不同类之间的关系

下面我们来理一理三个类之间的关系：

list用来控制整个链表，无论是push_back还是insert等操作，都通过list中的成员函数来实现

而list_iterator是迭代器，用来定位和访问； 通过重载++，–等操作符，将迭代器封装成类似指针的效果

最后的list_node就是一个一个的节点了；

好了，根据上述对底层源码的简单分析之后，我们来搭一下基础框架

二、类模板框架搭建

1、结构实现

注意⚠️：我们实现的仅仅是基础版，为方便起见，我们加入成员变量_size

namespace stl
{
//节点
template<class T>
struct list_node
{
list_node(const T& data = T())
:_data(data)
, _prev(nullptr)
, _next(nullptr)
{}

T _data;
list_node<T>* _prev;
list_node<T>* _next;
};

//迭代器
template<class T>
struct list_iterator
{
typedef list_node<T> Node;
typedef list_iterator<T> Self;

list_iterator(Node* node)
:_node(node)
{}

Node* _node;
};

template<class T>
class list
{
public:
typedef list_node<T> Node;
typedef list_iterator<T> iterator;

private:
Node* _head;
size_t _size;
public:

};
}

下面我们来写list的默认构造函数

分析： 首先要new一个节点，这个节点即为哨兵位 接着修改指针的指向，并给_size赋值

list()
{
_head = new Node;
_head->_prev = _head;
_head->_next = _head;

_size = 0;
}

2、基础接口实现

我们先来实现size和empty

size_t size()
{
return _size;
}

bool empty()
{
return _size == 0;
}

接着来实现begin和end

单参数构造函数可以进行隐式类型转换，我们直接返回节点的地址即可

iterator begin()
{
return _head->_next;
}

iterator end()
{
return _head->_prev->_next;
}

三、迭代器实现

1、iterator

上一篇对list接口的介绍中，我们知道list的迭代器是双向迭代器；

也就是说只能++,–

但是对于链表来说，由于不是顺序存储； 因此，对于普通指针，无论是++还是–之后，都无法到达下一个节点；

此时我们就需要对运算符进行重载！

a、代码实现

首先来分析怎样重载？

迭代器的遍历是通过解引用来得到信息，因此需要重载*运算符，函数返回类型是T&

分析逻辑： 在写list_iterator时，迭代器类的构造函数就会将_node指向迭代器变量所指的位置； 那么直接返回_node->_data即可

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

对于++，–；我们的目的是能够到达下一个节点；返回的是节点的地址，即T* 而_node中就存储着前一个节点和下一个节点的地址，直接返回即可

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) const
{
return _node == s._node;
}

bool operator!=(const Self& s) const
{
return _node != s._node;
}

b、测试

为了便于测试，我们先实现push_back

分析： 先new节点，接着修改指针指向即可

template<class T>
void list<T>::push_back(const T& val)
{
Node* newnode = new Node(val);

_head->_prev->_next = newnode;
newnode->_prev = _head->_prev;
newnode->_next = _head;
_head->_prev = newnode;

_size++;
}

下面来测试一下

对于内置类型没有问题，接着来测试一下自定义类型

编译报错

问题就在于这个*it，解引用之后拿到的是A的对象或者引用，因此需要用.来访问

这样显得有点麻烦，不如直接重载->运算符

返回_data的地址，这样直接返回一个指针，再用一个->即可解决 注意：两个->会省略成一个->

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

2、const_iterator

首先思考一下，const迭代器和普通迭代器的区别是什么？

const迭代器到底是迭代器本身不能被修改，还是所指向的内容不能被修改？

答案显然是所指向的内容不能被修改！

在前面的vector中，我们直接在begin,end的返回值改成const_iterator，通过const成员函数重载； 同时函数后面也加上const

这样返回值的类型就是const T& ptr const,返回一个只读引用； 解引用之后只读，避免迭代器所指向内容被修改

而在list中，显然不能直接在begin,end前加上const了； 因为这两个函数返回的只是第一个有效位置和最后一个位置的下一个位置的迭代器； 就算加上const返回值类型为const iterator，对迭代器访问没有作用！

关键在于*运算符，限制*的返回类型即可避免迭代器所指向的内容被修改

a、代码实现

理解完const_iterator之后，发现与iterator的不同就是*运算符的不同

那么该怎么写呢？

我们可以选择封装一个const_iterator类，里面将*的返回值加上const即可

//const_iterator
template<class T>
struct list_const_iterator
{
typedef list_node<T> Node;
typedef list_const_iterator<T> Self;

list_const_iterator(Node* node)
:_node(node)
{}

Node* _node;

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

const T* operator->() const
{
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) const
{
return _node == s._node;
}

bool operator!=(const Self& s) const
{
return _node != s._node;
}

};

b、测试

我们通过一个打印容器的函数模板来测试

template<class Con>
void print_container(const Con& con)
{
for (const auto& e : con)
{
std::cout << e << " ";
}
std::cout << std::endl;
}

3、优化

对于iterator类以及const_iterator类，两个类大体上高度相似；

真的有必要再重新封装一个类吗？

我们来看源码是怎么做的

发现源码将模板参数设计成了三个参数，并且也没有额外的类

此时我们来分析一下： Ref表示引用；Ptr表示指针；

也就是说给list_iterator类的参数不同，就实例化出不同的类；

我们来分析为什么给普通迭代器传的是T,T&,T*而const迭代器则是T,const T&,const T*?

通过成员函数来分析：

主要来看*和->

如果是普通迭代器：

对于*,我们返回的是Ref,而此时Ref就是T& 对于->，我们返回的是Ptr，此时Ptr就是T* 完全符合情况！

如果是const迭代器：

对于*,我们返回的是Ref,而此时Ref就是const T& 对于->，我们返回的是Ptr，此时Ptr就是const T* 同样完全符合情况！

因此，源码直接设计方式非常优雅简洁；

我们也同样采用这种方式；

需要注意的是：在list中对不同参数均需做出声明

//迭代器
//template<class T>
template<class T,class Ref,class Ptr>
struct list_iterator
{
typedef list_node<T> Node;
typedef list_iterator<T,T&,T*> iterator;
typedef list_iterator<T,const T&,const T*> const_iterator;
typedef list_iterator<T,Ref,Ptr> Self;

list_iterator(Node* node)
:_node(node)
{}

Node* _node;

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

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

其他成员函数保持原样即可

四、核心接口实现

1、insert

分析逻辑： 注意返回值是迭代器，指向第一个被插入的元素 接着pos是迭代器，在pos之前插入数据

template<class T>
list<T>::iterator list<T>::insert(iterator pos, const T& val)
{
Node* newnode = new Node(val);
Node* cur = pos._node;
Node* prev = cur->_prev;

newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
prev->_next = newnode;

++_size;

return newnode;
}

来测试一下

2、erase

接着来看erase

iterator erase (iterator position);
iterator erase (iterator first, iterator last);

分析： 删除pos位置的节点，更改指针指向即可 最后返回pos位置的下一个节点的迭代器

template<class T>
list<T>::iterator list<T>::erase(iterator pos)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;

prev->_next = next;
next->_prev = prev;

delete cur;
cur = nullptr;

—_size;

return next;
}

来测试一下

3、push_front、pop_front、pop_back

这几个均直接复用代码即可

void push_front(const T& val)
{
insert(begin(), val);
}

void pop_front()
{
erase(begin());
}

void pop_back()
{
erase(—end());
}

五、完善结构

1、构造函数

下面我们实现list里面的构造函数

目前只实现了默认构造函数

我们依次来实现

对于n个val构造： 注意⚠️：先创建出哨兵位，再复用push_back

直接将创建哨兵位封装成函数

void empty_init()
{
_head = new Node;
_head->_prev = _head;
_head->_next = _head;

_size = 0;
}

//n个val构造
list(size_t n, const T& val = T())
{
//先创建头节点
empty_init();

for (size_t i = 1; i <= n; i++)
{
push_back(val);
}
}

对于迭代器区间构造： 首先创建出哨兵位，接着同样复用push_back

//迭代器区间构造
template <class InputIterator>
list(InputIterator first, InputIterator last)
{
//先创建头节点
empty_init();

auto it = first;
while (it != last)
{
push_back(*it);
++it;
}
}

对于拷贝构造

同样先创建哨兵位，接着复用push_back即可

//拷贝构造
list(const list& lt)
{
//先创建头节点
empty_init();

for (auto& e : lt)
{
push_back(e);
}
}

我们来测试一下

2、赋值运算符

void swap(list& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}

//现代写法
list& operator=(list lt)
{
swap(lt);

return *this;
}

来测试一下

3、析构函数

最后来看析构函数

分析： 逐个节点释放，最终释放哨兵位

不妨将逐个节点释放封装成函数

void clear()
{
auto it = begin();
while (it != end())
{
it = erase(it);
}
}

~list()
{
clear();

delete _head;
_head = nullptr;

_size = 0;
}

六、总结

至此，我们已经越过了STL的两座大山——vector和list

下面我们来总结一下两者的区别

如果觉得有帮助，可以关注Github项目持续更新