Wednesday, February 14, 2024

Swift Collections 1.1

Karoy Lorentey (Mastodon):

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.
  • BitSet and BitArray are two alternate representations of a bitmap type, backed by dynamically allocated storage.
  • 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.

Michael Steindorfer has written a paper and thesis about CHAMP.


Update (2024-02-21): Majid Jabrayilov:

Dictionary and Set types that Swift language provides us store values in a single flat hash table that you copy on every write or mutation. The Swift Collection package introduces TreeDictionary and TreeSet types implementing Compressed Hash-Array Mapped Prefix Trees. In other words, TreeDictionary and TreeSet types hold values in the tree-based structure, allowing the efficient updating of only the needed branches.


The TreeDictionary is still a struct, but the implementation uses the UnsafeMutablePointer type to access memory and mutate it directly without copying on write. Another benefit of the TreeDictionary and TreeSet types is the optimized way to compare because of their tree-based nature. Usually, they handle this operation in a constant time.

Comments RSS · Twitter · Mastodon

Leave a Comment