golang container package

container package

golang에는 빌트인으로 사용할 수 있는 container package가 있다.

개발을 하다보면, 자료구조를 사용할 일이 꽤 생긴다.

go에서는 container 패키지에서 기본 자료구조를 제공해주므로 꽤나 편리하게 사용할 수 있다.

패키지에서 제공하는 자료구조는 다음과 같다.

• Linked list

• Heap

• Ring (Circular list)

container 패키지를 이용해서 간단한 자료구조를 구현해보자.

container/list

package main

import (
	"container/list"
	"log"
)

func main() {
	lst := list.New()
	lst.PushBack(1)
	lst.PushBack(2)
	lst.PushBack(3)

	log.Println(lst.Len())
}

위와 같이 container/list 패키지를 import하면, 손쉽게 linked list를 사용할 수 있다.

개발을 하면서 linked list를 사용해야 한다면, 꽤나 시간을 단축시킬 수 있을 것이다.

list를 순회하고 싶다면 아래와 같은 방법도 가능하다.

package main

import (
	"container/list"
	"fmt"
	"log"
)

func main() {
	lst := list.New()
	lst.PushBack(1)
	lst.PushBack(2)
	lst.PushBack(3)

	log.Println(lst.Len())

	for e := lst.Front(); e != nil; e = e.Next() { // 연결 리스트의 맨 앞부터 끝까지 순회
		fmt.Println(e.Value)
	}
}

container/heap

다음은 heap 패키지이다. 필자는 최근 회사에서 체결엔진/오더북을 구현하면서 min heap과 max heap을 구현할 일이 있었는데,

container/heap 패키지를 통해 간단하게 구현할 수 있었다.

heap 패키지에서는 기본적으로 다음과 같은 인터페이스가 필요하다.

package heap 

type Interface interface {
	Len() int
	Less(i, j int) bool
	Swap(i, j int)
	Push(x any)
	Pop() any  
}

한 번 구현해서 사용해보자. 예제에서는 min heap을 구현해본다.

package main

import (
	"container/heap"
	"log"
)

type IMinHeap interface {
	heap.Interface
}

type MinHeap struct {
	heap []uint
}

func (m *MinHeap) Len() int {
	return len(m.heap)
}

func (m *MinHeap) Less(i, j int) bool {
	return m.heap[i] < m.heap[j]
}

func (m *MinHeap) Swap(i, j int) {
	m.heap[i], m.heap[j] = m.heap[j], m.heap[i]
}

func (m *MinHeap) Push(x any) {
	m.heap = append(m.heap, x.(uint))
}

func (m *MinHeap) Pop() any {
	old := m.heap
	n := len(old)
	element := old[n-1]
	m.heap = old[0 : n-1]
	return element
}

func main() {
	minHeap := &MinHeap{heap: []uint{}}

	heap.Init(minHeap)

	heap.Push(minHeap, uint(10))
	heap.Push(minHeap, uint(20))
	heap.Push(minHeap, uint(50))
	heap.Push(minHeap, uint(5))

	log.Println(heap.Pop(minHeap)) // 5
	log.Println(heap.Pop(minHeap)) // 10
	log.Println(heap.Pop(minHeap)) // 20
	log.Println(heap.Pop(minHeap)) // 50
}

Less 조건의 부호만 반대로 바꿔줘도 max heap으로 바꾸어 사용할 수 있어 편하다.

container/ring

다음은 ring이다. ring은 비교적 사용할 일이 많이 없는 듯 보이지만, 알아두면 때때로 도움이 될 수도 있다.

개인적으로는 list를 쓰는 편이긴 하다.

package main

import (
	"container/ring"
	"fmt"
)

func main() {
	data := []string{"Maria", "John", "Andrew", "James"}
	r := ring.New(len(data))       // 노드의 개수를 지정하여 링 생성
	for i := 0; i < r.Len(); i++ { // 링 노드 개수만큼 반복
		r.Value = data[i] // 링의 노드에 값 넣기
		r = r.Next()      // 다음 노드로  이동
	}

	r.Do(func(x interface{}) { // 링의 모든 노드 순회
		fmt.Println(x)
	})

	// "Maria" 
	// "John" 
	// "Andrew"
	// "James"
}

두 개의 ring을 연결하는 것도 물론 가능하다.

package main

import (
	"container/ring"
	"fmt"
)

func main() {
	data := []string{"Maria", "John", "Andrew", "James"}
	r := ring.New(len(data))       // 노드의 개수를 지정하여 링 생성
	for i := 0; i < r.Len(); i++ { // 링 노드 개수만큼 반복
		r.Value = data[i] // 링의 노드에 값 넣기
		r = r.Next()      // 다음 노드로  이동
	}

	r.Do(func(x interface{}) { // 링의 모든 노드 순회
		fmt.Println(x)
	})

	// "Maria" 
	// "John" 
	// "Andrew"
	// "James"

	newData := []uint{1, 2, 3, 4}

	r2 := ring.New(len(newData))
	for i := 0; i < r2.Len(); i++ { // 링 노드 개수만큼 반복
		r2.Value = newData[i] // 링의 노드에 값 넣기
		r2 = r2.Next()        // 다음 노드로  이동
	}

	r3 := r.Link(r2)

	r3.Do(func(x interface{}) { // 링의 모든 노드 순회
		fmt.Println(x)
	})
	// John
	// Andrew
	// James
	// Maria
	// 1
	// 2
	// 3
	// 4
}