Given S = Set{Vector{Int}}, how do I get a reference to the original object in S?

Given a set S = Set{Vector{Int}}(s_1,…,s_n) and a vector v such that
v == s_k but not v===s_k, how do I return the original object s_k from S?

SA = [S...]
s_k = SA[findfirst(isequal(v), SA)]
1 Like

I guess this works, but then you lose the O(1) lookup of sets/dicts.

The solution I use right now is to use a dictionary as follows. Given,
s = [1,1,2]
S = Dict(hash(s) => s)

with v==s and !(v===s), get s as follows
s = S[hash(v)]

This is efficient and does what I need, but I feel the same should be possible using a set.

Because you’re comparing objects by value, you need to check elements one-by-one, so it can’t be O(1).

That’s not how sets work

Ah, good catch, I’m wrong (I thought it compared vectors by reference).

@stillyslalom, my approach using a Dict is O(1).

Looking at the source, Set uses Dicts under the hood:

so you can use

s_k = getkey(S.dict, v, Nothing)
1 Like

@stillyslalom, great catch! That solves it.