Commonly used data structures for Swift
This feature release adds a number of new data structure implementations, along with minor changes to existing constructs.
Heap
implements a min-max heap, backed by a native array. (Contributed by @AquaGeek)BitSet
and BitArray
are two alternate representations of a bitmap type, backed by dynamically allocated storage. (Contributed by @MahanazAtiqullah)TreeSet
and TreeDictionary
are hashed collections implementing Compressed Hash-Array Mapped Prefix Trees (CHAMP). They provide similar API as Set
/Dictionary
in the Standard Library, but as persistent data structures, supporting incremental mutations of shared instances and efficient structural diffing. (Contributed by @msteindorfer)OrderedSet.isEqualSet
family of functions provide a way to test that two containers contain the same members, ignoring the order of elements. (https://github.com/apple/swift-collections/issues/183, https://github.com/apple/swift-collections/pull/234)OrderedSet.filter
implements a version of the standard filter operation that returns an OrderedSet
instead of an Array
. (https://github.com/apple/swift-collections/pull/159)debugDescription
implementations have been updated to follow Swift best practice. (These are called by container types like Array
to print their elements, so they work best when they're succinct variants of description
that are suitable for embedding in structured output: specifically, they must not produce unpaired delimiter characters ([
/]
, (
/)
, {
/}
, <
/>
etc), raw top level commas, semicolons, colons, unquoted strings etc. debugDescription
should not needlessly print type names etc.)Many thanks to our contributors for their great work (and patience)!
Full Changelog: https://github.com/apple/swift-collections/compare/1.0.6...1.1.0
subscript(offset:)
for now by @lorentey in https://github.com/apple/swift-collections/pull/92
release/1.0
into main
by @lorentey in https://github.com/apple/swift-collections/pull/108
Heap
hasn't been tagged yet & list other enhancements in progress by @lorentey in https://github.com/apple/swift-collections/pull/109
import Foundation
by @compnerd in https://github.com/apple/swift-collections/pull/118
ascending
and descending
views by @lorentey in https://github.com/apple/swift-collections/pull/119
release/1.0
to main
by @lorentey in https://github.com/apple/swift-collections/pull/141
PersistentSet
by @lorentey in https://github.com/apple/swift-collections/pull/193
PriorityQueueModule
to HeapModule
by @lorentey in https://github.com/apple/swift-collections/pull/194
mutating
keywords by @lorentey in https://github.com/apple/swift-collections/pull/238
Shareable
to Tree
by @lorentey in https://github.com/apple/swift-collections/pull/242
Sendable
conformance by @lorentey in https://github.com/apple/swift-collections/pull/271
self
doesn’t get destroyed before we’re done working with it by @lorentey in https://github.com/apple/swift-collections/pull/276
Rope.find
returns a bogus remainder for the end position by @lorentey in https://github.com/apple/swift-collections/pull/291
This bugfix release adds Sendable
conformances to all public types (fixing compatibility with Swift's strict concurrency checking), and speeds up equality checks (==
) of identical collection values.
Full Changelog: https://github.com/apple/swift-collections/compare/1.0.5...1.0.6
Thank you to everyone who contributed to this release!
This bugfix release improves compatibility with recent Swift versions, eliminating several compiler warnings on Swift 5.8 and 5.9. It contains no API-level changes.
Full Changelog: https://github.com/apple/swift-collections/compare/1.0.4...1.0.5
Thank you to everyone who contributed to this release!
This is a documentation update, including the addition of basic DocC documentation bundles. This release has no functional changes.
rethrows
position (by @ensan-hcl)Full Changelog: https://github.com/apple/swift-collections/compare/1.0.3...1.0.4
Thank you to everyone who contributed to this release! Your bug reports, discussions and pull requests all help improve this package.
This release resolves issues uncovered since 1.0.2 was tagged. The fixes improve performance of some operations, resolve compile-time issues and update documentation. This release contains no observable behavioral changes.
OrderedDictionary
's uniquing/unique/grouping initializers and merge operations no longer gets flagged as ambiguous in certain cases involving type inference. (#125, #139)OrderedCollections
module now make use of the stdlib's temporary allocation facility. (#160)filter
and merge
methods of OrderedDictionary
. (#145)Full Changelog: https://github.com/apple/swift-collections/compare/1.0.2...1.0.3
Thank you to everyone who contributed to this release! Your bug reports, discussions and pull requests all help improve this package.
This release resolves issues uncovered since 1.0.1 was tagged, including a high severity crash in OrderedSet
and OrderedDictionary
. Upgrading is recommended for all clients.
OrderedSet
and OrderedDictionary
that could result in some mutation methods corrupting shared copies of the same value, leading to subsequent crashes. (Issue #104)Deque.append(contentsOf:)
now uses an exponential storage resizing strategy, as expected. Calling it in a loop no longer results in O(n) reallocations. (Issue #113)Thank you to everyone who contributed to this release! Your bug reports, discussions and pull requests all help improve this package.
The CMake configuration now supports building the package for AArch64 Linux distributions, unblocking adoption in SPM.
(Note that the CMake configuration is intended only to support the use of this package from within Swift toolchain builds. It is provided as is, with no source compatibility guarantees.)
Minor documentation updates.
Thank you to everyone who contributed to this release! Your bug reports, discussions and pull requests all help improve this package.
This release marks an important milestone for this package -- the advent of source stability!
OrderedDictionary
methods that were deprecated in 0.0.7 are now marked unavailable.OrderedDictionary.init(uncheckedUniqueElements:)
no longer creates large dictionary instances without an associated hash table.Thank you to everyone who contributed to this release! Your bug reports, discussions and pull requests all help improve this package.
This release prepares for source stability by deprecating some OrderedDictionary APIs that we'd like to remove in version 1.0 of the package. (All deprecated names have reasonable replacements.)
The two OrderedDictionary.modifyValue
methods were renamed updateValue
, to better align with the standard updateValue
function (#90)
/* Old: */ d.modifyValue(forKey: key, default: []) { $0.append(newValue) }
/* New: */ d.updateValue(forKey: key, default: []) { $0.append(newValue) }
/* Old: */ d.modifyValue(forKey: key, insertingDefault: [], at: 0) { $0.append(newValue) }
/* New: */ d.updateValue(forKey: key, insertingDefault: [], at: 0) { $0.append(newValue) }
OrderedDictionary.subscript(offset:)
was removed; it used inconsistent terminology. To access a key-value pair at a given position, you can continue using the unlabeled subscript on the elements
view.
/* Deprecated: */ d[offset: 42]
/* Replacement: */ d.element[42]
The collections benchmarks were moved to a standalone nested package in a subdirectory of the repository, allowing the top-level package manifest to stop declaring a dependency on swift-collections-benchmark. This will make it easier to add Swift Collections as a dependency, especially in projects such as the Package Manager (or the benchmarking tool itself).
The old names for removed/renamed APIs are still available as deprecated members -- these will be removed in the 1.0 release.
subscript(offset:)
for now (by @lorentey)Thank you to everyone who contributed to this release! Your bug reports, discussions and pull requests all help improve this package.
This release consists of an update to the CMake config that is used during non-bootstrapped builds of the Swift toolchain. It contains no changes for package-based projects.
Thank you to everyone who contributed to this release! Your bug reports, discussions and pull requests all help improve this package.