STL源码分析之list

spb 2018-06-25

STL用环状双向链表来实现list,方法和leveldb的缓存环状链表一样,链表持有一个傀儡节点,不存储数据,只为这个链表的入口。迭代链表时,首先通过链表获得这个这个傀儡节点,然后通过next迭代所有数据。

STL将链表的傀儡节点作为链表的end节点,傀儡节点的next为begin节点,这样以来,就可以用[begin,end)这种左闭右开的形式来表示迭代器范围,和其他容器保持一致。

list节点结构

STL源码分析之list

因为是双向链表,所以有两个指针,分别指向前向指针和后向指针。

迭代器类型

因为list数据不是存储在连续的内存内,所以不能通过指针的加1减一来实现迭代器。list数据是通过指针链表结合在一起的,所以为了迭代所有数据,必须通过上个节点找到下个节点的地址,进而访问下个节点。list迭代器就是用这个原理,实现如下:

STL源码分析之list

STL源码分析之list

以上就是list的迭代器实现,只实现了迭代器的++,--,取值,成员调用四个基本操作,并没有像vector迭代器那样的+n操作,主要是因为地址不连续。

list实现

接下来看下list实现,list只有一个成员变量,就是那个傀儡节点,也是end节点。

先来看构造函数:

STL源码分析之list

这个构造函数为默认构造函数,就是创建一个节点,然后前后指向自己而已。说到配置器,由于list用的是自己定义节点结构体,所以也定义了相应类型的配置器。

STL源码分析之list

list还定义几种构造函数,用n个值来初始化list,将另一个list的一部分数据来初始化list和复制构造函数。

STL源码分析之list

这几个函数调用了fill_initialize和range_initialize,来看下这两个函数。

STL源码分析之list

这两个函数最后分别调用了insert函数的不同版本。一起来看下这两个insert函数。

STL源码分析之list

这两个函数通过循环调用 iterator insert(iterator position, const T& x) 这个insert版本,将数据一个一个插入到position之前,初始时就是插入到傀儡节点后面,形成初始链表,源码如下:

STL源码分析之list

最后看下析构函数

STL源码分析之list

这两个函数,clear是清空链表所有数据,然后put_node是将傀儡节点回收了。

一些小函数

STL源码分析之list

最后一个交换两个链表,只需要通过标准函数库的swap函数,交换两个傀儡节点即可,因为傀儡节点是每个链表的入口。

一些常用函数

往链表前插一个元素,通过调用insert完成。

STL源码分析之list

往链表尾巴插一个元素,也是通过insert函数完成。

STL源码分析之list

移除一个元素

STL源码分析之list

这个函数也很简单,只需要将被移除节点的前后节点跳过当前节点即可。

前后删除一个节点,用erase函数实现:

STL源码分析之list


transfer函数

这个函数是很多list接口调用的函数。这个函数有点难看懂,我把《STL源码剖析》上的图截下来,容易理解:

STL源码分析之list

;

源码如下:

STL源码分析之list

按着序号来读那个示意图,应该能看懂,本质上就那几个关键节点的前后关系。

有了这个函数之后,就出现了一些很有用的函数:

STL源码分析之list

remove函数

将数值为value的所有元素移除:

STL源码分析之list

merge函数

合并两个链表,前提是两个链表必须有序,合并之后的链表也是有序的。merge之后,x链表被清空了。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

template <class T, class Alloc>

void list<T, Alloc>::merge(list<T, Alloc>& x) {

iterator first1 = begin();

iterator last1 = end();

iterator first2 = x.begin();

iterator last2 = x.end();

while (first1 != last1 && first2 != last2)

if (*first2 < *first1) {

iterator next = first2;

transfer(first1, first2, ++next);

first2 = next;

}

else

++first1;

if (first2 != last2) transfer(last1, first2, last2);

}

reverse函数

这个函数是用于将链表数据反序:

STL源码分析之list

这里要注意的是,在链表begin前插入元素,都将改变链表的begin。

sort函数

list不能使用STL的sort算法,因为STL的sort算法必须接受RamdonAccessIterator,而sort的迭代器为Bidirectional iterators,所以list自己实现了这个sort算法:

STL源码分析之list

这个排序算法,本人看的也不是很懂,看了鱼思故渊的博客,略懂程序执行流程。大家可以看他的博客。

当然list还提供了带自定义比较的上述函数

STL源码分析之list

list大概就这些就这些了。

看STL源码真心可以学到东西,首先把基本数据结构复习了一遍,而且SGI里的数据结构比平时写的数据结构优秀多了。其次好好掌握了STL模板库用法。最后就是学到一些细节的东西,比如int(),double()表示这种类型的默认值。

相关推荐

TiDBPingCAP / 0评论 2020-07-29