swift 有序集

Question

Swift 有有序集合类型吗？如果没有，如果我想使用一个，我有什么选择？

标准库的 Set 是无序的，正如文档中明确指出的那样:

Arrays are ordered collections of values. Sets are unordered collections of unique values. Dictionaries are unordered collections of key-value associations.

然而，许多适用于实现有序集(和字典)的数据结构是已知的，特别是 balanced binary trees例如Red-Black trees .

例如，c++ 的 STL 有 ordered sets和 map ，并允许使用下限和上限对它们进行范围查询。

我知道一个集合的成员可以排序到一个数组中，但我在寻找一个具有O(log(n)) 插入、删除和查询的数据结构。

Answer 1

Swift 没有原生的有序集类型。如果你使用 Foundation，你可以在 Swift 中使用 NSOrderedSet。如果没有，您有机会编写自己的有序集数据结构。

更新:Swift Package Manager includes an OrderedSet implementation这可能会有用。它包装了一个数组和一个集合，并管理获取有序集合行为的访问。

更新 #2:Apple's Swift Collections repository包含有序集实现。