golang maps; using slice as a key

[Sankar]

Is there a way to use a slice as a key to a map ? If I try, I get a compilation error: `invalid map key type`. 

I tried creating a custom type, which contains an array as the element. However, I could not find out what method to implement for my custom type(such as: func (i *myType) Equal(j *myType) bool ) that would make the equality operator call this function. 

An example program, where I needed to use a slice/array as the key of a map is also available at: https://play.golang.org/p/kXwAaHckL76 

Is there a way (or alternate solutions) to use a slice as the map key ? 

Thanks.

[Volker Dobler]

No, sorry, slices cannot be used as map keys.

Also note that equality is not dependent on methods

and not user changeable but solely determined by

the language spec.

If you can derive e.g. a string from the slice and use

that string as the map key you would be fine.

V.

[Justin Israel]

Use an array instead of a slice. An array has a fixed size and can be used as a key to a map

https://play.golang.org/p/xxxmrwpx08A

Thanks.

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Bakul Shah]

Your example problem is solvable without needing a map[slice].

Outline: sort the array, put duplicates in the same slot. Thus
for example [-1, 0, 1, 2, -1, -4] turns into
[{-4},{-1,-1},{0},{1},{2}]

Now for a given number N with D duplicates you can pick 0..D
elements. Thus for the example list, we have 2x3x2x2x2
combinations with duplicates (i.e. 48 instead of 64, if there
were no duplicates) containing 0 to 5 numbers. Throw out all
non-triples as well as nonzero triples.

[Sankar P]

Use an array instead of a slice. An array has a fixed size and can be used as a key to a map

https://play.golang.org/p/xxxmrwpx08A

This seem to not work. The arr is returning only duplicate elements in your playground url. 

For example:

       var arr [][]int

for mem := range m {

fmt.Println("Appending: ", mem[:])

arr = append(arr, mem[:])

}

fmt.Println("Final arr is:", arr)

the output is:

Appending:  [-1 0 1]
Appending:  [-1 -1 2]
Final arr is: [[-1 -1 2] [-1 -1 2]]

I am not really able to understand why the above code works so. The "Appending" and the "Final arr" statements have different values.

 

--

Sankar P
http://psankar.blogspot.com

[Karan Chaudhary]

One other simpler (and not so elegant) solution is to use separate set for each element.

https://play.golang.org/p/9ZSRfAyOX4-

@Bakul's solution sounds good but haven't tried to understand it clearly.

[Karan Chaudhary]

And a little better way to create `numMem`

https://play.golang.org/p/fAWgSpi2CKR

[Sankar P]

https://play.golang.org/p/dqp7po8Tg_4 is a working solution and it takes only O(n^2), if you are curios. Your way of creating a numMem is also nice. Thanks.

--
You received this message because you are subscribed to a topic in the Google Groups "golang-nuts" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/golang-nuts/fcBDb2wjtac/unsubscribe.
To unsubscribe from this group and all its topics, send an email to golang-nuts+unsubscribe@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

[Sankar P]

I extracted the confusing part alone, when appending to an array, the items are different than the resultant array into a separate go program. 

The Playground URL is: https://play.golang.org/p/BJM0H_rYNdb 

If someone can explain the output I would be thankful. It feels like a bug to me, but I am sure that I am only misunderstanding and it may not be a bug.

Thanks.

[pierre...@gmail.com]

You keep the reference of the loop index that points at the last array.

Either make a copy of it or use a slice of arrays.

https://play.golang.org/p/WcOHQ_wIKjx

https://play.golang.org/p/CToFC9w88M7

[Sankar P]

Thanks.

--

You received this message because you are subscribed to a topic in the Google Groups "golang-nuts" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/golang-nuts/fcBDb2wjtac/unsubscribe.
To unsubscribe from this group and all its topics, send an email to golang-nuts+unsubscribe@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

[Karan Chaudhary]

The slice which is created to be appended to b,  points to &i,  which (i) gets updated in next (last) loop iteration.  

Hence in last iteration,  first element in `b` will start pointing to the new array [4,5,6].

This could have been mitigated had `i` been allocated to new location on every iteration.

But that does not seem to be the case and I don't understand why.

On a side note,  I don't think this program would have compiler in Rust :) .

Thanks.

To unsubscribe from this group and all its topics, send an email to golang-nuts...@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

[Matthias B.]

On Wed, 23 May 2018 13:29:17 +0530
Sankar P <sankar.c...@gmail.com> wrote:

> I extracted the confusing part alone, when appending to an array, the
> items are different than the resultant array into a separate go
> program.
>
> The Playground URL is: https://play.golang.org/p/BJM0H_rYNdb
>
> If someone can explain the output I would be thankful. It feels like
> a bug to me, but I am sure that I am only misunderstanding and it may
> not be a bug.

Maybe this makes it clearer:

https://play.golang.org/p/YolkDuYzrW8

There are 2 things to realize:

a) arrays are VALUES in Go, not pointers like in C. This means that the
loop variable i is not a pointer, it's an actual independent array that
has its own storage not shared with any of the arrays that are stored
as keys in the map. At the start of the first iteration of the map, the
numbers 1,2,3 are COPIED from the memory of the key [1,2,3] stored in
m1 to the memory of i. At the start of the 2nd iteration of the loop,
the numbers 4,5,6 are COPIED from the memory of the key [4,5,6] stored
in m1 to the memory of i. This overwrites the memory of i.

b) slices are a triples of a pointer, a length and maximum
length(capacity). Length and capacity are not relevant to understanding
this issue. So for the purposes of this issue, you can consider a slice
as a pointer. This means that the expression i[:] creates a pointer to
the storage address of i. Because i does not change its storage for the
whole duration of the loop, the expression i[:] is always the same.
It's a pointer to the storage that during the 1st iteration of the loop
contains 1,2,3 and during the 2nd iteration contains 4,5,6.
You can see this in my playground example. The printed pointer address
is the same in both cases.

Taken together this means that at the end of the program, b contains 2
copies of the same (address,length,capacity) triple with address
pointing to the storage of i (which because Go is garbage collected
remains valid). The storage of i contains the last value copied to it,
which is 4,5,6.

MSB

--
If you do not fear death, how can you love life?

[lafolle]

Thanks Mathias for clearing this out.

I reasoned this out by looking at the address to which `i` was allocated to,

though I wanted to _peek_ inside the slice's header to be affirmative.  But

I can't clearly understand how to use unsafe pointer.  Thanks for showing

how to use it.

 One thing I don't understand is that why `i` is always allocated to same 

address?  Is it to reduce allocations?  Do other languages also do this?

[Bakul Shah]

On Wed, 23 May 2018 00:25:49 -0700 Karan Chaudhary <fgh...@gmail.com> wrote:
>
> One other simpler (and not so elegant) solution is to use separate set for
> each element.
>
> https://play.golang.org/p/9ZSRfAyOX4-
>
> @Bakul's solution sounds good but haven't tried to understand it clearly.

See https://play.golang.org/p/_DrcHFTpHox

I first implemented it in k and then translated it fairly
mechanically to Go. [BTW, this is where Go not having generics
makes things a bit messy!]

The solution may seem cryptic but it is using typical array
programming components: each, reduce, cross-product, filter,
concatenate etc. Once you develop a correct solution, you can
convert it to avoid building intermediate vectors + add other
optimizations. [Ideally done by a source to source converter]

[Uli Kunitz]

You don't need maps for this: https://play.golang.org/p/ylIdX7P9Syy

Sorting is your friend.

[Matthias B.]

On Wed, 23 May 2018 03:03:18 -0700 (PDT)
lafolle <fgh...@gmail.com> wrote:

> Thanks Mathias for clearing this out.
>
> I reasoned this out by looking at the address to which `i` was
> allocated to, though I wanted to _peek_ inside the slice's header to
> be affirmative. But I can't clearly understand how to use unsafe
> pointer. Thanks for showing how to use it.
>
> One thing I don't understand is that why `i` is always allocated to
> same address? Is it to reduce allocations? Do other languages also
> do this?

Most languages do not have arrays as values and therefore this special
case does not apply to them. With respect to ordinary loops, yes,
that's the normal way to do it. In fact for typical loops that use
integer loop variables that live only for the duration of the loop,
there is no allocation. The variable is simply kept in a processor
register. Even the Go compiler does that when possible. It's easier to
understand when you look at a loop like this

for i := 0; i < 10; i++ {
...
}

The "i:=0" is only executed ONCE, at the very start of the loop. So
it's obvious that if an allocation is necessary, it occurs only once,
as neither "i<10" nor "i++" can cause an allocation.

Your loop is really just a fancy version of this same pattern.

MSB

--
Light travels faster than sound. This is why some people appear bright
until you hear them speak.