本章通过底层C源码来分析Python里的列表类型,以及与列表相关的基本操作。比如,列表的获取数据、更新数据的操作,列表的片段操作,列表的加法、乘法操作,以及列表的迭代操作等。

    页面导航: 英文教程的下载地址:

    本篇文章是根据英文教程《Python Tutorial》来写的学习笔记。该英文教程的下载地址如下:

    百度盘地址:http://pan.baidu.com/s/1c0eXSQG

    DropBox地址:点此进入DropBox链接

    Google Drive:点此进入Google Drive链接

    这是学习笔记,不是翻译,因此,内容上会与英文原著有些不同。以下记录是根据英文教程的第十章来写的。(文章中的部分链接,包括下载链接,可能需要通过代理访问!)

    本篇文章也会涉及到Python的C源代码,这些C源码都是2.7.8版本的。想使用gdb来调试python源代码的话,就需要按照前面"Python基本的操作运算符"文章中所说的,使用configure --with-pydebug命令来重新编译安装python。

    如果Python的官方网站取消了Python-2.7.8.tgz的源码包的话,可以在以下两个链接中下载到:

    DropBox:Python-2.7.8.tgz的DropBox网盘链接

    Google Drive:Python-2.7.8.tgz的Google Drive网盘链接

列表类型及相关操作:

    先看个简单的例子:

[email protected]:~$ gdb -q python
....................................................
>>> list1 = [123,234,457,789]
....................................................

Breakpoint 1, PyEval_EvalFrameEx (f=0xb7daca44, throwflag=0)
    at Python/ceval.c:2203
2203	            x =  PyList_New(oparg);
(gdb) l
2198	                continue;
2199	            }
2200	            break;
2201	
2202	        case BUILD_LIST:
2203	            x =  PyList_New(oparg);
2204	            if (x != NULL) {
2205	                for (; --oparg >= 0;) {
2206	                    w = POP();
2207	                    PyList_SET_ITEM(x, oparg, w);
(gdb) until 2210
PyEval_EvalFrameEx (f=0xb7daca44, throwflag=0) at Python/ceval.c:2210
2210	                continue;
(gdb) ptype (PyListObject *)x
type = struct {
    struct _object *_ob_next;
    struct _object *_ob_prev;
    Py_ssize_t ob_refcnt;
    struct _typeobject *ob_type;
    Py_ssize_t ob_size;
    PyObject **ob_item;
    Py_ssize_t allocated;
} *
(gdb) p ((PyListObject *)x)->ob_size 
$1 = 4
(gdb) p *(PyIntObject *)(((PyListObject *)x)->ob_item[0])
$2 = {_ob_next = 0x8208170, _ob_prev = 0x8208148, ob_refcnt = 5, 
  ob_type = 0x81c2d80, ob_ival = 123}
(gdb) p *(PyIntObject *)(((PyListObject *)x)->ob_item[1])
$3 = {_ob_next = 0x820884c, _ob_prev = 0x8208824, ob_refcnt = 4, 
  ob_type = 0x81c2d80, ob_ival = 234}
(gdb) p *(PyIntObject *)(((PyListObject *)x)->ob_item[2])
$4 = {_ob_next = 0xb7ca1a00, _ob_prev = 0x820f9b0, ob_refcnt = 3, 
  ob_type = 0x81c2d80, ob_ival = 457}
(gdb) p *(PyIntObject *)(((PyListObject *)x)->ob_item[3])
$5 = {_ob_next = 0x820f988, _ob_prev = 0xb7ca1ae0, ob_refcnt = 3, 
  ob_type = 0x81c2d80, ob_ival = 789}
(gdb) p ((PyListObject *)x)->allocated 
$6 = 4
(gdb) c
Continuing.
[40767 refs]
>>> list1
[123, 234, 457, 789]
....................................................


    从上面gdb的调试输出中,可以看到Python列表类型所对应的C结构体为PyListObject,该结构体的具体结构如下所示:

type = struct {
    struct _object *_ob_next;
    struct _object *_ob_prev;
    Py_ssize_t ob_refcnt;
    struct _typeobject *ob_type;
    Py_ssize_t ob_size;
    PyObject **ob_item;
    Py_ssize_t allocated;
}


    在该结构中,前4个字段是每个Python对象都具有的字段。

    第5个ob_size字段表示该列表所包含的对象个数。

    第6个ob_item字段则是一个动态数组,该数组中包含了列表的每个成员对象的指针值。

    第7个allocated字段表示Python内部为ob_item动态数组所分配的内存空间中,实际可以容纳多少个对象。在一开始创建列表时,allocated的值等于ob_size的值。当对ob_item动态数组进行添加删除对象的操作时,allocated的值就可能会大于ob_size的值。比如,从列表中删除了某个对象后,ob_item数组对应的内存空间可以不改变即allocated值不变,只是将ob_size减一即可,多余的内存空间可以用于下一次的添加对象操作。

    在上面gdb的调试输出里,就可以看到list1列表的这几个字段的值:

(gdb) p ((PyListObject *)x)->ob_size 
$1 = 4
(gdb) p *(PyIntObject *)(((PyListObject *)x)->ob_item[0])
$2 = {_ob_next = 0x8208170, _ob_prev = 0x8208148, ob_refcnt = 5, 
  ob_type = 0x81c2d80, ob_ival = 123}
(gdb) p *(PyIntObject *)(((PyListObject *)x)->ob_item[1])
$3 = {_ob_next = 0x820884c, _ob_prev = 0x8208824, ob_refcnt = 4, 
  ob_type = 0x81c2d80, ob_ival = 234}
(gdb) p *(PyIntObject *)(((PyListObject *)x)->ob_item[2])
$4 = {_ob_next = 0xb7ca1a00, _ob_prev = 0x820f9b0, ob_refcnt = 3, 
  ob_type = 0x81c2d80, ob_ival = 457}
(gdb) p *(PyIntObject *)(((PyListObject *)x)->ob_item[3])
$5 = {_ob_next = 0x820f988, _ob_prev = 0xb7ca1ae0, ob_refcnt = 3, 
  ob_type = 0x81c2d80, ob_ival = 789}
(gdb) p ((PyListObject *)x)->allocated 
$6 = 4
....................................................
>>> list1
[123, 234, 457, 789]


    可以看到,这些字段的值与list1实际存储的数据是一致的。

    在前面的gdb调试输出里,还可以看到,列表在内部的组建过程,是通过Python/ceval.c文件中的PyEval_EvalFrameEx函数里的opcode(操作码)为BUILD_LIST的执行过程来完成的:

PyObject *
PyEval_EvalFrameEx(PyFrameObject *f, int throwflag)
{
        ............................................
        switch (opcode) {
        ........................................
        case BUILD_LIST:
            x =  PyList_New(oparg);
            if (x != NULL) {
                for (; --oparg >= 0;) {
                    w = POP();
                    PyList_SET_ITEM(x, oparg, w);
                }
                PUSH(x);
                continue;
            }
            break;
        ........................................
        } /* switch */
        ............................................
}


    上面在BUILD_LIST过程中,会先通过PyList_New(oparg)来创建一个空列表(根据oparg参数来确定列表的ob_item动态数组的初始大小)。接着会在for循环里,循环通过PyList_SET_ITEM宏,将需要添加的对象,都设置到新创建的列表的ob_item数组中。PyList_SET_ITEM是定义在Include/listobject.h头文件里的宏:

/* Macro, trading safety for speed */
#define PyList_GET_ITEM(op, i) (((PyListObject *)(op))->ob_item[i])
#define PyList_SET_ITEM(op, i, v) (((PyListObject *)(op))->ob_item[i] = (v))
#define PyList_GET_SIZE(op)    Py_SIZE(op)


    PyList_SET_ITEM宏的第一个op参数表示需要操作的列表对象,第二个i参数表示需要设置的ob_item动态数组的索引值,第三个v参数表示需要设置到该索引的对象的指针值。在PyList_SET_ITEM宏的上面还定义了一个PyList_GET_ITEM宏,该宏则是用于从列表中获取某个成员对象的,如下例所示:

[email protected]:~$ gdb -q python
....................................................
>>> list1
[123, 234, 457, 789]
>>> list1[0]
....................................................

Breakpoint 2, PyEval_EvalFrameEx (f=0xb7d8ce44, throwflag=0)
    at Python/ceval.c:1388
1388	            w = POP();
(gdb) l
1383	            SET_TOP(x);
1384	            if (x != NULL) continue;
1385	            break;
1386	
1387	        case BINARY_SUBSCR:
1388	            w = POP();
1389	            v = TOP();
1390	            if (PyList_CheckExact(v) && PyInt_CheckExact(w)) {
1391	                /* INLINE: list[int] */
1392	                Py_ssize_t i = PyInt_AsSsize_t(w);
(gdb) l
1393	                if (i < 0)
1394	                    i += PyList_GET_SIZE(v);
1395	                if (i >= 0 && i < PyList_GET_SIZE(v)) {
1396	                    x = PyList_GET_ITEM(v, i);
1397	                    Py_INCREF(x);
1398	                }
1399	                else
1400	                    goto slow_get;
1401	            }
1402	            else
(gdb) c
Continuing.
123
....................................................
>>> list1[-1]
789
>>> list1[3]
789
>>> 


    可以看到,当从列表中获取某个索引对应的成员对象时,在内部是通过Python/ceval.c文件中的PyEval_EvalFrameEx函数里的opcode(操作码)为BINARY_SUBSCR的执行过程来完成的。该执行过程就会使用PyList_GET_ITEM(v, i)宏来获取索引值为i的成员对象指针。从该过程里还可以看到,当索引值小于0时,它还会将索引值加上列表包含的对象个数,从而将其转为有效的索引值,例如,上面的list1包含了4个整数对象,那么 list[-1] 就相当于 list[-1 + 4] 即 list1[3]。

    此外,从列表中获取某个片段的过程,又与上面获取单个对象的过程有所不同,如下例所示:

[email protected]:~$ gdb -q python
....................................................
>>> list1
[123, 234, 457, 789]
>>> list1[1:4]
Program received signal SIGINT, Interrupt.
0xb7ee09f8 in ___newselect_nocancel () from /lib/libc.so.6
(gdb) b list_slice
Breakpoint 3 at 0x8080206: file Objects/listobject.c, line 472.
(gdb) c
Continuing.


Breakpoint 3, list_slice (a=0xb7c956c4, ilow=1, ihigh=4)
    at Objects/listobject.c:472
472	    if (ilow < 0)
(gdb) c
Continuing.
[234, 457, 789]
....................................................
>>>


    当list1[1:4]脚本执行时,在内部会通过Objects/listobject.c文件中的list_slice函数来获取索引1到索引4的片段,list_slice这个C函数的源码如下:

static PyObject *
list_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh)
{
    PyListObject *np;
    PyObject **src, **dest;
    Py_ssize_t i, len;
    if (ilow < 0)
        ilow = 0;
    else if (ilow > Py_SIZE(a))
        ilow = Py_SIZE(a);
    if (ihigh < ilow)
        ihigh = ilow;
    else if (ihigh > Py_SIZE(a))
        ihigh = Py_SIZE(a);
    // 这里用ihigh - ilow计算出len值,
    // len值为获取的片段中所包含的对象个数,
    // 例如,list1[1:4]脚本执行时,
    // ilow为1,ihigh为4,len为4 - 1即3,
    // 那么下面就会将索引值1到4(不包括4在内)
    // 的3个对象构成一个新列表,并将这个
    // 新列表作为结果返回。
    len = ihigh - ilow;
    // 根据len值创建一个新的空列表,
    // 新列表的初始长度为len,
    // 最后的for语句就会将a即原列表中的ilow到
    // ihigh(不包括ihigh在内)的对象拷贝到
    // 这个新列表中。
    np = (PyListObject *) PyList_New(len);
    if (np == NULL)
        return NULL;

    // 将a->ob_item[ilow]作为片段拷贝的
    // 起始点。
    src = a->ob_item + ilow;
    dest = np->ob_item;
    // 通过for循环将片段拷贝到新列表中。
    for (i = 0; i < len; i++) {
        PyObject *v = src[i];
        Py_INCREF(v);
        dest[i] = v;
    }
    // 将新列表作为结果返回。
    return (PyObject *)np;
}


    根据这段C源码,前面例子中的list1[1:4]执行时,就会使用list1[1],list1[2],list[3]这三个对象构成一个新列表,并将新列表作为slice(片段)操作的结果了。

    下面再看下列表中更新数据的例子:

[email protected]:~$ gdb -q python
....................................................
>>> list1
[123, 234, 457, 789]
....................................................
>>> list1[2] = 2001
....................................................

Breakpoint 1, list_ass_item (a=0xb7c956c4, i=2, v=0x820f9c4)
    at Objects/listobject.c:764
764	    if (i < 0 || i >= Py_SIZE(a)) {
(gdb) until 775
list_ass_item (a=0xb7c956c4, i=2, v=0x820f9c4) at Objects/listobject.c:775
775	    return 0;
(gdb) p *(PyIntObject *)v
$1 = {_ob_next = 0xb7ca1114, _ob_prev = 0xb7ca01d8, ob_refcnt = 4, 
  ob_type = 0x81c2d80, ob_ival = 2001}
(gdb) p i
$2 = 2
(gdb) p *(PyIntObject *)a->ob_item[i]
$3 = {_ob_next = 0xb7ca1114, _ob_prev = 0xb7ca01d8, ob_refcnt = 4, 
  ob_type = 0x81c2d80, ob_ival = 2001}
(gdb) c
Continuing.
....................................................
>>> list1[2]
2001
....................................................


    从调试输出中可以看到,当 list1[2] = 2001 脚本执行时,在Python内部会通过list_ass_item这个C函数来完成列表的设置操作。

    该函数的第一个参数a表示需要操作的列表对象,本例中对应的就是list1。

    第二个参数i表示需要设置的索引值,本例中的索引值为2

    第三个参数v则是需要设置到该索引里的对象指针,本例中就是2001这个整数对象的指针。

    这个C函数定义在Objects/listobject.c文件里:

static int
list_ass_item(PyListObject *a, Py_ssize_t i, PyObject *v)
{
    PyObject *old_value;
    if (i < 0 || i >= Py_SIZE(a)) {
        // 当索引值超出范围时,会抛出IndexError的错误。
        PyErr_SetString(PyExc_IndexError,
                        "list assignment index out of range");
        return -1;
    }
    // 当v为NULL时(NULL就是0),
    // 会通过list_ass_slice函数从列表中删除
    // 索引值为i的对象。
    // 例如:del list1[2]的脚本执行时,
    // 也会调用当前这个list_ass_item函数,
    // 只不过此时的v为0
    if (v == NULL)
        return list_ass_slice(a, i, i+1, v);
    Py_INCREF(v);
    // 先获取索引值为i的原对象指针,
    // 最后会将这个被替换掉的原对象
    // 的引用计数减一。当一个对象的引用
    // 计数减到0时,就表示该对象没被使用了,
    // 就可以被Python的垃圾回收机制给处理掉。
    old_value = a->ob_item[i];
    // 将新的对象指针设置到列表中。
    a->ob_item[i] = v;
    Py_DECREF(old_value);
    return 0;
}


    从上面的源码中可以看到,当索引值超出列表的有效范围时,会抛出IndexError的错误。此外,当使用del语句删除列表里的单个成员对象时,也会调用list_ass_item函数,如下例所示:

[email protected]:~$ gdb -q python
....................................................
>>> list1
[123, 234, 457, 789]
....................................................
>>> list1[4] = 22

....................................................
Traceback (most recent call last):
  File "", line 1, in 
IndexError: list assignment index out of range
[40801 refs]
>>> del list1[2]

Breakpoint 1, list_ass_item (a=0xb7c956c4, i=2, v=0x0)
    at Objects/listobject.c:764
764	    if (i < 0 || i >= Py_SIZE(a)) {
(gdb) n
769	    if (v == NULL)
(gdb) 
770	        return list_ass_slice(a, i, i+1, v);
(gdb) s
list_ass_slice (a=0xb7c956c4, ilow=2, ihigh=3, v=0x0)
    at Objects/listobject.c:623
623	    PyObject **recycle = recycle_on_stack; /* will allocate more if needed */
(gdb) c
Continuing.
[40800 refs]
>>> list1
[123, 234, 789]
....................................................


    上面del语句在执行时,最终会通过list_ass_slice函数来完成具体的删除操作。该函数除了可以对列表里的成员进行删除操作外,还可以对列表中的片段进行设置:

[email protected]:~$ gdb -q python
....................................................
>>> list1
[123, 234, 457, 789]
>>> list1[2:3] = (105, 106)
....................................................

Breakpoint 2, list_ass_slice (a=0xb7ca1ab4, ilow=2, ihigh=3, v=0xb7d3a99c)
    at Objects/listobject.c:623
623	    PyObject **recycle = recycle_on_stack; /* will allocate more if needed */
....................................................
>>> list1
[123, 234, 105, 106, 789]
>>> list1[3:5] = [111, 112]
>>> list1
[123, 234, 105, 111, 112]
>>> list1[3:5] = 'ab'
>>> list1
[123, 234, 105, 'a', 'b']
>>> list1[3:5] = 'e'
>>> list1
[123, 234, 105, 'e']
>>> list1[3:5] = 2003
Traceback (most recent call last):
  File "", line 1, in 
TypeError: can only assign an iterable
>>> 


    从上面的输出中可以看到,当对列表进行slice(片段)的设置操作时,设置到列表片段中的对象必须是iterable(可迭代)的。例如,上面的(105, 106)是元组类型,[111, 112]是列表类型,'ab''e'则是字符串类型,这几个对象类型都是可迭代的。当使用不可迭代的对象时,如上面的2003这个整数对象是不可迭代的,就会抛出TypeError错误。

    在对列表片段进行设置时,都是通过list_ass_slice这个底层C函数来完成的,该函数也定义在Objects/listobject.c文件中:

/* a[ilow:ihigh] = v if v != NULL.
 * del a[ilow:ihigh] if v == NULL.
 *
 * Special speed gimmick:  when v is NULL and ihigh - ilow <= 8, it's
 * guaranteed the call cannot fail.
 */
static int
list_ass_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)
{
    ................................................
    // v为NULL时,会将变量n设置为0,
    // n为0时,下面的变量d就会是负值,
    // 在d小于0时,就会执行删除操作。
    if (v == NULL)
        n = 0;
    else {
        // v是需要设置的可迭代的对象,
        // 当v本身就是列表或元组时,
        // PySequence_Fast就直接将其返回,因为
        // 列表和元组的C结构是差不多的,
        // 两者的成员对象的指针
        // 都存储在ob_item数组中,
        // 只不过列表的ob_item是动态数组,
        // 里面的成员及数组尺寸是可变的,
        // 而元组的ob_item数组里的成员及
        // 数组的尺寸是不变的。
        // 当v是其他的迭代类型,如字符串时,
        // 就会创建一个新的列表,并将字符串里的
        // 每个字符都添加到新列表中,每个字符
        // 都对应为一个列表成员。
        v_as_SF = PySequence_Fast(v, "can only assign an iterable");
        if(v_as_SF == NULL)
            goto Error;
        n = PySequence_Fast_GET_SIZE(v_as_SF);
        // 将ob_item数组指针设置到vitem。
        vitem = PySequence_Fast_ITEMS(v_as_SF);
    }
    ................................................

    // ilow为要设置的列表片段的起始点,
    // ihigh为要设置的片段的结束点,
    // ihigh - ilow得到片段的长度,
    // 该长度信息不包括ihigh在内。
    norig = ihigh - ilow;
    ................................................
    // 下面的n表示需要设置的可迭代对象里的成员数,
    // norig则表示需要设置的列表片段的长度,
    // d是n与norig的差值。

    // 当d等于0时,说明迭代对象的成员数与
    // 片段长度相同,那么迭代对象里的成员
    // 可以刚好覆盖掉片段里的原成员,
    // 因此就不需要对列表进行额外的
    // 添加和删除操作。
    // 例如:list1[3:5] = [111, 112]执行时,
    // 就只需将list1[3]替换为111,
    // 并将list1[4]替换为112即可。

    // 当d小于0时,说明迭代对象的成员数
    // 小于列表片段长度,那么要将片段
    // 完全用迭代对象的成员进行替换的话,
    // 就必须对列表进行删除操作,将片段
    // 长度超出的部分给删除掉。
    // 例如:list1[3:5] = 'e'执行时,
    // 在将list1[3]设置为'e'后,
    // 还需要将list1[4]给删除掉。
    // 当然,下面具体执行时,会先对列表的ob_item
    // 数组执行删除操作,最后再执行设置成员的操作。

    // 当d大于0时,说明迭代成员数大于
    // 片段长度,那么片段要完全容纳下这些
    // 迭代成员的话,就必须对列表进行
    // 插入成员的操作。
    // 例如:list1[2:3] = (105, 106)执行时,
    // 在将list1[2]设置为105后,
    // 还需要在list1[2]后面插入106,让106
    // 成为新的list1[3]成员,而原来的list1[3]
    // 成员则变为list1[4]成员。
    // 当然,下面具体执行时,会先对列表的ob_item
    // 数组执行插入操作,最后再执行设置成员的操作。
    d = n - norig;
    ................................................

    // d小于0时,对列表的ob_item数组执行删除操作。
    if (d < 0) { /* Delete -d items */
        memmove(&item[ihigh+d], &item[ihigh],
            (Py_SIZE(a) - ihigh)*sizeof(PyObject *));
        list_resize(a, Py_SIZE(a) + d);
        item = a->ob_item;
    }
    // d大于0时,对列表的ob_item数组执行插入操作。
    else if (d > 0) { /* Insert d items */
        k = Py_SIZE(a);
        if (list_resize(a, k+d) < 0)
            goto Error;
        item = a->ob_item;
        memmove(&item[ihigh+d], &item[ihigh],
            (k - ihigh)*sizeof(PyObject *));
    }
    // 最后将迭代对象里的成员,依次设置
    // 到列表片段中。
    for (k = 0; k < n; k++, ilow++) {
        PyObject *w = vitem[k];
        Py_XINCREF(w);
        item[ilow] = w;
    }
    ................................................
}


    列表作为包含多个成员的集合,其与集合相关的操作都定义在list_as_sequence变量中,该变量也定义在Objects/listobject.c文件里:

static PySequenceMethods list_as_sequence = {
    (lenfunc)list_length,                       /* sq_length */
    (binaryfunc)list_concat,                    /* sq_concat */
    (ssizeargfunc)list_repeat,                  /* sq_repeat */
    (ssizeargfunc)list_item,                    /* sq_item */
    (ssizessizeargfunc)list_slice,              /* sq_slice */
    (ssizeobjargproc)list_ass_item,             /* sq_ass_item */
    (ssizessizeobjargproc)list_ass_slice,       /* sq_ass_slice */
    (objobjproc)list_contains,                  /* sq_contains */
    (binaryfunc)list_inplace_concat,            /* sq_inplace_concat */
    (ssizeargfunc)list_inplace_repeat,          /* sq_inplace_repeat */
};


    其中的list_slicelist_ass_item以及list_ass_slice这几个C函数,在之前已经介绍过了。

    当使用len内建函数来获取列表中所包含的成员个数时,在内部就会通过上面的list_length这个C函数来完成具体的操作(该函数也定义在Objects/listobject.c文件中):

[email protected]:~$ gdb -q python
....................................................
>>> list1
[123, 234, 457, 789]
>>> len(list1)
....................................................

Breakpoint 4, list_length (a=0xb7c956c4) at Objects/listobject.c:434
434	    return Py_SIZE(a);
(gdb) c
Continuing.
4
>>> 


    list_length函数中,其实就是通过Py_SIZE宏来获取列表的成员个数,该宏定义在Include/object.h头文件里:

#define Py_REFCNT(ob)           (((PyObject*)(ob))->ob_refcnt)
#define Py_TYPE(ob)             (((PyObject*)(ob))->ob_type)
#define Py_SIZE(ob)             (((PyVarObject*)(ob))->ob_size)


    从上面定义中可以看到,Py_SIZE宏其实就是获取的列表对象里的ob_size字段的值。该字段的含义在开头已经解释过了,它表示一个列表对象中一共包含了多少个成员。

    当对列表执行加运算时,内部会通过上面list_as_sequence变量中的list_concat函数来完成具体的操作,如下例所示:

[email protected]:~$ gdb -q python
....................................................
>>> list1
[123, 234, 457, 789]
>>> list2
['hello', 'zengl']
>>> list1 + list2
....................................................

Breakpoint 5, list_concat (a=0xb7c956c4, bb=0xb7ca1ab4)
    at Objects/listobject.c:512
512	    if (!PyList_Check(bb)) {
....................................................
(gdb) c
Continuing.
[123, 234, 457, 789, 'hello', 'zengl']
>>> 


    list_concat函数定义在Objects/listobject.c文件里:

static PyObject *
list_concat(PyListObject *a, PyObject *bb)
{
    Py_ssize_t size;
    Py_ssize_t i;
    PyObject **src, **dest;
    PyListObject *np;
    // 列表只能与列表进行连接操作。
    // 如果与其他类型的对象进行连接操作的话,
    // 就会抛出TypeError错误。
    if (!PyList_Check(bb)) {
        PyErr_Format(PyExc_TypeError,
                  "can only concatenate list (not \"%.200s\") to list",
                  bb->ob_type->tp_name);
        return NULL;
    }
#define b ((PyListObject *)bb)
    // 得到两个列表连接后的总长度。
    size = Py_SIZE(a) + Py_SIZE(b);
    if (size < 0)
        return PyErr_NoMemory();
    // 根据总长度创建一个新的空列表。
    np = (PyListObject *) PyList_New(size);
    if (np == NULL) {
        return NULL;
    }
    src = a->ob_item;
    dest = np->ob_item;
    // 先将第一个列表里的成员拷贝
    // 到新列表的开头。
    for (i = 0; i < Py_SIZE(a); i++) {
        PyObject *v = src[i];
        Py_INCREF(v);
        dest[i] = v;
    }
    src = b->ob_item;
    dest = np->ob_item + Py_SIZE(a);
    // 最后再将第二个列表里的成员
    // 拷贝到新列表的结尾。
    // 从而将两个列表连接成为一个新的列表。
    for (i = 0; i < Py_SIZE(b); i++) {
        PyObject *v = src[i];
        Py_INCREF(v);
        dest[i] = v;
    }
    // 将新列表作为结果返回。
    return (PyObject *)np;
#undef b
}


    因此,两个列表在执行加法运算时,得到的是一个copy(拷贝),该拷贝里包含了两个列表里的所有成员。

    当对列表执行乘法运算时,内部会通过上面list_as_sequence变量中的list_repeat函数来完成具体的操作,如下所示:

[email protected]:~$ gdb -q python
....................................................
>>> list1
[123, 'hello']
>>> list1 * 4
....................................................

Breakpoint 6, list_repeat (a=0xb7ca1bcc, n=4) at Objects/listobject.c:552
552	    if (n < 0)
(gdb) p *(PyIntObject *)a->ob_item[0]
$7 = {_ob_next = 0x8208170, _ob_prev = 0x8208148, ob_refcnt = 3, 
  ob_type = 0x81c2d80, ob_ival = 123}
(gdb) c
Continuing.
[123, 'hello', 123, 'hello', 123, 'hello', 123, 'hello']
>>> 


    list_repeat函数的第一个参数a表示需要操作的原列表,上例中对应为list1。第二个参数n表示需要重复的次数,上例中为4,表示需要将list1里的成员重复4次。该函数也定义在Objects/listobject.c文件里:

static PyObject *
list_repeat(PyListObject *a, Py_ssize_t n)
{
    Py_ssize_t i, j;
    Py_ssize_t size;
    PyListObject *np;
    PyObject **p, **items;
    PyObject *elem;
    if (n < 0)
        n = 0;
    if (n > 0 && Py_SIZE(a) > PY_SSIZE_T_MAX / n)
        return PyErr_NoMemory();
    // 根据原列表a的长度乘以重复次数n,
    // 得到重复后列表的总长度。
    size = Py_SIZE(a) * n;
    if (size == 0)
        return PyList_New(0);
    // 根据总长度创建一个新的空列表。
    np = (PyListObject *) PyList_New(size);
    if (np == NULL)
        return NULL;

    items = np->ob_item;
    // 如果原列表中只包含单个成员的话,
    // 直接将这个成员重复拷贝n次到新列表中即可。
    if (Py_SIZE(a) == 1) {
        elem = a->ob_item[0];
        for (i = 0; i < n; i++) {
            items[i] = elem;
            Py_INCREF(elem);
        }
        return (PyObject *) np;
    }
    p = np->ob_item;
    items = a->ob_item;
    // 通过双循环,将原列表里的所有成员
    // 重复拷贝n次到新列表中。
    // 如果列表a为[123, 'hello'],n为4的话,
    // 重复拷贝后,得到的新列表就会是:
    // [123, 'hello', 123, 'hello', 123, 'hello', 123, 'hello']
    for (i = 0; i < n; i++) {
        for (j = 0; j < Py_SIZE(a); j++) {
            *p = items[j];
            Py_INCREF(*p);
            p++;
        }
    }
    // 将新列表作为结果返回。
    return (PyObject *) np;
}


    因此,列表的乘法运算得到的结果也是一个copy(拷贝),该拷贝是原列表经过重复拷贝生成的。

    当通过in关键字,来判断某个对象是否存在于列表中时,Python内部会通过前面list_as_sequence变量中的list_contains函数来完成具体的操作,如下所示:

[email protected]:~$ gdb -q python
....................................................
>>> list1
[123, 'hello']
>>> 123 in list1
....................................................

Breakpoint 7, list_contains (a=0xb7ca1bcc, el=0x820815c)
    at Objects/listobject.c:443
443	    for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i)
(gdb) l
438	list_contains(PyListObject *a, PyObject *el)
439	{
440	    Py_ssize_t i;
441	    int cmp;
442	
443	    for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i)
444	        cmp = PyObject_RichCompareBool(el, PyList_GET_ITEM(a, i),
445	                                           Py_EQ);
446	    return cmp;
447	}
(gdb) p *(PyIntObject *)a->ob_item[0]
$8 = {_ob_next = 0x8208170, _ob_prev = 0x8208148, ob_refcnt = 6, 
  ob_type = 0x81c2d80, ob_ival = 123}
(gdb) p *(PyIntObject *)el
$9 = {_ob_next = 0x8208170, _ob_prev = 0x8208148, ob_refcnt = 6, 
  ob_type = 0x81c2d80, ob_ival = 123}
(gdb) c
Continuing.
True
>>> 


    list_contains函数的第一个参数a表示要进行判断的列表,本例中对应为list1。第二个参数el表示要进行判断的对象,本例中对应为123这个整数对象。list_contains函数中会通过for语句,从索引值0开始,循环将列表里的每个成员提取出来,并通过PyObject_RichCompareBool函数与el进行比较,当el与列表中的某个成员相等时,就说明该对象的值存在于列表中,结果就会返回True,否则返回False

    但是,在下面这种情况下,in语句执行时并不会去调用list_contains函数:

[email protected]:~$ gdb -q python
....................................................
>>> 3 in ['hello','world',3,3000]
True
>>> 


    由于上面的['hello','world',3,3000]是一个临时的列表,Python编译器在进行编译时,会将其编译为元组类型。因此,这里的in语句在执行时就不会去调用list_contains函数了,因为该列表已经被编译器在内部转为了元组类型了。这是作者通过gdb调试器分析出来的结果,如果读者想进行调试的话,需要对该脚本的opcode(操作码)进行一步步的调试分析。

    下面再看下与列表迭代相关的内部C函数:

[email protected]:~$ gdb -q python
....................................................
>>> list1
[123, 'hello']
>>> for x in list1:
...   print x
... 

Breakpoint 8, list_iter (seq=0xb7ca1bcc) at Objects/listobject.c:2869
2869	    if (!PyList_Check(seq)) {
(gdb) p *(PyIntObject *)((PyListObject *)seq)->ob_item[0]
$13 = {_ob_next = 0x8208170, _ob_prev = 0x8208148, ob_refcnt = 3, 
  ob_type = 0x81c2d80, ob_ival = 123}
(gdb) c
Continuing.

Breakpoint 9, listiter_next (it=0xb7ca1d1c) at Objects/listobject.c:2904
2904	    assert(it != NULL);
(gdb) c
Continuing.
123

Breakpoint 9, listiter_next (it=0xb7ca1d1c) at Objects/listobject.c:2904
2904	    assert(it != NULL);
(gdb) c
Continuing.
hello

Breakpoint 9, listiter_next (it=0xb7ca1d1c) at Objects/listobject.c:2904
2904	    assert(it != NULL);
(gdb) c
Continuing.
>>> 


    从上面的输出中可以看到,在Python脚本中用for语句对列表进行迭代时,内部会先调用list_iter这个C函数来获取列表相关的迭代器。再根据该迭代器,通过listiter_next函数将列表里的每个成员依次获取出来。这两个C函数以及与列表迭代器相关的C结构体,都定义在Objects/listobject.c文件中:

/*********************** List Iterator **************************/

typedef struct {
    PyObject_HEAD
    // it_index字段中存储了
    // 迭代所需的列表索引值
    long it_index;
    // it_seq字段则存储了
    // 需要进行迭代的列表,
    // 当列表中的所有成员
    // 都迭代完后,该字段
    // 会被设置为NULL(即0)
    PyListObject *it_seq; /* Set to NULL when iterator is exhausted */
} listiterobject;

....................................................

static PyObject *
list_iter(PyObject *seq)
{
    // listiterobject就是上面定义过的
    // 列表迭代器相关的C结构体。
    listiterobject *it;

    if (!PyList_Check(seq)) {
        PyErr_BadInternalCall();
        return NULL;
    }
    // 创建一个新的列表迭代器,
    // 并将迭代器的指针存储到it变量中。
    it = PyObject_GC_New(listiterobject, &PyListIter_Type);
    if (it == NULL)
        return NULL;
    // 将迭代器的初始索引值设置为0,
    // 这样当第一次进行迭代操作时,就会
    // 将列表中的第一个成员给获取出来了。
    it->it_index = 0;
    Py_INCREF(seq);
    // 将seq设置为需要进行迭代的列表。
    it->it_seq = (PyListObject *)seq;
    _PyObject_GC_TRACK(it);
    // 将新的迭代器作为结果返回。
    return (PyObject *)it;
}

....................................................

static PyObject *
listiter_next(listiterobject *it)
{
    PyListObject *seq;
    PyObject *item;

    assert(it != NULL);
    // 从迭代器中获取
    // 需要进行迭代的列表对象。
    seq = it->it_seq;
    if (seq == NULL)
        return NULL;
    assert(PyList_Check(seq));

    // 如果迭代器的it_index索引值
    // 小于列表的总成员数时,说明当前的
    // it_index是一个有效的索引值,
    // 则通过PyList_GET_ITEM宏将列表中
    // it_index索引对应的成员给获取出来,
    // 并将该成员对象作为本次迭代的结果。
    if (it->it_index < PyList_GET_SIZE(seq)) {
        item = PyList_GET_ITEM(seq, it->it_index);
        ++it->it_index;
        Py_INCREF(item);
        return item;
    }

    Py_DECREF(seq);
    // 如果列表中的所有成员都迭代完后,
    // 则将迭代器的it_seq字段设置为NULL,
    // 并将NULL作为结果返回。
    it->it_seq = NULL;
    return NULL;
}


    以上就是和Python的列表类型及列表的基本操作相关的内容。

结束语:

    限于篇幅,本章先到这里。下一篇将介绍与列表相关的脚本函数。

    OK,休息,休息一下 o(∩_∩)o~~

    一个有纸、笔、橡皮擦并且坚持严格的行为准则的人,实质上就是一台通用图灵机。

——  艾伦·图灵
 
上下篇

下一篇: Python列表相关的脚本函数

上一篇: Python字符串相关的函数

相关文章

Python用户自定义函数

Python的基本语法

Python列表相关的脚本函数

Python基本的操作运算符

Python词典类型

Python三角函数