KJHの博客

List 就是链表，这个我们在很久之前就学习过了单向链表，双向链表。之前对STL有过大概的剖析，但没涉及到链表，早几天使用到了STL中的，对其中的有些细节不明了，特意重新阅读了下源码，对STL中的List 加深一下理解。。。。论指针（地址）的重要性。

附带说一句，阅读源码，建议使用Source Insight，非常好的源码阅读工具，没有其二。

1、List 概述

list 和 vector 是两个最常用的容器（序列式容器）。二者最显著的区别自然就是vector是连续线性空间，list则是不连续线性空间，相比于vector（动态数组），它的好处是每次插入和删除一个元素，只需配置或释放一个元素空间，对于任何位置的元素插入或元素移除，list永远是常数时间。尺有所长，寸有所短，list 寻址某一元素也没有vector（常数时间）方便。那么什么时机下最适合使用哪一种容器呢？必须视元素的多寡，元素的构造复杂度，元素存取行为的特定而定。

2、list 的节点

侯捷先生剖析的是STL203版的源码，我们这里紧跟下时尚，来剖析最新的STL源码http://www.sgi.com/tech/stl/download.html

以下是STL list的节点结构：

1
2
3
4
5
6
7
8

struct _List_node_base {
  _List_node_base* _M_next;
  _List_node_base* _M_prev;
};
template <class _Tp>
struct _List_node : public _List_node_base {
  _Tp _M_data;
};

显然这是一个双向链表，链表节点的数据部分单独的放在一个结构体中，然后通过继承来获得链表的先后指针。node_base中仅含指针，这赶脚有点类似于linux内核中的list。

先了解几个必要成员及函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

//对源码略作调整
iterator _M_start;                  //表示目前使用空间的头
iterator _M_finish;                 //表示目前使用空间的尾（尾：最后一个元素的下一个位置）
iterator _M_end_of_storage;         //表示目前可用空间的尾
iterator begin() { return _M_start; }
iterator end()   { return _M_finish; }
size_type size() const                  //目前空间元素的个数
{
	return size_type(end() - begin());
}
size_type max_size() const
{
	return size_type(-1) / sizeof(_Tp);
}
size_type capacity() const              //容量
{
	return size_type(_M_end_of_storage - begin());
}
bool empty() const
{
	return begin() == end();
}

这里先学习 insert() 函数（后面介绍另一个版本的 insert()：插入n个指定元素）：关于 construc() 函数的介绍可以参见其它博客

这里继续学习基于配置器之上的一些内存基本处理工具。主要剖析 SGI STL 源码（http ://www.sgi.com/tech/stl/download.html v3.3）中的几个内存处理函数(由函数名可知，是对未初始化空间的初始化操作，即通过复制或赋值的方式初始化未初始化的空间)：
uninitialized_copy()，uninitialized_copy_n()，uninitialized_fill()，uninitialized_fill_n()。

先学习 uninitiated_copy()

1
2
3
4
5
6
7
8
9
10
11
12

//stl source code（v3.3）
//defined in <stl_uninitialized.h>
inline char* uninitialized_copy(const char* __first, const char* __last, char* __result) 
{
	memmove(__result, __first, __last - __first);
	return __result + (__last - __first);  //返回该连续区域的末尾
}
inline wchar_t*   // typedef unsigned short wchar_t;
uninitialized_copy(const wchar_t* __first, const wchar_t* __last, wchar_t* __result)
{
	memmove(__result, __first, sizeof(wchar_t)* (__last - __first));
	return __result + (__last - __first);

上面两个是对两种特化类型的处理，下面为泛化版本

考虑到小型区块所可能造成的内存破碎问题，SGI 设计了双层级配置器，这里则学习第二级配置器，第二级配置器的设计思想为：

1. 如果配置区块超过128 bytes，则移交给第一级配置器处理；
2. 如果配置区块小于128 bytes，则采用内存池管理（memory pool）。每次配置一大块内存，则维护对应的自由链表（free-list），下次若再有相同大小的内存需求，就直接从 free-list 中拨出（没有就继续配置内存，具体后面讲述），如果客端释换小额区块，就有配置器回收到 free-list 中。

需要说明的是：本系列引用的STL源码版本为 v3.3，对比版本 v2.03 风格上有了些许变化，但设计思想还是不变的。

1
2
3
4
5
6
7
8
9

/* part of stl source code v3.3 */
enum { _ALIGN = 8 };                //小型区块的上调边界
enum { _MAX_BYTES = 128 };          //小型区块的上限
enum { _NFREELISTS = 16 }; // _MAX_BYTES/_ALIGN   //free-list 编号数
//配置内存后，维护对应内存块的空闲链表节点结构
union _Obj {
	union _Obj* _M_free_list_link;   //空闲链表
	char _M_client_data[1];    /* The client sees this. 用户使用的*/
};

考虑内存对其等因素，SGI 第二级配置器会主动将任何小额区块的内存需求量上调至 8 的倍数。并维护 16 个 free-list，各自管理大小分别为 8，16，24，32，40，48，56，64，72，80，88，96，104，112，120，128 bytes 的小额区块。

我们再来学习内存的配置与释放（定义在头文件 <stl_alloc.h> 中）。其设计思想为：

• 向 system heap 要求空间；
• 考虑多线程 (multi-threads) 状态；
• 考虑内存不足时的应变措施；
• 考虑过多 “小型区块” 可能造成的内存碎片 (fragment) 问题。

我们后面将通过分析源码来了解这设计思想是如何在设计中体现的。SGI 设计了双层级配置器，第一级配置器直接使用 malloc() 和 free()，第二级则视情况采用不同策略，并采用了复杂的内存池(memory pool) 整理方式。
整个设计究竟只开放第一级配置器，或是同时开放第二级配置器，取决于宏 __USE_MALLOC 是否被定义。