Swift Collections

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

如需了解有关该软件包及其背后意图的更多信息，请阅读 swift.org 上的公告。

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

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

• OrderedSet<Element>，标准 Set 的变体，其中项目的顺序是明确定义的，并且项目可以任意重新排序。 使用 ContiguousArray 作为其后备存储，并由单独的位打包偏移量哈希表进行扩充。

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

以下附加类型预计将在 1.1 版本中很快发布：

• BitSet 和 BitArray，动态位集合。

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

• TreeSet 和 TreeDictionary，持久化的哈希集合，实现了压缩哈希数组映射前缀树 (CHAMP)。 这些的工作方式类似于标准的 Set 和 Dictionary，但它们在修改共享副本的用例中表现出色，可显著节省内存并大幅缩短时间。

这些新类型的预览版本可在 release/1.1 分支上找到。 请注意，在这些类型在已标记的发行版中发布之前，它们的 API 和实现可能会在没有通知的情况下发生更改——现在在生产代码中依赖它们不是一个好主意。 但是，您可以通过在软件包清单中使用基于分支或提交的依赖项要求在实验性项目中尝试它们。

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

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

通过“带下划线的声明”，我们指的是在其完全限定名称中的任何位置都有前导下划线的声明。 例如，以下是一些即使它们在技术上被标记为 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 代码的任何 OS 版本上运行。）

要在 SwiftPM 项目中使用此软件包，您需要将其设置为软件包依赖项

// swift-tools-version:5.7
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 论坛，人们可以在这里提问和回答关于如何使用或开发此软件包的问题。 它也是讨论其发展的好地方。

如果您发现任何看起来像错误的东西，请打开一个 错误报告！ 尽可能填写更多详细信息。

我们有一些基本的关于软件包内部结构的文档，这将帮助您入门。

通过提交拉取请求，您表示您有权将您的贡献许可给 Apple 和社区，并且通过提交补丁，您同意您的贡献已根据 Swift 许可证获得许可，该许可证的副本已在此存储库中提供。

1. 提交一个 PR 并包含您的更改。 如果存在要修复的错误的现有问题，请包含对它的引用。
2. 确保添加测试以涵盖您所做的任何更改。

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 核心团队的成员。