append

向 List Object 任意位置插入數(shù)據(jù)，只要插入位置不是結(jié)尾，那么就需要將插入位置之后的元素后移，因此插入數(shù)據(jù)的時(shí)間復(fù)雜度為 O(n)。向數(shù)據(jù)插入數(shù)據(jù)有一個(gè)特例位置，向尾部追加 append 一個(gè)元素，時(shí)間復(fù)雜度為 O(1) 。

Python 的實(shí)現(xiàn)非常簡(jiǎn)單：

static int app1(PyListObject *self, PyObject *v) {Py_ssize_t n = PyList_GET_SIZE(self);// 省略了錯(cuò)誤處理代碼if (list_resize(self, n+1) < 0)return -1;Py_INCREF(v);PyList_SET_ITEM(self, n, v);return 0; }

只有兩步：重置 List 空間；新增元素設(shè)置到尾部。非常直接，常數(shù)時(shí)間內(nèi)即可完成。

pop

List 通過(guò) pop 方法彈出元素。具體實(shí)現(xiàn)：

//Objects/listobject.c:1025 static PyObject * list_pop_impl(PyListObject *self, Py_ssize_t index) /*[clinic end generated code: output=6bd69dcb3f17eca8 input=b83675976f329e6f]*/ {PyObject *v;int status;// 忽略一些無(wú)關(guān)代碼v = self->ob_item[index];// 如果要彈出結(jié)尾元素，快捷處理if (index == Py_SIZE(self) - 1) {status = list_resize(self, Py_SIZE(self) - 1);if (status >= 0)return v; /* and v now owns the reference the list had */elsereturn NULL;}// 如果位于 List 中間，則刪除元素Py_INCREF(v);status = list_ass_slice(self, index, index+1, (PyObject *)NULL);if (status < 0) {Py_DECREF(v);return NULL;}return v; }

pop 元素根據(jù)彈出元素是否是尾部元素區(qū)別處理，如果是尾部元素，那么只是進(jìn)行 resize 操作，彈出元素會(huì)被直接截?cái)鄴仐墶?shí)際上在這個(gè)過(guò)程中有可能根本不會(huì)發(fā)生真正的 resize，只是調(diào)整了 ob_size 的大小。此時(shí)時(shí)間復(fù)雜度為O(1)。

較為復(fù)雜的情況是彈出元素在數(shù)組中間或者頭部，當(dāng)目標(biāo)元素彈出后，會(huì)在 List 中出現(xiàn)一個(gè) “空缺”，其后的元素會(huì)被 “前移”，這與插入過(guò)程恰好相反，時(shí)間復(fù)雜度為O(n)。

因此，pop 方法從尾部彈出的效率更高，長(zhǎng) List 頻繁的從中部彈出元素，性能會(huì)變得很差。如果有隨機(jī)彈出的需要，最好考慮其他更合適的容器對(duì)象，比如dequeue。

今天就這樣，明天繼續(xù)努力～

關(guān)注我，了解程序員的燒腦日常，還有開(kāi)源 Python 教程。

總結(jié)

以上是生活随笔為你收集整理的c++ list容器获取第n给元素_深入Python(17)-List 的 append 和 pop的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。