algorithm - Go 中的容器类型

Question

我试图让自己熟悉 Go，因此试图实现一些搜索功能，但查看容器类型的文档，没有一个内置类型实现contains方法。我是否遗漏了什么，如果没有，我该如何进行会员资格测试？我必须实现自己的方法还是必须遍历所有元素。如果是这样，那么省略这种容器类型的基本方法背后的基本原理是什么？

Answer 1

标准库的容器类型要求您在拉出元素时进行类型断言。容器本身无法对成员资格进行测试，因为它们不知道它们所包含的类型并且无法进行比较。

Ric Szopa 的跳过列表实现可能正是您想要的。它有一个 Set 类型，它实现了 Contains 方法。

https://github.com/ryszard/goskiplist

我一直在生产中使用它并且对它非常满意。

Answer 2

地图是一种内置类型，它具有“包含”结构，而不是方法。

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

package main

import (
    "fmt"
)

func main() {
    a := map[string]string{"foo": "bar"}
    _, k := a["asd"]
    fmt.Println(k)
    _, k = a["foo"]
    fmt.Println(k)
}

Answer 3

使用 container/list 包，您可以编写自己的循环来搜索事物。正如 Dystroy 所说，没有在包中提供这个的原因可能是隐藏了 O(n) 操作。

您无法添加方法，因此您只需编写一个循环。

for e := l.Front(); e != nil; e = e.Next() {
    data := e.Value.(dataType) // type assertion
    if /* test on data */ {
        // do something
        break
    }
}

它很简单，O(n) 复杂度是显而易见的。

In your review of data structures supplied with Go that support searching, don't miss the sort package. Functions there allow a slice to be sorted in O(n log(n)) and then binary searched in O(log(n)) time.

Finally as Daniel suggested, consider third-party packages. There are some popular and mature packages for container types.