[swift-evolution] Custom equality/hash for Sets

[Andrew Bennett]

*Wrapper Solution?*

I've had a go at a wrapper solution before and it seems to either need a
unique type per sort, or a block stored per element (unstable).

Similar overheads were discussed when an index needs to store a reference
to the parent. There's some work to fix it that makes indices moveable, so
instead of going index.successor() you use collection.next(index).

https://github.com/apple/swift/blob/master/test/Prototypes/CollectionsMoveIndices.swift

*Potential solution:*

The collection interfaces could change like this:

- struct Set<Element: Hashable> {
- struct Set<Element> {
    ...
-   public init() { ... }
+   public init<H: Hashable>(elementHasher: Element -> H) {
      ...
    }
-   public init(minimumCapacity: Int) { ... }
+   public init<H: Hashable>(minimumCapacity: Int, elementHasher: Element
-> H) {
      ...
    }
    ... (same for other public initialisers)
  }

Then the Hashable specific initialisers added back like this:

+ extension Set where Element: Hashable {
+   public init() { ... }
+   public init(minimumCapacity: Int) { ... }
+ }

*Potential Implementation*

I've had a quick look at `HashedCollections.swift.gyb`, there's currently
two underlying implementations ObjC and Swift Native, it may be possible to
specialise (gyb) this Native implementation into two implementations
(HashableNative, ClosureNative).

The specialisation is probably just a one liner in `_bucket()` and
`hashValue` to use a different method to get the hash.

I don't think this would break any code, except new initialisers that may
need `where Hashable` added. I think it will provide the desired
functionality.

It may even be a fairly straightforward implementation (famous last words),
although I haven't got time to do much more at the moment.

On Friday, 19 February 2016, Dave Abrahams via swift-evolution <
swift-evolution at swift.org> wrote:

>
> on Thu Feb 18 2016, Jacob Bandes-Storch <swift-evolution at swift.org> wrote:
>
> > Would it make sense for the standard library Set to provide variants (or
> > parallel versions of the same data structure) that take custom
> hashValue/==
> > implementations at init time (functions taking in Elements), rather than
> > relying on Hashable/Comparable protocols?
> >
> > Use case: I want a set of objects that are compared for equality using
> ===
> > rather than ==. This doesn't seem possible today, using Set, without
> > creating some sort of wrapper object.
> >
> > This particular case would be analogous to using NSHashTable with
> > NSPointerFunctionsObjectPointerPersonality. (Maybe all I'm asking for is
> a
> > Swiftier API for NSHashTable — including ArrayLiteralConvertible, using
> > generics instead of UnsafePointer<Void>, etc.)
> >
> > Similarly, C++'s unordered_map
> > <http://en.cppreference.com/w/cpp/container/unordered_map> and friends
> have
> > template parameters specifying the hash function and equality comparator,
> > which use std::hash and == by default.
>
> It might make sense.  How bad is the wrapper solution for user code?
>
> --
> -Dave
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160219/aea5877c/attachment.html>