std::unordered_set<Key,Hash,KeyEqual,Allocator>::insert

std::pair<iterator,bool> insert( const value_type& value );	(1)	(с C++11)
std::pair<iterator,bool> insert( value_type&& value );	(2)	(с C++11)
iterator insert( const_iterator hint, const value_type& value );	(3)	(с C++11)
iterator insert( const_iterator hint, value_type&& value );	(4)	(с C++11)
template< class InputIt > void insert( InputIt first, InputIt last );	(5)	(с C++11)
void insert( std::initializer_list<value_type> ilist );	(6)	(с C++11)
insert_return_type insert( node_type&& nh );	(7)	(с C++17)
iterator insert( const_iterator hint, node_type&& nh );	(8)	(с C++17)

Вставляет элемент(ы) в контейнер, если в контейнере ещё нет элемента с эквивалентным ключом.

1,2) Вставляет value.

3,4) Вставляет value, используя hint в качестве необязательной подсказки, с какой позиции начать поиск.

5) Вставляет элементы из диапазона [first, last). Если несколько элементов в диапазоне имеют эквивалентные ключи, какой элемент будет вставлен, не определено (ожидается решение LWG2844).

6) Вставляет элементы из списка инициализации ilist. Если несколько элементов в диапазоне имеют эквивалентные ключи, какой элемент будет вставлен, не определено (ожидается решение LWG2844).

7) Если nh — пустой указатель узла, ничего не делает. В противном случае, вставляет элемент, принадлежащий nh в контейнер, если в контейнере ещё нет элемента с ключом, эквивалентным nh.key(). Поведение не определено, если nh не пуст и get_allocator() != nh.get_allocator().

8) Если nh — пустой указатель узла, ничего не делает и возвращает итератор на конец. В противном случае вставляет элемент, принадлежащий nh в контейнер, если в контейнере ещё нет элемента с ключом, эквивалентным nh.key(), и возвращает итератор, указывающий на элемент с ключом, эквивалентным nh.key() (независимо от того, произошла вставка или нет). Если вставка успешна, nh перемещается, в противном случае сохраняет владение элементом. hint используется как неявная подсказка, с какой позиции начать поиск. Поведение не определено, если nh не пуст и get_allocator() != nh.get_allocator().

Если после операции новое количество элементов больше старого max_load_factor() * bucket_count(), происходит перехеширование.
Если перехеширование происходит (из-за вставки), все итераторы становятся недействительными. В противном случае (нет перехеширования), итераторы не становятся недействительными. Если вставка успешна, указатели и ссылки на элемент, полученные, когда он хранится в указателе узла, становятся недействительными, а указатели и ссылки, полученные на этот элемент до его извлечения, становятся действительными.(с C++17)

Параметры

hint	-	итератор, используемый как подсказка, куда вставить содержимое
value	-	значение элемента для вставки
first, last	-	диапазон элементов для вставки
ilist	-	список инициализации для вставки значений из него
nh	-	совместимый указатель узла
Требования к типу
-`InputIt` должен соответствовать требованиям LegacyInputIterator.

Возвращаемое значение

1,2) Возвращает пару, состоящую из итератора на вставленный элемент (или на элемент, который помешал вставке) и bool , указывающей, произошла ли вставка.

3,4) Возвращает итератор на вставленный элемент или на элемент, который помешал вставке.

5,6) (нет)

7) Возвращает insert_return_type с инициализированными членами следующим образом:

Если nh пуст, inserted — false, position — end(), и node — пуст.
В противном случае, если вставка произошла, inserted — true, position указывает на вставленный элемент, и node — пуст.
Если вставка не удалась, inserted — false, node имеет предыдущее значение nh, и position указывает на элемент с ключом, эквивалентным nh.key().

8) Итератор на конец, если nh был пустым, итератор на вставленный элемент, если вставка произошла, и итератор на элемент с ключом, эквивалентным nh.key() , если вставка не удалась.

Исключение

1-4) Если выбрасывается исключение, вставка не имеет эффекта.

Сложность

1-4) Средний случай: O(1), худший случай O(size()).

5,6) Средний случай: O(N), где N — количество элементов для вставки. Худший случай: O(N * size() + N).

7,8) Средний случай: O(1), худший случай O(size()).

Примечания

Вставка с подсказкой (3,4) не возвращает boolean, чтобы быть совместимой с позиционной вставкой в последовательных контейнерах, таких как std::vector::insert. Это позволяет создавать универсальные вставки, такие как std::inserter. Один из способов проверить успешность вставки с подсказкой — сравнить size() до и после.

Пример

#include <array>
#include <iostream>
#include <unordered_set>
 
std::ostream& operator<<(std::ostream& os, std::unordered_set<int> const& s)
{
    for (os << '[' << s.size() << "] { "; int i : s)
        os << i << ' ';
    return os << "}\n";
}
 
int main ()
{
    std::unordered_set<int> nums = {2, 3, 4};
 
    std::cout << "1) Initially: " << nums << std::boolalpha;
    auto p = nums.insert(1); // insert element, overload (1)
    std::cout << "2) '1' was inserted: " << p.second << '\n';
    std::cout << "3) After insertion: " << nums;
 
    nums.insert(p.first, 0); // insert with hint, overload (3)
    std::cout << "4) After insertion: " << nums;
 
    std::array<int, 4> a = {10, 11, 12, 13};
    nums.insert(a.begin(), a.end()); // insert range, overload (5)
    std::cout << "5) After insertion: " << nums;
 
    nums.insert({20, 21, 22, 23}); // insert initializer_list, (6)
    std::cout << "6) After insertion: " << nums;
 
    std::unordered_set<int> other_nums = {42, 43};
    auto node = other_nums.extract(other_nums.find(42));
    nums.insert(std::move(node)); // insert node, overload (7)
    std::cout << "7) After insertion: " << nums;
 
    node = other_nums.extract(other_nums.find(43));
    nums.insert(nums.begin(), std::move(node)); // insert node with hint, (8)
    std::cout << "8) After insertion: " << nums;
}

Возможный вывод:

1) Initially: [3] { 4 3 2 }
2) '1' was inserted: true
3) After insertion: [4] { 1 2 3 4 }
4) After insertion: [5] { 0 1 2 3 4 }
5) After insertion: [9] { 13 12 11 10 4 3 2 1 0 }
6) After insertion: [13] { 23 22 13 12 11 10 21 4 20 3 2 1 0 }
7) After insertion: [14] { 42 23 22 13 12 11 10 21 4 20 3 2 1 0 }
8) After insertion: [15] { 43 42 23 22 13 12 11 10 21 4 20 3 2 1 0 }

См. также

emplace	создаёт элемент на месте (публичный член-функция)
emplace_hint	создаёт элементы на месте с подсказкой (публичный член-функция)
inserter	создаёт итератор типа, выведенного из аргумента (шаблон функции)

© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/w/cpp/container/unordered_set/insert