Namespaces
Variants

std::set<Key,Compare,Allocator>:: insert

From cppreference.net
C++
Containers library
std::set
Member functions
Non-member functions
(until C++20) (until C++20) (until C++20) (until C++20) (until C++20)
Deduction guides (C++17)
std:: pair < iterator, bool > insert ( const value_type & value ) ;
(1) (constexpr начиная с C++26)
std:: pair < iterator, bool > insert ( value_type && value ) ;
(2) (начиная с C++11)
(constexpr начиная с C++26)
(3)
iterator insert ( iterator pos, const value_type & value ) ;
(до C++11)
iterator insert ( const_iterator pos, const value_type & value ) ;
(начиная с C++11)
(constexpr начиная с C++26)
iterator insert ( const_iterator pos, value_type && value ) ;
(4) (начиная с C++11)
(constexpr начиная с C++26)
template < class InputIt >
void insert ( InputIt first, InputIt last ) ;
(5) (constexpr начиная с C++26)
void insert ( std:: initializer_list < value_type > ilist ) ;
(6) (начиная с C++11)
(constexpr начиная с C++26)
insert_return_type insert ( node_type && nh ) ;
(7) (начиная с C++17)
(constexpr начиная с C++26)
iterator insert ( const_iterator pos, node_type && nh ) ;
(8) (начиная с C++17)
(constexpr начиная с C++26)
template < class K >
std:: pair < iterator, bool > insert ( K && x ) ;
(9) (начиная с C++23)
(constexpr начиная с C++26)
template < class K >
iterator insert ( const_iterator pos, K && x ) ;
(10) (начиная с C++23)
(constexpr начиная с C++26)

Пытается вставить элемент(ы) в * this .

  • Если * this уже содержит элемент с эквивалентным ключом, ничего не делает.
  • В противном случае, вставляет элемент(ы) в * this .
1-4) Вставляет value . Если pos указан, value будет вставлен как можно ближе к позиции непосредственно перед pos .
1,3) Если value_type не является CopyInsertable в set , поведение не определено.
2,4) Если value_type не является MoveInsertable в set , поведение не определено.
(since C++11)
5) Вставляет элементы из диапазона [ first , last ) .
Если удовлетворяется любое из следующих условий, поведение не определено:
(начиная с C++11)
  • first или last является итератором на * this .
6) Вставляет элементы из списка инициализации ilist .
Эквивалентно insert ( ilist. begin ( ) , ilist. end ( ) ) .
7) Если nh является пустым node handle , не делает ничего. В противном случае вставляет элемент, принадлежащий nh в контейнер, если контейнер ещё не содержит элемент с ключом, эквивалентным nh. key ( ) . Поведение не определено, если nh не пуст и get_allocator ( ) ! = nh. get_allocator ( ) .
8) Если nh является пустым node handle , не выполняет никаких действий и возвращает конечный итератор. В противном случае вставляет элемент, принадлежащий nh , в контейнер, если контейнер еще не содержит элемент с ключом, эквивалентным nh. key ( ) , и возвращает итератор, указывающий на элемент с ключом, эквивалентным nh. key ( ) (независимо от того, была ли вставка успешной или нет). Если вставка успешна, nh перемещается, в противном случае он сохраняет владение элементом. Элемент вставляется как можно ближе к позиции непосредственно перед pos . Поведение не определено, если nh не пуст и get_allocator ( ) ! = nh. get_allocator ( ) .
9,10) Создает объект u типа value_type с помощью std:: forward < K > ( x ) и затем вставляет u в * this . Существование эквивалентного ключа определяется прозрачно с использованием x перед созданием u .
Если выполняется любое из следующих условий, поведение не определено:
9) Эта перегрузка участвует в разрешении перегрузки только если Compare является прозрачным .
10) u будет вставлен как можно ближе к позиции непосредственно перед pos .
Эта перегрузка участвует в разрешении перегрузки только при выполнении всех следующих условий:

Никакие итераторы или ссылки не инвалидируются. Если вставка успешна, указатели и ссылки на элемент, полученные пока он содержался в node handle, инвалидируются, а указатели и ссылки, полученные на этот элемент до его извлечения, становятся валидными. (since C++17)

Содержание

Параметры

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

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

1,2) Пара, состоящая из итератора к вставленному элементу (или к элементу, который предотвратил вставку) и значения типа bool , установленного в true тогда и только тогда, когда вставка произошла.
3,4) Итератор на вставленный элемент или на элемент, который предотвратил вставку.
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 ( ) если она не удалась.
9) Пара, состоящая из итератора на вставленный элемент (или на элемент, который предотвратил вставку) и bool значения, установленного в true тогда и только тогда, когда вставка произошла.
10) Итератор на вставленный элемент или на элемент, который предотвратил вставку.

Исключения

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

Сложность

Дано N как size ( ) :

1,2) log(N)
3,4) Амортизированная константа, если вставка происходит в позицию непосредственно после (until C++11) перед (since C++11) pos , log(N) в противном случае.
5,6) log(N+M) , где M - количество элементов для вставки.
7) log(N)
8) Амортизированная константа, если вставка происходит в позицию непосредственно перед pos , log(N) в противном случае.
9) log(N)
10) Амортизированная константа, если вставка происходит в позицию непосредственно перед pos , log(N) в противном случае.

Примечания

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

Перегрузки ( 5,6 ) часто реализуются как цикл, вызывающий перегрузку ( 3 ) с end() в качестве подсказки; они оптимизированы для добавления отсортированной последовательности (такой как другой std::set ), чей наименьший элемент больше последнего элемента в * this .

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

Макрос тестирования возможностей Значение Стандарт Возможность
__cpp_lib_associative_heterogeneous_insertion 202311L (C++26) Гетерогенные перегрузки для оставшихся функций-членов в упорядоченных и неупорядоченных ассоциативных контейнерах. ( 9,10 )

Пример

Запустить этот код 
#include <cassert>
#include <iostream>
#include <set>
int main()
{
    std::set<int> set;
    auto result_1 = set.insert(3);
    assert(result_1.first != set.end()); // это валидный итератор
    assert(*result_1.first == 3);
    if (result_1.second)
        std::cout << "insert done\n";
    auto result_2 = set.insert(3);
    assert(result_2.first == result_1.first); // тот же итератор
    assert(*result_2.first == 3);
    if (!result_2.second)
        std::cout << "no insertion\n";
}

Вывод: 

insert done
no insertion

Отчеты о дефектах

Следующие отчеты об изменениях поведения, влияющие на дефекты, были применены ретроактивно к ранее опубликованным стандартам C++.

DR Применяется к Поведение в опубликованной версии Корректное поведение
LWG 233 C++98 pos был просто подсказкой, его можно было полностью игнорировать вставка должна быть
как можно ближе к
позиции непосредственно перед pos
LWG 264 C++98 сложность перегрузки ( 5 ) должна была быть линейной, если
диапазон [ first , last ) отсортирован согласно Compare 		убрано требование линейной сложности
в этом специальном случае
LWG 316 C++98 в возвращаемом значении перегрузки ( 1 ) не было указано,
какое значение bool указывает на успешную вставку 		успех указывается значением true

Смотрите также

(C++11)
создаёт элемент на месте
(public member function)
(C++11)
создаёт элементы на месте с использованием подсказки
(public member function)
создаёт std::insert_iterator типа, выведенного из аргумента
(function template)