[绝对原创 转载请注明出处]
Python源码剖析
——PyListObject对象(1)
本文作者: Robert Chen (search.pythoner@gmail.com )
元素的一个群是一个非常重要的抽象概念，我们可以将符合某一特性的一堆元素聚集为一个群，当然，还要可以向群中添加或删除元素。这样的群的概念对于编程语言十分重要，C语言就内建了数组的概念，随着编程语言的发展，现在所有的编程语言都会在语言中或标准库中实现这样的群的概念。而且群的概念还进一步地细分为多种实现方式，比如map，vector等。每一种实现都为某种目的的元素聚集或元素访问提供了极大的方便。
PyListObject是Python提供的对列表的抽象，熟悉C++的人可能会条件反射地将PyListObject与C++中的list对应起来（至少它们名字是相同的：）。而实际上，Python中的列表和C++的STL中的vector更为相似。
PyListObject对象可以有效地支持插入，添加，删除等操作，在Python的列表中，无一例外地存放的都是PyObject的指针。所以实际上，你可以这样看待Python中的列表：vector<PyObject*>。
很显然，PyListObject一定是一个变长对象，因为不同的list中存储的元素的个数会是不同的。但是，和PyStringObject不同的是，PyListObject对象还支持插入删除等操作，可以在运行时动态地调整其所维护的内存，所以，它还是一个可变对象。
下面看一看PyListObject的声明：
[listobject.h]
typedef struct { PyObject_VAR_HEAD /* Vector of pointers to list elements. list[0] is ob_item[0], etc. */ PyObject **ob_item; int allocated; } PyListObject;
如我们所想，在PyListObject的头，赫然是一个PyObject_VAR_HEAD，随后是一个PyObject**，这个指针正是维护了PyObject*列表的关键。我们知道在PyObject_VAR_HEAD中，有一个ob_size，而在PyListObject的最后，又有一个allocated，那么这两个变量之间的关系是什么呢？
其实，ob_size和allocated都和内存的管理有关，PyListObject所采用的内存管理策略和C++中vector采取的内存分配策略是一样的。它并不是存了多少东西就申请对应大小的内存，这样的申请策略显然是低效的，因为我们有理由相信，用户选用列表正是为了频繁地插入删除元素。因此，PyListObject在每一次需要申请内存的时候，会申请一大块内存，这是申请的总内存的大小记录在allocated中，而这些内存中实际被有效的PyObject*占用的内存大小被记录在了ob_size中。那么不难得到，对于一个PyListObject对象，一定存在以下的关系：
0 <= ob_size <= allocated
len(list) == ob_size
ob_item == NULL implies ob_size == allocated == 0
这里ob_size和allocated的关系就像C++的vector中size和capacity的关系一样。
