集合中的插入顺序（解析 {} 时）

Question

有人问here为什么将1和True放在set中时只保留1。

这当然是因为1==True。但是在哪些情况下保留1，在哪些情况下保留True？

让我们看看：

传递 list 来构建 set 而不是使用 set 表示法：

>>> set([True,1])
{True}
>>> set([1,True])
{1}

似乎合乎逻辑：set 迭代内部列表，并且不添加第二个元素，因为它等于第一个元素（注意 set([True,1]) 不能 yield 1, 因为 set 不知道列表里面有什么。它甚至可能不是 list 而是 iterable)

现在使用 set 表示法：

>>> {True,1}
{1}
>>> {1,True}
{True}

似乎在那种情况下，项目列表以相反的顺序处理（在 Python 2.7 和 Python 3.4 上测试）。

但这有保证吗？或者只是一个实现细节？

Answer 1

从最近的一个版本开始，dict 保留顺序作为实现细节的副作用。在 3.7 中，可以保证这种行为。也许它对集合文字也有一些影响。

Python 3.6.2:

>>> {True,1}
{True}
>>> {1,True}
{1}
>>> set([True,1])
{True}
>>> set([1,True])
{1}

Answer 2

语言规范似乎不能保证集合文字中元素的插入顺序。但是，Python 3.6 已更改，因此它具有预期的从左到右的评估顺序。有关此更改的完整详细信息，请参阅引入插入顺序更改的 issue, and also the commit。

为了更详细地描述这个变化，在第一次将指针推送到 True 和1 到虚拟机的内部堆栈。

在 Python 3.4 中，BUILD_SET 使用以下循环将元素插入到集合中（注意在我们的例子中 oparg 是 2）：

while (--oparg >= 0) {
    PyObject *item = POP();
    if (err == 0)
        err = PySet_Add(set, item);
        Py_DECREF(item);

由于 1 是最后添加到堆栈中的，因此它首先被弹出，并且是第一个插入到集合中的对象。

在 Python 的较新版本（例如 3.6）中，BUILD_SET 操作码使用 PEEK 而不是 POP:

for (i = oparg; i > 0; i--) {
    PyObject *item = PEEK(i);
    if (err == 0)
        err = PySet_Add(set, item);
        Py_DECREF(item);

PEEK(i) 从堆栈中获取第 i^th 项，因此对于 {True, 1}，对象 True 首先添加到集合中.

Answer 3

设置显示中从左到右的顺序由 the documentation 保证：

its elements are evaluated from left to right and added to the set object

示例：

>>> def f(i, seq="left to right".split()): print(seq[i])
>>> {f(0), f(1), f(2)}
left
to
right
{None}

因此，{1, True}实际上是：

>>> S = set()
>>> S.add(1)
>>> S.add(True) # no effect according to docs
>>> S
{1}

该集合可能只包含 True 或 1 之一，因为从 set 的角度来看它们是重复的：

>>> hash(1) == hash(True)
True
>>> 1 == True
True

Python 3 保证 1 == True。见 Is `False == 0 and True == 1 in Python an implementation detail or is it guaranteed by the language?:

Booleans: These represent the truth values False and True [...] Boolean values behave like the values 0 and 1, respectively, in almost all contexts, the exception being that when converted to a string, the strings "False" or "True" are returned, respectively.

如果 {1, True} 打印 {True} 那么它是一个 bug ("set_display evaluation order doesn't match documented behaviour")。输出应与 set([1, True]) 相同。它在最近的 pypy、jython 和 cpython 2.7.13+、3.5.3+ 版本上按预期工作 ({1})。

集合中的插入顺序（解析 {} 时）

Order of insertion in sets (when parsing {})

python

set

python-internals