为什么我们没有一个固定的数据结构

我正在尝试解决“go编程语言”练习#1.4，这需要我有一套。我可以创建一个集合类型，但为什么语言不附带一个?Go语言起源于谷歌(番石榴也起源于谷歌)，为什么语言设计者不选择增加对基本数据结构的支持呢?为什么要强迫用户为像集合这样基本的东西创建自己的实现呢?

185114 次浏览
小开

部分原因是Go没有泛型(所以每种类型都需要一个集合类型，或者退回到反射，这是相当低效的)。

部分原因是，如果你所需要的只是“向一个集合中添加/删除单个元素”和“相对节省空间”，你可以通过使用map[yourtype]bool(并将集合中的任何元素的值设置为true)来获得相当多的空间效率，或者为了提高空间效率，你可以使用一个空结构体作为值，并使用_, present = the_setoid[key]来检查是否存在。

小开

一个原因是很容易从map创建一个set:

s := map[int]bool{5: true, 2: true}
_, ok := s[6] // check for existence
s[8] = true // add element
delete(s, 2) // remove element

联盟

s_union := map[int]bool{}
for k, _ := range s1{
s_union[k] = true
}
for k, _ := range s2{
s_union[k] = true
}

十字路口

s_intersection := map[int]bool{}
if len(s1) > len(s2) {
s1, s2 = s2, s1 // better to iterate over a shorter set
}
for k,_ := range s1 {
if s2[k] {
s_intersection[k] = true
}
}

实现所有其他set操作并不难。

小开

就像Vatine写的那样:由于go缺乏泛型，它必须成为语言的一部分，而不是标准库。为此，你将不得不污染语言的关键字集，联合，交集，差异，子集…

另一个原因是，我们根本不清楚集合的“正确”实现是什么:

  1. 有一个函数式的方法:

    func IsInEvenNumbers(n int) bool {
if n % 2 == 0 {
return true
}
return false
}

This is a set of all even ints. It has a very efficient lookup and union, intersect, difference and subset can easily be done by functional composition.

  1. Or you do a has-like approach like Dali showed.

A map does not have that problem, since you store something associated with the value.

小开

另一种可能是使用位集，至少有一个包，或者你可以使用内置的大包。在这种情况下，基本上需要定义一种将对象转换为索引的方法。


提交答案