repository·main·Indexed 26 days ago
https://github.com/apple/swift-collectionsAn open-source package providing high-performance, specialized data structure implementations for Swift. It includes stable modules for Deques, OrderedSet, OrderedDictionary, BitSet, BitArray, Heap, and persistent hashed collections (TreeSet, TreeDictionary). The library also offers ownership-aware containers for systems programming and experimental features gated behind package traits such as UnstableContainersPreview, UnstableHashedContainers, and UnstableSortedCollections.
HashTreeCollections is a component of the Swift Collections package that provides persistent data structures. Specifically, it includes implementations for TreeSet and TreeDictionary, which are designed for functional-style, persistent collection usage.OrderedCollections is a component of the Swift Collections open-source package. It provides specialized data structures that maintain element order while offering efficient lookups, specifically OrderedSet and OrderedDictionary.Swift Collections is an open-source package providing specialized data structure implementations. The package is organized into several modules based on use cases:
UniqueArray and RigidArray, which are noncopyable array variants designed for more predictable performance compared to the standard Array.BitSet and BitArray for dynamic bit-level collections.Deque<Element>, a double-ended queue implemented via a ring buffer. It supports range-replacement, mutation, and random access.Heap, a min-max heap backed by an array, ideal for priority queue implementations.OrderedSet<Element> (an ordered variant of Set) and OrderedDictionary<Key, Value> (an ordered variant of Dictionary). These maintain a well-defined order of elements.TreeSet and TreeDictionary, which are persistent hashed collections using Compressed Hash-Array Mapped Prefix Trees (CHAMP). These are optimized for scenarios involving mutations of shared copies.TrailingArray, a low-level ManagedBuffer variant designed for interoperability with C constructs using fixed-size headers followed by variable-size storage.BitCollections module provides specialized bit-oriented data structures for the Swift programming language. It currently includes implementations for BitSet and BitArray.Swift Collections provides several specialized data structure implementations organized into thematic modules. These include:
UniqueArray<Element> and RigidArray<Element>.Deque<Element> (copy-on-write), UniqueDeque<Element> (noncopyable), and RigidDeque<Element> (fixed-capacity).Set and Dictionary that preserve insertion order, specifically OrderedSet<Element> and OrderedDictionary<Key, Value>.BitSet (for Set<Int>) and BitArray (for Array<Bool>).Heap<Element>) suitable for priority queues.TreeSet<Element> and TreeDictionary<Key, Value> for efficient mutations of shared copies.TrailingArray, TrailingPadding<Header>, and the TrailingElements protocol.UnstableContainersPreview trait), featuring UniqueBox<Value>.Collections, these containers are optimized for environments with strict performance constraints and can handle types that cannot be copied or escaped.The Container protocol is an ownership-aware analogue of Collection. It represents a type that physically holds its contents in memory, making them directly accessible. Unlike Iterable types that might generate items on demand (generative iteration), Container types are restricted to visitative semantics, meaning elements must pre-exist in the container.
Key characteristics:
count must be returned in $O(1)$ complexity.Failure is required to be Never because elements are pre-existing and always accessible.Iterable: All Iterable algorithms work with Container types.The Swift Collections library uses an ownership-aware container model designed to support noncopyable elements and improve performance through bulk iteration. The design space is defined by four axes:
Elementwise vs. Bulk Iteration:
Sequence): Exposes one element at a time via next(). Simple but can be slow due to frequent protocol entry points.Iterable, Container): Exposes multiple elements at once using a Span. This is more efficient for piecewise contiguous storage.Borrowing vs. Taking Elements:
Iterable): Clients receive temporary, read-only access to elements. The container retains ownership.Producer): Clients receive full ownership of the elements, which is necessary for noncopyable types if you want to move them out of a container.Generative vs. Visitative Iteration:
Iterable): Elements are materialized on the fly (e.g., a String's Characters). Elements may "evaporate" once the iterator advances.Container): Elements already exist in memory. Clients can safely hold references to them as long as the container isn't mutated.Failable vs. Non-failable Iteration:
Iterable): Iteration can throw errors (using typed throws). This is common for generative processes.Container): Iteration cannot throw, as visiting existing memory is assumed to be safe.An OrderedSet is a collection of unique elements that maintains a specific user-specified order and supports efficient random-access traversal. It is a suitable alternative to Set when order matters, or to Array when you need uniqueness and fast membership testing.
To use OrderedSet, import OrderedCollections and ensure your element type conforms to Hashable.
import OrderedCollections
let buildingMaterials: OrderedSet = ["straw", "sticks", "bricks"]The OrderedCollections module provides two primary data structures:
OrderedSet: A collection of unique elements that maintains a stable order.OrderedDictionary: A collection of key-value pairs that maintains a stable order of keys.The ShareableHashedCollections module provides ShareableSet and ShareableDictionary. These are tree-based, unordered collections that use a prefix tree structure based on hash values.
Unlike standard Set and Dictionary which use all-or-nothing copy-on-write (requiring a full copy of the storage upon the first mutation of a shared instance), ShareableSet and ShareableDictionary allow mutated copies to share as much of their structure as possible. This results in:
subtracting) because shared subtrees can be skipped during comparison.Use these types when your application frequently takes snapshots of collections and performs mutations or diffing operations on those snapshots.
The swift-collections package is source-stable and follows Semantic Versioning.
The stable public API consists of non-underscored declarations marked public within the following modules:
CollectionsBasicContainersBitCollectionsContainersPreviewDequeModuleHashTreeCollectionsHeapModuleOrderedCollectionsTrailingElementsModuleDo not rely on the following, as they may change or be removed in any release:
_someMember, _Bar, _FooModule).UnstableContainersPreview, UnstableHashedContainers, or UnstableSortedCollections package traits.SortedCollections and _RopeModule are currently unstable.