АТД Множество является представлением математического множества, то есть набора элементов, в котором порядок элементов не важен.
Основные операции
Операция|Эффективность|Вызов
--|--|--
конструктор (пустое множество) | `O(1)`| ``set<int> s;``\
``unordered_set<int> s;``\
``flat_set<int> s;``
количество элементов | `O(1)`| ``size_t n=s.size();``
получение итератора на первый элемент (конец набора) | `O(1)`| ``auto b=s.begin(), e=s.end();``
поиск элемента |`O(log N)`\
меньше для ``unordered_set``| ``if(s.contains(5)) ...``\
``auto it=s.find(5)``\
возвращается "конец набора", если не найден
добавление элемента |`O(log N)` для ``set``\
`O(N)` для ``flat_set``| ``auto it=s.insert(5);``\
возвращается пара (итератор на добавленный элемент, true)\
или (итератор на существующий элемент, false)
удаление элемента |`O(log N)` для ``set``\
`O(N)` для ``flat_set``| ``int k=s.erase(5);`` возвращается количество удаленных элементов\
``auto ne=s.erase(it);`` возвращается итератор на следующий элемент
Операции над двумя множествами (для ``set`` и ``flat_set``)
АТД Мультимножество представлением математического мультимножества, в котором элементы могут повторяться.
Основные операции
Операция|Эффективность|Вызов
--|--|--
конструктор (пустое множество) | `O(1)`| ``multiset<int> s;``\
``unordered_multiset<int> s;``\
``flat_multiset<int> s;``
количество элементов | `O(1)`| ``int n=s.size();``
получение итератора на первый элемент (конец набора) | `O(1)`| ``auto b=s.begin(), e=s.end();``
поиск элемента |`O(log N)`\
меньше для ``unordered_multiset``| ``if(s.contains(5)) ...``\
``auto it=s.find(5)``\
возвращается "конец набора", если не найден
добавление элемента |`O(log N)` для ``multiset``\
`O(N)` для ``flat_multiset``| ``auto it=s.insert(5);``\
возвращается итератор на добавленный элемент
удаление всех элементов с заданным ключом,\
одного элемента по итератору |`O(log N+k)`\
`O(N)` для ``flat_multiset``| ``int k=s.erase(5);`` возвращается количество удаленных элементов\
``auto ne=s.erase(it);`` возвращается итератор на следующий элемент
количество элементов, равных значению |`O(k)`| ``int k=s.count(5);``