Как удалить дубликаты из слайса с сохранением порядка в Go

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

Знаете ли вы идиоматичное решение через map, умеете ли сделать его обобщённым и понимаете ли, как слайс делит память с базовым массивом. Следом часто просят решение без выделения нового слайса или спрашивают про пакет slices.

Как отвечать

Базовый вариант: проход по слайсу, map как множество, результат в новый слайс.

• множество: seen := make(map[T]struct{}, len(s)). Пустая структура не занимает места под значение, а заданная ёмкость избавляет от перестроения map по мере роста;
• обобщённая функция: func Dedup[T comparable](s []T) []T, дженерики есть с Go 1.18. Ограничение comparable нужно, потому что ключ map сравнивается через ==;
• на месте: out := s[:0], и в него append только новых элементов. Новый массив не выделяется, но исходные данные перезаписываются, это стоит проговорить вслух;
• пакет slices: slices.Compact (Go 1.21) удаляет только соседние дубли, поэтому работает после slices.Sort, а сортировка ломает исходный порядок. Для задачи с сохранением порядка остаётся map.

Сложность O(n) по времени и O(n) по памяти на map. На очень коротких слайсах вложенный цикл без map бывает быстрее за счёт отсутствия хеширования, это полезно упомянуть, если разговор уйдёт в микрооптимизации.

Две оговорки по типам. У float64 значение NaN не равно себе, поэтому каждый NaN ляжет в map отдельным ключом. Структура годится в ключ целиком, если все её поля сравнимы; поле-слайс или поле-map делает тип несравнимым, и код не скомпилируется.

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

Фильтруют на месте через s[:0] и продолжают пользоваться исходным слайсом. Обе переменные смотрят в один массив, данные там уже перезаписаны. Для слайса указателей хвост за новой длиной ещё держит ссылки, и сборщик мусора их не освободит без clear(s[len(out):]).

Собирают результат обходом map. Порядок итерации по map в Go намеренно случайный, и порядок элементов теряется.

Думают, что slices.Compact убирает все дубликаты. Он схлопывает только идущие подряд: [1, 2, 1] останется [1, 2, 1].