search

pointfreeco / swift-identified-collections

A library of data structures for working with collections of identifiable elements in an ergonomic, performant way.
MIT License
539 stars 46 forks source link

Add IdentifiedSet with SetAlgebra conformance #20

Closed Saklad5 closed 3 years ago

Saklad5 commented 3 years ago

I often find myself using types like Dictionary<IdentifiableValue.ID, IdentifiableValue> to hold information. I’d prefer to use a Set, but I need O(1) subscript lookup.

IdentifiedArray is almost perfect for my needs, but maintains order instead of using set operations. Would it be possible to make an unordered counterpart?

stephencelis commented 3 years ago

@Saklad5 Thanks for the question! We probably won't have time to explore such a collection soon as we don't have a use case for it, but we're definitely open to helping get something across the finish line if you're interested in doing the exploratory work of what such a type's API would look like.

Are you interested in working on and submitting a PR?

Saklad5 commented 3 years ago

If I end up needing it, certainly. I was thinking it could be similar to the implementation of IdentifiedArray, but with a Hashable requirement and SetAlgebra conformance similar to the unordered view of an OrderedSet.

Saklad5 commented 3 years ago

The only reason OrderedSet limits SetAlgebra conformance to an unordered view is because it needs to discriminate based on order, which violates the necessary assumptions. Meanwhile, it uses a hash table to track position much like a dictionary with keys. An IdentifiedSet could conform directly.

stephencelis commented 3 years ago

@Saklad5 Sounds good! I'm going to convert this to a discussion where design/details could be fleshed out further. We try to keep our issues sections focussed on bug tracking over requested features.