Python 源码剖析 - PyListObject 对象

Question

元素的一个群是一个非常重要的抽象概念，我们可以将符合某一特性的一堆元素聚集为一个群，当然，还要可以向群中添加或删除元素。这样的群的概念对于编程语言十分重要，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 的关系一样。