Swift Collections 是 Swift 编程语言的数据结构实现的开源包。

在 swift.org 上的公告中阅读更多关于该包以及背后的意图的信息。

该包目前提供了以下实现

• BitSet 和 BitArray，动态位集合。

• Deque<Element>，一个由环形缓冲区支持的循环队列。Deques 是范围可替换的、可变的、随机访问集合。

• Heap，一个数组支持的 min-max 堆，适合用作优先队列。

• OrderedSet<Element>，标准 Set 的一个变体，其中项的顺序是明确定义的，项可以被任意排序。它使用 ContiguousArray 作为其存储后端，并通过一个独立的位打包偏移量哈希表对其进行增强。

• OrderedDictionary<Key, Value>，标准 Dictionary 的一个有序变体，提供类似的好处。

• TreeSet 和 TreeDictionary，实现压缩的哈希-数组映射前缀树（CHAMP）的持久性哈希集合。它们的工作方式类似于标准 Set 和 Dictionary，但在修改共享副本的使用案例中表现卓越，提供了显著的内存节省和大幅的时间改进。

以下额外数据结构目前正在开发中，但它们还不够稳定，无法预览。

• SortedSet 和 SortedDictionary，由内存持久性 b-树支持的排序集合。
• SparseSet，一个常时集合构造，以牺牲内存为代价换取速度。

Swift Collections 使用类似于 Swift Numerics 的模块化方法：它为其实施的每个主题数据结构组提供独立的模块。例如，如果您只需要双端队列类型，您可以通过导入 DequeModule 只导入它。由于 OrderedSet 和 OrderedDictionary 共享大部分底层实现，因此它们通过一个名为 OrderedCollections 的单个模块提供。但是，还有一个顶级的 Collections 模块，它可以通过单个导入语句为您提供所有集合类型。

import Collections

var deque: Deque<String> = ["Ted", "Rebecca"]
deque.prepend("Keeley")
deque.append("Nathan")
print(deque) // ["Keeley", "Ted", "Rebecca", "Nathan"]

Swift Collections 包源代码稳定。版本号遵循语义版本控制 —— 对于公共 API 的源代码破坏性更改只能出现在一个新的主要版本中。

swift-collections 包的 1.1 版本公共 API 由在 Collections、BitCollections、DequeModule、HeapModule、OrderedCollections 和 HashTreeCollections 模块中标记为 public 的非下划线声明组成。

不属于公共 API 的接口可以在任何版本中继续更改，包括补丁版本。如果您有一个需要使用下划线 API 的用例，请提交功能请求描述它！我们希望公共接口尽可能有用——尽管最好不损害安全性或限制未来进化。

“下划线声明”是指其完全限定名称中任何位置都有前导下划线的声明。例如，以下是一些不会被考虑为公共 API 的名称，即使技术上标记为公共

• FooModule.Bar._someMember(value:)（下划线成员）
• FooModule._Bar.someMember（下划线类型）
• _FooModule.Bar（下划线模块）
• FooModule.Bar.init(_value:)（下划线初始化器）

请注意，Tests、Utils 和 Benchmarks 子目录的内容不是公共 API。我们不对它们做出任何源代码兼容性承诺——它们可能随时更改，并且在新版本中可能会删除代码。请勿依赖于它们。

该包的后续小版本可以根据需要更新这些规则。

我们希望这个包能够快速接纳与它的使命相关的 Swift 语言和工具链改进。因此，不时有新版本的这个包需要客户端升级到更早的 Swift 工具链版本。（这使得该包能够利用新的语言/stdlib 特性，建立在程序员错误修复的基础上，并尽快采用新的包管理器功能。）补丁（即错误修复）版本不会增加所需工具链版本，但任何小版本（即新功能版本）都可能增加。

以下表格列出了现有包版本与它们所需的最小 Swift 工具链版本之间的映射

（注意：这个包没有最低部署目标，因此尽管它需要客户端使用最新的 Swift 工具链来构建它，但代码本身可以在任何支持运行 Swift 代码的 OS 版本上运行。）

要使用这个包在 SwiftPM 项目中，您需要将其设置为包依赖项

// swift-tools-version:5.9
import PackageDescription

let package = Package(
  name: "MyPackage",
  dependencies: [
    .package(
      url: "https://github.com/apple/swift-collections.git", 
      .upToNextMinor(from: "1.1.0") // or `.upToNextMajor
    )
  ],
  targets: [
    .target(
      name: "MyTarget",
      dependencies: [
        .product(name: "Collections", package: "swift-collections")
      ]
    )
  ]
)

我们有一个专门的Swift Collections 论坛，人们可以询问和回答关于如何使用或处理这个包的问题。这也是讨论其进化的好地方。

如果您发现了一些看起来像错误的东西，请提交错误报告！填写尽可能多的详细信息。

我们为包的每个次要版本维护独立的分支

更改必须落在它们将要发布的最早发布版本的对应分支上。它们将定期按以下方向传播

release/1.0 → release/1.1 → main

例如，任何落在release/1.0的东西最终都会出现在release/1.1上，然后还会出现在main上；对于每个发布线，没有必要提交独立的PR。 （变更传播目前需要人工操作——由项目维护者执行。）

我们有一些关于软件包内部结构的基本文档，这可以帮助你开始。

通过提交拉取请求，你表示你有权许可你的贡献给Apple和社区，并同意通过提交补丁，你的贡献处于Swift许可之下，该许可的副本已包含在本存储库中。

1. 确保首先查看你想要修复会部署的次要版本的适当分支。（见上文。）
2. 提交包含你的更改的PR。如果你正在修复的错误已经有了现有问题，请包含对它的引用。
3. 确保添加涵盖你所做的更改的测试。

1. 提出一个功能请求。讨论为什么实现它很重要。
2. 提交包含你的实现方式的PR，并参与审查讨论。
3. 当达成共识认为该功能很重要，并且实现良好，经过全面测试和文档记录后，它将被合并。
4. 欢呼吧！

我们打算让这个软件包收集一般有用的数据结构——那些每个Swift工程师的基本工具箱都应该易于获取的数据结构。我们必须发布的实现必须是最高技术质量，抛光得和Swift标准库中的任何内容一样闪亮。（唯一的真正区别是，这个软件包不受正式Swift Evolution流程的约束，其代码也不是ABI稳定的。）

因此，向这个软件包添加新的数据结构不是一件容易或快速的事情，并不是所有有用的数据结构都适合。

如果你有一个可能会成为这个软件包好补充的数据结构的主意，请在论坛上发起一个主题，解释为什么你认为实现它很重要。这样我们可以确定它是否适合这个软件包，讨论实现策略，并计划分配容量来提供帮助。

并非所有的数据结构都会达到足够高的有用级别以在软件包中发布——那些受众更有限的数据结构可能作为独立的软件包更适合。当然，合情合理的人可能会对包含任何特定数据结构的重要性有不同的看法；但最终，是否将实现纳入的决定取决于这个软件包的维护者。

如果维护者已经同意你的实现可能是一个好补充，那么是时候开始工作了。一旦你有东西可以展示，就提交包含你的实现的PR！我们喜欢尽早参与进来。历史上，最好的增援来自贡献者与软件包维护者之间的紧密合作。

参与审查讨论，并相应地调整代码。有时我们可能需要经过几个月几轮的审查！这是很好的——这使最终结果变得更加完美。当就某个特性的准备就绪达成共识，并且实现已完全测试和文档化时，维护者将合并PR。这是一个庆祝的好时机——合并是一个良好的迹象，表明新增的特性将最终发布。

历史上，添加新数据结构的PR通常合并到一个新特性分支而不是直接到发布分支或main，且从初步合并到发布新特性的tag之间的时间很长。没有人喜欢等待，但从准备好合并的状态到准备发布的状态实际上是一项相当困难的任务，这需要维护者提前安排时间和精力。实现越接近标准库的编码规范和性能基线，等待时间就越短，合并和发布之间的改动也越少。

类似于所有Swift.org项目，我们希望Swift Collections项目能够培养一个多样和友好的社区。我们期望贡献者遵守Swift.org行为准则。本仓库中有本文件的副本在此。

此包的当前代码所有者是Karoy Lorentey (@lorentey)。您可以在Swift论坛上联系他，或通过发送电子邮件到 Klorentey@apple dot com。 (请确保相关于此项目。)

在出现管理问题时，您也可以直接联系Swift核心团队的成员。