Почему в Go нет встроенного типа данных "множество" (Set) и как его реализовать?

Почему в Go нет встроенного Set?

Разработчики Go (Грисс, Пайк, Томпсон) руководствовались принципом минимализма и практичности. Они считали, что map[T]struct{} — это достаточно элегантная и эффективная реализация множества, которая не требует отдельного типа в языке. Основные причины:

• Избежание дублирования: map уже предоставляет хеш-таблицу с O(1) доступом. Set — это та же хеш-таблица, но без значений. Зачем два типа, если один можно использовать как другой?
• Простота спецификации: Каждый новый тип усложняет язык, компилятор и документацию. Go стремится к минимальному набору концепций.
• Прозрачность: map[T]struct{} явно показывает, что вы используете хеш-таблицу. Нет магии — вы контролируете поведение.
• Исторический контекст: Когда создавался Go (2007-2009), дженериков не было. Сделать типобезопасный Set без дженериков было бы очень громоздко (пришлось бы использовать interface{} и приведение типов).

Правильная реализация множества в Go (до дженериков)

Стандартный идиоматический подход — использовать map[T]struct{}. Почему struct{}{}, а не bool?

• struct{}{} занимает 0 байт в памяти, в то время как bool — 1 байт.
• Это явно показывает намерение: "мне не нужно значение, только ключ".

package main

import "fmt"

func main() {
    // Создаем множество целых чисел
    set := make(map[int]struct{})

    // Добавляем элементы
    set[1] = struct{}{}
    set[2] = struct{}{}
    set[3] = struct{}{}
    set[1] = struct{}{} // дубликат игнорируется

    // Проверка вхождения
    if _, exists := set[2]; exists {
        fmt.Println("2 есть в множестве")
    }

    // Удаление
    delete(set, 2)

    // Размер
    fmt.Println("Размер:", len(set)) // 2

    // Итерация
    for key := range set {
        fmt.Println(key)
    }
}

Современный подход (Go 1.18+ с дженериками)

С появлением дженериков можно создать типобезопасную обертку:

package main

import "fmt"

// Set — обобщенное множество
type Set[T comparable] struct {
    items map[T]struct{}
}

// NewSet создает новое множество
func NewSet[T comparable]() *Set[T] {
    return &Set[T]{items: make(map[T]struct{})}
}

// Add добавляет элемент
func (s *Set[T]) Add(item T) {
    s.items[item] = struct{}{}
}

// Remove удаляет элемент
func (s *Set[T]) Remove(item T) {
    delete(s.items, item)
}

// Contains проверяет наличие
func (s *Set[T]) Contains(item T) bool {
    _, exists := s.items[item]
    return exists
}

// Size возвращает размер
func (s *Set[T]) Size() int {
    return len(s.items)
}

// ToSlice конвертирует в срез
func (s *Set[T]) ToSlice() []T {
    result := make([]T, 0, len(s.items))
    for item := range s.items {
        result = append(result, item)
    }
    return result
}

func main() {
    intSet := NewSet[int]()
    intSet.Add(1)
    intSet.Add(2)
    intSet.Add(1) // игнорируется
    fmt.Println(intSet.Contains(1)) // true
    fmt.Println(intSet.ToSlice())   // [1 2] (порядок не гарантируется)

    stringSet := NewSet[string]()
    stringSet.Add("hello")
    stringSet.Add("world")
    fmt.Println(stringSet.ToSlice()) // [hello world]
}

Библиотеки для продвинутого использования

Если вам нужны дополнительные операции (объединение, пересечение, разность), рекомендую:

• golang.org/x/exp/maps — экспериментальная библиотека с утилитами для map.
• github.com/deckarep/golang-set — популярная библиотека с потокобезопасными множествами.
• github.com/emirpasic/gods — коллекция структур данных, включая HashSet.

Итог: В Go нет отдельного типа Set по идеологическим причинам, но map[T]struct{} — это полноценная замена. С дженериками вы можете создать удобную обертку за 5 минут. Не пытайтесь бороться с идиомами Go — принимайте их!

package main

import (
    "fmt"
    "math/bits"
)

const MaxSize = 1024

type BitSet struct {
    words []uint64
}

func NewBitSet() *BitSet {
    return &BitSet{words: make([]uint64, MaxSize/64+1)}
}

func (s *BitSet) Add(x int) {
    idx, bit := x/64, uint(x%64)
    s.words[idx] |= 1 << bit
}

func (s *BitSet) Contains(x int) bool {
    idx, bit := x/64, uint(x%64)
    return s.words[idx]&(1<