Swift 集合

Swift 集合 是一个为 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 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。如果您要修复的错误存在 现有 issue，请包含对其的引用。
3. 确保添加测试以覆盖您正在进行的任何更改。

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

我们希望此软件包收集通用的数据结构 -- 那些应该在每个 Swift 工程师的基本工具箱中易于访问的数据结构。我们发布的实现需要具有最高的技术质量，打磨到与 Swift 标准库中包含的任何内容相同的光泽。（唯一的真正区别在于此软件包不在正式的 Swift Evolution 流程下，并且其代码不是 ABI 稳定的。）

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

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

并非所有数据结构都能达到足够高的实用水平以在此软件包中发布 -- 那些受众更有限的数据结构可能更适合作为独立软件包。当然，理性的人可能会对包含任何特定数据结构的重要性持有不同意见；但最终，是否接受实现取决于此软件包的维护者。

如果维护者同意您的实现可能是一个不错的补充，那么就该开始着手开发了。一旦您有准备好展示的东西，请立即提交包含您的实现的 PR！我们很乐意尽早参与。从历史上看，最好的添加是贡献者和软件包维护者密切合作的结果。

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

从历史上看，添加新数据结构的 PR 通常会被合并到新的功能分支，而不是直接合并到发布分支或 main，并且从初始合并到标记发布新功能之间有很长一段时间。没有人喜欢等待，但是将新的数据结构实现从准备好合并的状态变为准备好发布的状态实际上是非常困难的工作，并且需要提前安排维护者的时间和精力。实现越接近标准库的编码约定和性能基线，此等待时间就越短，并且合并和发布之间的更改就越少。

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

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

如果遇到审核问题，您也可以直接联系 Swift 核心团队 的成员。