読者です 読者をやめる 読者になる 読者になる

ぱいそんのおぶじぇくと-りすとへん(3)「挿入」「追加」

listに要素を追加する際にどうなっているか見てみます。

int
PyList_Insert(PyObject *op, Py_ssize_t where, PyObject *newitem)

呼び出し口はこのとおり、どこに何を挿入するかに過ぎません。
内部では、ins1を呼び出しています。

static int
ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
{
	Py_ssize_t i, n = self->ob_size;
	PyObject **items;

NULL要素をいれようとしてないか、
リストに入りきらない要素数にならないかチェックをしているだけなので飛ばします。

	if (list_resize(self, n+1) == -1)
		return -1;

ここで適切なサイズにリサイズします。
既に確保している領域allocatedが足りていればサイズが増えても確保はせず単にob_sizeを新しいサイズにするだけです。
もし確保している領域では足りなければPyMem_RESIZEを呼び出してリサイズします。
サイズが確保できたら、

	if (where < 0) {
		where += n;
		if (where < 0)
			where = 0;
	}
	if (where > n)
		where = n;

と、こんな感じで
どこに挿入するのか、を決めています。
負数なら現在の終端からの差分を見ます。
最大を超えているようなら終端にします。

	items = self->ob_item;
	for (i = n; --i >= where; )
		items[i+1] = items[i];

配列式のリストにおける避けられない隣に対する要素コピー。

	Py_INCREF(v);

要素に対する参照をインクリメントしてから格納です。

	items[where] = v;
	return 0;

挿入はこれだけ。


追加は

int
PyList_Append(PyObject *op, PyObject *newitem)

実装は

static int
app1(PyListObject *self, PyObject *v)
{
	Py_ssize_t n = PyList_GET_SIZE(self);

チェックは省略。
これもリサイズしてから、リストの最後に要素をいれているだけです。

	if (list_resize(self, n+1) == -1)
		return -1;

	Py_INCREF(v);
	PyList_SET_ITEM(self, n, v);
	return 0;
}

かんたんですね。