# Adding more data structures to the standard library

**URL:** <https://forums.swift.org/t/adding-more-data-structures-to-the-standard-library/23651>\
**Category:** Discussion\
**Created:** [April 25, 2019, 3:19am UTC](https://forums.swift.org/t/adding-more-data-structures-to-the-standard-library/23651 "2019-04-25T03:19:11Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![AlexanderM](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/alexanderm/32/9781_2.png) [@AlexanderM](https://forums.swift.org/u/AlexanderM)\
**Post date:** [April 25, 2019, 3:19am UTC](https://forums.swift.org/t/adding-more-data-structures-to-the-standard-library/23651/1 "2019-04-25T03:19:11Z")

</div>

I'm studying for job interviews for Swift positions by completing code problems. By far the most painful part of this preparation is the dismal state of data structures in Swift.

If I were programming in Java (which I _really_ rather wouldn't), I would have easy access to...

# Java's collections

### Sets

- Unordered sets (`HashSet`, `CopyOnWriteArraySet`, `EnumSet`)
- Insertion ordered sets (`LinkedHashSet`)
- Naturally ordered sets (`TreeSet`, `ConcurrentSkipListSet`)

### Maps ("Dictionaries" in Swift)

- Unordered dictionaries (`HashMap`, `WeakHashMap`, `IdentityHashMap`, `EnumMap`)
- Insertion ordered dictionaries (`LinkedHashMap`)
- Naturally ordered sets (`TreeMap`)

### Ordered collections

- Arrays (`ArrayList`, `LinkedList`, `Vector` (a synchronized array), `LinkedList`)
- Queues (`ArrayDeque`, `ConcurrentLinkedDeque`, `PriorityQueue`, `SyncrhonousQueue`, ArrayBlockingQueue`, `DelayQueue`, `LinkedBlockingQueue`, `PriorityBLockingQueue`, `linkedTransferQueue`, `LinkedBlockingDequeue`)

Behold this beauty: [Collection&nbsp;Hierarchy](http://www.falkhausen.de/Java-10/java.util/Collection-Hierarchy.html)

 ![](https://global.discourse-cdn.com/swift/original/2X/2/27bdf71d321e92a854948790f5b1949f81720452.png)

and [Map&nbsp;Simple](http://www.falkhausen.de/Java-10/java.util/Map-Simple.html)

 ![](https://global.discourse-cdn.com/swift/original/2X/2/2bc604cbd885fd45caa63c3dc88fb24389edc8a5.png)

Amazingly, many Java programmers _ **don't even find these sufficient!** _ The Guava library (a ubiquitous Java library by Google) adds in all kinds of collections like multi maps (map keys to multiple values), BiMaps (which offer `O(1)` look up from key to value, _and_ from value to key), and all kinds of immutable, concurrent, lazy, etc. variants of most things above.

# Meanwhile in Swift land

We have just `Set` (unordered), `Dictionary` (unordered), and `Array`. No concurrent collections (value types solves most of the issues here, but it doesn't solve things like the classic produce-consumer, for example), no linked lists, queues, stacks, bimaps, multimaps, or sort ordered collections.

If we import the ObjC data structures available from Foundation, and have a masochistic desire to cast everywhere because of the lack of generics, we get ordered sets, counted set, and that's ... about it.

# Anticipated responses

## "The standard library is meant to be very minimal"

If we took that to its conclusions, then we shouldn't have `Dictionary`, `Set` or `Array`, either. People should just use `Unsafe(Mutable)?(Raw)?(Buffer)?Pointer`. All of those pointer types could be implemented in terms of `UnsafeMutableRawPointer`, so there isn't even a _need_ for any of the other variants.

Clearly that's infeasible. These are too useful to pass up. But so are ordered dictionaries, counted sets, and synchronized collections. I can't count how many times have I have had to wrap a dictionary and an array of keys for ordering (it's real fun to keep them in sync!).

## "But you can just import XYZ library"

Generally yes, but not in a programming challenge, interview or quick scratch project.

Also, there's no prevailing standards, so there's no established "common currency" types for the use-cases these structures fill.

## "Just write your own"

... 🤦🏻‍♂️

---

<div class="post-metadata">

**Author:** ![Lantua](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/lantua/32/8868_2.png) [@Lantua](https://forums.swift.org/u/Lantua)\
**Post date:** [April 25, 2019, 3:49am UTC](https://forums.swift.org/t/adding-more-data-structures-to-the-standard-library/23651/2 "2019-04-25T03:49:10Z")

</div>

I'd prefer to have a _blessed_ library to use. They're something people generally get wrong, so it's probably worthwhile to have.

If anything, many of these data structures don't match Swift's `Collection` contract; most notably, their _natural_ subscript isn't O(1). So I don't think many of them will conform to the protocol.

---

<div class="post-metadata">

**Author:** ![ben-cohen](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/ben-cohen/32/296_2.png) [@ben-cohen](https://forums.swift.org/u/ben-cohen)\
**Post date:** [April 25, 2019, 3:50am UTC](https://forums.swift.org/t/adding-more-data-structures-to-the-standard-library/23651/3 "2019-04-25T03:50:30Z")

</div>

Can I suggest starting from a slightly more constructive position? Between the opening title and the concluding facepalm, this post is a bit antagonistic.

Keeping the standard library so super-minimal that it doesn't cover the most basic of data structures is definitely a non-goal.

The main reasons the standard library doesn’t have a wider range of data structures are:

1. we were pending ABI stability - both as a project focus and as a barrier to increasing the binary size since it shipped with every app; and
2. no-one's yet done the work of researching, designing, implementing and proposing them.

Since 1) is now behind us, proposals for fundamental data structures would definitely be welcome! @lorentey is also planning to spend some time on this for the next couple of releases and I expect would be keen to work with some collaborators. I'd suggest the right place to start is a discussion of the suitable fundamental data structures, over on the [standard library development forum](https://forums.swift.org/c/development/stdlib). From there, an overview doc can be put together then people can take individual parts to work on.

My view is this would be: key first additions are ordered and sorted sets and dictionaries, a bimap, and some lower-level types that can be built on top of, like a ring buffer. Linked lists have been discussed a few times in the past as a candidate, but are really not that widely useful. Note, Swift's `Array` can act as a stack already. Concurrent collections are a topic that should probably be deferred for now.

---

<div class="post-metadata">

**Author:** ![Tino](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/tino/32/1073_2.png) [@Tino](https://forums.swift.org/u/Tino)\
**Post date:** [April 25, 2019, 3:51am UTC](https://forums.swift.org/t/adding-more-data-structures-to-the-standard-library/23651/4 "2019-04-25T03:51:59Z")

</div>

> [@AlexanderM](#):
>
> "The standard library is meant to be very minimal"

That’s not even true 😂 - but admittedly, many people don’t even seem to use `Set` and are happy with nothing but arrays and dictionaries...

---

<div class="post-metadata">

**Author:** ![Lantua](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/lantua/32/8868_2.png) [@Lantua](https://forums.swift.org/u/Lantua)\
**Post date:** [April 25, 2019, 3:53am UTC](https://forums.swift.org/t/adding-more-data-structures-to-the-standard-library/23651/5 "2019-04-25T03:53:19Z")

</div>

> [@ben-cohen](#):
>
> I'd suggest the right place to start is a discussion of the suitable fundamental data structures, over on the [standard library development forum](https://forums.swift.org/c/development/stdlib).

I don't even know this sub-category exist! Thanks for bringing this up!

---

<div class="post-metadata">

**Author:** ![ben-cohen](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/ben-cohen/32/296_2.png) [@ben-cohen](https://forums.swift.org/u/ben-cohen)\
**Post date:** [April 25, 2019, 3:56am UTC](https://forums.swift.org/t/adding-more-data-structures-to-the-standard-library/23651/6 "2019-04-25T03:56:00Z")

</div>

> [@Lantua](#):
>
> If anything, many of these data structures don't match Swift's `Collection` contract; most notably, their _natural_ subscript isn't O(1). So I don't think many of them will conform to the protocol.

For many data structures this isn't an issue in practice, only in theory. For example, with many tree-based `Collection` designs, while subscript access might theoretically be `O(depth)`, the maximum depth the tree might reach is so low that you can effectively treat it as `O(1)`.

(tbh the main problem with `Collection` is the requirement `Index` be `Comparable`... but it's not a showstopper in most cases, just more work)

---

<div class="post-metadata">

**Author:** ![AlexanderM](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/alexanderm/32/9781_2.png) [@AlexanderM](https://forums.swift.org/u/AlexanderM)\
**Post date:** [April 25, 2019, 3:56am UTC](https://forums.swift.org/t/adding-more-data-structures-to-the-standard-library/23651/7 "2019-04-25T03:56:13Z")

</div>

I didn't intend for the title to sound antagonistic, it was just a genuine observation of mine. I haven't seen anything to suggest that data structures were being taken seriously. I suspect part of the cause is that a large portion of Swift's audience is iOS devs, where JSON is commonly used for interacting with restful APIs, which doesn't support anything besides arrays and dictionaries.

I would be glad to put together an initial proposal for a "first round" of data types (the more important ones like you mentioned), if that seems like something that people would be interested in. This thread is here to gauge interest.

> [@ben-cohen](#):
>
> Note, Swift's `Array` can act as a stack already.

Yeah, which is why I have been loving code problems that require use of a stack. But when I need a queue, and have O(n) head deletions... ouch.

---

<div class="post-metadata">

**Author:** ![AlexanderM](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/alexanderm/32/9781_2.png) [@AlexanderM](https://forums.swift.org/u/AlexanderM)\
**Post date:** [April 25, 2019, 3:57am UTC](https://forums.swift.org/t/adding-more-data-structures-to-the-standard-library/23651/8 "2019-04-25T03:57:26Z")

</div>

> [@ben-cohen](#):
>
> (tbh the main problem with `Collection` is the requirement `Index` be `Comparable` ... but it's not a showstopper in most cases, just more work)

Is that for the purpose of bounds checking? What indexes aren't comparable (raw pointers?)?

---

<div class="post-metadata">

**Author:** ![AlexanderM](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/alexanderm/32/9781_2.png) [@AlexanderM](https://forums.swift.org/u/AlexanderM)\
**Post date:** [April 25, 2019, 3:59am UTC](https://forums.swift.org/t/adding-more-data-structures-to-the-standard-library/23651/9 "2019-04-25T03:59:20Z")

</div>

What are the general thoughts around marker protocols that have no API? e.g. `SortedCollection`, where the protocol can't really do anything to ensure conforming types are sorted, by can be used as documentation (e.g. in a return type, a parameter to a binary search function, etc.)

---

<div class="post-metadata">

**Author:** ![TellowKrinkle](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/tellowkrinkle/32/3370_2.png) [@TellowKrinkle](https://forums.swift.org/u/TellowKrinkle)\
**Post date:** [April 25, 2019, 4:00am UTC](https://forums.swift.org/t/adding-more-data-structures-to-the-standard-library/23651/10 "2019-04-25T04:00:16Z")

</div>

I've had issues with linked list indices before, I would guess indices for trees would have similar difficulties  
The easy solution is to include a distance from start parameter, but then if you want to be a bidirectional collection you need an `O(1)` size to get the distance of the endIndex

---

<div class="post-metadata">

**Author:** ![ben-cohen](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/ben-cohen/32/296_2.png) [@ben-cohen](https://forums.swift.org/u/ben-cohen)\
**Post date:** [April 25, 2019, 4:08am UTC](https://forums.swift.org/t/adding-more-data-structures-to-the-standard-library/23651/11 "2019-04-25T04:08:09Z")

</div>

Yeah, for a linked list you need to store a count from start, though the end doesn’t need it, you can just define `.end > _`.

Tree indices can be a path from the root down to the element.

---

<div class="post-metadata">

**Author:** ![ben-cohen](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/ben-cohen/32/296_2.png) [@ben-cohen](https://forums.swift.org/u/ben-cohen)\
**Post date:** [April 25, 2019, 4:09am UTC](https://forums.swift.org/t/adding-more-data-structures-to-the-standard-library/23651/12 "2019-04-25T04:09:06Z")

</div>

I think they’re the source of much debate as to whether they’re a good or bad idea :)

---

<div class="post-metadata">

**Author:** ![TellowKrinkle](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/tellowkrinkle/32/3370_2.png) [@TellowKrinkle](https://forums.swift.org/u/TellowKrinkle)\
**Post date:** [April 25, 2019, 4:09am UTC](https://forums.swift.org/t/adding-more-data-structures-to-the-standard-library/23651/13 "2019-04-25T04:09:48Z")

</div>

Even if `.end > _` what's `.index(before: .end)` on your doubly-linked list?

---

<div class="post-metadata">

**Author:** ![ben-cohen](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/ben-cohen/32/296_2.png) [@ben-cohen](https://forums.swift.org/u/ben-cohen)\
**Post date:** [April 25, 2019, 4:12am UTC](https://forums.swift.org/t/adding-more-data-structures-to-the-standard-library/23651/14 "2019-04-25T04:12:57Z")

</div>

Oh right. Yes, you’re stuck there. You could store the count on the node too, but then you lose O(1) inserts which is kinda one of the points of linked list... ☹

---

<div class="post-metadata">

**Author:** ![AlexanderM](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/alexanderm/32/9781_2.png) [@AlexanderM](https://forums.swift.org/u/AlexanderM)\
**Post date:** [April 25, 2019, 4:16am UTC](https://forums.swift.org/t/adding-more-data-structures-to-the-standard-library/23651/15 "2019-04-25T04:16:01Z")

</div>

This gets me thinking... what is `Dictionary<Key, Value>.Index`, and how is it comparable?

---

<div class="post-metadata">

**Author:** ![TellowKrinkle](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/tellowkrinkle/32/3370_2.png) [@TellowKrinkle](https://forums.swift.org/u/TellowKrinkle)\
**Post date:** [April 25, 2019, 4:17am UTC](https://forums.swift.org/t/adding-more-data-structures-to-the-standard-library/23651/16 "2019-04-25T04:17:38Z")

</div>

AFAIK Dictionary indices are just indices into the underlying array. The only weirdness is that `index(after:)` has to skip over all the unused slots

Edit: You can see it in the repl:

```nohighlight
  1> let dic = Dictionary(uniqueKeysWithValues: (0..<10000).lazy.map { ($0, $0) }) 
// Large dictionary printout removed
  2> dic.startIndex
$R0: Dictionary<Int, Int>.Index = {
  _variant = native {
    native = {
      bucket = {
        offset = 1
      }
      age = -1612773233
    }
  }
}

```

---

<div class="post-metadata">

**Author:** ![AlexanderM](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/alexanderm/32/9781_2.png) [@AlexanderM](https://forums.swift.org/u/AlexanderM)\
**Post date:** [April 25, 2019, 4:20am UTC](https://forums.swift.org/t/adding-more-data-structures-to-the-standard-library/23651/17 "2019-04-25T04:20:57Z")

</div>

> [@TellowKrinkle](#):
>
> The only weirdness is that `index(after:)` has to skip over all the unused slots

And there's no way to do that skip without linear probing, right? So `O(bucketCount)`?

---

<div class="post-metadata">

**Author:** ![Lantua](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/lantua/32/8868_2.png) [@Lantua](https://forums.swift.org/u/Lantua)\
**Post date:** [April 25, 2019, 4:22am UTC](https://forums.swift.org/t/adding-more-data-structures-to-the-standard-library/23651/18 "2019-04-25T04:22:08Z")

</div>

That'd require more bookkeeping, and it's already O(1) amortized when looping. So I don't really see a point.

---

<div class="post-metadata">

**Author:** ![TellowKrinkle](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/tellowkrinkle/32/3370_2.png) [@TellowKrinkle](https://forums.swift.org/u/TellowKrinkle)\
**Post date:** [April 25, 2019, 4:23am UTC](https://forums.swift.org/t/adding-more-data-structures-to-the-standard-library/23651/19 "2019-04-25T04:23:01Z")

</div>

A single call would be `O(bucketCount)`, but obviously looping over the whole dictionary isn't `O(bucketCount^2)` due to the fact that the dictionary can't have `bucketCount` gaps between _every_ pair of indices

Edit: though because of this, calling `index(after:)` in a lazy collection wrapper's subscript _will_ make that `O(n)` in unlucky cases (though other collections exhibit much bigger issues than Dictionary here, like `LazyFilterCollection`)

---

<div class="post-metadata">

**Author:** ![griotspeak](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/griotspeak/32/1966_2.png) [@griotspeak](https://forums.swift.org/u/griotspeak)\
**Post date:** [April 25, 2019, 5:55am UTC](https://forums.swift.org/t/adding-more-data-structures-to-the-standard-library/23651/20 "2019-04-25T05:55:56Z")

</div>

> [@ben-cohen](#):
>
> Linked lists have been discussed a few times in the past as a candidate, but are really not that widely useful.

YOU TAKE THAT BACK! 😝

[Next page](https://forums.swift.org/t/adding-more-data-structures-to-the-standard-library/23651.md?page=2)