Cheat Sheet by Data Structures in Go

Some companies conduct interviews with online code writing. It is required to solve the speed Olympiad puzzle. In such circumstances, there is no time to look at the details of the implementation of data structures - you need to immediately implement the idea. But courses on algorithms and data structures provide examples in either pseudocode or C ++. Also, reference problem solutions are often written in C ++. In preparation for the interview, I compiled a crib of libraries - analogous to STL containers, so as not to waste precious time searching.

Let's start with the obvious.

Dynamic continuous array

Analog std::vector .
Supports accessing an item by index for a constant time of several processor cycles. You can increase or decrease capacity. This is a built-in slice:

 vector := []int{} 

Conveniently, basic concepts are built into the language.
')

Stek

Analog std::stack .

An ordered set in which new items are added and existing ones are removed from one end. The first item from the stack is the item that was placed there last (last-in, first-out - LIFO). This is again built in slice. Snippets are copied from project to project:

 // Push stack = append(stack, value) 

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

The slice operation does not allocate a new memory.

Turn

Analog std::queue and std::deque .

The queues implement extract and add operations to start and end in constant time. The first element in the queue is the element that was first placed (first-in, first-out - FIFO). The buffered channel is a queue on the ring buffer; you can use it when the reader and the writer are different mountain types. But there is no separate queue implementation in the standard library. The awesome-go list advises the https://github.com/gammazero/deque library.

 import "github.com/gammazero/deque" 

Realized operations:

 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{} 

Doubly linked list

Analog std::list .
It consists of elements that contain, in addition to their own data, references to the next and previous element of the list. It is in the standard library:

 import "container/list" 

As expected, it supports insert operations (at the beginning, at the end, before and after the element whose pointer is passed) and deletes.

 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 does not provide specific syntax for iterators. Therefore, the next / previous element can be obtained from a pointer to any node. These methods do not foul after adding / removing an item to the list, without surprises.

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

Priority queue

Analog std::priority_queue
Allows you to add items in any order, and get at any time the most priority of the remaining. It is used, for example, in the algorithm for constructing a minimal spanning tree, when at the next step the algorithm chooses the shortest edge of all, with one end beginning at the already covered vertices.

In the standard library there is an adapter that turns any sortable container (implementing sort.Interface ) into a priority queue.

 import "container/heap" 

This is a classic binary heap . Implements insert and delete in O (log n).

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

Hash table

It is a dictionary and associative array.

Analog std::unordered_map .

It allows you to add a key-value, delete a value by a key, and check the presence of an element beyond O (1) on average. Obviously, the map is built into the language:

 unorderedMap := make(map[string]int) 

The result of make (map) is a pointer, and the way it works is slightly different from standard containers:

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

“Runtime / map”, unlike std :: unordered_map, takes care of the programmer — it's safe to delete values ​​during iteration over them.

Lots of

Analog std::unordered_set .
Almost the same as the hash table, but without saving the value.
If we only need a quick entry check, then the built-in map can be used again. You only need to specify an empty value to indicate that only the key is important.

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

But this implementation does not support complex operators. To merge, intersect, the difference out of the box, you need third-party libraries. The most used, judging by the number of stars: https://github.com/deckarep/golang-set

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

The most necessary part of the 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 

Set int

In the experimental part of the standard library there is an optimized plurality of int that saves every bit.

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

It also supports union, intersection, set difference.

Binary Search Trees

Analogs std::set and std::map .
A newbie may seem like bad counterparts in hash tables:
also support adding, deleting and checking the entry, but beyond O (log n).
But trees keep nodes sorted by key.

There are no trees in the standard go library, a repository containing AVL, Red-Black and B-trees is widely used.

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

Commonly used API methods:

 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 

There are two particularly important tree methods:

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

returns the smallest existing item more than the key.

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

returns the largest existing element less than the key.

Tasks for this relatively often come across in interviews. In real life it is used in database indexes:

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

If there is an index, it will work for O (log n), for 1 search for the boundary in the B-tree.

Bloom filter

But this data structure in stl no.
Like a hash table, it allows you to check whether an element belongs to a set. But the filter does not store keys when added, and takes a constant amount of memory. It is possible to get a false positive response (there is no element in the set, but the data structure reports that it exists), but not a false negative. It is used as a filter to quickly cut off almost all non-existing keys, saving more expensive checks, such as reading from disk or making a query to the database.
There is a third-party library: https://github.com/willf/bloom

 import "github.com/willf/bloom" 

Not so often used, the API can and peep.

HyperLogLog

In the standard C ++ library there is no such thing.

Probabilistic data structure. With a small error (≈ 0.4%), he considers the number of unique elements without storing the keys themselves. Gives huge memory savings. If the task is to quickly calculate the number of visitors or requests - HyperLogLog fits perfectly.

The most popular library for this now.

https://github.com/axiomhq/hyperloglog

 import "github.com/axiomhq/hyperloglog" 

Sorting

Analogs std::sort and std::stable_sort .
From a consumer point of view, there are only 2 fundamentally different types:
Stable (do not change the order of equal elements [[4, 0], [1, 2], [1, 1], [5, 6]] - [[1, 2], [1, 1], [4 , 0], [5, 6]])
and not stable, not giving a guarantee for the sequence of other fields.
Both are in the standard library:

 func Sort(data Interface) 

This is the implementation of quick sorting Hoare, unstable. But for sections of length <12, heap sorting is used as optimization.

 func Stable(data Interface) 

Inside it is merge sorted, but, for efficiency, when the recursive algorithm reaches less than 20 elements, sorting by inserts is used.

These are the classic algorithms that work for O (n log n).

If you read it - congratulations. Knowledge of specific APIs helps in solving test problems. (If you have worked with something and know the best alternatives - write in the comments.