Finding Unique Items in a Go Slice or Array

Question

I'm pretty new to go and I'm really, really confused right now.

Let's say I have a list of coordinates and lets say I have some doubles in this list of coordinates. I can't for the life of me figure out how to make a unique list. Normally in Python I can "cheat" with sets and other built-ins. Not so much in Go.

package main

import (
    "fmt"
    "reflect"
)

type visit struct {
    x, y int
}

func main() {
    var visited []visit
    var unique []visit

    visited = append(visited, visit{1, 100})
    visited = append(visited, visit{2, 2})
    visited = append(visited, visit{1, 100})
    visited = append(visited, visit{1, 1})

    unique = append(unique, visit{1, 1})

    fmt.Println(unique)

    // Go through the visits and find the unique elements
    for _, v := range visited {
        for _, u := range unique {

            fmt.Printf("Here's unique: %v\n", unique)
            fmt.Printf("Comparing %v to %v is %v\n", v, u, reflect.DeepEqual(v, u))

            if reflect.DeepEqual(v, u) {
                fmt.Println("Skip")
            } else {
                unique = append(unique, v)
            }
        }
    }

    fmt.Println(unique)
}

Run it on Playground

Answer 1

There are multiple errors in your code. The most serious is that since you're comparing each specific element of the visited slice to all of the elements of unique, you will end up appending it if unique contains at least one which is different. And going forward, you will end up appending it multiple times if there are more elements in unique which differ as your inner for loop doesn't "break". This is not what you want, you want to append elements which equals to none of unique.

Also note that a struct in Go is comparable if each of its fields are comparable. Since your visit struct contains only 2 int fields, it is comparable and so you can compare values of visit type simply with the == operator, no need that ugly reflect.DeepEqual(). See Spec: Comparison operators:

Struct values are comparable if all their fields are comparable. Two struct values are equal if their corresponding non-blank fields are equal.

Here's a simplified, correct version that applies your logic:

visited := []visit{
    visit{1, 100},
    visit{2, 2},
    visit{1, 100},
    visit{1, 1},
}
var unique []visit

for _, v := range visited {
    skip := false
    for _, u := range unique {
        if v == u {
            skip = true
            break
        }
    }
    if !skip {
        unique = append(unique, v)
    }
}

fmt.Println(unique)

Output (try it on the Go Playground):

[{1 100} {2 2} {1 1}]

Alternative

It's true that Go doesn't have a built-in set type, but you can use a map[visit]bool easily as a set. With that, it becomes really simple! Note that visit can be used as key in the map because it is comparable (see above).

visited := []visit{
    visit{1, 100},
    visit{2, 2},
    visit{1, 100},
    visit{1, 1},
}
unique := map[visit]bool{}

for _, v := range visited {
    unique[v] = true
}

fmt.Println(unique)

Output (try it on the Go Playground):

map[{2 2}:true {1 1}:true {1 100}:true]

The unique "list" is the list of keys in the map.

If you want the unique visit values as a slice, see this variant:

var unique []visit
m := map[visit]bool{}

for _, v := range visited {
    if !m[v] {
        m[v] = true
        unique = append(unique, v)
    }
}

fmt.Println(unique)

Output (as expected, try it on the Go Playground):

[{1 100} {2 2} {1 1}]

Note that this index expression: m[v] evaluates to true if v is already in the map (as a key, true is the value we stored in the map). If v is not yet in the map, m[v] yields the zero value of the value type which is false for the type bool, properly telling that the value v is not yet in the map. See Spec: Index expressions:

For a of map type M:

...if the map is nil or does not contain such an entry, a[x] is the zero value for the value type of M

Answer 2

i think you can make a map of visits. Something like this

visited := make(map[visit]Boolean)

than you can set the value of the visited.

visited[visit]=true

and lastly, you can fetch all visited locations by this code

for k, _ := range visited {
    unique = append(unique, k)
}