Множества Set в Dart

Что такое множества

Коллекция Set (множество) в программировании — это структура данных, которая хранит только уникальные элементы. Это означает, что если попытаться добавить один и тот же элемент несколько раз, Set сохранит его только один раз. Это делает Set очень полезным в ситуациях, когда необходимо исключить дубликаты и работать только с уникальными значениями.

Проблема дублирования данных

Система голосования: Каждый человек должен иметь только один голос. Если бы дублирование было разрешено, результаты голосования были бы искажены.

Уникальные идентификаторы (ID): В любой системе (паспортные данные, номера счетов в банке) каждому объекту присваивается уникальный ID. Дублирование ID приведет к путанице и потере данных.

Билеты на концерт: Каждый билет должен быть уникальным и использоваться только один раз. Дублирование билетов приведет к тому, что на одно место могут претендовать несколько человек.

Как решали проблему дублирования до Set? Писали велосипеды ...

Dart - Решение без Set

void main() {
  List uniqueVotes = [];

  void addVote(String email) {
    bool exists = false;
    for (var vote in uniqueVotes) {
      // O(n) — медленно!
      if (vote == email) {
        exists = true;
        break;
      }
    }
    if (!exists) {
      uniqueVotes.add(email);
    }
  }

  addVote('artem@ya.ru');
  addVote('artem@ya.ru');
  addVote('anna@ya.ru');
  addVote('natasha@ya.ru');

  print(uniqueVotes); 
  // [artem@ya.ru, anna@ya.ru, natasha@ya.ru]
}

Проблемы такого подхода:

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

То же решение с использованием множества:

Dart - Решение с Set

void main() {
  Set uniqueVotes = {}; // Создание пустого множества

  void addVote(String email) {
    uniqueVotes.add(email);
  }

  addVote('artem@ya.ru');
  addVote('artem@ya.ru');
  addVote('anna@ya.ru');
  addVote('natasha@ya.ru');

  print(uniqueVotes); 
  // [artem@ya.ru, anna@ya.ru, natasha@ya.ru]
}

Достоинства:

Хеш-таблица с временем доступа O(1)
Гарантированная уникальность элементов
Встроенные операции: объединение, пересечение, разность

Количество элементов	List (мс)	Set (мс)
1 000	15	0.2
10 000	1 500	0.3
100 000	150 000	0.5

Множества особенно эффективны в сценариях, когда:

Требуется уникальность элементов
Порядок элементов не важен
Необходимо быстро проверять наличие элемента
Требуется выполнять операции над наборами данных (объединение, пересечение, разность)

Пример простого множества

Dart - Простое множество

Set games = {
  'Witcher', 
  'MTGA', 
  'GTA6', 
  'HSR', 
  'LostArk',
  'LostArk',
  'LostArk',
};

print(games); // {'Witcher', 'MTGA', 'GTA6', 'HSR', 'LostArk'}

Типы реализаций Set в Dart

В Dart существуют различные реализации множеств, каждая со своими особенностями:

HashSet — неупорядоченная реализация, порядок итерации не определен.
LinkedHashSet — сохраняет порядок вставки элементов (реализация по умолчанию).
SplayTreeSet — поддерживает элементы в отсортированном порядке.

Выбор конкретной реализации зависит от требований вашего приложения: если важен порядок добавления — используйте LinkedHashSet, если необходима сортировка — SplayTreeSet, если важна только скорость — HashSet

Создание множеств

Dart - Создание с помощью литералов

// Создание с помощью литералов
Set games = {
  'Witcher', 
  'MTGA', 
  'GTA6', 
  'HSR', 
  'LostArk',
  'LostArk',
  'LostArk',
};

// !!! ВНИМАНИЕ: var names = {}; создаст Map, а не Set!

// Создание пустого множества (важно указать тип!)
var names = {};

Специальные конструкторы

Dart - Создание из списка

void main() {

  List gameList = [
    'Witcher',
    'MTGA',
    'GTA6',
    'HSR',
    'LostArk',
    'LostArk',
    'LostArk',
  ];

  print(gameList); // [Witcher, MTGA, GTA6, HSR, LostArk, LostArk, LostArk]

  // Создание Множества из Списка
  // Все дубликаты в списке удаляются! Очень удобно!
  Set gameSet = Set.from(gameList);

  print(gameSet); // {Witcher, MTGA, GTA6, HSR, LostArk}
}

Dart - Константное множество

// Создание константного множества
final constantGames = const {'Witcher', 'Gwint', 'DMC', 'FF', 'LostArk'};

// constantGames.add('Gothic2'); 
// Ошибка: Cannot modify unmodifiable set

Основные свойства и методы Set

Dart - Основные свойства

var games = {'Witcher', 'Gwint', 'DMC', 'FF', 'LostArk'};
 
print(games.length);     // 5 - количество элементов
print(games.first);      // Первый элемент
print(games.last);       // Последний элемент
print(games.isEmpty);    // false - проверка на пустоту
print(games.isNotEmpty); // true - проверка на непустоту

Dart - Методы доступа

var games = {'Witcher', 'Gwint', 'DMC', 'FF', 'LostArk'};

// Получение элемента по индексу
print(games.elementAt(0)); // Элемент с индексом 0

// Проверка наличия элемента
print(games.contains('Witcher')); // true

// Поиск элемента (возвращает сам элемент или null)
print(games.lookup('Witcher')); // Witcher
print(games.lookup('Skyrim')); // null

Методы для модификации множества

Dart - Добавление и удаление

var games = {'Witcher', 'Gwint'};

// Добавление одного элемента
games.add('TES');

// Добавление нескольких элементов
games.addAll({'Langrisser', 'Gothic2', 'Gothic2'});
print(games); // {Witcher, Gwint, TES, Langrisser, Gothic2}

// Обратите внимание: 'Gothic2' добавится только один раз!

// Удаление элемента
games.remove('Gwint');

// Удаление элементов по условию
games.removeWhere((game) => game.length > 5);

// Очистка множества
games.clear();

Операции над множествами

Set предоставляет мощные методы для выполнения математических операций над множествами

Dart - Операции над множествами

var setA = {'Witcher', 'Gwint', 'DMC', 'FF', 'LostArk'};
var setB = {'Warcraft', 'Witcher', 'Gwint', 'Diablo'};

// Разность множеств (A - B): элементы из A, которых нет в B
print(setA.difference(setB)); // {DMC, FF, LostArk}

// Пересечение множеств (A ∩ B): элементы, общие для A и B
print(setA.intersection(setB)); // {Witcher, Gwint}

// Объединение множеств (A ∪ B): все элементы из A и B
print(setA.union(setB)); // {Witcher, Gwint, DMC, FF, LostArk, Warcraft, Diablo}

Отношения между множествами

Dart - Проверка отношений

var setA = {'Witcher', 'Gwint', 'DMC'};
var setB = {'Witcher', 'Gwint'};
var setC = {'Warcraft', 'Diablo'};


// Проверка, является ли setB подмножеством setA
print(setB.every((element) => setA.contains(element))); // true

// или

print(setA.containsAll(setB)); // true
  
// Проверка, являются ли множества непересекающимися
print(setA.intersection(setC).isEmpty); // true - множества не пересекаются

Spread-операторы

Dart - Spread-операторы

var basicGames = {'Witcher', 'Gwint'};
var additionalGames = {'DMC', 'FF'};

// Использование spread-оператора для объединения множеств
var allGames = {...basicGames, ...additionalGames};
print(allGames); // {Witcher, Gwint, DMC, FF}

// Null-aware spread оператор
Set? nullableGames;
var safeGames = {...basicGames, ...?nullableGames};
print(safeGames); // {Witcher, Gwint}

Условные конструкции и циклы

Dart - Условные конструкции и циклы

var isRPGFan = true;
var adventureGames = {'Tomb Raider', 'Uncharted'};

// Условное добавление элементов с помощью if
var games = {
  'Witcher',
  'DMC',
  if (isRPGFan) 'Final Fantasy',
};  

// Добавление элементов с помощью for
var moreGames = {
  'Witcher',
  'DMC',
  for (var game in adventureGames) 'Adventure: $game',
};

Особенности и ограничения

При работе с множествами в Dart следует помнить о следующих особенностях

Производительность: Set быстрее List при поиске элементов, особенно в больших коллекциях, благодаря хеш-таблицам.
Сравнение множеств: Два множества считаются равными, если они содержат одинаковые элементы, независимо от порядка.

Практическое применение

Set особенно полезен в следующих сценариях:

1. Удаление дубликатов из списка:

Dart - Удаление дубликатов

var listWithDuplicates = ['A', 'B', 'A', 'C', 'B'];
var uniqueItems = Set.from(listWithDuplicates).toList();
print(uniqueItems); // [A, B, C]

2. Проверка уникальности элементов:

Dart - Проверка уникальности

bool hasUniqueElements(List list) {
  return list.length == Set.from(list).length;
}

3. Фильтрация данных:

Dart - Фильтрация данных

var allUsers = {'Анна', 'Артём', 'Настя', 'Антон'};
var activeUsers = {'Анна', 'Настя'};

var inactiveUsers = allUsers.difference(activeUsers);
print(inactiveUsers); // {Артём, Антон}

4. Нахождение общих элементов:

Dart - Общие элементы

var teamA = {'Анна', 'Юля', 'Наташа'};
var teamB = {'Юля', 'Антон', 'Артём'};

var inBothTeams = teamA.intersection(teamB);
print(inBothTeams); // {Юля}