swift-collections

Swift Collections

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

Table of Contents

• 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

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

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 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 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 module

Provides efficient implementations of bit maps.

• struct BitSet is a more efficient implementation of Set<Int>.
• struct BitArray is a more efficient implementation of Array<Bool>.

HeapModule module

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

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 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 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 module

This module makes the contents of the following modules available with a single import statement:

• BitCollections (struct BitArray and struct BitSet)
• DequeModule (struct Deque<Element>, struct RigidDeque<Element> and struct UniqueDeque<Element>)
• HeapModule (struct Heap<Element>)
• OrderedCollections (struct OrderedSet<Element> and struct OrderedDictionary<Key, Value>)
• HashTreeCollections (struct TreeSet<Element>, struct TreeDictionary<Key, Value>)

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 and SpanPreview modules:

• struct InputSpan<Element> (in SpanPreview) is a reference to a contiguous memory region of in-place consumable items.
• 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 DrainableContainer<Element> models a container that allows partial in-place consumption (and removal) of its contents.
• 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 CountedProducer<Element, Failure> refines Producer to add a precise count of remaining elements.
• protocol Drain<Element> refines CountedProducer to model a source of in-place consumable elements – primarily for use around container types.
• protocol ContainerDrain<Element> refines Drain to allow retrieving a valid index after the items have been drained.
• protocol RangeExpression2<Bound> refines the standard RangeExpression to support container subranges.

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 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 are kept unstable for now, as we expect we will 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 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

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

The public API of version 1.7 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, when they are built without any package traits.

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 SpanPreview, 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

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
swift-collections 1.7.x	>= Swift 6.2.4	>= Xcode 26.3

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.)

When deploying standalone macOS executables or frameworks built with Swift 6.2 or later to systems older than macOS 26, you may need to install Swift backdeployment libraries alongside your binaries. In particular, a binary that links to @rpath/libswiftCompatibilitySpan.dylib needs that library in a location covered by its runtime search paths. Xcode handles this for app bundles, but standalone binaries need their deployment process to provide it. See the maintainer’s deployment guidance for details.

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-tools-version:6.3
import PackageDescription

let package = Package(
  name: "MyPackage",
  dependencies: [
    .package(
      url: "https://github.com/apple/swift-collections.git",
      .upToNextMinor(from: "1.7.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 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

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	Obsolete, closed
swift-collections 1.4.x		Bugfixes only
swift-collections 1.5.x		Bugfixes only
swift-collections 1.6.x		Bugfixes only
swift-collections 1.7.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 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

We expect contributors to adhere to our Code of Conduct.

Contact information

The current maintainer 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.)