apple / apple/swift-collections
Weak-keyed/weak-valued hashed collections
- 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
Assessment
This issue has not been assessed yet.