## File: README.md # Swift Collections **Swift Collections** is an open-source package of data structure implementations for the Swift programming language. [](https://swiftpackageindex.com/apple/swift-collections) [](https://swiftpackageindex.com/apple/swift-collections) ## Table of Contents * [Stable Data Structures](#stable-data-structures) * [`BasicContainers` module](#basiccontainers-module) * [`DequeModule` module](#dequemodule-module) * [`OrderedCollections` module](#orderedcollections-module) * [`BitCollections` module](#bitcollections-module) * [`HeapModule` module](#heapmodule-module) * [`HashTreeCollections` module](#hashtreecollections-module) * [`TrailingElementsModule` module](#trailingelementsmodule-module) * [`ContainersPreview` module](#containerspreview-module) * [`Collections` module](#collections-module) * [Experimental Features](#experimental-features) * [`UnstableContainersPreview` package trait](#unstablecontainerspreview-package-trait) * [`UnstableHashedContainers` package trait](#unstablehashedcontainers-package-trait) * [`UnstableSortedCollections` package trait](#unstablesortedcollections-package-trait) * [Project Status](#project-status) * [Definition of Public API](#public-api) * [Minimum Required Swift Toolchain Version](#minimum-required-swift-toolchain-version) * [Using Swift Collections in your project](#using-swift-collections-in-your-project) * [Contributing to Swift Collections](#contributing-to-swift-collections) * [Branching Strategy](#branching-strategy) * [Working on the package](#working-on-the-package) * [Fixing a bug or making a small improvement](#fixing-a-bug-or-making-a-small-improvement) * [Proposing a small enhancement](#proposing-a-small-enhancement) * [Proposing the addition of a new data structure](#proposing-the-addition-of-a-new-data-structure) * [Code of Conduct](#code-of-conduct) * [Contact information](#contact-information) ## Stable Data Structures 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`][UniqueArray] is a uniquely held, dynamically resizing array. - [`struct RigidArray`][RigidArray] is a fixed-capacity array. [BasicContainers]: https://swiftpackageindex.com/apple/swift-collections/documentation/basiccontainers [RigidArray]: https://swiftpackageindex.com/apple/swift-collections/documentation/basiccontainers/rigidarray [UniqueArray]: https://swiftpackageindex.com/apple/swift-collections/documentation/basiccontainers/uniquearray #### [`DequeModule`][DequeModule] module Implementations of double-ended queue types, implemented by a ring buffer. - [`struct Deque`][Deque] is a classic collection, implementing value semantics with the copy-on-write optimization. - [`struct UniqueDeque`][UniqueDeque] is a uniquely held, dynamically resizing, noncopyable deque. - [`struct RigidDeque`][RigidDeque] is a fixed-capacity deque implementation. [DequeModule]: https://swiftpackageindex.com/apple/swift-collections/documentation/dequemodule [Deque]: https://swiftpackageindex.com/apple/swift-collections/documentation/dequemodule/deque [RigidDeque]: https://swiftpackageindex.com/apple/swift-collections/documentation/dequemodule/rigiddeque [UniqueDeque]: https://swiftpackageindex.com/apple/swift-collections/documentation/dequemodule/uniquedeque #### [`OrderedCollections`][OrderedCollections] module Provides variants of the standard `Set` and `Dictionary` types with user-defined ordering. - [`struct OrderedSet`][OrderedSet] is a `Set` that preserves insertion order. - [`struct OrderedDictionary`][OrderedDictionary] is a `Dictionary` that preserves insertion order. [OrderedCollections]: https://swiftpackageindex.com/apple/swift-collections/documentation/orderedcollections [OrderedSet]: https://swiftpackageindex.com/apple/swift-collections/documentation/orderedcollections/orderedset [OrderedDictionary]: https://swiftpackageindex.com/apple/swift-collections/documentation/orderedcollections/ordereddictionary #### [`BitCollections`][BitCollections] module Provides efficient implementations of bit maps. - [`struct BitSet`][BitSet] is a more efficient implementation of `Set`. - [`struct BitArray`][BitArray] is a more efficient implementation of `Array`. [BitCollections]: https://swiftpackageindex.com/apple/swift-collections/documentation/bitcollections [BitSet]: https://swiftpackageindex.com/apple/swift-collections/documentation/bitcollections/bitset [BitArray]: https://swiftpackageindex.com/apple/swift-collections/documentation/bitcollections/bitarray #### [`HeapModule`][HeapModule] module - [`struct Heap`][Heap], a min-max heap backed by an array, suitable for use as a priority queue. [HeapModule]: https://swiftpackageindex.com/apple/swift-collections/documentation/heapmodule [Heap]: https://swiftpackageindex.com/apple/swift-collections/documentation/heapmodule/heap #### [`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`][TreeSet] is a persistent hashed set. - [`struct TreeDictionary`][TreeDictionary] is a persistent hashed dictionary. [HashTreeCollections]: https://swiftpackageindex.com/apple/swift-collections/documentation/hashtreecollections [TreeSet]: https://swiftpackageindex.com/apple/swift-collections/documentation/hashtreecollections/treeset [TreeDictionary]: https://swiftpackageindex.com/apple/swift-collections/documentation/hashtreecollections/treedictionary #### [`TrailingElementsModule`][TrailingElementsModule] module - [`struct TrailingArray`][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`][TrailingElements] - [`struct TrailingPadding
`][TrailingPadding] [TrailingElementsModule]: https://swiftpackageindex.com/apple/swift-collections/documentation/trailingelementsmodule [TrailingArray]: https://swiftpackageindex.com/apple/swift-collections/documentation/trailingelementsmodule/trailingarray [TrailingElements]: https://swiftpackageindex.com/apple/swift-collections/documentation/trailingelementsmodule/trailingelements [TrailingPadding]: https://swiftpackageindex.com/apple/swift-collections/documentation/trailingelementsmodule/trailingpadding #### [`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`](#unstablecontainerspreview-package-trait) package trait and are not considered stable API. The type below is the only stable entry point: - [`struct UniqueBox`][UniqueBox] is a heap-allocated noncopyable wrapper for an arbitrary value. [ContainersPreview]: https://swiftpackageindex.com/apple/swift-collections/documentation/containerspreview [UniqueBox]: https://swiftpackageindex.com/apple/swift-collections/documentation/containerspreview/uniquebox #### [`Collections`][CollectionsModule] module Exposes the most commonly used collection types with a single import statement: - [`struct BitArray`][BitArray] from `BitCollections` - [`struct BitSet`][BitSet] from `BitCollections` - [`struct Deque`][Deque] from `DequeModule` - [`struct Heap`][Heap] from `HeapModule` - [`struct OrderedSet`][OrderedSet] from `OrderedCollections` - [`struct OrderedDictionary`][OrderedDictionary] from `OrderedCollections` - [`struct TreeSet`][TreeSet] from `HashTreeCollections` - [`struct TreeDictionary`][TreeDictionary] from `HashTreeCollections` [CollectionsModule]: https://swiftpackageindex.com/apple/swift-collections/documentation/collections ## Experimental Features 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 This trait enables the following types in the [`ContainersPreview`][ContainersPreview] module: - [`struct InputSpan`][InputSpan] is a reference to a contiguous region of consumable items. - [`struct Ref`][Ref] represents a borrowing reference to an item. - [`struct MutableRef`][MutableRef] represents a mutating reference to an item. - [`protocol BorrowingSequence`][BorrowingSequence] models borrowing sequences with ephemeral lifetimes. - [`protocol BorrowingIteratorProtocol`][BorrowingIteratorProtocol] models borrowing iterators with ephemeral elements. - [`protocol Container`][Container] models containers, or constructs that physically store their contents. - [`protocol BidirectionalContainer`][BidirectionalContainer] is the container analogue of `BidirectionalCollection`. - [`protocol RandomAccessContainer`][RandomAccessContainer] is the container analogue of `RandomAccessCollection`. - [`protocol PermutableContainer`][PermutableContainer] models a container that allows items to be arbitrarily reordered (sorted, reversed, etc). - [`protocol MutableContainer`][MutableContainer] refines `PermutableContainer` to also support arbitrary element replacements/mutations, like `MutableCollection`. - [`protocol RangeReplaceableContainer`][RangeReplaceableContainer] models a (potentially fixed capacity) container with insert/append/replace operations. - [`protocol DynamicContainer`][DynamicContainer] refines `RangeReplaceableContainer` to add operations that require dynamic storage sizing. - [`protocol Producer`][Producer] models a generative iterator -- an abstraction for producing items on demand. - [`protocol Drain`][Drain] refines `Producer` to model a source of in-place consumable elements -- primarily for use around container types. [InputSpan]: https://github.com/apple/swift-collections/blob/main/Sources/ContainersPreview/Types/InputSpan.swift [Ref]: https://github.com/apple/swift-collections/blob/main/Sources/ContainersPreview/Types/Ref.swift [MutableRef]: https://github.com/apple/swift-collections/blob/main/Sources/ContainersPreview/Types/MutableRef.swift [BorrowingSequence]: https://github.com/apple/swift-collections/blob/main/Sources/ContainersPreview/Protocols/BorrowingSequence.swift [BorrowingIteratorProtocol]: https://github.com/apple/swift-collections/blob/main/Sources/ContainersPreview/Protocols/BorrowingIteratorProtocol.swift [Container]: https://github.com/apple/swift-collections/blob/main/Sources/ContainersPreview/Protocols/Container/Container.swift [BidirectionalContainer]: https://github.com/apple/swift-collections/blob/main/Sources/ContainersPreview/Protocols/Container/Container.swift [RandomAccessContainer]: https://github.com/apple/swift-collections/blob/main/Sources/ContainersPreview/Protocols/Container/RandomAccessContainer.swift [PermutableContainer]: https://github.com/apple/swift-collections/blob/main/Sources/ContainersPreview/Protocols/Container/PermutableContainer.swift [MutableContainer]: https://github.com/apple/swift-collections/blob/main/Sources/ContainersPreview/Protocols/Container/MutableContainer.swift [RangeReplaceableContainer]: https://github.com/apple/swift-collections/blob/main/Sources/ContainersPreview/Protocols/Container/RangeReplaceableContainer.swift [DynamicContainer]: https://github.com/apple/swift-collections/blob/main/Sources/ContainersPreview/Protocols/Container/DynamicContainer.swift [Producer]: https://github.com/apple/swift-collections/blob/main/Sources/ContainersPreview/Protocols/Producer.swift [Drain]: https://github.com/apple/swift-collections/blob/main/Sources/ContainersPreview/Protocols/Drain.swift 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 This trait enables the following hashed containers in the [`BasicContainers`][BasicContainers] module: - [`struct UniqueSet`][UniqueSet] is a uniquely held, dynamically resizing set. - [`struct RigidSet`][RigidSet] is a fixed-capacity set. - [`struct UniqueDictionary`][UniqueDictionary] is a uniquely held, dynamically resizing dictionary. - [`struct RigidDictionary`][RigidDictionary] is a fixed-capacity dictionary. [RigidSet]: https://github.com/apple/swift-collections/tree/main/Sources/BasicContainers/RigidSet [UniqueSet]: https://github.com/apple/swift-collections/tree/main/Sources/BasicContainers/UniqueSet [RigidDictionary]: https://github.com/apple/swift-collections/tree/main/Sources/BasicContainers/RigidDictionary [UniqueDictionary]: https://github.com/apple/swift-collections/tree/main/Sources/BasicContainers/UniqueDictionary 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 This trait enables the following types in the [`SortedCollections`][SortedCollections] module: - [`struct SortedSet`][SortedSet] is a set type that requires its element to be `Comparable`, and keeps its members sorted in strictly increasing order. - [`struct SortedDictionary`][SortedDictionary] is a dictionary type that always keeps its keys sorted in strictly increasing order. [SortedCollections]: https://github.com/apple/swift-collections/tree/main/Sources/SortedCollections [SortedSet]: https://github.com/apple/swift-collections/tree/main/Sources/SortedCollections/SortedSet [SortedDictionary]: https://github.com/apple/swift-collections/tree/main/Sources/SortedCollections/SortedDictionary 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 The Swift Collections package is source-stable. The version numbers follow [Semantic Versioning][semver] -- source breaking changes to public API can only land in a new major version. [semver]: https://semver.org ### Definition of Public API 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][enhancement] 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 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: | Package version | Swift version | Xcode release | | ----------------------- | --------------- | ------------- | | swift-collections 1.0.x | >= Swift 5.3.2 | >= Xcode 12.4 | | swift-collections 1.1.x | >= Swift 5.7.2 | >= Xcode 14.2 | | swift-collections 1.2.x | >= Swift 5.10.0 | >= Xcode 15.3 | | swift-collections 1.3.x | >= Swift 6.0.3 | >= Xcode 16.2 | | swift-collections 1.4.x | >= Swift 6.0.3 | >= Xcode 16.2 | | swift-collections 1.5.x | >= Swift 6.0.3 | >= Xcode 16.2 | | swift-collections 1.6.x | >= Swift 6.0.3 | >= Xcode 16.2 | 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 To use this package in a SwiftPM project, you need to set it up as a package dependency: ```swift // 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 We have a dedicated [Swift Collections Forum][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. [forum]: https://forums.swift.org/c/related-projects/collections If you find something that looks like a bug, please open a [Bug Report][bugreport]! Fill out as many details as you can. ### Branching Strategy We maintain separate branches for each minor version of the package: | Package version | Branch | Status | | ----------------------- | ----------- | -------- | | swift-collections 1.0.x | release/1.0 | Obsolete, closed| | swift-collections 1.1.x | release/1.1 | Obsolete, closed| | swift-collections 1.2.x | release/1.2 | Obsolete, closed| | swift-collections 1.3.x | release/1.3 | Bugfixes only| | swift-collections 1.4.x | | Bugfixes only | | swift-collections 1.5.x | | Bugfixes only | | swift-collections 1.6.x | | Bugfixes only | | n.a. | main | Feature work towards next minor release | 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 We have some basic [documentation on package internals](./Documentation/Internals/README.md) 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](https://swift.org/LICENSE.txt), a copy of which is [provided in this repository](LICENSE.txt). #### 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][PR] with your change. If there is an [existing issue][issues] for the bug you're fixing, please include a reference to it. 3. Make sure to add tests covering whatever changes you are making. [PR]: https://github.com/apple/swift-collections/compare [issues]: https://github.com/apple/swift-collections/issues [bugreport]: https://github.com/apple/swift-collections/issues/new?assignees=&labels=bug&template=BUG_REPORT.md #### Proposing a small enhancement 1. Raise a [Feature Request][enhancement]. 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! [enhancement]: https://github.com/apple/swift-collections/issues/new?assignees=&labels=enhancement&template=FEATURE_REQUEST.md #### 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 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](https://swift.org/code-of-conduct/). A copy of this document is [available in this repository][coc]. [coc]: CODE_OF_CONDUCT.md ## Contact information The current code owner of this package is Karoy Lorentey ([@lorentey](https://github.com/lorentey)). You can contact him [on the Swift forums](https://forums.swift.org/u/lorentey/summary), 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](https://swift.org/community/#community-structure). --- ## File: Documentation/Announcement-benchmarks/README.md # 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][announcement]. * [`generate-results.sh`](./generate-results.sh): A script that you can use to run the benchmark on your own machine, and to reproduce the charts. * [`Library.json`](./Library.json): The benchmark library definition collecting the chart definitions used in the blog post. * [`Theme.json`](./Theme.json): The chart theme to set up colors, line widths, font sizes etc. (Slightly adapted.) * [`Results.md`](./Results.md): The generated results summary. * [`Results/`](./Results/): The generated subdirectory containing the PNG files for the charts. * [`results.json`](./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][swift-collections-benchmark]. [announcement]: https://swift.org/blog/swift-collections [swift-collections-benchmark]: https://github.com/apple/swift-collections-benchmark --- ## File: Documentation/Announcement-benchmarks/Results.md # 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 # Package Internals ## Benchmarks The package includes an extensive library of benchmarks in the [Benchmarks](../../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**][swift-collections-benchmark]. [swift-collections-benchmark]: https://github.com/apple/swift-collections-benchmark ## Test Support Library The package comes with a rich test support library in the [Tests/_CollectionsTestSupport](../../Tests/_CollectionsTestSupport) directory. These were loosely adapted from the contents of the `StdlibUnittest*` modules in the [Swift compiler repository](https://github.com/apple/swift/tree/main/stdlib/private), 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`](../../Tests/_CollectionsTestSupport/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 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) } } } } ``` ``` 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 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`](../../Tests/_CollectionsTestSupport/AssertionContexts/Combinatorics.swift): 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 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`](../../Tests/_CollectionsTestSupport/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`](../../Tests/_CollectionsTestSupport/ConformanceCheckers/CheckSequence.swift) - [`Collection`](../../Tests/_CollectionsTestSupport/ConformanceCheckers/CheckCollection.swift) - [`BidirectionalCollection`](../../Tests/_CollectionsTestSupport/ConformanceCheckers/CheckBidirectionalCollection.swift) - [`Equatable`](../../Tests/_CollectionsTestSupport/ConformanceCheckers/CheckEquatable.swift) - [`Hashable`](../../Tests/_CollectionsTestSupport/ConformanceCheckers/CheckHashable.swift) - [`Comparable`](../../Tests/_CollectionsTestSupport/ConformanceCheckers/CheckComparable.swift) - [`MinimalTypes`](../../Tests/_CollectionsTestSupport/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`](../../Tests/_CollectionsTestSupport/MinimalTypes/MinimalSequence.swift) - [`MinimalCollection`](../../Tests/_CollectionsTestSupport/MinimalTypes/MinimalCollection.swift) - [`MinimalBidirectionalCollection`](../../Tests/_CollectionsTestSupport/MinimalTypes/MinimalBidirectionalCollection.swift) - [`MinimalRandomAccessCollection`](../../Tests/_CollectionsTestSupport/MinimalTypes/MinimalRandomAccessCollection.swift) - [`MinimalMutableRandomAccessCollection`](../../Tests/_CollectionsTestSupport/MinimalTypes/MinimalMutableRandomAccessCollection.swift) - [`MinimalRangeReplaceableRandomAccessCollection`](../../Tests/_CollectionsTestSupport/MinimalTypes/MinimalRangeReplaceableRandomAccessCollection.swift) - [`MinimalMutableRangeReplaceableRandomAccessCollection`](../../Tests/_CollectionsTestSupport/MinimalTypes/MinimalMutableRangeReplaceableRandomAccessCollection.swift) - [`MinimalIterator`](../../Tests/_CollectionsTestSupport/MinimalTypes/MinimalIterator.swift) - [`MinimalIndex`](../../Tests/_CollectionsTestSupport/MinimalTypes/MinimalIndex.swift) - [`MinimalEncoder`](../../Tests/_CollectionsTestSupport/MinimalTypes/MinimalEncoder.swift) - [`MinimalDecoder`](../../Tests/_CollectionsTestSupport/MinimalTypes/MinimalDecoder.swift) - [`Utilities`](../../Tests/_CollectionsTestSupport/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][asan] can be used to catch more serious problems.) [asan]: https://developer.apple.com/documentation/xcode/diagnosing_memory_thread_and_crash_issues_early?language=objc --- ## File: Documentation/Internals/ReleaseChecklist.md # 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](../../Utils/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](https://github.com/apple/swift-collections/issues/7). (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](../../Utils/run-full-tests.sh) 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](https://github.com/apple/swift-collections/releases/tag/0.0.7). 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](https://forums.swift.org/c/related-projects/collections/72), 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`](https://github.com/apple/swift/blob/main/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 # Shareable Hashed Collections Module - Authors: [Michael Steindorfer](https://github.com/msteindorfer), [Karoy Lorentey](https://forums.swift.org/u/lorentey) - Implementation: https://github.com/apple/swift-collections/tree/release/1.1/Sources/ShareableHashedCollections ## Table of contents * [Introduction](#introduction) * [Motivation](#motivation) * [Proposed solution](#proposed-solution) - [`ShareableSet`](#shareableset) - [`ShareableDictionary`](#shareabledictionary) * [Detailed design](#detailed-design) ## Introduction `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 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: ```swift 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: ```swift 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 We propose to introduce a new Swift Collections module, called `ShareableHashedCollections`, with two top-level public types, `ShareableSet` and `ShareableDictionary`. ### `ShareableSet` `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`: ```swift struct ShareableSet : 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 ```swift init() init(S) init(`Self`) init(ShareableDictionary.Keys) ``` #### Finding Elements ```swift func contains(Element) -> Bool func firstIndex(of: Element) -> Index? func lastIndex(of: Element) -> Index? ``` #### Adding and Updating Elements ```swift mutating func insert(Element) -> (inserted: Bool, memberAfterInsert: Element) mutating func update(with: Element) -> Element? mutating func update(Element, at: Index) -> Element ``` #### Removing Elements ```swift mutating func remove(Element) -> Element? mutating func remove(at: Index) -> Element func filter((Element) throws -> Bool) rethrows -> ShareableSet 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. ```swift func intersection(`Self`) -> ShareableSet func intersection(ShareableDictionary.Keys) -> ShareableSet func intersection(S) -> ShareableSet func union(`Self`) -> ShareableSet func union(ShareableDictionary.Keys) -> ShareableSet func union(S) -> ShareableSet func subtracting(`Self`) -> ShareableSet func subtracting(ShareableDictionary.Keys) -> ShareableSet func subtracting(S) -> ShareableSet func symmetricDifference(`Self`) -> ShareableSet func symmetricDifference(ShareableDictionary.Keys) -> ShareableSet func symmetricDifference(S) -> ShareableSet mutating func formIntersection(`Self`) mutating func formIntersection(ShareableDictionary.Keys) mutating func formIntersection(S) mutating func formUnion(`Self`) mutating func formUnion(ShareableDictionary.Keys) mutating func formUnion(S) mutating func subtract(`Self`) mutating func subtract(ShareableDictionary.Keys) mutating func subtract(S) mutating func formSymmetricDifference(`Self`) mutating func formSymmetricDifference(ShareableDictionary.Keys) mutating func formSymmetricDifference(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). ```swift static func == (`Self`, `Self`) -> Bool func isEqualSet(to: `Self`) -> Bool func isEqualSet(to: ShareableDictionary.Keys) -> Bool func isEqualSet(to: S) -> Bool func isSubset(of: `Self`) -> Bool func isSubset(of: ShareableDictionary.Keys) -> Bool func isSubset(of: S) -> Bool func isSuperset(of: `Self`) -> Bool func isSuperset(of: ShareableDictionary.Keys) -> Bool func isSuperset(of: S) -> Bool func isStrictSubset(of: `Self`) -> Bool func isStrictSubset(of: ShareableDictionary.Keys) -> Bool func isStrictSubset(of: S) -> Bool func isStrictSuperset(of: `Self`) -> Bool func isStrictSuperset(of: ShareableDictionary.Keys) -> Bool func isStrictSuperset(of: S) -> Bool func isDisjoint(with: `Self`) -> Bool func isDisjoint(with: ShareableDictionary.Keys) -> Bool func isDisjoint(with: S) -> Bool ``` ### `ShareableDictionary` `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. ```swift struct ShareableDictionary : 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`. ```swift ShareableDictionary.Keys ShareableDictionary.Values var keys: Keys var values: Values extension ShareableDictionary.Keys { func contains(Element) -> Bool func intersection(ShareableSet) -> Self func intersection(ShareableDictionary.Keys) -> Self func subtracting(ShareableSet) -> Self func subtracting(ShareableDictionary.Keys) -> Self } ``` #### Creating a Dictionary ```swift init() init(ShareableDictionary) init(Dictionary) init(uniqueKeysWithValues: S) init(S, uniquingKeysWith: (Value, Value) throws -> Value) rethrows init(grouping: S, by: (S.Element) throws -> Key) rethrows init(keys: ShareableSet, valueGenerator: (Key) throws -> Value) rethrows ``` #### Inspecting a Dictionary ```swift var isEmpty: Bool var count: Int ``` #### Accessing Keys and Values ```swift 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. ```swift mutating func updateValue(Value, forKey: Key) -> Value? mutating func updateValue(forKey: Key, with: (inout Value?) throws -> R) rethrows -> R mutating func updateValue(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, uniquingKeysWith: (Value, Value) throws -> Value) rethrows func merging(`Self`, uniquingKeysWith: (Value, Value) throws -> Value) rethrows -> ShareableDictionary func merging(S, uniquingKeysWith: (Value, Value) throws -> Value) rethrows -> ShareableDictionary ``` #### Removing Keys and Values ```swift mutating func removeValue(forKey: Key) -> Value? mutating func remove(at: Index) -> Element func filter((Element) throws -> Bool) rethrows -> ShareableDictionary mutating func removeAll(where shouldBeRemoved: (Element) throws -> Bool) rethrows ``` #### Comparing Dictionaries ```swift static func == (`Self`, `Self`) -> Bool ``` #### Transforming a Dictionary ```swift func mapValues((Value) throws -> T) rethrows -> ShareableDictionary func compactMapValues((Value) throws -> T?) rethrows -> ShareableDictionary ``` ## Detailed design 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/](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](https://github.com/apple/swift-collections/tree/release/1.1/Sources/ShareableHashedCollections) ## Alternatives Considered ### Naming 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 # Deque A collection implementing a double-ended queue. ## Declaration ```swift import DequeModule @frozen struct Deque ``` ## Overview `Deque` (pronounced "deck") implements an ordered random-access collection that supports efficient insertions and removals from both ends. ```swift 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: ```swift 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: ```swift 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: ```swift 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 # Heap A partially-ordered tree of elements with performant insertion and removal operations. ## Declaration ```swift public struct Heap ``` ## Overview Array-backed [binary heaps](https://en.wikipedia.org/wiki/Heap_(data_structure)) 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](https://en.wikipedia.org/wiki/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 There are a couple of options for initializing a `Heap`. To create an empty `Heap`, call `init()`: ```swift var heap = Heap() ``` You can also create a `Heap` from an existing sequence in linear time: ```swift var heap = Heap((1...).prefix(20)) ``` Finally, a `Heap` can be created from an array literal: ```swift var heap: Heap = [0.1, 0.6, 1.0, 0.15, 0.42] ``` ### Insertion #### Of a single element To insert an element into a `Heap`, call `insert(_:)`: ```swift 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`: ```swift var heap = Heap(0 ..< 10) heap.insert(contentsOf: (20 ... 100).shuffled()) heap.insert(contentsOf: [-5, -6, -8, -12, -3]) ``` ### Lookup As mentioned earlier, the smallest and largest elements can be queried in constant time: ```swift 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. ```swift 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 Removal has logarithmic complexity, and removing both the smallest and largest elements is supported: ```swift 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 `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 | Operation | Complexity | |-----------|------------| | Insert | O(log n) | | Get smallest element | O(1) | | Get largest element | O(1) | | Remove smallest element | O(log n) | | Remove largest element | O(log n) | 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 The implementation is based on the min-max heap data structure as introduced by [Atkinson et al. 1986]. [Atkinson et al. 1986]: https://doi.org/10.1145/6617.6621 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](https://doi.org/10.1145/6617.6621) --- ## File: Documentation/OrderedDictionary.md # `OrderedDictionary` An ordered collection of key-value pairs. ## Declaration ```swift import OrderedCollections @frozen struct OrderedDictionary ``` ## Overview 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. ```swift let responses: OrderedDictionary = [ 200: "OK", 403: "Access forbidden", 404: "File not found", 500: "Internal server error", ] ``` ### Equality of Ordered Dictionaries 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`. ```swift 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 `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: ```swift var dictionary: OrderedDictionary = [:] 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: ```swift let text = "short string" var counts: OrderedDictionary = [:] 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. ```swift let text = "short string" var counts: OrderedDictionary = [:] 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 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: ```swift 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: ```swift // 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(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 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`, containing all the keys in the original dictionary. ```swift 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: ```swift 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 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 An ordered dictionary consists of an ordered set of keys, alongside a regular `Array` value that contains their associated values. --- ## File: Documentation/OrderedSet.md # OrderedSet An ordered collection of unique elements. ## Declaration ```swift import OrderedCollections @frozen struct OrderedSet ``` ## Overview 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. ```swift let buildingMaterials: OrderedSet = ["straw", "sticks", "bricks"] ``` ### Equality of Ordered Sets 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`. ```swift 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 `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:)`. ```swift 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: ```swift 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: ```swift 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 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. ```swift var a: OrderedSet = [0, 1, 2, 3] let b: OrderedSet = [3, 2, 1, 0] a == b // false a.unordered == b.unordered // true func frobnicate(_ set: S) { ... } frobnicate(a) // error: `OrderedSet` 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. ```swift 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 Ordered sets are random-access collections. Members are assigned integer indices, with the first element always being at index `0`: ```swift 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: ```swift // 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(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 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. ```swift 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 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 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.)