Golang Set: map[T]struct{}, 집합 연산, 제네릭 Set

관용구: 값이 빈 맵

Go에는 set 키워드도 없고 표준 라이브러리에 집합도 없습니다. 원소를 키로 삼고 값에는 아무것도 담지 않는 맵으로 충분합니다.

package main

import "fmt"

func main() {
	tags := map[string]struct{}{}

	// add
	tags["go"] = struct{}{}
	tags["backend"] = struct{}{}
	tags["go"] = struct{}{} // adding again changes nothing

	// has
	_, ok := tags["go"]
	fmt.Println("has go:", ok)

	// remove
	delete(tags, "backend")

	// size
	fmt.Println("size:", len(tags))

	for t := range tags {
		fmt.Println("member:", t)
	}
}

struct{}는 빈 구조체 타입이고 struct{}{}는 그 유일한 값입니다. 0바이트를 차지하므로 맵은 키만 저장합니다.

맵의 규칙이 모두 적용됩니다. 키는 비교 가능해야 하고, 순회 순서는 무작위이며, nil 맵에 쓰면 패닉이 나고, 동시에 쓰려면 잠금이 필요합니다. 각각은 맵 페이지에서 다룹니다.

map[T]struct{}와 map[T]bool

다른 흔한 표기는 map[T]bool입니다. 없는 키가 false를 반환하므로 더 잘 읽힙니다:

seen := map[string]bool{}
seen["a"] = true
if seen["a"] { ... }

장단점은 다음과 같습니다:

많은 코드베이스가 빈 구조체를 선호하는 진짜 이유는 세 번째 행입니다. bool을 쓰면 언젠가 누군가 s[k] = false라고 쓰고, 그때부터 len(s)는 원소 개수가 아니게 됩니다. 작은 집합에서는 메모리 차이가 문제되지 않습니다.

슬라이스에서 중복 제거하기

집합의 가장 흔한 용도는 중복 제거입니다. 다음 코드는 각 값이 처음 나온 것을 남기고 순서를 유지합니다:

package main

import (
	"fmt"
	"slices"
)

func unique[T comparable](in []T) []T {
	seen := make(map[T]struct{}, len(in))
	out := make([]T, 0, len(in))
	for _, v := range in {
		if _, ok := seen[v]; ok {
			continue
		}
		seen[v] = struct{}{}
		out = append(out, v)
	}
	return out
}

func main() {
	fmt.Println(unique([]string{"b", "a", "b", "c", "a"}))
	fmt.Println(unique([]int{3, 1, 3, 3, 2}))

	// If order does not matter: sort, then drop adjacent duplicates.
	s := []int{3, 1, 3, 3, 2}
	slices.Sort(s)
	fmt.Println(slices.Compact(s))
}

출력:

[b a c]
[3 1 2]
[1 2 3]

합집합, 교집합, 차집합

집합 연산은 반복문 몇 개면 됩니다. 조회는 평균적으로 상수 시간이므로, 다른 집합에 포함되는지 확인할 때는 작은 집합을 순회하세요.

package main

import (
	"fmt"
	"maps"
	"slices"
)

type set map[string]struct{}

func of(items ...string) set {
	s := make(set, len(items))
	for _, it := range items {
		s[it] = struct{}{}
	}
	return s
}

func union(a, b set) set {
	out := maps.Clone(a)
	for k := range b {
		out[k] = struct{}{}
	}
	return out
}

func intersect(a, b set) set {
	if len(a) > len(b) {
		a, b = b, a
	}
	out := set{}
	for k := range a {
		if _, ok := b[k]; ok {
			out[k] = struct{}{}
		}
	}
	return out
}

func difference(a, b set) set {
	out := set{}
	for k := range a {
		if _, ok := b[k]; !ok {
			out[k] = struct{}{}
		}
	}
	return out
}

func sorted(s set) []string {
	return slices.Sorted(maps.Keys(s))
}

func main() {
	backend := of("go", "sql", "docker", "linux")
	devops := of("docker", "linux", "terraform")

	fmt.Println("union:     ", sorted(union(backend, devops)))
	fmt.Println("intersect: ", sorted(intersect(backend, devops)))
	fmt.Println("backend-only:", sorted(difference(backend, devops)))
}

sorted는 출력을 안정적으로 만들기 위해서만 있습니다. 집합을 range로 순회해 출력하면 실행할 때마다 순서가 달라집니다. maps.Keys와 slices.Sorted는 Go 1.23이 필요합니다.

type set map[string]struct{} 같은 이름 있는 타입도 여전히 맵입니다. 인덱싱, range, delete를 똑같이 쓸 수 있고, 메서드도 붙일 수 있습니다.

작은 제네릭 Set

제네릭(Go 1.18)을 쓰면 타입 하나로 비교 가능한 모든 원소 타입을 다룰 수 있습니다. 대부분의 프로그램에는 이 정도면 충분합니다:

package main

import (
	"cmp"
	"fmt"
	"maps"
	"slices"
)

type Set[T comparable] struct {
	m map[T]struct{}
}

func NewSet[T comparable](items ...T) *Set[T] {
	s := &Set[T]{m: make(map[T]struct{}, len(items))}
	for _, it := range items {
		s.Add(it)
	}
	return s
}

func (s *Set[T]) Add(v T)    { s.m[v] = struct{}{} }
func (s *Set[T]) Remove(v T) { delete(s.m, v) }
func (s *Set[T]) Len() int   { return len(s.m) }
func (s *Set[T]) Has(v T) bool {
	_, ok := s.m[v]
	return ok
}

func (s *Set[T]) Union(o *Set[T]) *Set[T] {
	out := &Set[T]{m: maps.Clone(s.m)}
	for v := range o.m {
		out.Add(v)
	}
	return out
}

// Sorted is a free function because it needs a stricter constraint than the type.
func Sorted[T cmp.Ordered](s *Set[T]) []T {
	return slices.Sorted(maps.Keys(s.m))
}

func main() {
	a := NewSet(1, 2, 3)
	b := NewSet(3, 4)
	a.Add(2)
	fmt.Println(a.Len(), a.Has(2), a.Has(9))

	u := a.Union(b)
	fmt.Println(Sorted(u))

	words := NewSet("go", "rust")
	words.Remove("rust")
	fmt.Println(Sorted(words))
}

맵을 구조체로 감싸면 struct{}{}라는 잡음이 가려지고, 생성자가 맵을 반드시 만들어 주므로 nil 맵 패닉도 사라집니다. Sorted는 메서드가 될 수 없습니다. 메서드는 자기만의 타입 매개변수를 선언하거나 타입의 comparable 제약을 좁힐 수 없는데, 정렬에는 cmp.Ordered가 필요하기 때문입니다. 제약은 제네릭 페이지에서 설명합니다.

기능이 풍부한 집합(스레드 안전 변형, 다양한 연산)이 필요하다면 github.com/deckarep/golang-set 같은 서드파티 패키지가 있습니다. 대부분의 코드에서 Go 개발자들은 맵 관용구나 이 정도의 30줄짜리 타입을 씁니다.

구조체 집합

비교 가능한 타입이라면 무엇이든 원소가 될 수 있고, 비교 가능한 필드로 된 구조체도 마찬가지입니다. 그래서 "이 쌍을 본 적이 있나" 같은 확인을 바로 할 수 있습니다:

type edge struct{ from, to string }
visited := map[edge]struct{}{}
visited[edge{"a", "b"}] = struct{}{}

슬라이스와 맵은 집합의 원소가 될 수 없습니다. 고유한 슬라이스를 추적하려면 먼저 각 슬라이스를 비교 가능한 키로 바꾸세요. 예를 들어 고정 크기 배열이나 fmt.Sprint로 만든 문자열을 쓸 수 있습니다.

흔한 실수

• 초기화를 잊음. var s map[string]struct{}는 nil이라서 처음 추가할 때 패닉이 납니다.
• 집합을 출력하면서 안정적인 출력을 기대함. 원소를 먼저 정렬하세요.
• map[T]bool을 쓰면서 false를 저장함. 그러면 len이 더 이상 원소 개수를 세지 않습니다. 제거할 때는 delete를 쓰세요.