swift-collections Documentation

File: README.md Copy Chapter

Swift Collections

Swift Collections is an open-source package of data structure implementations for the Swift programming language.

Table of Contents Copy Chapter

• Stable Data Structures
  • BasicContainers module
  • DequeModule module
  • OrderedCollections module
  • BitCollections module
  • HeapModule module
  • HashTreeCollections module
  • TrailingElementsModule module
  • ContainersPreview module
  • Collections module
• Experimental Features
  • UnstableContainersPreview package trait
  • UnstableHashedContainers package trait
  • UnstableSortedCollections package trait
• Project Status
  • Definition of Public API
  • Minimum Required Swift Toolchain Version
• Using Swift Collections in your project
• Contributing to Swift Collections
  • Branching Strategy
  • Working on the package
    • Fixing a bug or making a small improvement
    • Proposing a small enhancement
    • Proposing the addition of a new data structure
• Code of Conduct
• Contact information

Stable Data Structures Copy Chapter

The package currently provides the following types, organized into thematic modules:

[`BasicContainers`][BasicContainers] module

Ownership-aware reimplementations of the standard generic collection types Array, Set, and Dictionary.

• struct UniqueArray<Element> is a uniquely held, dynamically resizing array.
• struct RigidArray<Element> is a fixed-capacity array.

[`DequeModule`][DequeModule] module

Implementations of double-ended queue types, implemented by a ring buffer.

• struct Deque<Element> is a classic collection, implementing value semantics with the copy-on-write optimization.
• struct UniqueDeque<Element> is a uniquely held, dynamically resizing, noncopyable deque.
• struct RigidDeque<Element> is a fixed-capacity deque implementation.

[`OrderedCollections`][OrderedCollections] module

Provides variants of the standard Set and Dictionary types with user-defined ordering.

• struct OrderedSet<Element> is a Set that preserves insertion order.
• struct OrderedDictionary<Key, Value> is a Dictionary that preserves insertion order.

[`BitCollections`][BitCollections] module

Provides efficient implementations of bit maps.

• struct BitSet is a more efficient implementation of Set.
• struct BitArray is a more efficient implementation of Array.

[`HeapModule`][HeapModule] module

• struct Heap<Element>, a min-max heap backed by an array, suitable for use as a priority queue.

[`HashTreeCollections`][HashTreeCollections] module

Persistent hashed collections implementing Compressed Hash-Array Mapped Prefix Trees (CHAMP). These are like Set and Dictionary, but they support efficient mutations of shared copies of values, without duplicating the unchanged parts.

• struct TreeSet<Element> is a persistent hashed set.
• struct TreeDictionary<Key, Value> is a persistent hashed dictionary.

[`TrailingElementsModule`][TrailingElementsModule] module

• struct TrailingArray, a low-level, ownership-aware variant of ManagedBuffer, for interoperability with C constructs that consist of a fixed-size header directly followed by a variable-size storage buffer.
• protocol TrailingElements
• struct TrailingPadding<Header>

[`ContainersPreview`][ContainersPreview] module

An experimental preview of an ownership-aware container model in Swift. Most of this module's contents are gated behind the UnstableContainersPreview package trait and are not considered stable API. The type below is the only stable entry point:

• struct UniqueBox<Value> is a heap-allocated noncopyable wrapper for an arbitrary value.

[`Collections`][CollectionsModule] module

Exposes the most commonly used collection types with a single import statement:

• struct BitArray from BitCollections
• struct BitSet from BitCollections
• struct Deque<Element> from DequeModule
• struct Heap<Element> from HeapModule
• struct OrderedSet<Element> from OrderedCollections
• struct OrderedDictionary<Key, Value> from OrderedCollections
• struct TreeSet<Element> from HashTreeCollections
• struct TreeDictionary<Key, Value> from HashTreeCollections

Experimental Features Copy Chapter

The package also includes previews of features that aren't ready to be declared source-stable yet. This includes prototypes of basic abstractions that belong in the Swift Standard Library, as well as concrete data structures that aren't ready for production use -- either because they depend on unreleased language/stdlib improvements, or because they still have known API or implementation issues.

These features are disabled by default. The package provides several package traits to allow intrepid early adopters to selectively opt into using them, to validate potential use cases. All APIs and behavior that these traits enable are highly experimental, and completely unstable -- they can (and often will!) change in incompatible ways or they may even get removed with no advance notice, in any new release of the package (including patch releases).

`UnstableContainersPreview` package trait Copy Section

This trait enables the following types in the ContainersPreview module:

• struct InputSpan<Element> is a reference to a contiguous region of consumable items.

• struct Ref<Target> represents a borrowing reference to an item.

• struct MutableRef<Target> represents a mutating reference to an item.

• protocol BorrowingSequence<Element> models borrowing sequences with ephemeral lifetimes.

• protocol BorrowingIteratorProtocol<Element> models borrowing iterators with ephemeral elements.

• protocol Container<Element> models containers, or constructs that physically store their contents.

• protocol BidirectionalContainer<Element> is the container analogue of BidirectionalCollection.

• protocol RandomAccessContainer<Element> is the container analogue of RandomAccessCollection.

• protocol PermutableContainer<Element> models a container that allows items to be arbitrarily reordered (sorted, reversed, etc).

• protocol MutableContainer<Element> refines PermutableContainer to also support arbitrary element replacements/mutations, like MutableCollection.

• protocol RangeReplaceableContainer<Element> models a (potentially fixed capacity) container with insert/append/replace operations.

• protocol DynamicContainer<Element> refines RangeReplaceableContainer to add operations that require dynamic storage sizing.

• protocol Producer<Element, Failure> models a generative iterator -- an abstraction for producing items on demand.

• protocol Drain<Element> refines Producer to model a source of in-place consumable elements -- primarily for use around container types.

The trait also enables a large list of new APIs throughout the package that make use of these constructs -- such as generic methods for transferring items between container types, and implementations of the classic map/reduce/filter/etc algorithms.

These constructs are previews of potential stdlib additions. Some of these are already making their way through the Swift Evolution process; others are still unfinished and highly experimental. These need to remain unstable, as we expect that (as usual) these constructs will see some API breaking changes on their way to the stdlib; additionally, they will likely need to be removed from the package entirely once they are fully adopted into the Standard Library. (It would not be feasible to maintain two distinct versions of universal library primitives, or basic protocols / generic algorithms.)

`UnstableHashedContainers` package trait Copy Section

This trait enables the following hashed containers in the BasicContainers module:

• struct UniqueSet<Element> is a uniquely held, dynamically resizing set.
• struct RigidSet<Element> is a fixed-capacity set.
• struct UniqueDictionary<Key, Value> is a uniquely held, dynamically resizing dictionary.
• struct RigidDictionary<Key, Value> is a fixed-capacity dictionary.

These types support noncopyable elements -- noncopyable members in the set types, and noncopyable keys and/or values in the dictionary types. (Of course, they can also be used with copyable types.)

Under the hood, these containers implement Robin Hood hashing, achieving better memory utilization and more consistent lookup performance when compared to the standard Set and Dictionary types.

These types need to remain unstable for now, as they depend on compiler/stdlib features that have not shipped yet. Additionally, we may need to tweak their API as we gain more experience with using them.

`UnstableSortedCollections` package trait Copy Section

This trait enables the following types in the SortedCollections module:

• struct SortedSet<Element> is a set type that requires its element to be Comparable, and keeps its members sorted in strictly increasing order.
• struct SortedDictionary<Key, Value> is a dictionary type that always keeps its keys sorted in strictly increasing order.

These constructs are based around an in-memory B-tree implementation.

They remain unstable for now because they have known API deficiencies -- we expect many of their interfaces will need to be adjusted in source breaking ways.

Project Status Copy Chapter

The Swift Collections package is source-stable. The version numbers follow Semantic Versioning -- source breaking changes to public API can only land in a new major version.

Definition of Public API Copy Section

The public API of version 1.5 of the swift-collections package consists of non-underscored declarations that are marked public in the Collections, BasicContainers, BitCollections, ContainersPreview, DequeModule, HashTreeCollections, HeapModule, OrderedCollections, and TrailingElementsModule modules.

Interfaces that aren't part of the public API may continue to change in any release, including patch releases.

By "underscored declarations" we mean declarations that have a leading underscore anywhere in their fully qualified name. For instance, here are some names that wouldn't be considered part of the public API, even if they were technically marked public:

• FooModule.Bar._someMember(value:) (underscored member)
• FooModule._Bar.someMember (underscored type)
• _FooModule.Bar (underscored module)
• FooModule.Bar.init(_value:) (underscored initializer)

Interfaces that get enabled by opting into the UnstableContainersPreview, UnstableSortedCollections, or UnstableHashedContainers package traits are not part of the public API; those interfaces may get removed or changed in any release.

(Note: the list of stable modules above intentionally does not include SortedCollections nor _RopeModule -- these experimental modules are unstable and need more time in the oven before they can become public API.)

If you have a use case that requires using underscored (or otherwise non-public) APIs, please submit a Feature Request describing it! We'd like the public interface to be as useful as possible -- although preferably without compromising safety or limiting future evolution.

This source compatibility promise only applies to swift-collections when built as a Swift package. The repository also contains unstable configurations for building swift-collections using CMake and Xcode. These configurations are provided for internal Swift project use only -- such as for building the (private) swift-collections binaries that ship within Swift toolchains. As such, they are unstable and may arbitrarily change (including wholesale removal) in any swift-collections release.

The files in the Tests, Utils, Documentation, Xcode, cmake, and Benchmarks subdirectories may change at will; they may get added, modified, or removed in any new release. Do not rely on anything about them.

Future minor versions of the package may update these rules as needed.

Minimum Required Swift Toolchain Version Copy Section

We'd like this package to quickly embrace Swift language and toolchain improvements that are relevant to its mandate. Accordingly, from time to time, new versions of this package require clients to upgrade to a more recent Swift toolchain release. (This allows the package to make use of new language/stdlib features, build on compiler bug fixes, and adopt new package manager functionality as soon as they are available.) Patch (i.e., bugfix) releases will not increase the required toolchain version, but any minor (i.e., new feature) release may do so.

The following table maps package releases to their minimum required Swift toolchain release:

We make an effort to ensure that each new minor package version supports the most recent three major Swift versions at the time of its release.

(Note: the package has no minimum deployment target, so while it does require clients to use a recent Swift toolchain to build it, the code itself is able to run on any OS release that supports running Swift code.)

Select features may require a more recent compiler than the minimum specified above. (For example, RigidArray only works on Swift 6.2 or better.)

Using **Swift Collections** in your project Copy Chapter

To use this package in a SwiftPM project, you need to set it up as a package dependency:

// swift-tools-version:6.3
import PackageDescription

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

Contributing to Swift Collections Copy Chapter

We have a dedicated Swift Collections Forum where people can ask and answer questions on how to use or work on this package. It's also a great place to discuss its evolution.

If you find something that looks like a bug, please open a Bug Report! Fill out as many details as you can.

Branching Strategy Copy Section

We maintain separate branches for each minor version of the package:

Changes must land on the branch corresponding to the earliest release that they will need to ship on. They are periodically propagated to subsequent branches, in the following direction:

release/1.3 → release/1.4 → release/1.5 → main

For example, anything landing on release/1.3 will eventually appear on release/1.4, release/1.5, and then main too; there is no need to file standalone PRs for each release line. Change propagation is not instantaneous, as it currently requires manual work -- it is performed by project maintainers.

Working on the package Copy Section

We have some basic documentation on package internals that will help you get started.

By submitting a pull request, you represent that you have the right to license your contribution to Apple and the community, and agree by submitting the patch that your contributions are licensed under the Swift License, a copy of which is provided in this repository.

Fixing a bug or making a small improvement

1. Make sure to start by checking out the appropriate branch for the minor release you want the fix to ship in. (See above.)
2. Submit a PR with your change. If there is an existing issue for the bug you're fixing, please include a reference to it.
3. Make sure to add tests covering whatever changes you are making.

Proposing a small enhancement

1. Raise a Feature Request. Discuss why it would be important to implement it.
2. Submit a PR with your implementation, and participate in the review discussion.
3. When there is a consensus that the feature is desirable, and the implementation works well, it is fully tested and documented, then it will be merged.
4. Rejoice!

Proposing the addition of a new data structure

Note: We are currently fully preoccupied with refactoring our existing data structures to support noncopyable and/or nonescapable element types; this includes designing new container protocols around them. We don't expect to have capacity to work on any major new data structure implementations until this effort is complete.

Code of Conduct Copy Chapter

Like all Swift.org projects, we would like the Swift Collections project to foster a diverse and friendly community. We expect contributors to adhere to the Swift.org Code of Conduct. A copy of this document is available in this repository.

Contact information Copy Chapter

The current code owner of this package is Karoy Lorentey (@lorentey). You can contact him on the Swift forums, or by writing an email to klorentey at apple dot com. (Please keep it related to this project.)

In case of moderation issues, you can also directly contact a member of the Swift Core Team.

File: Documentation/Announcement-benchmarks/README.md Copy Chapter

Benchmark data from the swift.org announcement

This directory contains the benchmark configuration that we used to collect benchmarking data and render the charts in the Swift Collections announcement on swift.org.

• generate-results.sh: A script that you can use to run the benchmark on your own machine, and to reproduce the charts.
• Library.json: The benchmark library definition collecting the chart definitions used in the blog post.
• Theme.json: The chart theme to set up colors, line widths, font sizes etc. (Slightly adapted.)
• Results.md: The generated results summary.
• Results/: The generated subdirectory containing the PNG files for the charts.
• results.json: The result data we collected.

Note: If you'd like to try reproducing our results (it's easy!), note that the script is configured to collect 20 rounds of data on up to 16 million items, and this will likely take a very long time. Feel free to reduce the maximum size, or just plan to allow the measurement run overnight.

For more information on how to use the Swift Collections benchmarking tool, please see Swift Collections Benchmark.

File: Documentation/Announcement-benchmarks/Results.md Copy Chapter

Benchmark results

Click to expand individual items below.

All results

01: Deque - random access lookups



02: Deque - prepending individual integers



03: OrderedSet lookups



04: OrderedSet insertions



05: OrderedDictionary lookups



06: OrderedDictionary insertions

File: Documentation/Internals/README.md Copy Chapter

Package Internals

Benchmarks Copy Chapter

The package includes an extensive library of benchmarks in the Benchmarks directory, driven by a command-line executable target, called benchmark. These benchmarks, the executable target, and its command-line interface are not considered part of the public interface of the package. As such, new releases may break them without any special ceremony. We do expect the benchmarks will stabilize with time.

For more information on our benchmarking tool, please see its dedicated package, Swift Collections Benchmark.

Test Support Library Copy Chapter

The package comes with a rich test support library in the Tests/_CollectionsTestSupport directory. These were loosely adapted from the contents of the StdlibUnittest* modules in the Swift compiler repository, with some custom additions.

These components would likely be of interest to the wider Swift community, but they aren't yet stable enough (or documented enough) to publish them. Accordingly, these testing helpers are currently considered implementation details of this package, and are subject to change at whim.

The test support library currently provides the following functionality:

• AssertionContexts: Custom test assertions with support for keeping track of nested context information, including stopping execution when the current context matches a particular value. (Useful for debugging combinatorial tests.)

  Click here for a short demonstration

  swift Copy

  import XCTest
  import _CollectionsTestSupport
  
  final class DequeTests: CollectionTestCase {
    func test_demo() {
      let values = [0, 10, 20, 30, 42, 50, 60]
      for i in values.indices {
        context.withTrace("i: \(i)") {
          expectEqual(values[i], 10 * i)
        }
      }
    }
  }

  text Copy

  DemoTests.swift:21: error: -[DemoTests.DemoTests test_demo] : XCTAssertEqual failed: ("42") is not equal to ("40") - 
  Trace:
    - i: 4

  To debug issues, copy the trace message into a context.failIfTraceMatches(_:) invocation and set a breakpoint on test failures.

  swift Copy

  let values = [0, 10, 20, 30, 42, 50, 60]
      for i in values.indices {
        context.withTrace("i: \(i)") {
          // This will report a test failure before executing the `i == 4` case,
          // letting us investigate what's going on.
          context.failIfTraceMatches("""
            Trace:
              - i: 4
            """)
          expectEqual(values[i], 10 * i)
        }
      }

• Combinatorics: Basic support for exhaustive combinatorial testing. This allows us to easily verify that a collection operation works correctly on all possible instances up to a certain size, including behavioral variations such as unique/shared storage. This file also contains a basic set of functions for executing the same test code for all subsets or all permutations of a given collection, with each iteration registered in the current test context, for easy reproduction of failed cases.

  Click here for an example

  swift Copy

  func test_popFirst() {
    withEveryDeque("deque", ofCapacities: [0, 1, 2, 3, 5, 10]) { layout in
      withEvery("isShared", in: [false, true]) { isShared in
        withLifetimeTracking { tracker in
          var (deque, contents) = tracker.deque(with: layout)
          withHiddenCopies(if: isShared, of: &deque) { deque in
            let expected = contents[...].popFirst()
            let actual = deque.popFirst()
            expectEqual(actual, expected)
            expectEqualElements(deque, contents)
          }
        }
      }
    }
  }

• ConformanceCheckers: A set of generic, semi-automated protocol conformance tests for some Standard Library protocols. These can be used to easily validate the custom protocol conformances provided by this package. These checks aren't (can't be) complete -- but when used correctly, they are able to detect most accidental mistakes.

  We currently have conformance checkers for the following protocols:

  • Sequence
  • Collection
  • BidirectionalCollection
  • Equatable
  • Hashable
  • Comparable

• MinimalTypes: Minimally conforming implementations for standard protocols. These types conform to various standard protocols by implementing the requirements in as narrow-minded way as possible -- sometimes going to extreme lengths to, say, implement collection index invalidation logic in the most unhelpful way possible.

  • MinimalSequence
  • MinimalCollection
  • MinimalBidirectionalCollection
  • MinimalRandomAccessCollection
  • MinimalMutableRandomAccessCollection
  • MinimalRangeReplaceableRandomAccessCollection
  • MinimalMutableRangeReplaceableRandomAccessCollection
  • MinimalIterator
  • MinimalIndex
  • MinimalEncoder
  • MinimalDecoder

• Utilities: Utility types. Wrapper types for boxed values, a simple deterministic random number generator, and a lifetime tracker for catching simple memory management issues such as memory leaks. (The Address Sanitizer can be used to catch more serious problems.)

File: Documentation/Internals/ReleaseChecklist.md Copy Chapter

Swift Collections Release Checklist

1. Create a milestone for the new version (if one doesn't exist yet).

2. Collect all issues & PRs that are going to be included in the new tag under the new milestone.

3. If the new release moves code between source files or adds new API that has the potential to cause mutual dependencies between source files, then run the shuffle-sources.sh script for at least a few hundred iterations on the affected module to help catch nondeterministic build issues with the compiler's MergeModules phase. (Note: it's best to do this on a fresh clone. We can stop doing this when MergeModules is no longer used to build debug configurations in SPM.)

4. Run the full tests script on the commit that you intend to tag, with all supported (major) toolchain releases, and on as many supported platforms as are practical. (At minimum, run the script with the latest stable toolchain releases on macOS and one Linux distribution.)
   The script exercises a tiny subset of the environments this package can be built and run on.

   The full matrix includes the following axes:

   • Toolchains
     • All major Swift releases supported by the package, plus a recent toolchain snapshot from swift.org.
       E.g., for the Swift Collection 1.0 release, this included:
       • Swift 5.3 (from swift.org and Xcode 12)
       • Swift 5.4 (from swift.org and Xcode 12.5)
       • Prerelease builds of Swift 5.5 (using the latest swift.org snapshot and the latest Xcode 13 beta)
       • The latest main development snapshot from swift.org.
   • Platforms & architectures
     • macOS (using SPM, xcodebuild, cmake)
       • Intel, Apple Silicon
       • Deploying on any macOS release starting from macOS 10.10
     • Mac Catalyst (using xcodebuild)
       • Intel, Apple Silicon
       • Deploying on any macOS release starting from macOS 10.15
     • iOS (using xcodebuild)
       • Device (arm64, armv7), simulator (x86_64, i386, arm64)
       • Deploying on any iOS release starting from iOS 8
     • watchOS (using xcodebuild)
       • Device (arm64_32, arm7k), simulator (x86_64, i386, arm64)
       • Deploying on any watchOS release starting from watchOS 2
     • tvOS (using xcodebuild)
       • Device (arm64), simulator (x86_64, arm64)
       • Deploying on any tvOS 9 release starting from tvOS 10
     • Linux (using SPM, cmake)
       • All supported distributions
   • Build systems
     • Swift Package Manager
     • xcodebuild (for the package)
     • xcodebuild (for the unstable Xcode project in Xcode/)
     • CMake & ninja (note: this support isn't source stable)
   • Configurations
     • Debug
     • Release
   • Build settings
     • COLLECTIONS_INTERNAL_CHECKS
     • COLLECTIONS_DETERMINISTIC_HASHING
     • BUILD_LIBRARY_FOR_DISTRIBUTION=YES with xcodebuild (this is unsupported, but why break it)
     • -warnings-as-errors
     • Any combinations of the above
   • Components
     • The swift-collections package
     • The private benchmark executable under Benchmarks/

5. Submit PRs to fix any issues that pop up, then try again until no issues are found.

6. Update the README if necessary.

7. Draft a new release on GitHub, following the template established by previous releases.

8. As a final chance to catch issues, generate a diff between the last tagged release and the release candidate commit. Review it in case we landed something that isn't appropriate to include; watch out for potential issues such as source compatibility problems, or new public API without adequate documentation.

9. Double check that the new tag will have the right version number and it will be on the correct branch.

10. For nontrivial releases, announce the intention to tag on the Swift Forums, asking people to try building their projects with the candidate commit. Wait an appropriate number of days to see if anyone finds a blocker issue.

11. Hit publish.

12. File a PR on https://github.com/apple/swift that updates dependency declarations in the file utils/update_checkout/update-checkout-config.json, for all appropriate branch configurations. (Typically the main branch (and its derivatives, such as rebranch, next etc.) and possibly the currently active release branch.)

File: Documentation/Reviews/2022-10-31.ShareableHashedCollections/ShareableHashedCollections.md Copy Chapter

Shareable Hashed Collections Module

• Authors: Michael Steindorfer, Karoy Lorentey
• Implementation: https://github.com/apple/swift-collections/tree/release/1.1/Sources/ShareableHashedCollections

Table of contents Copy Chapter

• Introduction
• Motivation
• Proposed solution
  • ShareableSet
  • ShareableDictionary
• Detailed design

Introduction Copy Chapter

ShareableHashedCollections is a new module in Swift Collections, containing new hashed collection types that store their elements in a prefix tree structure, based on their hash values. The new types are tree-based equivalents to the standard Set and Dictionary; they're called ShareableSet and ShareableDictionary.

Like the standard hashed collections, ShareableSet and ShareableDictionary are unordered collections of unique items. However, the new collections are optimizing for making mutations of shared copies as efficient as practical, both by making such changes faster, but, just as importantly, by letting mutated copies of the same collection value share as much of their structure as possible, saving a considerable amount of memory.

Motivation Copy Chapter

Well-behaved Swift collection types are typically expected to implement the copy-on-write optimization: in this scheme, making copies of collection values is an O(1) operation, but the first time one of the copies gets mutated, its storage needs to be made unique.

In the case of the standard collection types, the only way to make a collection value's storage unique is to copy the entire collection into newly allocated storage. This maintains the illusion of value semantics, but such all-or-nothing copying can lead to undesirable spikes in complexity. Inserting an item will usually take constant time, but if we aren't careful about making copies, it sometimes jumps to linear complexity, which can easily render the code unusably slow, especially when the operation is called inside a loop.

As a toy example, consider a case of a system where we want to allow the user to arbitrarily mutate a set of integers, then periodically (say, every time we want to refresh the screen) we compare the current set to the one we previously saw, and do something based on the differences. To keep things simple, let's say we are just inserting a sequence of integers one by one, and we want to update the display state after every insertion:

typealias Model = Set

var _state: Model // Private
func updateState(
  with model: Model
) -> (insertions: Set, removals: Set) {
  let insertions = model.subtracting(_state)
  let removals = _state.subtracting(model)
  _state = model
  return (insertions, removals)
}

let c = 1_000_000
var model: Model = []
for i in 0 ..< c {
  model.insert(i)
  let r = updateState(with: model)
  precondition(r.insertions.count == 1 && r.removals.count = 0)
}

(Of course, ideally the set would remember precisely what items got inserted/removed in it since the last time a snapshot was made, so calculating the difference would be a trivial operation. But if we aren't able to maintain such a change log, this might be a reasonably pragmatic fallback approach.)

With the standard Set type, having to keep a copy of the model around is inconvenient: it not only makes the first mutation after the updateState call slow, but it also roughly doubles the memory that we need to use, as the new version of the model will need to have its own, completely independent storage. Even worse, calculating the differences between the current model and its previous snapshot is quite expensive: we don't have any information about what changed, so the subtracting operations need to carefully compare each item one by one -- there aren't any useful shortcuts.

Overall, the model update and the diffing operations all take time that's proportional to the number of items in the set, making it difficult to update the display state with high enough frequency once the set grows above a certain size.

This all-or-nothing copy-on-write behavior can be eliminated by organizing the contents of hashed collections into a prefix tree of hash values rather than a single flat hash table. ShareableSet and ShareableDictionary use tree nodes that contain at most 32 items -- each of which can either be a direct key-value pair, or a reference to a child node containing more items. The nodes themselves work like tiny hash tables themselves: each node along the path from the root to any given item handles 5 bits (2^5 == 32) worth of data from the item's hash value. New nodes get created whenever a new item's hash value matches another's up to the depth currently covered by its path; such collisions are resolved by allocating a new node that looks at 5 more bits' worth of information until the items can be distinguished or we exhaust all available bits in the hash value. (Special collision nodes handle items that fall in the latter case.)

A key aspect of this structure is that individual nodes can be reference counted, so they can be easily shared across different instances of the same collection type. Copies of collection values can be made just as easily as with the flat hash table -- we just need to make a copy of the reference to the root node, incrementing its reference count. Furthermore, when we need to insert a new item (or remove an existing one) from such a copy, we only need to make copies of the nodes along its path: all other nodes can continue to be linked into both trees.

This boosts the performance of shared mutations from linear to logarithmic time, bringing along a corresponding improvement to memory use -- two set values that only diverged slightly are still expected to share most of their storage.

Better, the trees are able to organically grow or shrink their storage to fit their contents: we don't need to think about reserving capacity, and we don't need to worry about temporary spikes in a collection's size inducing a corresponding increase in its size that lingers long after the collection is restored to a more typical size.

Sharing storage nodes between collection instances also brings about additional benefits: when comparing or combining two sets (or dictionaries), we can easily detect shared nodes and we can typically handle their entire subtree as a single unit, instead of having to individually compare/combine their items. For example, when subtracting one set from another, nodes that are shared between them can simply be skipped when building the result, without even looking at any of their contained items.

For example, simply changing the model type from Set to ShareableSet leads to an algorithmic improvement to running time:

typealias Model = ShareableSet

... // Same code as before

For a million items, the code that uses Set would have taken roughly five hours to run; the variant that uses ShareableCode runs in about two seconds!

Plotting the average time spent over one iteration of the loop on a log-log chart, we get the following result:

Over the entire spread of item counts from 1 to a million, Set goes from 100ns to >10ms spent in each iteration -- an increase of five orders of magnitude, corresponding to a linear growth rate. Meanwhile PeristentSet's growth is kept nicely logarithmic: its 8-10x growth factor is far removed from the growth rate of its input data.

For this particular use case, hash-array mapped prefix trees proved to be a far better data structure than a flat hash table. Of course, this does not mean that ShareableSet is going to always be a better choice than Set -- as always, it depends on the use case.

Maintaining the prefix tree involves a lot more bookkeeping than a flat hash table, including having to descend through multiple nodes when looking up items or iterating through the collection:

Not having to think about reserving capacity also means that the tree cannot preallocate nodes in advance, even if we know exactly how many items we will need to insert -- it needs to organically allocate/deallocate nodes as needed. The more complicated structure therefore leads to worse expected behavior (by a constant factor) when the use case cannot exercise the benefits of node sharing, such as when we only mutate a single dictionary in place, without ever making a copy of it.

(Still, certain use cases might still accept the constant-factor slowdown in exchange for the freedom of not having to worry about memory management.)

Proposed solution Copy Chapter

We propose to introduce a new Swift Collections module, called ShareableHashedCollections, with two top-level public types, ShareableSet and ShareableDictionary.

`ShareableSet` Copy Section

ShareableSet is a type with one generic argument, Element, required to be Hashable. Like the standard Set, ShareableSet is a SetAlgebra that is a forward-only, unordered Collection with an opaque index type. It is Hashable and conditionally Sendable and Codable, depending on its Element:

struct ShareableSet<Element: Hashable>
 : Sequence, Collection, 
   SetAlgebra, 
   Equatable, Hashable, 
   CustomStringConvertible, CustomDebugStringConvertible, CustomReflectable, 
   ExpressibleByArrayLiteral
{}

extension ShareableSet: Sendable where Element: Sendable {}
extension ShareableSet: Decodable where Element: Decodable {}
extension ShareableSet: Encodable where Element: Encodable {}

Internally, ShareableSet organizes its elements into a hash-array mapped prefix tree. To speed up indexing operations in such a structure, each index in a ShareableSet value contains a direct storage reference to the node within the tree that contains the element addressed. This means that unlike with Set, ShareableSet indices need to get invalidated on every mutation.

Creating a Set

init()
init<S: Sequence>(S)
init(`Self`)
init<Value>(ShareableDictionary<Element, Value>.Keys)

Finding Elements

func contains(Element) -> Bool
func firstIndex(of: Element) -> Index?
func lastIndex(of: Element) -> Index?

Adding and Updating Elements

mutating func insert(Element) -> (inserted: Bool, memberAfterInsert: Element)
mutating func update(with: Element) -> Element?
mutating func update(Element, at: Index) -> Element

Removing Elements

mutating func remove(Element) -> Element?
mutating func remove(at: Index) -> Element
func filter((Element) throws -> Bool) rethrows -> ShareableSet<Element>
mutating func removeAll(where shouldBeRemoved: (Element) throws -> Bool) rethrows

Combining Sets

All the standard combining operations (intersection, union, subtraction and symmetric difference) are supported, in both non-mutating and mutating forms. SetAlgebra only requires the ability to combine one set instance with another, but ShareableSet follows the tradition established by Set in providing additional overloads to each operation that allow combining a set with additional types, including arbitrary sequences.

func intersection(`Self`) -> ShareableSet<Element>
func intersection<Value>(ShareableDictionary<Element, Value>.Keys) -> ShareableSet<Element>
func intersection<S>(S) -> ShareableSet<Element>

func union(`Self`) -> ShareableSet<Element>
func union<Value>(ShareableDictionary<Element, Value>.Keys) -> ShareableSet<Element>
func union<S>(S) -> ShareableSet<Element>

func subtracting(`Self`) -> ShareableSet<Element>
func subtracting<V>(ShareableDictionary<Element, V>.Keys) -> ShareableSet<Element>
func subtracting<S>(S) -> ShareableSet<Element>

func symmetricDifference(`Self`) -> ShareableSet<Element>
func symmetricDifference<Value>(ShareableDictionary<Element, Value>.Keys) -> ShareableSet<Element>
func symmetricDifference<S>(S) -> ShareableSet<Element>

mutating func formIntersection(`Self`)
mutating func formIntersection<Value>(ShareableDictionary<Element, Value>.Keys)
mutating func formIntersection<S>(S)

mutating func formUnion(`Self`)
mutating func formUnion<Value>(ShareableDictionary<Element, Value>.Keys)
mutating func formUnion<S>(S)

mutating func subtract(`Self`)
mutating func subtract<Value>(ShareableDictionary<Element, Value>.Keys)
mutating func subtract<S>(S)

mutating func formSymmetricDifference(`Self`)
mutating func formSymmetricDifference<Value>(ShareableDictionary<Element, Value>.Keys)
mutating func formSymmetricDifference<S>(S)

Comparing Sets

ShareableSet supports all standard set comparisons (subset tests, superset tests, disjunctness test), including the customary overloads established by Set. As an additional extension, the isEqualSet family of member functions generalize the standard == operation to support checking whether a ShareableSet consists of exactly the same members as an arbitrary sequence. Like ==, the isEqualSet functions ignore element ordering and duplicates (if any).

static func == (`Self`, `Self`) -> Bool
func isEqualSet(to: `Self`) -> Bool
func isEqualSet<Value>(to: ShareableDictionary<Element, Value>.Keys) -> Bool
func isEqualSet<S>(to: S) -> Bool

func isSubset(of: `Self`) -> Bool
func isSubset<Value>(of: ShareableDictionary<Element, Value>.Keys) -> Bool
func isSubset<S>(of: S) -> Bool

func isSuperset(of: `Self`) -> Bool
func isSuperset<Value>(of: ShareableDictionary<Element, Value>.Keys) -> Bool
func isSuperset<S>(of: S) -> Bool

func isStrictSubset(of: `Self`) -> Bool
func isStrictSubset<Value>(of: ShareableDictionary<Element, Value>.Keys) -> Bool
func isStrictSubset<S>(of: S) -> Bool

func isStrictSuperset(of: `Self`) -> Bool
func isStrictSuperset<Value>(of: ShareableDictionary<Element, Value>.Keys) -> Bool
func isStrictSuperset<S>(of: S) -> Bool

func isDisjoint(with: `Self`) -> Bool
func isDisjoint<Value>(with: ShareableDictionary<Element, Value>.Keys) -> Bool
func isDisjoint<S>(with: S) -> Bool

`ShareableDictionary` Copy Section

ShareableDictionary is a type with two generic arguments, Key and Value, of which Key is required to be Hashable. Like the standard Dictionary, it implements a forward-only, unordered Collection of key-value pairs, with custom members providing efficient support for retrieving the value of any given key. ShareableDictionary is conditionally Sendable, Codable, Equatable and Hashable, depending on its Key and Value types.

struct ShareableDictionary<Key: Hashable, Value>
  : Sequence, Collection,
    CustomStringConvertible, CustomDebugStringConvertible, CustomReflectable,
    ExpressibleByDictionaryLiteral
{}

extension ShareableDictionary: Sendable where Key: Sendable, Value: Sendable {}
extension ShareableDictionary: Equatable where Value: Equatable {}
extension ShareableDictionary: Hashable where Value: Hashable {}
extension ShareableDictionary: Decodable where Key: Decodable, Value: Decodable {}
extension ShareableDictionary: Encodable where Key: Encodable, Value: Encodable {}

Internally, ShareableDictionary organizes its elements into a hash-array mapped prefix tree. To speed up indexing operations in such a structure, each index in a ShareableDictionary value contains a direct storage reference to the node within the tree that contains the element addressed. This means that unlike with Dictionary, ShareableDictionary indices are invalidated on every mutation, including mutations that only affect a value within the dictionary.

Collection Views

ShareableDictionary provides the customary dictionary views, keys and values. These are collection types that are projections of the dictionary itself, with elements that match only the keys or values of the dictionary, respectively. The Keys view is notable in that it provides operations for subtracting and intersecting the keys of two dictionaries, allowing for easy detection of inserted and removed items between two snapshots of the same dictionary. Because ShareableDictionary needs to invalidate indices on every mutation, its Values view is not a MutableCollection.

ShareableDictionary.Keys
ShareableDictionary.Values

var keys: Keys
var values: Values

extension ShareableDictionary.Keys {
  func contains(Element) -> Bool
  
  func intersection(ShareableSet<Key>) -> Self
  func intersection<Value2>(ShareableDictionary<Key, Value2>.Keys) -> Self

  func subtracting(ShareableSet<Key>) -> Self
  func subtracting<Value2>(ShareableDictionary<Key, Value2>.Keys) -> Self
}

Creating a Dictionary

init()
init(ShareableDictionary<Key, Value>)
init(Dictionary<Key, Value>)
init<S>(uniqueKeysWithValues: S)
init<S>(S, uniquingKeysWith: (Value, Value) throws -> Value) rethrows
init<S>(grouping: S, by: (S.Element) throws -> Key) rethrows
init(keys: ShareableSet<Key>, valueGenerator: (Key) throws -> Value) rethrows

Inspecting a Dictionary

var isEmpty: Bool
var count: Int

Accessing Keys and Values

subscript(Key) -> Value?
subscript(Key, default _: () -> Value) -> Value
func index(forKey: Key) -> Index?

Adding or Updating Keys and Values

Beyond the standard updateValue(_:forKey:) method, ShareableDictionary also provides additional updateValue variants that take closure arguments. These provide a more straightforward way to perform in-place mutations on dictionary values (compared to mutating values through the corresponding subscript operation.) ShareableDictionary also provides the standard merge and merging operations for combining dictionary values.

mutating func updateValue(Value, forKey: Key) -> Value?
mutating func updateValue<R>(forKey: Key, with: (inout Value?) throws -> R) rethrows -> R
mutating func updateValue<R>(forKey: Key, default: () -> Value, with: (inout Value) throws -> R) rethrows -> R

mutating func merge(`Self`, uniquingKeysWith: (Value, Value) throws -> Value) rethrows
mutating func merge<S>(S, uniquingKeysWith: (Value, Value) throws -> Value) rethrows

func merging(`Self`, uniquingKeysWith: (Value, Value) throws -> Value) rethrows -> ShareableDictionary<Key, Value>
func merging<S>(S, uniquingKeysWith: (Value, Value) throws -> Value) rethrows -> ShareableDictionary<Key, Value>

Removing Keys and Values

mutating func removeValue(forKey: Key) -> Value?
mutating func remove(at: Index) -> Element
func filter((Element) throws -> Bool) rethrows -> ShareableDictionary<Key, Value>
mutating func removeAll(where shouldBeRemoved: (Element) throws -> Bool) rethrows

Comparing Dictionaries

static func == (`Self`, `Self`) -> Bool

Transforming a Dictionary

func mapValues<T>((Value) throws -> T) rethrows -> ShareableDictionary<Key, T>
func compactMapValues<T>((Value) throws -> T?) rethrows -> ShareableDictionary<Key, T>

Detailed design Copy Chapter

For a precise list of all public APIs in the ShareableHashedCollections module, see the DocC documentation that is (temporarily) available at:

https://lorentey.github.io/swift-collections/ShareableHashedCollections/documentation/shareablehashedcollections/

Alternatively, you can browse the proposed implementation at:

https://github.com/apple/swift-collections/tree/release/1.1/Sources/ShareableHashedCollections

Alternatives Considered Copy Chapter

Naming Copy Section

The initial version of this document proposed to name the new types PersistentSet and PersistentDictionary, after the term of art "persistent data structure". Based on review feedback, we changed this to the current names. The new names eliminate confusion about the word "persistent", while also preserving the following important properties:

1. The name succinctly labels the primary feature that distinguishes them from existing collection types in this package and the Standard Library. In our case, this feature is that these types are pretty good at mutating copied values. because they can continue to share parts of their storage with their copies after such mutations.
2. The meaning is still at least somewhat understandable to folks who are familiar with this feature in, say, a purely functional context. (There is a bit of handwaving here -- the precise term "shareable" have never been applied to data structures in this (or from what I can tell, any other) sense. However, pointing out the possibility of shared storage seems to be striking a chord that other options have failed to match.)

Another widespread preexisting alternative term for such data structures is "immutable"; unfortunately, it is not applicable here.

File: Documentation/Deque.md Copy Chapter

Deque

A collection implementing a double-ended queue.

Declaration Copy Chapter

import DequeModule

@frozen struct Deque<Element>

Overview Copy Chapter

Deque (pronounced "deck") implements an ordered random-access
collection that supports efficient insertions and removals from both
ends.

var colors: Deque = ["red", "yellow", "blue"]

Deques implement the same indexing semantics as arrays: they use integer
indices, and the first element of a nonempty deque is always at index zero.
Like arrays, deques conform to RangeReplaceableCollection,
MutableCollection and RandomAccessCollection, providing a familiar
interface for manipulating their contents:

print(colors[1]) // "yellow"
print(colors[3]) // Runtime error: Index out of range

colors.insert("green", at: 1)
// ["red", "green", "yellow", "blue"]

colors.remove(at: 2) // "yellow"
// ["red", "green", "blue"]

Like all variable-size collections on the standard library, Deque
implements value semantics: each deque has an independent value that
includes the values of its elements. Modifying one deque does not affect any
others:

var copy = deque
copy[1] = "violet"
print(copy)  // ["red", "violet", "blue"]
print(deque) // ["red", "green", "blue"]

This is implemented with the copy-on-write optimization. Multiple copies of
a deque share the same underlying storage until you modify one of the
copies. When that happens, the deque being modified replaces its storage
with a uniquely owned copy of itself, which is then modified in place.

Deque stores its elements in a circular buffer, which allows efficient
insertions and removals at both ends of the collection; however, this comes
at the cost of potentially discontiguous storage. In contrast, Array is
(usually) backed by a contiguous buffer, where new data can be efficiently
appended to the end, but inserting at the front is relatively slow, as
existing elements need to be shifted to make room.

This difference in implementation means that while the interface of a deque
is very similar to an array, the operations have different performance
characteristics. Mutations near the front are expected to be significantly
faster in deques, but arrays may measure slightly faster for general
random-access lookups.

Deques provide a handful of additional operations that make it easier to
insert and remove elements at the front. This includes queue operations such
as popFirst and prepend, including the ability to directly prepend a
sequence of elements:

colors.append("green")
colors.prepend("orange")
// colors: ["orange", "red", "blue", "yellow", "green"]

colors.popLast() // "green"
colors.popFirst() // "orange"
// colors: ["red", "blue", "yellow"]

colors.prepend(contentsOf: ["purple", "teal"])
// colors: ["purple", "teal", "red", "blue", "yellow"]

Unlike arrays, deques do not currently provide direct unsafe access to their
underlying storage. They also lack a capacity property -- the size of the
storage buffer at any given point is an unstable implementation detail that
should not affect application logic. (However, deques do provide a
reserveCapacity method.)

File: Documentation/Heap.md Copy Chapter

Heap

A partially-ordered tree of elements with performant insertion and removal operations.

Declaration Copy Chapter

public struct Heap<Element: Comparable>

Overview Copy Chapter

Array-backed binary heaps provide performant lookups (O(1)) of the smallest or largest element (depending on whether it's a min-heap or a max-heap, respectively) as well as insertion and removal (O(log n)). Heaps are commonly used as the backing storage for a priority queue.

A variant on this, the min-max heap, allows for performant lookups and removal of both the smallest and largest elements by interleaving min and max levels in the backing array. Heap is an implementation of a min-max heap.

Initialization Copy Section

There are a couple of options for initializing a Heap. To create an empty Heap, call init():

var heap = Heap()

You can also create a Heap from an existing sequence in linear time:

var heap = Heap((1...).prefix(20))

Finally, a Heap can be created from an array literal:

var heap: Heap<Double> = [0.1, 0.6, 1.0, 0.15, 0.42]

Insertion Copy Section

Of a single element

To insert an element into a Heap, call insert(_:):

var heap = Heap()
heap.insert(6)
heap.insert(2)

This works by adding the new element into the end of the backing array and then bubbling it up to where it belongs in the heap.

Of a sequence of elements

You can also insert a sequence of elements into a Heap:

var heap = Heap(0 ..< 10)
heap.insert(contentsOf: (20 ... 100).shuffled())
heap.insert(contentsOf: [-5, -6, -8, -12, -3])

Lookup Copy Section

As mentioned earlier, the smallest and largest elements can be queried in constant time:

var heap = Heap(1 ... 20)
let min = heap.min  // 1
let max = heap.max  // 20

In a min-max heap, the smallest element is stored at index 0 in the backing array; the largest element is stored at either index 1 or index 2, the first max level in the heap (so to look up the largest, we compare the two and return the larger one).

We also expose a read-only view into the backing array, should somebody need that.

let heap = Heap((1...100).shuffled())
for val in heap.unordered {
   ...
}

Note: The elements aren't arbitrarily ordered (it is, after all, a heap). However, no guarantees are given as to the ordering of the elements or that this won't change in future versions of the library.

Removal Copy Section

Removal has logarithmic complexity, and removing both the smallest and largest elements is supported:

var heap = Heap((1...20).shuffled())
var heap2 = heap

while let min = heap.popMin() {
    print("Next smallest element:", min)
}

while let max = heap2.popMax() {
    print("Next largest element:", max)
}

To remove the smallest element, we remove and return the element at index 0. The element at the end of the backing array is put in its place at index 0, and then we trickle it down to where it belongs in the heap. To remove the largest element, we do the same except the index is whatever the index of the largest element is (see above) instead of 0.

We also have non-optional flavors that assume the heap isn't empty, removeMin() and removeMax().

Iteration Copy Section

Heap itself doesn't conform to Sequence because of the potential confusion around which direction it should iterate (largest-to-smallest? smallest-to-largest?).

Performance Copy Section

In all of the above, n is the number of elements in the heap.

The above graph was generated in release mode on a MacBook Pro (16-inch, 2019) with a 2.3 GHz 8-Core Intel Core i9 using the benchmarks defined in the swift-collections-benchmark target.

Implementation Details Copy Chapter

The implementation is based on the min-max heap data structure as introduced by Atkinson et al. 1986.

Min-max heaps are complete binary trees represented implicitly as an array of their elements. Each node at an even level in the tree is less than or equal to all its descendants, while each node at an odd level in the tree is greater or equal to all of its descendants.

// Min-max heap:
level 0 (min):         ┌────── A ──────┐
level 1 (max):     ┌── J ──┐       ┌── G ──┐
level 2 (min):   ┌ D ┐   ┌ B       F       C
level 3 (max):   I   E   H 

// Array representation:
["A", "J", "G", "D", "B", "F", "C", "I", "E", "H"]

By the min-max property above, the root node is an on even level, so its value ("A" in this example) must be the minimum of the entire heap. Its two children are on an odd level, so they hold the maximum value for their respective subtrees; it follows that one of them holds the maximum value for the whole tree -- in this case, "J". Accessing the minimum and maximum values in the heap can therefore be done in O(1) comparisons.

Mutations of the heap (insertions, removals) must ensure that items remain arranged in a way that maintain the min-max property. Inserting a single new element or removing the current minimum/maximum can be done by rearranging items on a single path in the tree; accordingly, these operations execute O(log(count)) comparisons/swaps.

M.D. Atkinson, J.-R. Sack, N. Santoro, T. Strothotte.
"Min-Max Heaps and Generalized Priority Queues."
Communications of the ACM, vol. 29, no. 10, Oct. 1986., pp. 996-1000,
doi:10.1145/6617.6621

File: Documentation/OrderedDictionary.md Copy Chapter

`OrderedDictionary`

An ordered collection of key-value pairs.

Declaration Copy Chapter

import OrderedCollections

@frozen struct OrderedDictionary<Key: Hashable, Value>

Overview Copy Chapter

Like the standard Dictionary, ordered dictionaries use a hash table to
ensure that no two entries have the same keys, and to efficiently look up
values corresponding to specific keys. However, like an Array (and
unlike Dictionary), ordered dictionaries maintain their elements in a
particular user-specified order, and they support efficient random-access
traversal of their entries.

OrderedDictionary is a useful alternative to Dictionary when the order
of elements is important, or when you need to be able to efficiently access
elements at various positions within the collection.

You can create an ordered dictionary with any key type that conforms to the
Hashable protocol.

let responses: OrderedDictionary = [
  200: "OK",
  403: "Access forbidden",
  404: "File not found",
  500: "Internal server error",
]

Equality of Ordered Dictionaries Copy Section

Two ordered dictionaries are considered equal if they contain the same
elements, and in the same order. This matches the concept of equality of
an Array, and it is different from the unordered Dictionary.

let a: OrderedDictionary = [1: "one", 2: "two"]
let b: OrderedDictionary = [2: "two", 1: "one"]
a == b // false
b.swapAt(0, 1) // `b` now has value [1: "one", 2: "two"]
a == b // true

(OrderedDictionary only conforms to Equatable when its Value is
equatable.)

Dictionary Operations Copy Section

OrderedDictionary provides many of the same operations as Dictionary.

For example, you can look up and add/remove values using the familiar
key-based subscript, returning an optional value:

var dictionary: OrderedDictionary<String, Int> = [:]
dictionary["one"] = 1
dictionary["two"] = 2
dictionary["three"] // nil
// dictionary is now ["one": 1, "two": 2]

If a new entry is added using the subscript setter, it gets appended to the
end of the dictionary. (So that by default, the dictionary contains its
elements in the order they were originally inserted.)

OrderedDictionary also implements the variant of this subscript that takes
a default value. Like with Dictionary, this is useful when you want to
perform in-place mutations on values:

let text = "short string"
var counts: OrderedDictionary<Character, Int> = [:]
for character in text {
  counts[character, default: 0] += 1
}
// counts is ["s": 2, "h": 1, "o": 1,
//            "r": 2, "t": 2, " ": 1,
//            "i": 1, "n": 1, "g": 1]

If the Value type implements reference semantics, or when you need to
perform a series of individual mutations on the values, the closure-based
updateValue(forKey:default:with:) method provides an easier-to-use
alternative to the defaulted key-based subscript.

let text = "short string"
var counts: OrderedDictionary<Character, Int> = [:]
for character in text {
  counts.updateValue(forKey: character, default: 0) { value in
    value += 1
  }
}
// Same result as before

(This isn't currently available on the regular Dictionary.)

The Dictionary type's original updateValue(_:forKey:) method is also
available, and so is index(forKey:), grouping/uniquing initializers
(init(uniqueKeysWithValues:), init(_:uniquingKeysWith:),
init(grouping:by:)), methods for merging one dictionary with another
(merge, merging), filtering dictionary entries (filter(_:)),
transforming values (mapValues(_:)), and a combination of these two
(compactMapValues(_:)).

Sequence and Collection Operations Copy Section

Ordered dictionaries use integer indices representing offsets from the
beginning of the collection. However, to avoid ambiguity between key-based
and indexing subscripts, OrderedDictionary doesn't directly conform to
Collection. Instead, it only conforms to Sequence, and provides a
random-access collection view over its key-value pairs:

responses[0] // `nil` (key-based subscript)
responses.elements[0] // `(200, "OK")` (index-based subscript)

Because ordered dictionaries need to maintain unique keys, neither
OrderedDictionary nor its elements view can conform to the full
MutableCollection or RangeReplaceableCollection protocols. However, they
are able to partially implement requirements: they support mutations
that merely change the order of elements, or just remove a subset of
existing members:

// Permutation operations from MutableCollection:
func swapAt(_ i: Index, _ j: Index)
func partition(by predicate: (Element) throws -> Bool) rethrows -> Index
func sort() where Element: Comparable
func sort(by predicate: (Element, Element) throws -> Bool) rethrows
func shuffle()
func shuffle<T: RandomNumberGenerator>(using generator: inout T)

// Removal operations from RangeReplaceableCollection:
func removeAll(keepingCapacity: Bool = false)
func remove(at index: Index) -> Element
func removeSubrange(_ bounds: Range)
func removeLast() -> Element
func removeLast(_ n: Int)
func removeFirst() -> Element
func removeFirst(_ n: Int)
func removeAll(where shouldBeRemoved: (Element) throws -> Bool) rethrows

OrderedDictionary also implements reserveCapacity(_) from
RangeReplaceableCollection, to allow for efficient insertion of a known
number of elements. (However, unlike Array and Dictionary,
OrderedDictionary does not provide a capacity property.)

Keys and Values Views Copy Section

Like the standard Dictionary, OrderedDictionary provides keys and
values properties that provide lightweight views into the corresponding
parts of the dictionary.

The keys collection is of type OrderedSet<Key>, containing all the keys
in the original dictionary.

let d: OrderedDictionary = [2: "two", 1: "one", 0: "zero"]
d.keys // [2, 1, 0] as OrderedSet

The keys property is read-only, so you cannot mutate the dictionary
through it. However, it returns an ordinary ordered set value, which can be
copied out and then mutated if desired. (Such mutations won't affect the
original dictionary value.)

The values collection is a mutable random-access collection of the values
in the dictionary:

d.values // "two", "one", "zero"
d.values[2] = "nada"
// `d` is now [2: "two", 1: "one", 0: "nada"]
d.values.sort()
// `d` is now [2: "nada", 1: "one", 0: "two"]

Both views store their contents in regular Array values, accessible
through their elements property.

Performance Copy Chapter

Like the standard Dictionary type, the performance of hashing operations
in OrderedDictionary is highly sensitive to the quality of hashing
implemented by the Key type. Failing to correctly implement hashing can
easily lead to unacceptable performance, with the severity of the effect
increasing with the size of the hash table.

In particular, if a certain set of keys all produce the same hash value,
then hash table lookups regress to searching an element in an unsorted
array, i.e., a linear operation. To ensure hashed collection types exhibit
their target performance, it is important to ensure that such collisions
cannot be induced merely by adding a particular list of keys to the
dictionary.

The easiest way to achieve this is to make sure Key implements hashing
following Hashable's documented best practices. The conformance must
implement the hash(into:) requirement, and every bit of information that
is compared in == needs to be combined into the supplied Hasher value.
When used correctly, Hasher produces high-quality, randomly seeded hash
values that prevent repeatable hash collisions.

When Key correctly conforms to Hashable, key-based lookups in an ordered
dictionary is expected to take O(1) equality checks on average. Hash
collisions can still occur organically, so the worst-case lookup performance
is technically still O(n) (where n is the size of the dictionary);
however, long lookup chains are unlikely to occur in practice.

Implementation Details Copy Chapter

An ordered dictionary consists of an ordered set of keys, alongside a
regular Array value that contains their associated values.

File: Documentation/OrderedSet.md Copy Chapter

OrderedSet

An ordered collection of unique elements.

Declaration Copy Chapter

import OrderedCollections

@frozen struct OrderedSet<Element: Hashable>

Overview Copy Chapter

Similar to the standard Set, ordered sets ensure that each element appears
only once in the collection, and they provide efficient tests for
membership. However, like Array (and unlike Set), ordered sets maintain
their elements in a particular user-specified order, and they support
efficient random-access traversal of their members.

OrderedSet is a useful alternative to Set when the order of elements is
important, or when you need to be able to efficiently access elements at
various positions within the collection. It can also be used instead of an
Array when each element needs to be unique, or when you need to be able to
quickly determine if a value is a member of the collection.

You can create an ordered set with any element type that conforms to the
Hashable protocol.

let buildingMaterials: OrderedSet = ["straw", "sticks", "bricks"]

Equality of Ordered Sets Copy Section

Two ordered sets are considered equal if they contain the same elements, and
in the same order. This matches the concept of equality of an Array, and
it is different from the unordered Set.

let a: OrderedSet = [1, 2, 3, 4]
let b: OrderedSet = [4, 3, 2, 1]
a == b // false
b.sort() // `b` now has value [1, 2, 3, 4]
a == b // true

Set Operations Copy Section

OrderedSet implements most, but not all, SetAlgebra requirements. In
particular, it supports the membership test contains(_:) as well as all
high-level set operations such as union(_:), intersection(_:) or
isSubset(of:).

buildingMaterials.contains("glass") // false
buildingMaterials.intersection(["bricks", "straw"]) // ["straw", "bricks"]

Operations that return an ordered set usually preserve the ordering of
elements in their input. For example, in the case of the intersection call
above, the ordering of elements in the result is guaranteed to match their
order in the first input set, buildingMaterials.

On the other hand, predicates such as isSubset(of:) tend to ignore element
ordering:

let moreMaterials: OrderedSet = ["bricks", "glass", "sticks", "straw"]
buildingMaterials.isSubset(of: moreMaterials) // true

However, OrderedSet does not implement insert(_:) nor update(with:) --
it provides its own variants for insertion that are more explicit about
where in the collection new elements gets inserted:

func insert(_ item: Element, at index: Index) -> (inserted: Bool, index: Int)
func append(_ item: Element) -> (inserted: Bool, index: Int)
func update(at index: Int, with item: Element) -> Element
func updateOrAppend(_ item: Element) -> Element?

Additionally,OrderedSet has an order-sensitive definition of equality (see
above) that is incompatible with SetAlgebra's documented semantic
requirements. Accordingly, OrderedSet does not (cannot) itself conform to
SetAlgebra.

Unordered Set View Copy Section

For cases where SetAlgebra conformance is desired (such as when passing an
ordered set to a function that is generic over that protocol), OrderedSet
provides an efficient unordered view of its elements that conforms to
SetAlgebra. The unordered view implements the same concept of equality as
the standard Set, ignoring element ordering.

var a: OrderedSet = [0, 1, 2, 3]
let b: OrderedSet = [3, 2, 1, 0]
a == b // false
a.unordered == b.unordered // true

func frobnicate<S: SetAlgebra>(_ set: S) { ... }
frobnicate(a) // error: `OrderedSet<String>` does not conform to `SetAlgebra`
frobnicate(a.unordered) // OK

The unordered view is mutable. Insertions into it implicitly append new
elements to the end of the collection.

buildingMaterials.unordered.insert("glass") // => inserted: true
// buildingMaterials is now ["straw", "sticks", "bricks", "glass"]

Accessing the unordered view is an efficient operation, with constant
(minimal) overhead. Direct mutations of the unordered view (such as the
insertion above) are executed in place when possible. However, as usual with
copy-on-write collections, if you make a copy of the view (such as by
extracting its value into a named variable), the resulting values will share
the same underlying storage, so mutations of either will incur a copy of the
whole set.

Sequence and Collection Operations Copy Section

Ordered sets are random-access collections. Members are assigned integer
indices, with the first element always being at index 0:

let buildingMaterials: OrderedSet = ["straw", "sticks", "bricks"]
buildingMaterials[1] // "sticks"
buildingMaterials.firstIndex(of: "bricks") // 2

for i in 0 ..< buildingMaterials.count {
  print("Little piggie #\(i) built a house of \(buildingMaterials[i])")
}
// Little piggie #0 built a house of straw
// Little piggie #1 built a house of sticks
// Little piggie #2 built a house of bricks

Because OrderedSet needs to keep its members unique, it cannot conform to
the full MutableCollection or RangeReplaceableCollection protocols.
Operations such as MutableCollection's subscript setter or
RangeReplaceableCollection's replaceSubrange assume the ability to
insert/replace arbitrary elements in the collection, but allowing that could
lead to duplicate values.

However, OrderedSet is able to partially implement these two protocols;
namely, there is no issue with mutation operations that merely change the
order of elements, or just remove some subset of existing members:

// Permutation operations from MutableCollection:
func swapAt(_ i: Int, _ j: Int)
func partition(by predicate: (Element) throws -> Bool) -> rethrows Int
func sort() where Element: Comparable
func sort(by predicate: (Element, Element) throws -> Bool) rethrows
func shuffle()
func shuffle<T: RandomNumberGenerator>(using generator: inout T)
func reverse()

// Removal operations from RangeReplaceableCollection:
func removeAll(keepingCapacity: Bool = false)
func remove(at index: Int) -> Element
func removeSubrange(_ bounds: Range)
func removeLast() -> Element
func removeLast(_ n: Int)
func removeFirst() -> Element
func removeFirst(_ n: Int)
func removeAll(where shouldBeRemoved: (Element) throws -> Bool) rethrows

OrderedSet also implements reserveCapacity(_) from
RangeReplaceableCollection, to allow for efficient insertion of a known
number of elements. (However, unlike Array and Set, OrderedSet does
not provide a capacity property.)

Accessing The Contents of an Ordered Set as an Array Copy Section

In cases where you need to pass the contents of an ordered set to a function
that only takes an array value or (or something that's generic over
RangeReplaceableCollection or MutableCollection), then the best option
is usually to directly extract the members of the OrderedSet as an Array
value using its elements property. OrderedSet uses a standard array
value for element storage, so extracting the array value has minimal
overhead.

func pickyFunction(_ items: Array)

var set: OrderedSet = [0, 1, 2, 3]
pickyFunction(set) // error
pickyFunction(set.elements) // OK

It is also possible to mutate the set by updating the value of the
elements property. This guarantees that direct mutations happen in place
when possible (i.e., without spurious copy-on-write copies).

However, the set needs to ensure the uniqueness of its members, so every
update to elements includes a postprocessing step to detect and remove
duplicates over the entire array. This can be slower than doing the
equivalent updates with direct OrderedSet operations, so updating
elements is best used in cases where direct implementations aren't
available -- for example, when you need to call a MutableCollection
algorithm that isn't directly implemented by OrderedSet itself.

Performance Copy Section

Like the standard Set type, the performance of hashing operations in
OrderedSet is highly sensitive to the quality of hashing implemented by
the Element type. Failing to correctly implement hashing can easily lead
to unacceptable performance, with the severity of the effect increasing with
the size of the hash table.

In particular, if a certain set of elements all produce the same hash value,
then hash table lookups regress to searching an element in an unsorted
array, i.e., a linear operation. To ensure hashed collection types exhibit
their target performance, it is important to ensure that such collisions
cannot be induced merely by adding a particular list of members to the set.

The easiest way to achieve this is to make sure Element implements hashing
following Hashable's documented best practices. The conformance must
implement the hash(into:) requirement, and every bit of information that
is compared in == needs to be combined into the supplied Hasher value.
When used correctly, Hasher produces high-quality, randomly seeded hash
values that prevent repeatable hash collisions.

When Element implements Hashable correctly, testing for membership in an
ordered set is expected to take O(1) equality checks on average. Hash
collisions can still occur organically, so the worst-case lookup performance
is technically still O(n) (where n is the size of the set); however,
long lookup chains are unlikely to occur in practice.

Implementation Details Copy Section

An OrderedSet stores its members in a regular Array value (exposed by
the elements property). It also maintains a standalone hash table
containing array indices alongside the array; this is used to implement fast
membership tests. The size of the array is limited by the capacity of the
corresponding hash table, so indices stored inside the hash table can be
encoded into fewer bits than a standard Int value, leading to a storage
representation that can often be more compact than that of Set itself.

Inserting or removing a single member (or a range of members) needs to
perform the corresponding operation in the storage array, in addition to
renumbering any subsequent members in the hash table. Therefore, these
operations are expected to have performance characteristics similar to an
Array: inserting or removing an element to the end of an ordered set is
expected to execute in O(1) operations, while they are expected to take
linear time at the front (or in the middle) of the set. (Note that this is
different to the standard Set, where insertions and removals are expected
to take amortized O(1) time.)