Go数据结构备忘单

一些公司采访在线写作代码。 需要解决奥林匹克竞赛的速度问题。 在这种情况下，没有时间查看数据结构实现的详细信息-您需要立即意识到这一点。 但是有关算法和数据结构的课程提供了伪代码或C ++的示例。 有关问题的更多参考解决方案通常用C ++编写。 在准备采访时，我做了一个婴儿床，例如STL容器，以免浪费宝贵的时间。

让我们从显而易见的地方开始。

动态连续阵列

模拟std::vector 。
支持在几个处理器周期的恒定时间内按索引访问元素。 您可以增加或减少容量。 这是内置切片：

 vector := []int{} 

方便地，基本概念已内置到该语言中。

叠放

类似std::stack 。

从一端完成添加新元素并删除现有元素的有序集合。 最后被放置的元素（后进先出-LIFO）首先从堆栈中删除。 这又是一个有围墙的切片。 片段在项目之间复制：

 // Push stack = append(stack, value) 

 // Pop // ,  len(stack) > 0 stack, value = a[:len(stack)-1], a[len(stack)-1] 

切片操作不会分配新的内存。

列

类似std::queue和std::deque 。

队列以恒定的时间实现开始和结束的检索和添加操作。 首先从队列中删除首先放置的元素（先进先出-FIFO）。 缓冲通道是环形缓冲区上的队列，您可以在读取器和写入器是不同的goroutines时使用它。 但是标准库中没有单独的队列实现。 很棒的清单建议该库https://github.com/gammazero/deque 。

 import "github.com/gammazero/deque" 

正在进行的操作：

 func (q *Deque) PushBack(elem interface{}) func (q *Deque) PushFront(elem interface{}) func (q *Deque) PopBack() interface{} func (q *Deque) PopFront() interface{} func (q *Deque) Back() interface{} func (q *Deque) Front() interface{} func (q *Deque) At(i int) interface{} 

双链表

类似于std::list 。
它包含一些元素，这些元素除了包含自己的数据外，还包含指向下一个和上一个列表项的链接。 它在标准库中：

 import "container/list" 

如预期的那样，它支持插入操作（在元素的开头，结尾，元素之前和之后，传递对象的指针）和删除操作。

 func (l *List) PushBack(v interface{}) *Element func (l *List) PushFront(v interface{}) *Element func (l *List) InsertAfter(v interface{}, mark *Element) *Element func (l *List) InsertBefore(v interface{}, mark *Element) *Element func (l *List) Remove(e *Element) interface{} 

Go不为迭代器提供特定的语法。 因此，可以从指向任何节点的指针获得下一个/上一个元素。 在将项目添加/删除到列表中之后，这些方法不会变差，不会感到惊讶。

 func (e *Element) Next() *Element func (e *Element) Prev() *Element 

优先队列

模拟std::priority_queue
允许您以任何顺序堆叠项目，并随时获得剩余项目的最高优先级。 例如，在用于构建最小生成树的算法中使用了该算法，当在下一步中，该算法选择所有一端中已经覆盖的顶点处的最短边缘时。

标准库具有一个适配器，该适配器可将任何可排序的容器（实现sort.Interface ）转换为优先级队列。

 import "container/heap" 

这是经典的二进制堆 。 在O中实现插入和删除（日志n）。

 func Pop(h Interface) interface{} func Push(h Interface, x interface{}) func Remove(h Interface, i int) interface{} 

哈希表

它是一个字典和一个关联数组。

模拟std::unordered_map 。

允许您添加键值，按键删除值，并检查平均是否存在O（1）元素。 显然，地图内置于语言中：

 unorderedMap := make(map[string]int) 

make（map）的结果是一个指针，其工作方式与标准容器略有不同：

 //  : _, ok := unorderedMap["route"] //  : delete(unorderedMap, "route") //  : n := len(unorderedMap) 

“运行时/映射”与std :: unordered_map不同，它负责程序员-在迭代过程中删除值是安全的。

许多

模拟std::unordered_set
与哈希表几乎相同，但不保存值。
如果仅需要快速进入检查，则可以再次使用内置地图。 只需指定一个空值即可表明只有键很重要。

 var m = make(map[string]struct{}) m["!"] = struct{}{} _, ok := m["!"] // true 

但是此实现不支持复杂的运算符。 要合并，相交，区别框内的差异，您需要第三方库。 从星数来看，最常用的是： https : //github.com/deckarep/golang-set

 import "github.com/deckarep/golang-set" 

API最需要的部分：

 Add(i interface{}) bool Remove(i interface{}) Cardinality() int // len() Contains(i ...interface{}) bool IsSubset(other Set) bool Intersect(other Set) Set Union(other Set) Set Difference(other Set) Set SymmetricDifference(other Set) Set 

设置int

在标准库的实验部分，有一个优化的set int，它可以节省每一位。

 import "golang.org/x/tools/container/intsets" 

它还支持联合，相交，集合差异。

二叉搜索树

类似物std::set和std::map 。
哈希表似乎是一个新手不好的新手：
还支持添加，删除和检查事件，但不超过O（log n）。
但是树存储按键排序的节点。

标准go库中没有树，包含AVL，红黑和B树的存储库被广泛使用。

 import "github.com/emirpasic/gods/trees/avltree" 

最常用的API方法：

 func (tree *Tree) Get(key interface{}) (value interface{}, found bool) func (tree *Tree) Put(key interface{}, value interface{}) func (tree *Tree) Remove(key interface{}) func (tree *Tree) Size() int func (tree *Tree) Keys() []interface{} func (tree *Tree) Values() []interface{} func (tree *Tree) Left() *Node func (tree *Tree) Right() *Node 

有两种特别重要的树方法：

 func (tree *Tree) Ceiling(key interface{}) (ceiling *Node, found bool) 

返回大于键的最小现有项。

 func (tree *Tree) Floor(key interface{}) (floor *Node, found bool) 

返回小于键的现有最大元素。

相对而言，这些任务通常在访谈中找到。 在现实生活中，它用于数据库索引：

 select x from table where x <= $1 limit 1; 

如果有索引，它将对O（log n）有效，对B树中的边界进行1次搜索。

布隆过滤器

但是stl中的数据结构不是。
像哈希表一样，它允许您检查元素是否属于集合。 但是过滤器在添加时不存储键，并占用恒定的内存量。 可能会收到错误的肯定响应（集合中没有元素，但数据结构报告它是正确的），但不会收到错误的否定响应。 它用作过滤器以快速切断几乎所有不存在的密钥，从而节省了更昂贵的验证，例如，从磁盘读取或向数据库发出请求。
有一个第三方库： https : //github.com/willf/bloom

 import "github.com/willf/bloom" 

不太常用，您可以查看API 。

超级日志

标准的C ++库中没有这样的东西。

概率数据结构。 误差很小（≈0.4％）时，它会考虑不存储键本身的唯一元素的数量。 它节省了大量内存。 如果任务是快速计算访问者或请求的数量，那么HyperLogLog是理想的选择。

现在最受欢迎的库。

https://github.com/axiomhq/hyperloglog

 import "github.com/axiomhq/hyperloglog" 

排序

类似物std::sort和std::stable_sort 。
从消费者的角度来看，只有两种根本不同的类型：
稳定（不要更改相等元素的顺序[[4，0]，[1、2]，[1、1]，[5、6]]-> [[1、2]，[1、1]，[4 ，0]，[5，6]]）
并且不稳定，不能保证其余字段的一致性。
两者都在标准库中：

 func Sort(data Interface) 

这是一个Hoar快速排序实现，不稳定。 但是对于长度小于12的部分，堆排序被用作优化。

 func Stable(data Interface) 

在内部，这是一种合并排序，但是为了提高效率，当递归算法到达少于20个元素的块时，将使用插入排序。

这些是适用于O（n log n）的经典算法。

如果您阅读了，那么恭喜您。 了解特定的API有助于解决测试问题。 （如果您使用过某些东西，并且知道最佳选择，请在评论中写。