swift-collections

Commonly used data structures for Swift

4,394

372

4,394

View on GitHub

Top Related Projects

mimalloc

13,177

mimalloc is a compact general purpose allocator with excellent performance.

Hoard

1,217

The Hoard Memory Allocator: A Fast, Scalable, and Memory-efficient Malloc for Linux, Windows, and Mac.

rpmalloc

2,473

Public domain cross platform lock free thread caching 16-byte aligned memory allocator implemented in C

Quick Overview

Swift Collections is an open-source package that provides data structure implementations for the Swift programming language. It offers a set of efficient, performant, and thread-safe collection types that extend the capabilities of the Swift standard library.

Pros

Provides additional collection types not available in the Swift standard library
Highly optimized for performance and memory efficiency
Well-documented and maintained by the Swift core team
Designed with thread-safety in mind

Cons

Requires Swift 5.3 or later, which may limit compatibility with older projects
Some collection types may have a steeper learning curve compared to standard library collections
As a separate package, it adds an extra dependency to projects

Code Examples

Using OrderedSet:

import OrderedCollections

var orderedSet = OrderedSet<String>()
orderedSet.append("apple")
orderedSet.append("banana")
orderedSet.append("apple") // Duplicate, won't be added

print(orderedSet) // ["apple", "banana"]

Using Deque:

import DequeModule

var deque = Deque<Int>()
deque.append(1)
deque.prepend(0)
deque.append(2)

print(deque) // [0, 1, 2]
print(deque.popFirst()) // Optional(0)
print(deque.popLast()) // Optional(2)

Using OrderedDictionary:

import OrderedCollections

var orderedDict = OrderedDictionary<String, Int>()
orderedDict["one"] = 1
orderedDict["two"] = 2
orderedDict["three"] = 3

for (key, value) in orderedDict {
    print("\(key): \(value)")
}
// Prints:
// one: 1
// two: 2
// three: 3

Getting Started

To use Swift Collections in your project, add it as a dependency in your Package.swift file:

dependencies: [
    .package(url: "https://github.com/apple/swift-collections.git", from: "1.0.0")
]

Then, add the specific module you want to use as a dependency to your target:

targets: [
    .target(
        name: "YourTarget",
        dependencies: [
            .product(name: "OrderedCollections", package: "swift-collections"),
            .product(name: "DequeModule", package: "swift-collections")
        ]
    )
]

Finally, import the desired module in your Swift file:

import OrderedCollections
import DequeModule

You can now use the additional collection types provided by Swift Collections in your code.

Competitor Comparisons

mimalloc

13,177

mimalloc is a compact general purpose allocator with excellent performance.

Pros of mimalloc

Highly performant general-purpose allocator, optimized for multi-threaded applications
Cross-platform support (Windows, macOS, Linux, etc.)
Extensive benchmarking and performance analysis tools included

Cons of mimalloc

Focused solely on memory allocation, not a collection of data structures
May require more integration effort for specific use cases
C/C++ based, potentially less idiomatic for Swift developers

Code Comparison

mimalloc:

#include <mimalloc.h>
void* p = mi_malloc(sizeof(int));
mi_free(p);

swift-collections:

import Collections
var deque = Deque<Int>()
deque.append(42)

Key Differences

mimalloc is a memory allocator library, while swift-collections is a collection of data structures for Swift. mimalloc focuses on efficient memory management, whereas swift-collections provides ready-to-use data structures like deques, ordered sets, and ordered dictionaries.

mimalloc is language-agnostic and can be used in various programming environments, while swift-collections is specifically designed for Swift developers and integrates seamlessly with the Swift ecosystem.

The choice between these libraries depends on the specific needs of your project: low-level memory management (mimalloc) or high-level data structure implementations (swift-collections).

Hoard

1,217

The Hoard Memory Allocator: A Fast, Scalable, and Memory-efficient Malloc for Linux, Windows, and Mac.

Pros of Hoard

Designed for multi-threaded applications, offering better performance in concurrent scenarios
Language-agnostic, can be used with C, C++, and other languages that can interface with C
Focuses on memory allocation efficiency, which can lead to improved overall application performance

Cons of Hoard

Less integrated with Swift ecosystem compared to Swift Collections
May require more manual memory management and careful usage
Not specifically optimized for Swift's memory model and language features

Code Comparison

Swift Collections (OrderedSet):

var set = OrderedSet(["a", "b", "c"])
set.append("d")
set.remove("b")

Hoard (C++ usage example):

#include <hoard.h>
void* ptr = hoard_malloc(sizeof(int));
// Use the allocated memory
hoard_free(ptr);

Key Differences

Swift Collections provides high-level data structures for Swift, while Hoard focuses on low-level memory allocation
Swift Collections is tailored for Swift development, whereas Hoard is more general-purpose
Hoard requires explicit memory management, while Swift Collections leverages Swift's automatic memory management

Use Cases

Swift Collections: Ideal for Swift projects requiring efficient, Swift-native data structures
Hoard: Suitable for multi-threaded applications with intensive memory allocation needs, especially in C/C++ environments

rpmalloc

2,473

Public domain cross platform lock free thread caching 16-byte aligned memory allocator implemented in C

Pros of rpmalloc

Focused on high-performance memory allocation
Language-agnostic, can be used in C/C++ projects
Designed for multi-threaded applications

Cons of rpmalloc

Limited to memory allocation, not a general-purpose collection library
May require more manual memory management
Less integrated with Swift ecosystem

Code Comparison

swift-collections:

var deque = Deque<Int>()
deque.append(1)
deque.prepend(0)
let first = deque.popFirst()
let last = deque.popLast()

rpmalloc:

void* ptr = rpmalloc(size);
// Use the allocated memory
rpfree(ptr);

Summary

swift-collections is a Swift-specific library providing various collection types, while rpmalloc is a C library focused on efficient memory allocation. swift-collections offers higher-level abstractions and is more integrated with Swift, whereas rpmalloc provides low-level memory management across different languages. The choice between them depends on the specific needs of the project, programming language, and whether high-performance memory allocation or diverse collection types are more critical.

jemalloc

11,003

Pros of jemalloc

Widely used and battle-tested memory allocator for large-scale applications
Optimized for multi-threaded performance and reduced fragmentation
Language-agnostic, can be used with various programming languages

Cons of jemalloc

More complex to integrate and configure compared to Swift Collections
Not specifically designed for Swift or Apple ecosystem
May require additional setup and tuning for optimal performance

Code Comparison

jemalloc:

#include <jemalloc/jemalloc.h>

void *ptr = malloc(size);
// Use ptr
free(ptr);

Swift Collections:

import Collections

var deque = Deque<Int>()
deque.append(1)
deque.prepend(0)

Summary

jemalloc is a general-purpose memory allocator focused on efficiency and scalability, while Swift Collections provides specialized data structures for Swift. jemalloc offers broader language support and is well-suited for large-scale applications, but may require more setup. Swift Collections integrates seamlessly with Swift and the Apple ecosystem, offering easy-to-use, performant data structures tailored for Swift developers. The choice between them depends on the specific project requirements, language preferences, and performance needs.

tcmalloc

5,224

Pros of tcmalloc

Highly optimized memory allocator for C++ applications
Designed for multi-threaded environments, reducing contention
Provides detailed heap profiling and memory usage statistics

Cons of tcmalloc

Limited to C++ applications, while swift-collections is Swift-specific
May require more setup and integration compared to swift-collections
Not directly applicable to Swift development ecosystems

Code Comparison

tcmalloc (C++):

#include <tcmalloc/tcmalloc.h>

void* ptr = tc_malloc(size);
tc_free(ptr);

swift-collections (Swift):

import Collections

var deque = Deque<Int>()
deque.append(1)
deque.prepend(0)

Summary

tcmalloc is a specialized memory allocator for C++ applications, offering high performance and detailed profiling. swift-collections provides efficient data structures for Swift, focusing on language-specific optimizations. While tcmalloc excels in C++ environments, swift-collections is better suited for Swift development. The choice between them depends on the programming language and specific project requirements.

Convert designs to code with AI

Introducing Visual Copilot: A new AI model to turn Figma designs to high quality code using your components.

Try Visual Copilot

README

Swift Collections

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

Stable Data Structures
Experimental Features
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
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

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

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

Experimental Features

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

struct InputSpan<Element> is a reference to a contiguous region of consumable items.
struct Ref<Target> represents a borrowing reference to an item.
struct MutableRef<Target> represents a mutating reference to an item.
protocol BorrowingSequence<Element> models borrowing sequences with ephemeral lifetimes.
protocol BorrowingIteratorProtocol<Element> models borrowing iterators with ephemeral elements.
protocol Container<Element> models containers, or constructs that physically store their contents.
protocol BidirectionalContainer<Element> is the container analogue of BidirectionalCollection.
protocol RandomAccessContainer<Element> is the container analogue of RandomAccessCollection.
protocol PermutableContainer<Element> models a container that allows items to be arbitrarily reordered (sorted, reversed, etc).
protocol MutableContainer<Element> refines PermutableContainer to also support arbitrary element replacements/mutations, like MutableCollection.
protocol RangeReplaceableContainer<Element> models a (potentially fixed capacity) container with insert/append/replace operations.
protocol DynamicContainer<Element> refines RangeReplaceableContainer to add operations that require dynamic storage sizing.
protocol Producer<Element, Failure> models a generative iterator -- an abstraction for producing items on demand.
protocol Drain<Element> refines Producer to model a source of in-place consumable elements -- primarily for use around container types.

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

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

`UnstableHashedContainers` package trait

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

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

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

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

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

`UnstableSortedCollections` package trait

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.5 of the swift-collections package consists of non-underscored declarations that are marked public in the Collections, BasicContainers, BitCollections, ContainersPreview, DequeModule, HashTreeCollections, HeapModule, OrderedCollections, and TrailingElementsModule modules.

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

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

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

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

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

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

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

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

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

Minimum Required Swift Toolchain Version

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

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

let package = Package(
  name: "MyPackage",
  dependencies: [
    .package(
      url: "https://github.com/apple/swift-collections.git",
      .upToNextMinor(from: "1.5.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
swift-collections 1.1.x	release/1.1	Obsolete
swift-collections 1.2.x	release/1.2	Obsolete
swift-collections 1.3.x	release/1.3	Bugfixes only
swift-collections 1.4.x	release/1.4	Bugfixes only
swift-collections 1.5.x	release/1.5	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

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

Proposing a small enhancement

Raise a Feature Request. Discuss why it would be important to implement it.
Submit a PR with your implementation, and participate in the review discussion.
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.
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

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

Contact information

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

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

Top Related Projects

Convert designs to code with AI

Introducing Visual Copilot: A new AI model to turn Figma designs to high quality code using your components.

Try Visual Copilot

Top Related Projects

Quick Overview

Pros

Cons

Code Examples

Getting Started

Competitor Comparisons

Pros of mimalloc

Cons of mimalloc

Code Comparison

Key Differences

Pros of Hoard

Cons of Hoard

Code Comparison

Key Differences

Use Cases

Pros of rpmalloc

Cons of rpmalloc

Code Comparison

Summary

Pros of jemalloc

Cons of jemalloc

Code Comparison

Summary

Pros of tcmalloc

Cons of tcmalloc

Code Comparison

Summary

Convert designs to code with AI

README

Swift Collections

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

Top Related Projects

Convert designs to code with AI

`BasicContainers` module

`DequeModule` module

`OrderedCollections` module

`BitCollections` module

`HeapModule` module

`HashTreeCollections` module

`TrailingElementsModule` module

`ContainersPreview` module

`Collections` module

`UnstableContainersPreview` package trait

`UnstableHashedContainers` package trait

`UnstableSortedCollections` package trait