列表都有哪些自定義方法，它們是怎么實現(xiàn)的？
楔子
上一篇文章我們介紹了列表作為序列型對象支持的方法，但列表還有很多的自定義方法。作為一名優(yōu)秀的 Python 工程師，我們必須要知道這些方法的實現(xiàn)過程，以及相應(yīng)的時間復(fù)雜度。
實例對象能夠調(diào)用的方法都定義在類型對象中，類型對象無一例外都是 PyTypeObject 結(jié)構(gòu)體實例，該結(jié)構(gòu)體有一個 tp_methods 字段，負(fù)責(zé)維護(hù)實例對象能夠調(diào)用的方法。
// Include/pytypedefs.h
typedef struct _typeobject PyTypeObject;
// Include/cpython/object.h
struct _typeobject {
// ...
struct PyMethodDef *tp_methods;
// ...
}
/* tp_methods 指向 PyMethodDef 結(jié)構(gòu)體類型的數(shù)組
* 所以一個 PyMethodDef 結(jié)構(gòu)體實例，就是 Python 實例對象能夠調(diào)用的一個方法
*/
// Include/methodobject.h
struct PyMethodDef {
// 暴露給 Python 的方法名
const char *ml_name;
// 承載了具體邏輯的 C 函數(shù)
PyCFunction ml_meth;
// 指示函數(shù)的調(diào)用方式和傳遞參數(shù)的方式，比如
/* METH_NOARGS: 表示函數(shù)不接收任何參數(shù)
* METH_O: 函數(shù)只接收一個參數(shù)
* METH_VARARGS: 函數(shù)支持以元組的形式接收多個位置參數(shù)
* METH_KEYWORDS: 函數(shù)支持關(guān)鍵字參數(shù)
* METH_CLASS: 函數(shù)是一個類方法，等價于 Python 里的 @classmethod
* METH_STATIC: 函數(shù)是一個靜態(tài)方法，即 @staticmethod
* METH_FASTCALL: 函數(shù)使用優(yōu)化的快速調(diào)用協(xié)議，Python 3.7 及以上版本可用
傳遞參數(shù)時使用 C 數(shù)組，而不是 Python 元組
* METH_COEXIST: 如果希望存在兩個同名函數(shù)，但類和實例分別調(diào)用不同的函數(shù)
那么便可以指定 METH_COEXIST
*/
int ml_flags;
// 函數(shù)的 docstring
const char *ml_doc;
};而 list 在底層對應(yīng) PyList_Type，它的 tp_methods 字段被賦值為 list_method。
圖片
里面定義了列表可以調(diào)用的方法，我們隨便看一個，比如 append。
// Objects/clinic/listobject.c.h
#define LIST_APPEND_METHODDEF \
{"append", (PyCFunction)list_append, \
METH_O, list_append__doc__},
// 列表調(diào)用時使用的方法名為 append
// 內(nèi)部會執(zhí)行 list_append 函數(shù)
// 只接收一個參數(shù)相信當(dāng)你以后想查看某個對象的方法的底層實現(xiàn)時，已經(jīng)知道該怎么定位了，下面我們就來看看這些方法的實現(xiàn)過程。
append：在尾部追加元素
append 方法在底層對應(yīng) list_append，我們上面已經(jīng)看到了，那么它的實現(xiàn)細(xì)節(jié)是怎樣的呢。
// Objects/listobject.c
static PyObject *
list_append(PyListObject *self, PyObject *object)
{
// 調(diào)用 _PyList_AppendTakeRef 添加元素
if (_PyList_AppendTakeRef(self, Py_NewRef(object)) < 0) {
return NULL;
}
// 該函數(shù)返回 None
Py_RETURN_NONE;
}
// Include/internal/pycore_list.h
static inline int
_PyList_AppendTakeRef(PyListObject *self, PyObject *newitem)
{
assert(self != NULL && newitem != NULL);
assert(PyList_Check(self));
// 獲取列表的長度
Py_ssize_t len = PyList_GET_SIZE(self);
// 獲取列表的容量，即底層數(shù)組的長度
Py_ssize_t allocated = self->allocated;
assert((size_t)len + 1 < PY_SSIZE_T_MAX);
// 如果長度沒有達(dá)到容量
if (allocated > len) {
// 那么將 newitem 設(shè)置在 ob_item 中索引為 len 的位置
PyList_SET_ITEM(self, len, newitem);
// 將列表的 ob_size 加 1
Py_SET_SIZE(self, len + 1);
return 0;
}
// 如果長度達(dá)到容量了，那么會調(diào)用下面這個函數(shù)
return _PyList_AppendTakeRefListResize(self, newitem);
}
// Objects/listobject.c
int
_PyList_AppendTakeRefListResize(PyListObject *self, PyObject *newitem)
{
Py_ssize_t len = PyList_GET_SIZE(self);
assert(self->allocated == -1 || self->allocated == len);
// 邏輯是類似的，但這里會多一步擴容操作
if (list_resize(self, len + 1) < 0) {
Py_DECREF(newitem);
return -1;
}
PyList_SET_ITEM(self, len, newitem);
return 0;
}所謂往尾部追加元素，本質(zhì)上就是將元素設(shè)置在索引為 len 的位置。
insert：在任意位置插入元素
接下來是列表的 insert 方法。
// Objects/clinic/listobject.c.h
#define LIST_INSERT_METHODDEF \
{"insert", _PyCFunction_CAST(list_insert), \
METH_FASTCALL, list_insert__doc__},它由 list_insert 函數(shù)負(fù)責(zé)實現(xiàn)。
// Objects/listobject.c
static PyObject *
list_insert(PyListObject *self, PyObject *const *args, Py_ssize_t nargs)
{
// 函數(shù)返回值，但只會返回 None
PyObject *return_value = NULL;
// 插入的位置
Py_ssize_t index;
// 插入的元素
PyObject *object;
// insert 方法精確接收兩個參數(shù)
if (!_PyArg_CheckPositional("insert", nargs, 2, 2)) {
goto exit;
}
{
// 參數(shù) args 是一個元組，里面包含了插入位置和元素
Py_ssize_t ival = -1;
// 插入位置，對象必須實現(xiàn) __index__
PyObject *iobj = _PyNumber_Index(args[0]);
if (iobj != NULL) {
// 轉(zhuǎn)成 Py_ssize_t
ival = PyLong_AsSsize_t(iobj);
Py_DECREF(iobj);
}
if (ival == -1 && PyErr_Occurred()) {
goto exit;
}
// 賦值給 index
index = ival;
}
// 拿到待插入的元素
object = args[1];
// 調(diào)用 list_insert_impl 執(zhí)行元素插入邏輯
return_value = list_insert_impl(self, index, object);
exit:
// 雖然這里返回了 return_value，但我們知道 insert 方法是沒有返回值的
// 或者說返回值為 None，所以上面的 list_insert_impl 一定返回了 None
return return_value;
}
static PyObject *
list_insert_impl(PyListObject *self, Py_ssize_t index, PyObject *object)
{
// 調(diào)用 ins1 插入元素，插入成功之后返回 None
if (ins1(self, index, object) == 0)
Py_RETURN_NONE;
return NULL;
}
static int
ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
{
// 初始化循環(huán)變量 i
// n 為列表長度
Py_ssize_t i, n = Py_SIZE(self);
// 指向 ob_item 數(shù)組的首元素
PyObject **items;
if (v == NULL) {
PyErr_BadInternalCall();
return -1;
}
assert((size_t)n + 1 < PY_SSIZE_T_MAX);
// 只要涉及到元素個數(shù)的改變，比如添加和刪除元素
// 都會先調(diào)用 list_resize，在里面檢測一下容量
// 比如這里，如果發(fā)現(xiàn) (容量 >= n + 1) && (容量 / 2 <= n + 1)
// 那么說明容量目前是合理的，不需要做任何的擴容或縮容操作（如果條件不滿足則需要）
// 然后將列表的 ob_size 修改為 n + 1，直接返回
if (list_resize(self, n+1) < 0)
return -1;
// 判斷插入位置，如果 where 小于 0，那么加上列表長度
if (where < 0) {
where += n;
// 加上列表長度之后如果還小于 0，那么讓其等于 0
if (where < 0)
where = 0;
}
// 如果插入位置大于列表長度 n，那么讓其等于 n
// 此時相當(dāng)于 append
if (where > n)
where = n;
items = self->ob_item;
// 將 where 以及之后的元素依次向右移動一個位置
for (i = n; --i >= where; )
items[i+1] = items[i];
// 將待插入元素 v 的引用計數(shù)加 1，并設(shè)置在底層數(shù)組中索引為 where 的位置
items[where] = Py_NewRef(v);
return 0;
}以上就是 insert 函數(shù)的底層邏輯，列表在插入數(shù)據(jù)的時候是非常靈活的，不管你在什么位置插入，都是合法的。它會自己調(diào)整，在確定待插入位置 where 之后，會將 where 以及之后的所有元素都向后挪動一個位置，空出來的地方設(shè)置為待插入的值。
另外我們看到 append 和 insert 其實非常像，都是基于索引設(shè)置元素。只不過對于 append 來說，索引就是列表長度，而對于 insert 來說，索引是由外界指定的，但函數(shù)內(nèi)部會進(jìn)行邊界調(diào)整。
并且由于 insert 會涉及元素的移動，所以它的時間復(fù)雜度是 O(n)，而 append 則不會，所以它的時間復(fù)雜度是 O(1)。當(dāng)然在極端情況下（發(fā)生擴容），append 也會退化成 O(n)，只不過這個過程不會頻繁發(fā)生，所以 append 的復(fù)雜度仍然是 O(1) 的。
pop：從尾部彈出一個元素
pop 默認(rèn)會從尾部彈出一個元素，當(dāng)然我們也可以指定索引，彈出指定索引對應(yīng)的元素。如果不指定索引，那么默認(rèn)是 -1。
// Objects/clinic/listobject.c.h
#define LIST_POP_METHODDEF \
{"pop", _PyCFunction_CAST(list_pop), \
METH_FASTCALL, list_pop__doc__},它由 list_pop 函數(shù)負(fù)責(zé)實現(xiàn)。
// Objects/clinic/listobject.c.h
static PyObject *
list_pop(PyListObject *self, PyObject *const *args, Py_ssize_t nargs)
{
// 返回值
PyObject *return_value = NULL;
Py_ssize_t index = -1;
// pop 接收 0 ~ 1 個參數(shù)
if (!_PyArg_CheckPositional("pop", nargs, 0, 1)) {
goto exit;
}
// 如果參數(shù)個數(shù)小于 1，說白了就是沒有傳參，直接跳轉(zhuǎn)到 skip_optional 標(biāo)簽
if (nargs < 1) {
goto skip_optional;
}
{
// 如果傳參了，那么拿到指定的索引
Py_ssize_t ival = -1;
PyObject *iobj = _PyNumber_Index(args[0]);
if (iobj != NULL) {
ival = PyLong_AsSsize_t(iobj);
Py_DECREF(iobj);
}
if (ival == -1 && PyErr_Occurred()) {
goto exit;
}
index = ival;
}
skip_optional:
// 將列表和 index 作為參數(shù)傳進(jìn)去，如果不指定索引，那么 index 默認(rèn)為 -1
return_value = list_pop_impl(self, index);
exit:
// 返回彈出的元素
return return_value;
}
// Objects/listobject.c
static PyObject *
list_pop_impl(PyListObject *self, Py_ssize_t index)
{
PyObject *v;
int status;
// 如果列表為空，那么拋出 IndexError: pop from empty list
if (Py_SIZE(self) == 0) {
/* Special-case most common failure cause */
PyErr_SetString(PyExc_IndexError, "pop from empty list");
return NULL;
}
// 如果 index 小于 0，那么加上列表長度
if (index < 0)
index += Py_SIZE(self);
// 檢測索引是否合法，如果索引小于 0 或大于等于列表長度
// 那么拋出 IndexError: pop index out of range
if (!valid_index(index, Py_SIZE(self))) {
PyErr_SetString(PyExc_IndexError, "pop index out of range");
return NULL;
}
// 獲取 ob_item 數(shù)組
PyObject **items = self->ob_item;
// 拿到索引為 index 的元素，這也是一會兒要返回的元素
v = items[index];
// pop 之后，列表的長度（ob_size）要減去 1
const Py_ssize_t size_after_pop = Py_SIZE(self) - 1;
// 如果減 1 之后長度為 0，說明列表沒有元素了
if (size_after_pop == 0) {
// 增加 v 的引用計數(shù)
Py_INCREF(v);
// 將列表清空掉，注意這里的清空不僅僅是將元素清空，因為列表已經(jīng)為空了
// _list_clear 還會將列表中每個元素指向的對象的引用計數(shù)減 1
// 并將 ob_item 設(shè)置為 NULL，將 ob_size 和 allocated 設(shè)置為 0
// 等于讓列表回歸到初始狀態(tài)，因為 Python 認(rèn)為當(dāng)列表為空時，
// 你可能已經(jīng)不用這個列表了，因此不會再讓它占用額外內(nèi)存
status = _list_clear(self);
}
else {
// 否則檢測彈出的是否是最后一個元素
// 如果不是，那么要將 index 之后的元素依次向前移動一個位置
if ((size_after_pop - index) > 0) {
memmove(&items[index], &items[index+1],
(size_after_pop - index) * sizeof(PyObject *));
}
// 檢測容量的大小是否合理，如果合理，則不做任何操作
// 直接將 ob_size 設(shè)置為 size_after_pop，然后返回即可
status = list_resize(self, size_after_pop);
// 可能有人好奇為什么這里沒有增加引用計數(shù)呢？
// 首先元素從列表中彈出時，應(yīng)該減少引用計數(shù)，但它又返回了，所以還要增加引用計數(shù)
// 因此兩個操作相互抵消，不需要操作引用計數(shù)。但問題來了，為什么上面要執(zhí)行加 1 操作呢
// 很簡單，因為列表為空時會調(diào)用 _list_clear，將引用計數(shù)減 1，所以在調(diào)用之前要先加 1
}
// status 表示 list_resize 的執(zhí)行結(jié)果
// 在 C 中一般約定，執(zhí)行成功返回 0，失敗返回 -1
if (status >= 0) {
// 返回彈出的對象
return v;
}
else {
// list resize failed, need to restore
memmove(&items[index+1], &items[index],
(size_after_pop - index)* sizeof(PyObject *));
items[index] = v;
return NULL;
}
}在 3.8 的時候，pop 彈出元素是這么做的。
list_ass_slice(self, index, index+1, (PyObject *)NULL等價于 self[index: index + 1] = []，但在 3.12 的時候，調(diào)用了 C 標(biāo)準(zhǔn)庫的 memmove 函數(shù)，將 index + 1 以及之后的元素拷貝到 index 的位置。
index：查詢元素首次出現(xiàn)的位置
index 方法可以接收一個元素，然后返回該元素首次出現(xiàn)的位置。當(dāng)然還可以額外指定一個 start 和 end，表示查詢的范圍。
// Objects/clinic/listobject.c.h
#define LIST_INDEX_METHODDEF \
{"index", _PyCFunction_CAST(list_index), \
METH_FASTCALL, list_index__doc__},它由 list_index 負(fù)責(zé)實現(xiàn)。
// Objects/clinic/listobject.c.h
static PyObject *
list_index(PyListObject *self, PyObject *const *args, Py_ssize_t nargs)
{
PyObject *return_value = NULL;
PyObject *value;
Py_ssize_t start = 0;
Py_ssize_t stop = PY_SSIZE_T_MAX;
// index 方法接收 1 ~ 3 個參數(shù)
if (!_PyArg_CheckPositional("index", nargs, 1, 3)) {
goto exit;
}
// args[0] 表示查找的元素
value = args[0];
if (nargs < 2) {
goto skip_optional;
}
// args[1] 表示查找的起始位置
if (!_PyEval_SliceIndexNotNone(args[1], &start)) {
goto exit;
}
if (nargs < 3) {
goto skip_optional;
}
// args[2] 表示查找的結(jié)束位置
if (!_PyEval_SliceIndexNotNone(args[2], &stop)) {
goto exit;
}
skip_optional:
// 調(diào)用 list_index_impl 查找元素
return_value = list_index_impl(self, value, start, stop);
exit:
// 返回
return return_value;
}
// Objects/listobject.c
static PyObject *
list_index_impl(PyListObject *self, PyObject *value, Py_ssize_t start,
Py_ssize_t stop)
{
Py_ssize_t i;
// 如果 start 小于 0，那么加上列表長度
if (start < 0) {
start += Py_SIZE(self);
// 如果相加之后還小于 0，那么等于 0
if (start < 0)
start = 0;
}
// 如果結(jié)束位置小于 0，那么加上列表長度，所以它們都支持負(fù)數(shù)索引
if (stop < 0) {
stop += Py_SIZE(self);
// 如果相加之后還小于 0，那么等于 0
if (stop < 0)
stop = 0;
}
// 從 start 開始遍歷
for (i = start; i < stop && i < Py_SIZE(self); i++) {
// 獲取對應(yīng)元素
PyObject *obj = self->ob_item[i];
Py_INCREF(obj);
// 然后進(jìn)行比較，這個函數(shù)我們之前說過
// 它會先比較地址是否相同，如果地址相同，那么直接判定為相等
// 如果地址不同，那么比較值是否相等
int cmp = PyObject_RichCompareBool(obj, value, Py_EQ);
Py_DECREF(obj);
// 相等返回 1，不相等返回 0，比較失敗返回 -1
// 如果 cmp 大于 0，表示兩者相等，返回索引
if (cmp > 0)
return PyLong_FromSsize_t(i);
else if (cmp < 0)
return NULL;
}
// 到這里說明元素不存在，那么拋出 ValueError: x is not in list
PyErr_Format(PyExc_ValueError, "%R is not in list", value);
return NULL;
}所以列表 index 方法的時間復(fù)雜度為 O(n)，因為它在底層要循環(huán)整個列表，如果運氣好，可能第一個元素就是；運氣不好，就只能循環(huán)整個列表了。
然后需要注意的是，在比較的時候，會先判斷地址是否相同，然后再比較值是否相等。
class A:
def __eq__(self, other):
return False
a = A()
data = [a]
print(a == data[0]) # False
print(data.index(a)) # 0a 和 data[0] 指向的對象不相等，但 data.index(a) 卻返回了相應(yīng)的索引，因為兩者保存的地址是相同的。
同理 if v in data 這種也是類似的，先比較地址，地址不同再比較維護(hù)的值。
count：查詢元素出現(xiàn)的次數(shù)
列表有一個 count 方法，可以計算出某個元素出現(xiàn)的次數(shù)。
// Objects/clinic/listobject.c.h
#define LIST_COUNT_METHODDEF \
{"count", (PyCFunction)list_count, \
METH_O, list_count__doc__},它由 list_count 函數(shù)負(fù)責(zé)實現(xiàn)。
// Objects/listobject.c
static PyObject *
list_count(PyListObject *self, PyObject *value)
{
Py_ssize_t count = 0;
Py_ssize_t i;
// 遍歷每一個元素
for (i = 0; i < Py_SIZE(self); i++) {
PyObject *obj = self->ob_item[i];
// 如果地址相同，直接判定為相等，count 自增 1
if (obj == value) {
count++;
continue;
}
Py_INCREF(obj);
// 地址不同（a is b 不成立），則比較維護(hù)的值是否相等（看 a == b 是否成立）
int cmp = PyObject_RichCompareBool(obj, value, Py_EQ);
Py_DECREF(obj);
if (cmp > 0)
count++;
else if (cmp < 0)
return NULL;
}
// 返回元素出現(xiàn)的次數(shù)
return PyLong_FromSsize_t(count);
}毫無疑問，count 方法無論在什么情況下，它都是一個時間復(fù)雜度為 O(n) 的操作，因為列表必須要從頭遍歷到尾。
但還是要注意里面判斷相等的方式，因為變量只是一個指針，所以 C 的 == 相當(dāng)于 Python 的 is，但 Python 的 == 則對應(yīng) PyObject_RichCompare 函數(shù)。而源碼里面在比較的時候先調(diào)用 ==，所以會先判斷兩者是不是同一個對象。
class A:
def __eq__(self, other):
return False
a = A()
data = [a, a, a]
print(data[0] == a) # False
print(data[1] == a) # False
print(data[2] == a) # False
print(data.count(a)) # 3我們看到列表里的三個元素和 a 都不相等，但計算數(shù)量的時候，結(jié)果是 3。原因就是比較的時候是先比較地址，如果地址一樣，那么認(rèn)為元素相同。
當(dāng)然 PyObject_RichCompareBool 函數(shù)里面已經(jīng)包含了比較地址的邏輯，該函數(shù)會先比較地址是否一樣，如果一樣則認(rèn)為相等，不一樣再比較對象維護(hù)的值是否相等。但在 count 方法里面，將比較地址的邏輯又單獨拿了出來，可以理解為快分支。當(dāng)然即遍沒有也無所謂，因為在函數(shù) PyObject_RichCompareBool 里面還是會先對地址進(jìn)行比較。
remove：刪除指定元素
除了根據(jù)索引刪除元素之外，也可以根據(jù)值來刪除元素，會刪除第一個出現(xiàn)的元素。
// Objects/clinic/listobject.c.h
#define LIST_REMOVE_METHODDEF \
{"remove", (PyCFunction)list_remove, \
METH_O, list_remove__doc__},它由 list_remove 函數(shù)實現(xiàn)。
// Objects/listobject.c
static PyObject *
list_remove(PyListObject *self, PyObject *value)
{
Py_ssize_t i;
// 遍歷每一個元素
for (i = 0; i < Py_SIZE(self); i++) {
PyObject *obj = self->ob_item[i];
Py_INCREF(obj);
// 比較是否相等，如果地址相同，那么認(rèn)為相等
int cmp = PyObject_RichCompareBool(obj, value, Py_EQ);
Py_DECREF(obj);
// 如果相等，那么進(jìn)行刪除
if (cmp > 0) {
// 可以看到在刪除元素的時候，調(diào)用了 list_ass_slice
// 等價于 self[i: i + 1] = []
if (list_ass_slice(self, i, i+1,
(PyObject *)NULL) == 0)
Py_RETURN_NONE;
return NULL;
}
else if (cmp < 0)
return NULL;
}
// 否則說明元素不在列表中，拋出 ValueError: list.remove(x): x not in list
PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");
return NULL;
}以上就是 remove 函數(shù)的底層實現(xiàn)，說白了就是一層 for 循環(huán)，依次比較列表的每個元素和待刪除元素是否相等。如果出現(xiàn)了相等的元素，則刪除，然后直接返回，因為只刪除一個；但如果整個循環(huán)遍歷結(jié)束也沒有發(fā)現(xiàn)滿足條件的元素，那么報錯，待刪除元素不存在。
所以背后的邏輯并沒有我們想象中的那么神秘。
reverse：翻轉(zhuǎn)列表
如果是你的話，你會怎么對列表進(jìn)行翻轉(zhuǎn)呢？顯然是采用雙指針，頭指針指向列表的第一個元素，尾指針指向列表的最后一個元素，然后兩兩交換。
交換完畢之后，頭指針后移一位、尾指針前移一位，繼續(xù)交換。當(dāng)兩個指針相遇時，停止交換，而 Python 底層也是這么做的。
// Objects/clinic/listobject.c.h
#define LIST_REVERSE_METHODDEF \
{"reverse", (PyCFunction)list_reverse, \
METH_NOARGS, list_reverse__doc__},它由 list_reverse 負(fù)責(zé)實現(xiàn)。
// Objects/clinic/listobject.c.h
static PyObject *
list_reverse(PyListObject *self, PyObject *Py_UNUSED(ignored))
{
return list_reverse_impl(self);
}
// Objects/listobject.c
static PyObject *
list_reverse_impl(PyListObject *self)
{
// 如果列表長度不大于 1，那么什么也不做，直接返回 None 即可
if (Py_SIZE(self) > 1)
// 大于 1 的話，執(zhí)行 reverse_slice，傳遞了兩個參數(shù)
// 第一個參數(shù)顯然是底層數(shù)組首元素的地址
// 而第二個參數(shù)則是底層數(shù)組中索引為 ob_size 的元素的地址
// 但很明顯能訪問的最大索引應(yīng)該是 ob_size - 1 才對啊
// 別急，我們繼續(xù)往下看，看一下 reverse_slice 函數(shù)的實現(xiàn)
reverse_slice(self->ob_item, self->ob_item + Py_SIZE(self));
Py_RETURN_NONE;
}
static void
reverse_slice(PyObject **lo, PyObject **hi)
{
assert(lo && hi);
// 我們看到又執(zhí)行了一次 --hi
// 讓二級指針 hi 指向了索引為 ob_size - 1 的元素
--hi;
// 數(shù)組元素的地址，從左往右是依次增大的
// 如果 lo < hi，證明 lo 依舊在 hi 的左邊，那么交換指向的元素
// 如果 lo > hi，證明兩者相遇了，交換結(jié)束
while (lo < hi) {
// 交換指向的元素，下面三步等價于 *lo, *hi = *hi, *lo
// 但 C 不支持這么寫，它需要借助一個中間變量
PyObject *t = *lo;
*lo = *hi;
*hi = t;
// 兩個指針繼續(xù)靠近，指向的元素繼續(xù)交換，直到兩個指針相遇
++lo;
--hi;
}
}所以到現(xiàn)在，你還認(rèn)為 Python 的列表神秘嗎？雖然我們很難自己寫出一個 Python 解釋器，但是底層的一些思想其實并沒有那么難，作為一名程序猿很容易想的到。
clear：清空列表
將列表中的元素全部清空，讓列表回到初始狀態(tài)。
// Objects/clinic/listobject.c.h
#define LIST_CLEAR_METHODDEF \
{"clear", (PyCFunction)list_clear, \
METH_NOARGS, list_clear__doc__},它由 list_clear 負(fù)責(zé)實現(xiàn)。
// Objects/clinic/listobject.c.h
static PyObject *
list_clear(PyListObject *self, PyObject *Py_UNUSED(ignored))
{
return list_clear_impl(self);
}
// Objects/listobject.c
static PyObject *
list_clear_impl(PyListObject *self)
{
// 在介紹 pop 方法的時候我們提到過這個函數(shù)
_list_clear(self);
Py_RETURN_NONE;
}
static int
_list_clear(PyListObject *a)
{
Py_ssize_t i;
PyObject **item = a->ob_item;
if (item != NULL) {
// 獲取列表的長度
i = Py_SIZE(a);
// 將 ob_size 設(shè)置為 0
Py_SET_SIZE(a, 0);
// ob_item 設(shè)置為 NULL
a->ob_item = NULL;
// 將容量設(shè)置為 0
a->allocated = 0;
// 將列表中每個元素指向的對象的引用計數(shù)減 1
while (--i >= 0) {
Py_XDECREF(item[i]);
}
// 釋放底層數(shù)組所占的內(nèi)存
PyMem_Free(item);
}
return 0;
}過程非常簡單，當(dāng)列表為空時，除了將 ob_size 和 allocated 設(shè)置為 0 之外，還會將底層數(shù)組釋放掉，減少內(nèi)存占用。
copy：列表的拷貝
調(diào)用列表的 copy 方法，可以將列表拷貝一份。
// Objects/clinic/listobject.c.h
#define LIST_COPY_METHODDEF \
{"copy", (PyCFunction)list_copy, \
METH_NOARGS, list_copy__doc__},它由 list_copy 負(fù)責(zé)實現(xiàn)。
// Objects/clinic/listobject.c.h
static PyObject *
list_copy(PyListObject *self, PyObject *Py_UNUSED(ignored))
{
return list_copy_impl(self);
}
// Objects/listobject.c
static PyObject *
list_copy_impl(PyListObject *self)
{
// 調(diào)用 list_slice，也就是基于切片獲取元素
// 所以 data.copy() 等價于 data[:]
return list_slice(self, 0, Py_SIZE(self));
}
static PyObject *
list_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh)
{
// 指向創(chuàng)建的新列表
PyListObject *np;
// 指向列表的底層數(shù)組的首元素
PyObject **src, **dest;
Py_ssize_t i, len;
// 創(chuàng)建的新列表的長度
len = ihigh - ilow;
if (len <= 0) {
return PyList_New(0);
}
// 創(chuàng)建底層數(shù)組長度為 len 的列表
np = (PyListObject *) list_new_prealloc(len);
if (np == NULL)
return NULL;
src = a->ob_item + ilow;
dest = np->ob_item;
// 將原始列表中的元素依次拷貝到新列表中
for (i = 0; i < len; i++) {
PyObject *v = src[i];
dest[i] = Py_NewRef(v);
}
// 將新列表的 ob_size 設(shè)置為 len
Py_SET_SIZE(np, len);
// 轉(zhuǎn)成泛型指針之后返回
return (PyObject *)np;
}過程非常簡單，但列表的 copy 方法或者說 data[:] 這種叫做列表的淺拷貝。關(guān)于列表的深淺拷貝也是初學(xué)者容易犯的錯誤之一，我們看一個 Python 的例子。
data = [[]]
# 默認(rèn)是淺拷貝，這個過程會創(chuàng)建一個新列表
# 但我們說列表里面的元素都是指針，因此只會將里面的指針拷貝一份
# 而指針指向的內(nèi)存并沒有拷貝
data_cp = data.copy()
# 兩個對象的地址是一樣的
print(id(data[0]), id(data[0]))
"""
1338344668224 1338344668224
"""
# 操作 data[0], 會改變 data_cp[0]
data[0].append(123)
print(data, data_cp)
"""
[[123]] [[123]]
"""
# 操作 data_cp[0]，會改變 data[0]
data_cp[0].append(456)
print(data, data_cp)
"""
[[123, 456]] [[123, 456]]
"""之所以會有這樣的現(xiàn)象，是因為 Python 的變量、容器里面的元素都是一個泛型指針 PyObject *，在傳遞的時候會傳遞指針， 但是在操作的時候會操作指針指向的內(nèi)存。
所以 data.copy() 就是創(chuàng)建了一個新列表，然后把元素拷貝了過去，只不過元素都是指針。因為只是拷貝指針，沒有拷貝指針指向的對象（內(nèi)存），所以它們指向的是同一個對象。
但如果我們就想在拷貝指針的同時也拷貝指針指向的對象呢？答案是使用一個叫 copy 的模塊。
import copy
data = [[]]
# 此時拷貝的時候，會把指針指向的對象也給拷貝一份
data_cp1 = copy.deepcopy(data)
data_cp2 = data[:]
data[0].append(123)
print(data_cp1) # [[]]
print(data_cp2) # [[123]]
# data[:] 這種方式也是淺拷貝，所以修改 data[0]，會影響 data_cp2[0]
# 但是沒有影響 data_cp1[0]，證明它們是相互獨立的，因為指向的是不同的對象淺拷貝示意圖如下：
圖片
里面的兩個指針數(shù)組存儲的元素是一樣的，都是同一個對象的地址。
深拷貝示意圖如下：
圖片
里面的兩個指針數(shù)組存儲的元素是不一樣的，因為是不同對象的地址。
注意：copy.deepcopy 雖然在拷貝指針的同時會將指針指向的對象也拷貝一份，但這僅僅是針對可變對象，而不可變對象是不會拷貝的。
import copy
data = [[], "古明地覺"]
data_cp = copy.deepcopy(data)
print(data[0] is data_cp[0]) # False
print(data[1] is data_cp[1]) # True為什么會這樣，其實原因很簡單。因為不可變對象是不支持本地修改的，你若想修改只能創(chuàng)建新的對象并指向它。但這對其它的變量而言則沒有影響，其它變量該指向誰就還指向誰。
因為 b = a 只是將 a 存儲的對象的指針拷貝一份給 b，然后 a 和 b 都指向了同一個對象，至于 a 和 b 本身則是沒有任何關(guān)系的。如果此時 a 指向了新的對象，是完全不會影響 b 的，b 還是指向原來的對象。
因此，如果一個指針指向的對象不支持本地修改，那么深拷貝不會拷貝對象本身，因為指向的是不可變對象，所以不會有修改一個影響另一個的情況出現(xiàn)。
關(guān)于列表還有一些陷阱：
data = [[]] * 5
data[0].append(1)
print(data) # [[1], [1], [1], [1], [1]]
# 列表乘上一個 n，等于把列表里面的元素重復(fù) n 次
# 但列表里面存儲的是指針，也就是將指針重復(fù) n 次
# 所以上面的列表里面的 5 個指針存儲的地址是相同的
# 也就是說，它們都指向了同一個列表
# 這種方式創(chuàng)建的話，里面的指針都指向了不同的列表
data = [[], [], [], [], []]
data[0].append(1)
print(data) # [[1], [], [], [], []]
# 再比如字典，在后續(xù)系列中會說
d = dict.fromkeys([1, 2, 3, 4], [])
print(d) # {1: [], 2: [], 3: [], 4: []}
d[1].append(123)
print(d) # {1: [123], 2: [123], 3: [123], 4: [123]}
# 它們都指向了同一個列表類似的陷阱還有很多，因此在工作中要注意，否則一不小心就會出現(xiàn)大問題。
總之記住三句話：雖然 Python 一切皆對象，但我們拿到的其實是指向?qū)ο蟮闹羔槪蛔兞吭趥鬟f的時候本質(zhì)上是將對象的指針拷貝一份，所以 Python 是變量的賦值傳遞、對象的引用傳遞；在操作變量（指針）的時候，會自動操作變量（指針）指向的內(nèi)存。
小結(jié)
到此關(guān)于列表的內(nèi)容就介紹完了，作為 Python 中的萬能容器，我們可以自由地添加、修改和刪除元素。但在使用的時候要了解它的底層結(jié)構(gòu)以及元素是如何存儲的，應(yīng)該在什么場景下使用列表，它的每個方法的時間復(fù)雜度是多少。
