spb 2018-06-25
STL用环状双向链表来实现list,方法和leveldb的缓存环状链表一样,链表持有一个傀儡节点,不存储数据,只为这个链表的入口。迭代链表时,首先通过链表获得这个这个傀儡节点,然后通过next迭代所有数据。
STL将链表的傀儡节点作为链表的end节点,傀儡节点的next为begin节点,这样以来,就可以用[begin,end)这种左闭右开的形式来表示迭代器范围,和其他容器保持一致。
因为是双向链表,所以有两个指针,分别指向前向指针和后向指针。
因为list数据不是存储在连续的内存内,所以不能通过指针的加1减一来实现迭代器。list数据是通过指针链表结合在一起的,所以为了迭代所有数据,必须通过上个节点找到下个节点的地址,进而访问下个节点。list迭代器就是用这个原理,实现如下:
以上就是list的迭代器实现,只实现了迭代器的++,--,取值,成员调用四个基本操作,并没有像vector迭代器那样的+n操作,主要是因为地址不连续。
接下来看下list实现,list只有一个成员变量,就是那个傀儡节点,也是end节点。
先来看构造函数:
这个构造函数为默认构造函数,就是创建一个节点,然后前后指向自己而已。说到配置器,由于list用的是自己定义节点结构体,所以也定义了相应类型的配置器。
list还定义几种构造函数,用n个值来初始化list,将另一个list的一部分数据来初始化list和复制构造函数。
这几个函数调用了fill_initialize和range_initialize,来看下这两个函数。
这两个函数最后分别调用了insert函数的不同版本。一起来看下这两个insert函数。
这两个函数通过循环调用 iterator insert(iterator position, const T& x) 这个insert版本,将数据一个一个插入到position之前,初始时就是插入到傀儡节点后面,形成初始链表,源码如下:
最后看下析构函数
这两个函数,clear是清空链表所有数据,然后put_node是将傀儡节点回收了。
最后一个交换两个链表,只需要通过标准函数库的swap函数,交换两个傀儡节点即可,因为傀儡节点是每个链表的入口。
往链表前插一个元素,通过调用insert完成。
往链表尾巴插一个元素,也是通过insert函数完成。
移除一个元素
这个函数也很简单,只需要将被移除节点的前后节点跳过当前节点即可。
前后删除一个节点,用erase函数实现:
这个函数是很多list接口调用的函数。这个函数有点难看懂,我把《STL源码剖析》上的图截下来,容易理解:
;
源码如下:
按着序号来读那个示意图,应该能看懂,本质上就那几个关键节点的前后关系。
有了这个函数之后,就出现了一些很有用的函数:
将数值为value的所有元素移除:
合并两个链表,前提是两个链表必须有序,合并之后的链表也是有序的。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);
}
这个函数是用于将链表数据反序:
这里要注意的是,在链表begin前插入元素,都将改变链表的begin。
list不能使用STL的sort算法,因为STL的sort算法必须接受RamdonAccessIterator,而sort的迭代器为Bidirectional iterators,所以list自己实现了这个sort算法:
这个排序算法,本人看的也不是很懂,看了鱼思故渊的博客,略懂程序执行流程。大家可以看他的博客。
当然list还提供了带自定义比较的上述函数
list大概就这些就这些了。
看STL源码真心可以学到东西,首先把基本数据结构复习了一遍,而且SGI里的数据结构比平时写的数据结构优秀多了。其次好好掌握了STL模板库用法。最后就是学到一些细节的东西,比如int(),double()表示这种类型的默认值。