Python学习之List对象详解

w8484855@qq.com

本文和大家分享的主要是python的List对象相关内容，一起来看看吧，希望对大家学习python有所帮助。
　　起步
　　typedef struct {
　　PyObject_VAR_HEAD
　　// ob_item为指向元素列表的指针，实际上python中list[0]就是ob_item[0]
　　PyObject **ob_item;
　　Py_ssize_t allocated;
　　} PyListObject;
　　allocated 表示了列表中可容纳的元素总数。我们知道 PyObject_VAR_HEAD 中有一个 ob_size这两者有什么关系了。ob_size代表当前列表中的个数。这就和C++中的vector类似了。它并不是存多少东西就申请多少内存，它会申请一块较大的内存，避免每次新增元素都要进行内存申请和元素拷贝。因此allocated和ob_size满足关系:
　　1. 0 <= ob_size <= allocated2. len(list) == ob_size3. ob_item == NULL 意味着 ob_size == allocated == 0
　　创建PyListObject对象
　　创建列表只能通过 PyList_New 函数来创建, 该函数接受一个 size 参数,意味着列表初始化可容纳元素的个数.
　　PyObject * PyList_New(Py_ssize_t size)
　　{
　　PyListObject *op;
　　...
　　// 缓冲池是否可用
　　if (numfree) {
　　numfree--;
　　op = free_list[numfree];
　　_Py_NewReference((PyObject *)op);
　　} else {
　　// 缓冲池不可用时
　　op = PyObject_GC_New(PyListObject, &PyList_Type);
　　if (op == NULL)
　　return NULL;
　　}
　　// 申请为PyListObject对象中维护的元素列表空间
　　if (size <= 0)
　　op->ob_item = NULL;
　　else {
　　// 空间申请size个空间的数组并重置0
　　op->ob_item = (PyObject **) PyMem_Calloc(size, sizeof(PyObject *));
　　}
　　Py_SIZE(op) = size;
　　op->allocated = size;
　　_PyObject_GC_TRACK(op);
　　return (PyObject *) op;
　　}
　　列表对象的创建需要申请两次内存, 一个是PyListObject本身,一个是元素列表(数组)的申请. numfree 缓冲池, python在创建列表时候先检查缓冲池中是否有可用的对象,如果有,则直接使用这个可用的对象.如果没有才通过 PyObject_GC_New 申请新的PyListObject对象.默认情况下, 缓冲池 free_list 中最多会维护80个PyListObject对象:
　　#define PyList_MAXFREELIST 80static PyListObject *free_list[PyList_MAXFREELIST];static int numfree = 0;
　　而缓冲池的对象的创建时间比较奇葩,它其实是将准备回收list对象后放回缓冲池的:
　　static void list_dealloc(PyListObject *op)
　　{
　　Py_ssize_t i;
　　PyObject_GC_UnTrack(op);
　　Py_TRASHCAN_SAFE_BEGIN(op)
　　if (op->ob_item != NULL) {
　　i = Py_SIZE(op);
　　// 释放list对象中维护的每一个对象
　　while (--i >= 0) {
　　Py_XDECREF(op->ob_item);
　　}
　　PyMem_FREE(op->ob_item);
　　}
　　// 将list对象放回缓冲池中
　　if (numfree < PyList_MAXFREELIST && PyList_CheckExact(op))
　　free_list[numfree++] = op;
　　else
　　Py_TYPE(op)->tp_free((PyObject *)op);
　　Py_TRASHCAN_SAFE_END(op)
　　}
　　设置元素
　　例如在python中 list[2] = 200 调用了PyList_SetItem:
　　int PyList_SetItem(PyObject *op, Py_ssize_t i,
　　PyObject *newitem)
　　{
　　PyObject **p;
　　// 索引越界检查
　　if (i < 0 || i >= Py_SIZE(op)) {
　　Py_XDECREF(newitem);
　　PyErr_SetString(PyExc_IndexError,
　　"list assignment index out of range");
　　return -1;
　　}
　　// 找到ob_item
　　p = ((PyListObject *)op) -> ob_item + i;
　　Py_XSETREF(*p, newitem);
　　return 0;
　　}
　　#define Py_XSETREF(op, op2)                     \
　　do {                                        \
　　PyObject *_py_tmp = (PyObject *)(op);   \
　　(op) = (op2);                           \
　　Py_XDECREF(_py_tmp);                    \
　　} while (0)
　　python会对list对象进行类型检查,然后找到指针要放的位置, 替换为新元素后, 被替换的对象引用计数-1.
　　插入对象
　　对应的是python中 list.insert(2, 200) 的插入动作:
　　[longobject.c]int PyList_Insert(PyObject *op, Py_ssize_t where, PyObject *newitem)
　　{
　　// 类型检查
　　if (!PyList_Check(op)) {
　　PyErr_BadInternalCall();
　　return -1;
　　}
　　return ins1((PyListObject *)op, where, newitem);
　　}
　　static int
　　ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
　　{
　　Py_ssize_t i, n = Py_SIZE(self);
　　PyObject **items;
　　if (list_resize(self, n+1) < 0)
　　return -1;
　　// 确定插入点
　　if (where < 0) {
　　where += n;
　　if (where < 0)
　　where = 0;
　　}
　　if (where > n)
　　where = n;
　　items = self->ob_item;
　　// 元素后移
　　for (i = n; --i >= where; )
　　items[i+1] = items;
　　Py_INCREF(v);
　　items[where] = v;
　　return 0;
　　}
　　函数中处理的插入点为负数和索引越界的情况后确定了插入的位置.将该位置的后面的元素统一向后移一个单位. 需要满足的是, 列表对象必须有足够的可容纳空间.因此调用了 list_resize 来确保这个条件成立.
　　删除元素
　　这是执行 list.remove(200) 这样的操作时:
　　static PyObject *
　　listremove(PyListObject *self, PyObject *v)
　　{
　　Py_ssize_t i;
　　for (i = 0; i < Py_SIZE(self); i++) {
　　int cmp = PyObject_RichCompareBool(self->ob_item, v, Py_EQ);
　　// 如果相等, 删除元素
　　if (cmp > 0) {
　　if (list_ass_slice(self, i, i+1,
　　(PyObject *)NULL) == 0)
　　Py_RETURN_NONE;
　　return NULL;
　　}
　　else if (cmp < 0)
　　return NULL;
　　}
　　PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");
　　return NULL;
　　}
　　python会遍历整个列表直到找到第一个匹配的元素, 列表中没有该元素时候则会抛出异常. list_ass_slice 函数的作用类似于 list[3:5] = [100, 200] , 当第三个参数是NULL时是 del list[3:5] .


来源：栖迟於一丘