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

General Usage
1

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?

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

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.

4

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

5

That’s not how sets work

6

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

7

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

8

Looking at the source, Set uses Dicts under the hood: https://github.com/JuliaLang/julia/blob/7e6ef91c9d0bf89de7b45a46aaacf4f644986b69/base/set.jl#L4

so you can use

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

@stillyslalom, great catch! That solves it.