swift-collections

Commonly used data structures for Swift

3,679

282

3,679

View on GitHub

Top Related Projects

mimalloc

10,496

mimalloc is a compact general purpose allocator with excellent performance.

Hoard

1,093

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

rpmalloc

2,143

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

10,496

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

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

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

9,465

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

4,311

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.

Read more about the package, and the intent behind it, in the announcement on swift.org.

The package currently provides the following implementations:

BitSet and BitArray, dynamic bit collections.
Deque<Element>, a double-ended queue backed by a ring buffer. Deques are range-replaceable, mutable, random-access collections.
Heap, a min-max heap backed by an array, suitable for use as a priority queue.
OrderedSet<Element>, a variant of the standard Set where the order of items is well-defined and items can be arbitrarily reordered. Uses a ContiguousArray as its backing store, augmented by a separate hash table of bit packed offsets into it.
OrderedDictionary<Key, Value>, an ordered variant of the standard Dictionary, providing similar benefits.
TreeSet and TreeDictionary, persistent hashed collections implementing Compressed Hash-Array Mapped Prefix Trees (CHAMP). These work similar to the standard Set and Dictionary, but they excel at use cases that mutate shared copies, offering dramatic memory savings and radical time improvements.

The following additional data structures are currently under development but they aren't stable enough to preview yet.

SortedSet and SortedDictionary, sorted collections backed by in-memory persistent b-trees.
SparseSet, a constant time set construct, trading off memory for speed.

Swift Collections uses the same modularization approach as Swift Numerics: it provides a standalone module for each thematic group of data structures it implements. For instance, if you only need a double-ended queue type, you can pull in only that by importing DequeModule. OrderedSet and OrderedDictionary share much of the same underlying implementation, so they are provided by a single module, called OrderedCollections. However, there is also a top-level Collections module that gives you every collection type with a single import statement:

import Collections

var deque: Deque<String> = ["Ted", "Rebecca"]
deque.prepend("Keeley")
deque.append("Nathan")
print(deque) // ["Keeley", "Ted", "Rebecca", "Nathan"]

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.

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

Interfaces that aren't part of the public API may continue to change in any release, including patch releases. If you have a use case that requires using underscored 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.

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)

Note that contents of the Tests, Utils and Benchmarks subdirectories aren't public API. We don't make any source compatibility promises about them -- they may change at whim, and code may be removed in any new release. Do not rely on anything about them.

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

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

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

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:5.9
import PackageDescription

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

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.0 â release/1.1 â main

For example, anything landing on release/1.0 will eventually appear on release/1.1 and then main too; there is no need to file standalone PRs for each release line. (Change propagation 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, 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

We intend this package to collect generally useful data structures -- the ones that ought to be within easy reach of every Swift engineer's basic toolbox. The implementations we ship need to be of the highest technical quality, polished to the same shine as anything that gets included in the Swift Standard Library. (The only real differences are that this package isn't under the formal Swift Evolution process, and its code isn't ABI stable.)

Accordingly, adding a new data structure to this package is not an easy or quick process, and not all useful data structures are going to be a good fit.

If you have an idea for a data structure that might make a good addition to this package, please start a topic on the forum, explaining why you believe it would be important to implement it. This way we can figure out if it would be right for the package, discuss implementation strategies, and plan to allocate capacity to help.

Not all data structures will reach a high enough level of usefulness to ship in this package -- those that have a more limited audience might work better as a standalone package. Of course, reasonable people might disagree on the importance of including any particular data structure; but at the end of the day, the decision whether to take an implementation is up to the maintainers of this package.

If maintainers have agreed that your implementation would likely make a good addition, then it's time to start work on it. Submit a PR with your implementation as soon as you have something that's ready to show! We'd love to get involved as early as you like. Historically, the best additions resulted from close work between the contributor and a package maintainer.

Participate in the review discussion, and adapt code accordingly. Sometimes we may need to go through several revisions over multiple months! This is fine -- it makes the end result that much better. When there is a consensus that the feature is ready, and the implementation is fully tested and documented, the PR will be merged by a maintainer. This is good time for a small celebration -- merging is a good indicator that the addition will ship at some point.

Historically, PRs adding a new data structure have typically been merged to a new feature branch rather than directly to a release branch or main, and there was an extended amount of time between the initial merge and the tag that shipped the new feature. Nobody likes to wait, but getting a new data structure implementation from a state that was ready to merge to a state that's ready to ship is actually quite difficult work, and it takes maintainer time and effort that needs to be scheduled in advance. The closer an implementation is to the coding conventions and performance baseline of the Standard Library, the shorter this wait is likely to become, and the fewer changes there will be between merging and shipping.

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

Contents

Project Status

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