Как реализовать структуру set в Go

Что проверяют

Знаете ли вы идиому с пустой структурой и понимаете ли, почему её выбирают.

Как отвечать

Встроенного множества в Go нет, поэтому его строят на карте. Идиоматический вариант использует пустую структуру в качестве значения:

set := make(map[string]struct{})

set["go"] = struct{}{}                  // добавление
_, ok := set["go"]                      // проверка
delete(set, "go")                       // удаление
len(set)                                // размер

Почему именно пустая структура: она занимает ноль байтов. Все её значения указывают на один и тот же адрес, поэтому память тратится только на ключи. Альтернатива с логическим значением проще читается, но добавляет байт на элемент и, что важнее, создаёт двусмысленность: отсутствие ключа и ключ со значением «ложь» это разные вещи, и на этом легко ошибиться.

Обёртка в тип с методами делает код гораздо приятнее, а с появлением обобщений она пишется один раз для всех типов:

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

func (s Set[T]) Add(v T)          { s[v] = struct{}{} }
func (s Set[T]) Has(v T) bool     { _, ok := s[v]; return ok }
func (s Set[T]) Delete(v T)       { delete(s, v) }

Ограничение на тип обязательно: ключом карты может быть только сравнимый тип. Срез, карта и функция ключами быть не могут, поэтому множество срезов напрямую не сделать. Обходят приведением к строке или к массиву фиксированной длины.

Операции над множествами вроде объединения, пересечения и разности пишутся вручную обычными циклами: готовых в стандартной библиотеке нет.

Что стоит добавить:

• порядок обхода случайный, как у любой карты. Нужен порядок, значит собирайте ключи и сортируйте;
• потокобезопасности нет: конкурентная запись уронит программу, поэтому при одновременном доступе нужен мьютекс;
• при известном размере полезно задать ёмкость при создании.

Где спотыкаются

Используют логическое значение и путают отсутствие ключа со значением «ложь».

Пытаются положить срез в качестве ключа.

Полагаются на порядок обхода.

Забывают про синхронизацию при доступе из нескольких горутин.