python源码学习(十)——list

By | 2014/07/11

python的list容器和C++ stl中的list容器不同,它和C++中的vector容器比较相似,python的list容器中存储的都是PyObject*指针,PyListObject对象不仅是一个变长对象,还是一个可变对象。看一下PyListObject的定义:

typedef struct {
    PyObject_VAR_HEAD
    /* Vector of pointers to list elements.  list[0] is ob_item[0], etc. */
    PyObject **ob_item;

    /* ob_item contains space for 'allocated' elements.  The number
     * currently in use is ob_size.
     * Invariants:
     *     0 <= ob_size <= allocated
     *     len(list) == ob_size
     *     ob_item == NULL implies ob_size == allocated == 0
     * list.sort() temporarily sets allocated to -1 to detect mutations.
     *
     * Items must normally not be NULL, except during construction when
     * the list is not yet visible outside the function that builds it.
     */
    Py_ssize_t allocated;
} PyListObject;

加入一个list能容纳10个元素,已经装入5个元素,则ob_size变为5,allocated为10。
创建与维护:
python创建list的唯一方法是PyList_New。这个函数接收一个size参数。源码如下:

PyObject *
PyList_New(Py_ssize_t size)
{
    PyListObject *op;
    size_t nbytes;
#ifdef SHOW_ALLOC_COUNT
    static int initialized = 0;
    if (!initialized) {
        Py_AtExit(show_alloc);
        initialized = 1;
    }
#endif

    if (size < 0) {
        PyErr_BadInternalCall();
        return NULL;
    }
    /* Check for overflow without an actual overflow,
     *  which can cause compiler to optimise out */
    if ((size_t)size > PY_SIZE_MAX / sizeof(PyObject *))
        return PyErr_NoMemory();
    nbytes = size * sizeof(PyObject *);
    if (numfree) {
        numfree--;
        op = free_list[numfree];
        _Py_NewReference((PyObject *)op);
#ifdef SHOW_ALLOC_COUNT
        count_reuse++;
#endif
    } else {
        op = PyObject_GC_New(PyListObject, &PyList_Type);
        if (op == NULL)
            return NULL;
#ifdef SHOW_ALLOC_COUNT
        count_alloc++;
#endif
    }
    if (size <= 0)
        op->ob_item = NULL;
    else {
        op->ob_item = (PyObject **) PyMem_MALLOC(nbytes);
        if (op->ob_item == NULL) {
            Py_DECREF(op);
            return PyErr_NoMemory();
        }
        memset(op->ob_item, 0, nbytes);
    }
    Py_SIZE(op) = size;
    op->allocated = size;
    _PyObject_GC_TRACK(op);
    return (PyObject *) op;
}

从上面的代码发现python的list要先检查是否内存溢出,然后为对象申请空间,开辟缓冲池,在没有元素的情况下将其初始化为null。
python的list的内存结构如下:
2014-07-11 16:54:36的屏幕截图
从以上可以看出,python的list其实在内存中是分为两部分的,ob_item是指向一个object*的数组。python的list容器主要有一下几种操作,设置、插入、删除:
设置:设置元素不许要移动内存;
插入:需要移动内存;
删除:需要移动内存。
同样,python的list也存在对象池这个概念,一个list释放后其实是释放了ob_item这个指针所指的内存,当需要再用到这个list是,python将会从对象池中取出这个list,并重新设置他的ob_item指针。如下:
2014-07-11 17:29:24的屏幕截图
OK,list讲完了,明天学习dict对象。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.