Is there anything similar to a slice.contains(object)
method in Go without having to do a search through each element in a slice?
-
8github.com/forestgiant/sliceutil– RodrigoMar 28, 2016 at 18:51
-
2Try never to use a third-party package for such a work, like @Rodrigo you offered. It makes you code bulky and fragile– Igor A. MelekhineMay 3, 2022 at 7:41
-
go.dev/play/p/B1qGeOLI9Na– Omkesh SajjanwarJul 12, 2022 at 12:59
-
There is no possible way to search a slice without visiting every element, so it will always be O(N). If you need scalability, a slice is the wrong data structure.– Jeff LearmanJul 24 at 12:38
19 Answers
Mostafa has already pointed out that such a method is trivial to write, and mkb gave you a hint to use the binary search from the sort package. But if you are going to do a lot of such contains checks, you might also consider using a map instead.
It's trivial to check if a specific map key exists by using the value, ok := yourmap[key]
idiom. Since you aren't interested in the value, you might also create a map[string]struct{}
for example. Using an empty struct{}
here has the advantage that it doesn't require any additional space and Go's internal map type is optimized for that kind of values. Therefore, map[string] struct{}
is a popular choice for sets in the Go world.
-
33Also note, that you have to write
struct{}{}
to get the value of the empty struct so that you can pass it to your map when you want to add an element. Just try it, and if you encounter any problems, feel free to ask. You can also use Mostafa's solution if that's easier for you to understand (unless you have huge amounts of data).– tux21bMay 7, 2012 at 17:43 -
19Solution is simple, that's true. But what it takes to add such basic functionality into runtime? I haven't found such issues in Go repo on github. That's sad and strange. May 23, 2017 at 6:06
-
4How does
map[string] bool
compare withmap[string] struct{}
.map[string] struct{}
seems like a hack especially initializing an empty structstruct {}{}
Sep 12, 2019 at 12:17 -
14@IgorPetrov agreed, I'm surprised such a basic feature is not in the runtime already.– jcollumApr 21, 2020 at 19:06
-
33
No, such method does not exist, but is trivial to write:
func contains(s []int, e int) bool {
for _, a := range s {
if a == e {
return true
}
}
return false
}
You can use a map if that lookup is an important part of your code, but maps have cost too.
-
527Actually it's not trivial, because you have to write one for each type that you use, and because there's no overloading, you have to name each function differently, like in C. append() can work generically because it has special runtime support. A generic contains would be useful for the same reason, but really the generic solution is just generics support in the language.– EloffJul 12, 2014 at 18:00
-
2
-
237trivial == 7 lines of code including 1 loop 1 branch if statement and 1 comparison? I think I'm missing something here ... Oct 19, 2016 at 21:06
-
91
-
24What's the point of Go if it's a pain like C in such regard... If
contains
is so trivial, it should be self explanatory to add it to the standard library.– AkitoMar 8, 2022 at 23:02
As of Go 1.21, you can use the stdlib slices
package which was promoted from the experimental package previously mentioned.
import "slices"
things := []string{"foo", "bar", "baz"}
slices.Contains(things, "foo") // true
Original Answer:
Starting with Go 1.18, you can use the slices
package – specifically the generic Contains
function:
https://pkg.go.dev/golang.org/x/exp/slices#Contains.
go get golang.org/x/exp/slices
import "golang.org/x/exp/slices"
things := []string{"foo", "bar", "baz"}
slices.Contains(things, "foo") // true
Note that since this is outside the stdlib as an experimental package, it is not bound to the Go 1 Compatibility Promise™ and may change before being formally added to the stdlib.
-
2unfortunately you cannot use Go 1.18 with older versions of macOS May 24, 2022 at 21:11
-
could not read Username for 'github.com': terminal prompts disabled Got above error during
go get
Jan 23 at 13:11
With Go 1.18+ we could use generics.
func Contains[T comparable](s []T, e T) bool {
for _, v := range s {
if v == e {
return true
}
}
return false
}
-
122Go is my favorite language because I love creating utilities from scratch that other languages offers OOTB. Feb 11, 2022 at 20:05
-
8@AbhijitSarkar I realize you're being facetious, and I do also agree that this should be in the stdlib, but generics were just introduced to Go. I prefer a language that is very deliberate about the features it introduces and remains relatively simple. I'm hopeful that over time this will be added to Golang.– dimiguelMay 7, 2022 at 16:03
-
1
-
11I would rather spend effort in writing business logic than writing utilities.– HemSep 20, 2022 at 20:39
-
6It seems like in golang they are trading simplicity in language implementation for additional complexity for anyone using it. I'm assuming every golang developer simply has all of the basic functionality implemented somewhere and copies and pastes it between their projects. It's basically Javascript all over again, except code quality is higher due to the high barrier to entry– BrandonSep 22, 2022 at 21:42
The sort package provides the building blocks if your slice is sorted or you are willing to sort it.
input := []string{"bird", "apple", "ocean", "fork", "anchor"}
sort.Strings(input)
fmt.Println(contains(input, "apple")) // true
fmt.Println(contains(input, "grow")) // false
...
func contains(s []string, searchterm string) bool {
i := sort.SearchStrings(s, searchterm)
return i < len(s) && s[i] == searchterm
}
SearchString
promises to return the index to insert x if x is not present (it could be len(a))
, so a check of that reveals whether the string is contained the sorted slice.
-
2In terms of time, the regular search is
O(n)
and this solution makes itO(n*log(n))
.– plesivMay 9, 2020 at 19:18 -
2@plesiv it’s a binary search, AFAICS. Wouldn’t that make it O(log n)? May 9, 2020 at 19:52
-
9yes, binary-search and the function
contains
areO(log(n))
, but the overall approach isO(n*log(n))
due to the sort.– plesivMay 25, 2020 at 14:06 -
1@plesiv Yes that's true for a single search, but if searching many times, say n times, then it's O(n + n * log(n)) vs O(n * n). Henrik's answer shows searching more than one time.– ZamicolJul 13, 2022 at 20:57
Instead of using a slice
, map
may be a better solution.
simple example:
package main
import "fmt"
func contains(slice []string, item string) bool {
set := make(map[string]struct{}, len(slice))
for _, s := range slice {
set[s] = struct{}{}
}
_, ok := set[item]
return ok
}
func main() {
s := []string{"a", "b"}
s1 := "a"
fmt.Println(contains(s, s1))
}
-
55In its current form this code offers no benefit, since there is no point in constructing a map from a slice if you are only going to use it once. — To be useful, this code should rather provide a function
sliceToMap
that does all the preparation. After that, querying the map is trivial and efficient. Oct 26, 2015 at 21:13 -
1You are creating a map by iterating the slice, it is double the work, more code, less efficient– JunaedMay 27, 2022 at 10:20
If the slice is sorted, there is a binary search implemented in the sort
package.
func Contain(target interface{}, list interface{}) (bool, int) {
if reflect.TypeOf(list).Kind() == reflect.Slice || reflect.TypeOf(list).Kind() == reflect.Array {
listvalue := reflect.ValueOf(list)
for i := 0; i < listvalue.Len(); i++ {
if target == listvalue.Index(i).Interface() {
return true, i
}
}
}
if reflect.TypeOf(target).Kind() == reflect.String && reflect.TypeOf(list).Kind() == reflect.String {
return strings.Contains(list.(string), target.(string)), strings.Index(list.(string), target.(string))
}
return false, -1
}
I think map[x]bool
is more useful than map[x]struct{}
.
Indexing the map for an item that isn't present will return false
. so instead of _, ok := m[X]
, you can just say m[X]
.
This makes it easy to nest inclusion tests in expressions.
-
1This is good, but keep in mind that struct{} has space complexity of 0 while bool has more– SerafFeb 24 at 13:59
You can use the reflect package to iterate over an interface whose concrete type is a slice:
func HasElem(s interface{}, elem interface{}) bool {
arrV := reflect.ValueOf(s)
if arrV.Kind() == reflect.Slice {
for i := 0; i < arrV.Len(); i++ {
// XXX - panics if slice element points to an unexported struct field
// see https://golang.org/pkg/reflect/#Value.Interface
if arrV.Index(i).Interface() == elem {
return true
}
}
}
return false
}
-
7Sure you can use the reflect package but just because you can, doesn't mean you should. Reflection is very expensive. Jul 2, 2019 at 1:22
-
1In actual application code no, you shouldn't do this. It is expensive. However, for unit tests, it doesn't matter so much and is very useful. May 14, 2021 at 2:12
Not sure generics are needed here. You just need a contract for your desired behavior. Doing the following is no more than what you would have to do in other languages if you wanted your own objects to behave themselves in collections, by overriding Equals() and GetHashCode() for instance.
type Identifiable interface{
GetIdentity() string
}
func IsIdentical(this Identifiable, that Identifiable) bool{
return (&this == &that) || (this.GetIdentity() == that.GetIdentity())
}
func contains(s []Identifiable, e Identifiable) bool {
for _, a := range s {
if IsIdentical(a,e) {
return true
}
}
return false
}
-
1"is no more than what you would have to do in other languages" isn't really true - e.g. in C#
Contains()
is implemented onList<T>
, so you only ever have to implementEquals()
for that work.– GeorgeMay 17, 2019 at 2:01
If it is not feasable to use a map for finding items based on a key, you can consider the goderive tool. Goderive generates a type specific implementation of a contains method, making your code both readable and efficient.
Example;
type Foo struct {
Field1 string
Field2 int
}
func Test(m Foo) bool {
var allItems []Foo
return deriveContainsFoo(allItems, m)
}
To generate the deriveContainsFoo method:
- Install goderive with
go get -u github.com/awalterschulze/goderive
- Run
goderive ./...
in your workspace folder
This method will be generated for deriveContains:
func deriveContainsFoo(list []Foo, item Foo) bool {
for _, v := range list {
if v == item {
return true
}
}
return false
}
Goderive has support for quite some other useful helper methods to apply a functional programming style in go.
Complementing @Adolfo's answer (and other answers here), the Contains function won't be something experimental anymore. Starting with GO v1.21, which will be released during August 2023, the aforementioned slice
package will be included into the core library (besides some other interesting packages like map
and cmp
), making it possible to run a linear search over a slice of elements (O(N) time complexity).
Additionally you will have some other interesting variations for searching an element (or elements) within a slice, like the new ContainsFunc, which reports whether at least one element e
of s satisfies f(e)
. You can check this at the example below, which is taken from the actual docs:
package main
import (
"fmt"
"slices"
)
func main() {
numbers := []int{0, 42, -10, 8}
hasNegative := slices.ContainsFunc(numbers, func(n int) bool {
return n < 0
})
fmt.Println("Has a negative:", hasNegative)
hasOdd := slices.ContainsFunc(numbers, func(n int) bool {
return n%2 != 0
})
fmt.Println("Has an odd number:", hasOdd)
}
Also, to keep in mind, if you are working with a sorted slice and you want to reduce the time complexity when searching for an element (O(logN)), you will also be able to use the BinarySearch
and the BinarySearchFunc
functions, which will also come with this new package.
Finally, if you want to make the search constant in time (O(1)), I would go for the approach suggested by @tux21b in the voted answer by using maps.
The go style:
func Contains(n int, match func(i int) bool) bool {
for i := 0; i < n; i++ {
if match(i) {
return true
}
}
return false
}
s := []string{"a", "b", "c", "o"}
// test if s contains "o"
ok := Contains(len(s), func(i int) bool {
return s[i] == "o"
})
-
3This does not answer the question, nor gives additional information.– CroolmanNov 15, 2019 at 12:13
If you have a byte
slice, you can use bytes
package:
package main
import "bytes"
func contains(b []byte, sub byte) bool {
return bytes.Contains(b, []byte{sub})
}
func main() {
b := contains([]byte{10, 11, 12, 13, 14}, 13)
println(b)
}
Or suffixarray
package:
package main
import "index/suffixarray"
func contains(b []byte, sub byte) bool {
return suffixarray.New(b).Lookup([]byte{sub}, 1) != nil
}
func main() {
b := contains([]byte{10, 11, 12, 13, 14}, 13)
println(b)
}
If you have an int
slice, you can use intsets
package:
package main
import "golang.org/x/tools/container/intsets"
func main() {
var s intsets.Sparse
for n := 10; n < 20; n++ {
s.Insert(n)
}
b := s.Has(16)
println(b)
}
func contains(slice []string, item string) bool {
for _, s := range slice {
if s == item {
return true
}
}
return false
}
I created the following Contains function using reflect package. This function can be used for various types like int32 or struct etc.
// Contains returns true if an element is present in a slice
func Contains(list interface{}, elem interface{}) bool {
listV := reflect.ValueOf(list)
if listV.Kind() == reflect.Slice {
for i := 0; i < listV.Len(); i++ {
item := listV.Index(i).Interface()
target := reflect.ValueOf(elem).Convert(reflect.TypeOf(item)).Interface()
if ok := reflect.DeepEqual(item, target); ok {
return true
}
}
}
return false
}
Usage of contains function is below
// slice of int32
containsInt32 := Contains([]int32{1, 2, 3, 4, 5}, 3)
fmt.Println("contains int32:", containsInt32)
// slice of float64
containsFloat64 := Contains([]float64{1.1, 2.2, 3.3, 4.4, 5.5}, 4.4)
fmt.Println("contains float64:", containsFloat64)
// slice of struct
type item struct {
ID string
Name string
}
list := []item{
item{
ID: "1",
Name: "test1",
},
item{
ID: "2",
Name: "test2",
},
item{
ID: "3",
Name: "test3",
},
}
target := item{
ID: "2",
Name: "test2",
}
containsStruct := Contains(list, target)
fmt.Println("contains struct:", containsStruct)
// Output:
// contains int32: true
// contains float64: true
// contains struct: true
Please see here for more details: https://github.com/glassonion1/xgo/blob/main/contains.go
There are several packages that can help, but this one seems promising:
https://github.com/wesovilabs/koazee
var numbers = []int{1, 5, 4, 3, 2, 7, 1, 8, 2, 3}
contains, _ := stream.Contains(7)
fmt.Printf("stream.Contains(7): %v\n", contains)
It might be considered a bit 'hacky' but depending the size and contents of the slice, you can join the slice together and do a string search.
For example you have a slice containing single word values (e.g. "yes", "no", "maybe"). These results are appended to a slice. If you want to check if this slice contains any "maybe" results, you may use
exSlice := ["yes", "no", "yes", "maybe"]
if strings.Contains(strings.Join(exSlice, ","), "maybe") {
fmt.Println("We have a maybe!")
}
How suitable this is really depends on the size of the slice and length of its members. There may be performance or suitability issues for large slices or long values, but for smaller slices of finite size and simple values it is a valid one-liner to achieve the desired result.
-
Will not work for situation where elements have similar text but not exactly the same
exSlice := ["yes and no", "maybe", "maybe another"]
Apr 21, 2020 at 18:41 -
2This is a rather nice approach for achieving a quick-and-dirty one-liner solution. You just need to require an unambiguous delimiter (could be a comma) and do the extra work to bracket both strings:
","+strings.Join(exSlice,",")+","
, and",maybe,"
Jun 21, 2020 at 13:27