Swift Collections

Swift Collections 是一个为 Swift 编程语言提供数据结构实现的开源软件包。

在 swift.org 上的公告中了解更多关于该软件包及其背后意图的信息。

该软件包目前提供以下实现：

• BitSet 和 BitArray，动态位集合。

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

• Heap，一个由数组支持的最小-最大堆，适合用作优先级队列。

• 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 语句获取每个集合类型。

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 的用例，请提交功能请求来描述它！我们希望公共接口尽可能有用——尽管最好是在不损害安全性或限制未来发展的情况下。

通过“带下划线的声明”，我们指的是在其完全限定名称的任何位置都有前导下划线的声明。例如，以下是一些即使它们在技术上被标记为 public，也不被视为公共 API 的名称：

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

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

软件包的未来次要版本可能会根据需要更新这些规则。

我们希望该软件包能够快速采用与其任务相关的 Swift 语言和工具链改进。因此，有时，该软件包的新版本要求客户端升级到更新的 Swift 工具链版本。（这允许软件包利用新的语言/stdlib 功能，建立在编译器错误修复之上，并尽快采用新的软件包管理器功能。）补丁（即错误修复）版本不会增加所需的工具链版本，但任何次要（即新功能）版本都可能这样做。

下表将现有软件包版本映射到其最低要求的 Swift 工具链版本

（注意：该软件包没有最低部署目标，因此虽然它确实要求客户端使用最新的 Swift 工具链来构建它，但代码本身能够在支持运行 Swift 代码的任何操作系统版本上运行。）

要在 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 演进过程的约束，并且其代码不是 ABI 稳定的。）

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

如果您对可能适合添加到此软件包的数据结构有想法，请在论坛上发起一个主题，解释为什么您认为实施它很重要。这样我们就可以确定它是否适合该软件包，讨论实施策略，并计划分配容量以提供帮助。

并非所有数据结构都会达到足够高的有用性级别来在此软件包中发布——那些受众更有限的数据结构可能更适合作为独立软件包使用。当然，理性的人可能会对包含任何特定数据结构的重要性持不同意见；但归根结底，是否采用该实现的决定权在于该软件包的维护者。

如果维护者同意您的实现可能是一个很好的补充，那么就可以开始进行开发了。尽快提交包含您的实现的 PR，只要您有准备好的东西可以展示！我们很乐意尽早参与。从历史上看，最好的补充是贡献者和软件包维护者之间的密切合作的结果。

参与审查讨论，并相应地调整代码。有时我们可能需要经过几个月的多项修订！这很好——它使最终结果变得更好。当达成共识认为该功能已准备就绪，并且该实现经过全面测试和记录时，PR 将由维护者合并。这是庆祝的好时机——合并是一个很好的指标，表明该添加将在某个时候发布。

从历史上看，添加新数据结构的 PR 通常会合并到一个新的特性分支，而不是直接合并到发布分支或 main 分支。从初始合并到发布新特性的标签之间存在很长的时间间隔。没有人喜欢等待，但将一个新的数据结构实现从可以合并的状态转变为可以发布的状态实际上是非常困难的工作，这需要维护人员的时间和精力，并且需要提前安排。实现越接近标准库的编码规范和性能基线，等待时间就越短，合并和发布之间的更改就越少。

与所有 Swift.org 项目一样，我们希望 Swift Collections 项目能够培养一个多元化和友好的社区。我们希望贡献者遵守 Swift.org 行为准则。 此文档的副本 可在本仓库中找到。

此软件包当前的负责人是 Karoy Lorentey (@lorentey)。您可以在 Swift 论坛上或通过发送电子邮件至 klorentey at apple dot com 与他联系。（请保持与本项目相关。）

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