列表作為序列型對象都支持哪些操作，它們在底層是怎么實現的？

作者：古明地覺 2024-07-29 12:27:55

開發前端

列表擁有非常多的方法，比如添加元素、查詢元素等，這些都屬于列表的自定義方法。當然不光是列表，任何對象都可以有自己的自定義方法，而這些方法會保存在類型對象的 tp_methods 里面。

楔子

圖片

當然列表除了擁有自定義的方法之外，還擁有作為序列型對象所共有的方法，比如合并、基于索引和切片獲取元素、基于索引和切片設置元素等等。

圖片

這些方法會基于種類被抽象成三個方法簇，分別是：

tp_as_number：數值型對象擁有的方法；
tp_as_sequence：序列型對象擁有的方法；
tp_as_mapping：映射型對象擁有的方法；

每個方法簇都包含了大量的 C 函數，每個 C 函數一般會對應 Python 里的一個魔法方法和操作符。比如 tp_as_sequence 的 sq_concat 對應序列型對象的 __add__ 方法，tp_as_number 的 nb_subtract 對應數值型對象的 __sub__ 方法。

那么接下來我們就詳細剖析一下這些方法的具體實現過程。

列表的相加

序列型對象都實現了加法運算，比如列表，兩個列表相加可以合并為一個新的列表。

print([1, 2, 3] + [4, 5])  
"""
[1, 2, 3, 4, 5]
"""

雖然使用了 + 操作符，但它在底層是由 tp_as_sequence.sq_concat 負責實現的，該字段被賦值為 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;
    // 如果 bb 不是列表，拋出 TypeError
    if (!PyList_Check(bb)) {
        PyErr_Format(PyExc_TypeError,
                  "can only concatenate list (not \"%.200s\") to list",
                  Py_TYPE(bb)->tp_name);
        return NULL;
    }
#define b ((PyListObject *)bb)
    // 兩個列表的長度相加一定小于 PY_SSIZE_T_MAX
    assert((size_t)Py_SIZE(a) + (size_t)Py_SIZE(b) < PY_SSIZE_T_MAX);
    // 新列表的長度，等于相加的兩個列表的長度之和
    size = Py_SIZE(a) + Py_SIZE(b);
    // 如果長度為 0，那么創建一個空列表，然后返回即可
    if (size == 0) {
        return PyList_New(0);
    }
    // 為 PyListObject 和底層數組申請空間（空間大小為 8 * size）
    np = (PyListObject *) list_new_prealloc(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];
        dest[i] = Py_NewRef(v);
    }
    // 將第二個列表的元素增加引用計數之后，拷貝到新列表中
    src = b->ob_item;
    dest = np->ob_item + Py_SIZE(a);
    for (i = 0; i < Py_SIZE(b); i++) {
        PyObject *v = src[i];
        dest[i] = Py_NewRef(v);
    }
    // 將新列表的 ob_size 設置為 size
    Py_SET_SIZE(np, size);
    // 轉成泛型指針之后返回
    return (PyObject *)np;
#undef b
}

邏輯非常簡單，假設兩個列表 a 和 b 相加，過程如下。

先申請一個新列表，長度為 len(a) + len(b)；
將列表 a 的元素拷貝到新列表中；
將列表 b 的元素拷貝到新列表中；

說白了就是兩個 for 循環。

列表的重復

列表可以乘上一個整數，將自身重復指定次數，該過程會返回一個新列表。

print([1, 2, 3] * 3)
"""
[1, 2, 3, 1, 2, 3, 1, 2, 3]
"""

雖然使用了 * 操作符，但它在底層是由 tp_as_sequence.sq_repeat 負責實現的，該字段被賦值為 list_repeat 函數，看一下它的內部邏輯。

// Objects/listobject.c
static PyObject *
list_repeat(PyListObject *a, Py_ssize_t n)
{
    // 獲取 a 指向的列表的長度
    const Py_ssize_t input_size = Py_SIZE(a);
    // 如果列表長度為 0，或者乘上一個小于等于 0 的數
    // 那么創建的新列表的長度依舊是 0，因此直接返回空列表即可
    if (input_size == 0 || n <= 0)
        return PyList_New(0);
    assert(n > 0);
    // 長度有限制，不能超過 PY_SSIZE_T_MAX
    if (input_size > PY_SSIZE_T_MAX / n)
        return PyErr_NoMemory();
    // 新列表的長度
    Py_ssize_t output_size = input_size * n;
    // 為新列表和底層數組申請空間，底層數組的長度為 output_size
    PyListObject *np = (PyListObject *) list_new_prealloc(output_size);
    if (np == NULL)
        return NULL;
    // 指向新列表的底層數組的首元素
    PyObject **dest = np->ob_item;
    // 如果原始列表的長度為 1，比如 a = [1]，n = 3
    // 那么新列表就是 [1, 1, 1]
    if (input_size == 1) {
        // 拿到第一個元素
        PyObject *elem = a->ob_item[0];
        // 因為要重復 n 次，所以引用計數增加 n
        _Py_RefcntAdd(elem, n);
        PyObject **dest_end = dest + output_size;
        // 將新列表的底層數組的元素全部設置為 elem
        while (dest < dest_end) {
            *dest++ = elem;
        }
    }
    // 如果原始列表的長度不為 1
    else {
        PyObject **src = a->ob_item;
        PyObject **src_end = src + input_size;
        // 將原始列表的元素依次拷貝到新列表中，但此時只拷貝了 1 次
        while (src < src_end) {
            _Py_RefcntAdd(*src, n);
            *dest++ = *src++;
        }
        // 將新列表里面的元素再重復 output_size / input_size - 1  次
        // 說白了就是再重復 n - 1 次
        _Py_memory_repeat((char *)np->ob_item, 
                          sizeof(PyObject *)*output_size,
                          sizeof(PyObject *)*input_size);
    }
    // 將新列表的 ob_size 設置為 output_size
    Py_SET_SIZE(np, output_size);
    return (PyObject *) np;
}

假設列表 a 和整數 n 相乘，過程如下。

創建一個新列表，長度為 len(a) * n；
將列表 a 的元素拷貝到新列表中；
將新列表的元素再重復 n - 1 次；

基于索引和切片獲取元素

列表可以基于索引和切片截取元素。

data = [1, 2, 3, 4, 5]
print(data[1])  # 2
print(data[1: 4])  # [2, 3, 4]

在底層它由 tp_as_mapping.mp_subscript 實現，該字段被賦值為 list_subscript 函數，看一下它的內部邏輯。

// Objects/listobject.c
static PyObject *
list_subscript(PyListObject* self, PyObject* item)
{   
    // 在基于索引和切片截取時，所有序列型對象的邏輯都差不多
    if (_PyIndex_Check(item)) {
        // 如果 item 是索引，那么轉成 Py_ssize_t 整數
        Py_ssize_t i;
        i = PyNumber_AsSsize_t(item, PyExc_IndexError);
        if (i == -1 && PyErr_Occurred())
            return NULL;
        // 如果 i 小于 0，那么加上列表長度，轉成正數索引
        if (i < 0)
            i += PyList_GET_SIZE(self);
        // 調用 list_item 獲取 ob_item 中索引為 i 的元素
        return list_item(self, i);
    }
    // 如果 item 是切片
    else if (PySlice_Check(item)) {
        // start, stop, step 分別表示起始位置、終止位置、步長
        // slicelength 表示切片截取的長度，也就是要截取多少個元素
        Py_ssize_t start, stop, step, slicelength, i;
        size_t cur;
        PyObject* result;
        PyObject* it;
        PyObject **src, **dest;
        // 獲取切片的 start、stop、step
        if (PySlice_Unpack(item, &start, &stop, &step) < 0) {
            return NULL;
        }
        // 傳入原始列表的長度，對 start 和 stop 進行調整，并返回 slicelength
        slicelength = PySlice_AdjustIndices(Py_SIZE(self), &start, &stop,
                                            step);
        // 如果 slicelength <= 0，說明截取不到任何元素
        // 比如 data[5: 1] 或者 data[1: 5: -1]，那么直接返回空列表
        if (slicelength <= 0) {
            return PyList_New(0);
        }
        // 如果步長為 1，那么直接將列表中 start 到 stop 之間的元素拷過去即可
        else if (step == 1) {
            return list_slice(self, start, stop);
        }
        // 否則說明步長不為 1
        else {
            // 為創建的新列表和底層數組申請空間
            result = list_new_prealloc(slicelength);
            if (!result) return NULL;
            src = self->ob_item;
            dest = ((PyListObject *)result)->ob_item;
            // 從 start 處開始遍歷，將元素拷貝過去
            // 然后 cur 每次增加 step，遍歷次數為 slicelength
            for (cur = start, i = 0; i < slicelength;
                cur += (size_t)step, i++) {
                it = Py_NewRef(src[cur]);
                dest[i] = it;
            }
            // 將新列表的 ob_size 設置為 slicelength
            Py_SET_SIZE(result, slicelength);
            return result;
        }
    }
    // 否則說明 item 既不是索引也不是切片，那么報錯
    else {
        PyErr_Format(PyExc_TypeError,
                     "list indices must be integers or slices, not %.200s",
                     Py_TYPE(item)->tp_name);
        return NULL;
    }
}

這個和之前介紹的 bytes 對象有點像，因為它們都是序列型對象，在基于索引和切片截取元素時的邏輯也是類似的。

但 bytes 對象只能截取元素，卻不能設置元素，而列表是可以的，因為列表是可變對象。

基于索引和切片設置元素

列表是可變對象，因為它支持設置元素，即對內部元素進行修改。基于索引設置元素就不說了，我們主要看切片，它背后還是有一些復雜的。

data = [1, 2, 3, 4, 5, 6, 7, 8]

# 通過切片設置元素，右值一定是一個可迭代對象
data[0: 3] = [11, 22, 33]
# 會將 data[0] 設置為 11，將 data[1] 設置為 22，將 data[2] 設置為 33
print(data)
"""
[11, 22, 33, 4, 5, 6, 7, 8]
"""

# 而且它們的長度是可以不相等的，這里表示將 [0: 3] 的元素設置為 [1, 2]
# 即 data[0] 設置成 1，data[1] 設置成 2，那么問題來了，data[2] 咋辦？
# 由于右值中已經沒有元素與之匹配了，那么 data[2] 就會被刪掉
data[0: 3] = [1, 2]
print(data)
"""
[1, 2, 4, 5, 6, 7, 8]
"""

# 所以如果想刪除 [0: 3] 的元素，那么只需要執行 data[0: 3] = [] 即可
# 因為 [] 里面沒有元素能與之匹配，所以 data 中 [0: 3] 的位置由于匹配不到
# 那么相當于執行了刪除操作，當然由于 Python 的動態特性，還可以像下面這么做
# data[0: 3] = []、data[0: 3] = ()、data[0: 3] = "" 等等也是沒問題的
data[0: 3] = ""
print(data)
"""
[5, 6, 7, 8]
"""
# 實際上執行 del data[0] 的時候，就是執行了 data[0: 1] = []
# 當然，如果右值元素多的話也是可以的，相當于插入
# 比如這里的 data[0] 匹配 1，然后左邊就結束了
# 于是右側剩余的元素會依次插在后面
data[0: 1] = [1, 2, 3, 4]
print(data)
"""
[1, 2, 3, 4, 6, 7, 8]
"""
# 重點來了，如果切片的步長不等于 1 的話，那么兩邊一定要匹配
# 由于 data[:: 2] 會得到 4 個元素，那么右邊的可迭代對象的長度就必須也是 4
data[:: 2] = ['a', 'b', 'c', 'd']
print(data)
"""
['a', 2, 'b', 4, 'c', 7, 'd']
"""

# 但如果長度不一致，那么會報錯
try:
    data[:: 2] = ['a', 'b', 'c']
except Exception as e:
    # 顯然會報錯
    print(e)  
"""
attempt to assign sequence of size 3 to extended slice of size 4
"""

至于它的源碼有興趣可以自己看一下，在底層它由 tp_as_mapping.mp_ass_subscript 負責實現，該字段被賦值為 list_ass_subscript 函數。邏輯比較長，但不難理解，我們總結一下。

list_subscript 用于獲取元素，list_ass_subscript 用于設置元素。調用這兩個函數，我們即可以傳入索引，也可以傳入切片。

獲取元素時傳入的是索引，那么 list_subscript 內部會調用 list_item，傳入的是切片，那么會調用 list_slice。
設置元素時傳入的是索引，那么 list_ass_subscript 內部會調用 list_ass_item，傳入的是切片，那么會調用 list_ass_slice。并且 list_ass_slice 雖然是設置元素，但刪除元素也是調用的它，比如通過 data[n:n+1]=[] 便可刪除索引為 n 的元素。事實上 remove 和 pop 方法都只是計算出待刪除元素的索引，真正的刪除操作還是通過 list_ass_slice 來執行的。

另外，當傳入切片時，只有步長為 1，才會調用 list_slice 和 list_ass_slice。如果步長不為 1，那么就采用循環的方式逐個遍歷。

小結

以上我們就介紹了列表作為序列型對象擁有的方法，但除了這些它還有很多自定義的方法。

責任編輯：武曉燕來源：古明地覺的編程教室

列表對象元素