swift - 与无效的迭代器/索引一起使用时，快速集合的安全性如何？

Question

我没有在快速的stdlib引用中看到很多信息。例如，Dictionary说某些方法(如remove)会使索引无效，仅此而已。

对于一种自称“安全”的语言，它需要经典C++脚枪的解决方案:

获取指向 vector 中元素的指针，然后添加更多元素(指针现在无效)，现在使用指针，使

崩溃

开始遍历一个集合。在迭代时，删除一些元素(在当前迭代器位置之前或之后)。继续迭代，崩溃。

(编辑:在C++中，您很幸运崩溃-更糟的情况是内存损坏)

我相信可以通过快速解决1，因为如果集合存储类，则对元素的引用(例如强指针)将增加refcount。但是，我不知道2的答案。

如果在C++中有一些脚步枪的比较而不能迅速解决的话，那将非常有用。

编辑，由于Robs的回答:

似乎确实存在一些未记录的类似快照的行为
使用字典和/或for循环。迭代创建快照/隐藏
它开始时的副本。

这给了我一个很大的“WAT”和“很酷，我猜这很安全”，以及“这个副本有多贵？”。

我在Generator或for循环中都没有看到此文件。

下面的代码打印字典的两个逻辑快照。首先
快照是userInfo，就像在迭代循环开始时一样，并且
不反射(reflect)在循环过程中所做的任何修改。

var userInfo: [String: String] = [
    "first_name" : "Andrei",
    "last_name" : "Puni",
    "job_title" : "Mad scientist"
]

userInfo["added_one"] = "1"  // can modify because it's var

print("first snapshot:")
var hijacked = false
for (key, value) in userInfo {
    if !hijacked {
        userInfo["added_two"] = "2"  // doesn't error     
        userInfo.removeValueForKey("first_name")  // doesn't error
        hijacked = true
    }
    print("- \(key): \(value)")
}

userInfo["added_three"] = "3" // modify again

print("final snapshot:")
for (key, value) in userInfo {
    print("- \(key): \(value)")
}

Answer 1

正如您所说，＃1并不是问题。您在Swift中没有指向该对象的指针。您要么具有它的值(value)，要么对其进行引用。如果您有它的值(value)，那么它就是副本。如果您有引用，那么它就受到保护。因此，这里没有问题。

但是让我们考虑第二个和实验，先感到惊讶，然后再停止感到惊讶。

var xs = [1,2,3,4]

for x in xs { // (1)
    if x == 2 {
        xs.removeAll() // (2)
    }
    print(x) // Prints "1\n2\n3\n\4\n"
}

xs // [] (3)

等一下，当我们删除(2)处的值时，它将如何打印所有值。我们现在很惊讶。

但是我们不应该这样。 Swift数组是值。 (1)处的xs是一个值。没有任何东西可以改变它。它不是“指向包含包含4个元素的数组结构的内存的指针”。这是值[1,2,3,4]。在(2)中，我们不会“从xs指向的内容中删除所有元素”。我们以xs为例，创建一个数组，如果您删除所有元素(在所有情况下均为[])，则生成该数组，然后将该新数组分配给xs。没什么不好的。

那么，文档“使所有索引无效”是什么意思？就是这个意思。如果我们生成索引，它们将不再有用。让我们来看看:

var xs = [1,2,3,4]

for i in xs.indices {
    if i == 2 {
        xs.removeAll()
    }
    print(xs[i]) // Prints "1\n2\n" and then CRASH!!!
}

一旦调用xs.removeAll()，就无法保证xs.indices的旧结果不再有意义。不允许您将这些索引安全地用于它们来自的集合。

Swift中的“无效索引”与C++的“无效迭代器”不同。我称这很安全，除了以下事实:使用集合索引总是有些危险，因此您应避免在可能的情况下为集合建立索引；而是迭代它们。即使您出于某种原因需要索引，也可以使用enumerate来获取它们，而不会产生任何建立索引的危险。

(附带说明，dict["key"]并未索引到dict中。字典有点困惑，因为它们的键不是索引。通过DictionaryIndex索引访问字典与通过Int索引访问数组一样危险。)

另请注意，以上内容不适用于NSArray。如果在迭代时修改NSArray，则会收到“迭代时收集的集合”错误。我只讨论Swift数据类型。

编辑:for-in是very explicit在它的工作方式:

The generate() method is called on the collection expression to obtain a value of a generator type—that is, a type that conforms to the GeneratorType protocol. The program begins executing a loop by calling the next() method on the stream. If the value returned is not None, it is assigned to the item pattern, the program executes the statements, and then continues execution at the beginning of the loop. Otherwise, the program does not perform assignment or execute the statements, and it is finished executing the for-in statement.

返回的Generator是struct，包含一个集合值。您不会期望对某些其他值进行任何更改来修改其行为。请记住:[1,2,3]与4没有什么不同。它们都是值(value)。当您分配它们时，它们会制作副本。因此，当您在集合值上创建生成器时，就将快照该值，就像我在数字4上创建了生成器一样。(这引起了一个有趣的问题，因为生成器并不是真正的值，因此不应该是结构。它们应该是类。Swiftstdlib已经修复了该问题。例如，参见新的AnyGenerator。但是它们仍然包含数组值，并且您永远都不会期望对其他数组值的更改会影响它们。)

另请参见"Structures and Enumerations Are Value Types"，它详细介绍了Swift中值类型的重要性。数组只是结构。

是的，这意味着有逻辑上的复制。 Swift进行了许多优化，以在不需要时最大程度地减少实际复制。在您的情况下，当您在对字典进行迭代时对其进行变异时，这将迫使复制发生。如果您是特定值的后备存储的唯一使用者，那么更改会很便宜。但是如果不是，则为O(n)。 (这是由Swift内置的isUniquelyReferenced()决定的。)长话短说:Swift集合是写时复制的，仅传递数组不会导致分配或复制实际内存。

您不会免费获得COW。您自己的结构不是COW。这是Swift在stdlib中所做的事情。 (有关如何重新创建它的信息，请参见Mike Ash的great discussion。)传递您自己的自定义结构会导致真实副本的发生。也就是说，大多数结构中的大部分内存都存储在集合中，而这些集合是COW，因此复制结构的成本通常很小。

这本书并没有花很多时间来研究Swift中的值类型(它解释了所有内容；只是不停地说“嘿，这就是这个意思”)。另一方面，这是WWDC不变的话题。您可能对Building Better Apps with Value Types in Swift尤其感兴趣，它与该主题有关。我相信Swift in Practice也对此进行了讨论。

编辑2:

@KarlP在下面的评论中提出了一个有趣的观点，值得解决。我们正在讨论的值(value)安全 promise 都没有与for-in有关。它们基于Array。 for-in完全不保证如果在迭代集合时对其进行了突变，将会发生什么。那甚至没有意义。 for-in不会“遍历集合”，它会在next()上调用Generators。因此，如果更改集合后您的Generator变得不确定，那么for-in将爆炸，因为Generator炸掉了。

这意味着以下内容可能是不安全的，具体取决于您阅读规范的程度:

func nukeFromOrbit<C: RangeReplaceableCollectionType>(var xs: C) {
    var hijack = true
    for x in xs {
        if hijack {
            xs.removeAll()
            hijack = false
        }
        print(x)
    }
}

而且编译器在这里无法为您提供帮助。适用于所有Swift集合。但是，如果为您的集合突变后调用next()是未定义的行为，则这是未定义的行为。

我的看法是，在这种情况下，Swift制作一个允许其Generator变为未定义的集合会很糟糕。您甚至可能会争辩说，这样做违反了Generator规范(除非生成器已被复制或返回nil，否则它不提供UB“out”)。因此，您可能会认为上述代码完全在规范范围内，并且生成器已损坏。这些论点往往与诸如Swift的“规范”有点杂乱，而“规范”并未深入到所有极端情况。

这是否意味着您可以在Swift中编写不安全的代码而不会得到明确的警告？绝对。但是在许多通常会导致实际错误的情况下，Swift的内置行为是正确的。在此方面，它比其他一些选择更安全。