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.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 以及您的更改。如果存在您要修复的错误的 现有 issue，请包含对其的引用。
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 在 apple 点 com。（请保持与本项目相关。）

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