Check whether a string slice contains a certain value in Go

Question

What is the best way to check whether a certain value is in a string slice? I would use a Set in other languages, but Go doesn't have one.

My best try is this so far:

package main

import "fmt"

func main() {
    list := []string{"a", "b", "x"}
    fmt.Println(isValueInList("b", list))
    fmt.Println(isValueInList("z", list))
}

func isValueInList(value string, list []string) bool {
    for _, v := range list {
        if v == value {
            return true
        }
    }
    return false
}

http://play.golang.org/p/gkwMz5j09n

This solution should be ok for small slices, but what to do for slices with many elements?

Bildungsroman

Answer 1

If you have a slice of strings in an arbitrary order, finding if a value exists in the slice requires O(n) time. This applies to all languages.

If you intend to do a search over and over again, you can use other data structures to make lookups faster. However, building these structures require at least O(n) time. So you will only get benefits if you do lookups using the data structure more than once.

For example, you could load your strings into a map. Then lookups would take O(1) time. Insertions also take O(1) time making the initial build take O(n) time:

set := make(map[string]bool)
for _, v := range list {
    set[v] = true
}

fmt.Println(set["b"])

You can also sort your string slice and then do a binary search. Binary searches occur in O(log(n)) time. Building can take O(n*log(n)) time.

sort.Strings(list)
i := sort.SearchStrings(list, "b")
fmt.Println(i < len(list) && list[i] == "b")

Although in theory given an infinite number of values, a map is faster, in practice it is very likely searching a sorted list will be faster. You need to benchmark it yourself.

Competitive

Answer 2

To replace sets you should use a map[string]struct{}. This is efficient and considered idiomatic, the "values" take absolutely no space.

Initialize the set:

set := make(map[string]struct{})

Put an item :

set["item"]=struct{}{}

Check whether an item is present:

_, isPresent := set["item"]

Remove an item:

delete(set, "item")

Ingest

Answer 3

You can use a map, and have the value e.g. a bool

m := map[string] bool {"a":true, "b":true, "x":true}
if m["a"] { // will be false if "a" is not in the map
    //it was in the map
}

There's also the sort package, so you could sort and binary search your slices

Wilheminawilhide

Note that you don't have to use bool dummy values. You can use an empty struct like this: map[string]struct{}. – Heronry

Just to clarify what @Heronry said, the advantage of using struct{} as the value is that it takes no memory. – Widthwise

"It takes no memory" … for the values, of course the map still takes memory for the keys and hash table (or whatever implementation), it just minimizes the memory used by the map (at the expense of requiring the if _, ok := map["a"]; ok style checks rather just if map["a"]). – Ravel

Answer 4

With Go 1.21 and higher, you can use slices#Contains:

list := []string{"a", "b", "x"}
fmt.Println(slices.Contains(list, "b")) // true
fmt.Println(slices.Contains(list, "z")) // false

(cf. https://go.dev/play/p/2ycquYNfLGR to run this example in Go Playground)

Pembroke