apple / apple/swift-collections

Weak-keyed/weak-valued hashed collections

Open
#2 1 comment 18 reactions 1 assignee Claimed by @obvgab View on GitHub
enhancement
Dominant language
Swift
Stars
4.5k
Forks
405
Avg merge
3d 3h
Merged PRs (30d)
10

Description

A weak `Set` and a weak-keyed (or weak-valued) `Dictionary` are often-requested data structures that aren't easy to implement. It's especially difficult to do it correctly in terms of the existing `Set` and `Dictionary` -- most attempts end up accidentally changing the identity of keys already in a hash table, which violates invariants and leads to runtime errors.

This package would be a good place to host a set of weak collection implementations.

While the implementation isn't entirely trivial, I expect this will be mostly an API design challenge. Some notes:

- These would work best if they came with their own hash table implementation whose lookup etc. operations are aware of the fact that keys/values could disappear at any moment, and are able to update the table accordingly.
- Deallocated keys work like tombstones.
- The `Element`, `Key` and/or `Value` types would be constrained to `AnyObject`. We can probably still allow custom `Hashable` implementations, as long as the hash table operations are aware of `nil`ed out entries. The tradeoff here is that requiring `Hashable` will make developers do more work by having to manually implement it, even if they only want to use object identity.
- Ideally lookup operations would be able to incrementally update the table by getting rid of obsolete entries they encounter. A mutating lookup would probably preclude the use of these types in concurrent contexts. This is fine -- these are typically used for caches local to a particular actor.
- These types probably won't be able to conform to `Collection` as their `count` can change at any point. This is fine -- they shouldn't even provide a `count` of live entries.
- The types may or may not implement value semantics (depending on whichever choice makes most sense). This is fine.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.