std::multimap<Key,T,Compare,Allocator>::insert

iterator insert( const value_type& value );	(1)
iterator insert( value_type&& value );	(2)	(начиная с C++17)
template< class P > iterator insert( P&& value );	(3)	(начиная с C++11)
iterator insert( iterator pos, const value_type& value );	(4)	(до C++11)
iterator insert( const_iterator pos, const value_type& value );	(4)		(начиная с C++11)
iterator insert( const_iterator pos, value_type&& value );	(5)	(начиная с C++17)
template< class P > iterator insert( const_iterator pos, P&& value );	(6)	(начиная с C++11)
template< class InputIt > void insert( InputIt first, InputIt last );	(7)
void insert( std::initializer_list<value_type> ilist );	(8)	(начиная с C++11)
iterator insert( node_type&& nh );	(9)	(начиная с C++17)
iterator insert( const_iterator pos, node_type&& nh );	(10)	(начиная с C++17)

Вставляет элемент(ы) в контейнер.

1-3) Вставляет value. Если контейнер содержит элементы с эквивалентным ключом, вставка выполняется в верхнюю границу этого диапазона.

Перегрузка (3) эквивалентна emplace(std::forward<P>(value)) и участвует в разрешении перегрузки только в том случае, если std::is_constructible<value_type, P&&>::value == true.

4-6) Вставляет value в позицию, максимально близкую к позиции непосредственно перед pos.

Перегрузка (6) эквивалентна emplace_hint(hint, std::forward<P>(value)) и участвует в разрешении перегрузки только в том случае, если std::is_constructible<value_type, P&&>::value == true.

7) Вставляет элементы из диапазона [first, last).

8) Вставляет элементы из списка инициализации ilist.

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

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

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

Параметры

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

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

1-6) Итератор на вставленный элемент.

7,8) Нет.

9,10) Итератор конца, если nh был пуст; в противном случае — итератор, указывающий на вставленный элемент.

Исключения

1-6) Если какая-либо операция выбрасывает исключение, вставка не оказывает никакого эффекта.

7,8) Гарантия безопасности при исключениях отсутствует.

9,10) Если какая-либо операция выбрасывает исключение, вставка не оказывает никакого эффекта.

Сложность

1-3) O(log(size()))

4-6) Амортизированная константная, если вставка выполняется в позицию непосредственно перед pos, O(log(size())) в противном случае.

7,8) O(N·log(size() + N)), где N — количество вставляемых элементов.

9) O(log(size()))

10) Амортизированная константная, если вставка выполняется в позицию непосредственно перед pos, O(log(size())) в противном случае.

Пример

#include <functional>
#include <iostream>
#include <map>
#include <string>
#include <string_view>
#include <utility>

template<class M>
void print(const std::string_view rem, const M& mmap)
{
    std::cout << rem << ' ';
    for (const auto& e : mmap)
        std::cout << '{' << e.first << ',' << e.second << "} ";
    std::cout << '\n';
}

int main()
{
    // list-initialize
    std::multimap<int, std::string, std::greater<int>> mmap
        {{2, "foo"}, {2, "bar"}, {3, "baz"}, {1, "abc"}, {5, "def"}};
    print("#1", mmap);
    
    // insert using value_type
    mmap.insert(decltype(mmap)::value_type(5, "pqr"));
    print("#2", mmap);
    
    // insert using pair
    mmap.insert(std::pair{6, "uvw"});
    print("#3", mmap);
    
    mmap.insert({7, "xyz"});
    print("#4", mmap);
    
    // insert using initializer_list
    mmap.insert({{5, "one"}, {5, "two"}});
    print("#5", mmap);
    
    // insert using a pair of iterators
    mmap.clear();
    const auto il = {std::pair{1, "ä"}, {2, "ё"}, {2, "ö"}, {3, "ü"}};
    mmap.insert(il.begin(), il.end());
    print("#6", mmap);
}

Вывод:

#1 {5,def} {3,baz} {2,foo} {2,bar} {1,abc}
#2 {5,def} {5,pqr} {3,baz} {2,foo} {2,bar} {1,abc}
#3 {6,uvw} {5,def} {5,pqr} {3,baz} {2,foo} {2,bar} {1,abc}
#4 {7,xyz} {6,uvw} {5,def} {5,pqr} {3,baz} {2,foo} {2,bar} {1,abc}
#5 {7,xyz} {6,uvw} {5,def} {5,pqr} {5,one} {5,two} {3,baz} {2,foo} {2,bar} {1,abc}
#6 {3,ü} {2,ё} {2,ö} {1,ä}

Отчёты об ошибках

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

Отчёт об ошибке	Применён к	Поведение согласно опубликованной версии	Корректное поведение
LWG 233	C++98	`pos` было лишь подсказкой и могло быть полностью проигнорировано	вставка должна выполняться в позицию, максимально близкую к позиции непосредственно перед `pos`
LWG 264	C++98	для перегрузки (5) требовалась линейная сложность, если диапазон `[first,` `last)` отсортирован согласно `Compare`	требование линейной сложности в этом частном случае было удалено
LWG 371	C++98	сохранение порядка эквивалентных элементов не гарантировалось	сохранение порядка стало обязательным
LWG 2005	C++11	описание перегрузок (3,6) было недостаточно точным	описание было улучшено

См. также

emplace (C++11)	конструирует элемент на месте (открытая функция-член)
emplace_hint (C++11)	конструирует элементы на месте, используя подсказку (открытая функция-член)
inserter	создаёт `std::insert_iterator` с типом, выведенным из аргумента (шаблон функции)

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