std::map::insert

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

Inserts element(s) into the container, if the container doesn't already contain an element with an equivalent key.

1-2) Inserts value. The overload (2) is equivalent to emplace(std::forward<P>(value)) and only participates in overload resolution if std::is_constructible<value_type, P&&>::value == true.

3-4) Inserts value in the position as close as possible, just prior(since C++11), to hint. The overload (4) is equivalent to emplace_hint(hint, std::forward<P>(value)) and only participates in overload resolution if std::is_constructible<value_type, P&&>::value == true.

5) Inserts elements from range [first, last).

6) Inserts elements from initializer list ilist.

No iterators or references are invalidated.

Parameters

hint

iterator, used as a suggestion as to where to start the search	(until C++11)
iterator to the position before which the new element will be inserted	(since C++11)

value - element value to insert

first, last - range of elements to insert

ilist - initializer list to insert the values from

Type requirements

- InputIt must meet the requirements of InputIterator.

Return value

1-2) Returns a pair consisting of an iterator to the inserted element (or to the element that prevented the insertion) and a bool denoting whether the insertion took place.

3-4) Returns an iterator to the inserted element, or to the element that prevented the insertion.

5-6) (none)

Exceptions

1-4) If an exception is thrown by any operation, the insertion has no effect.

Complexity

1-2) Logarithmic in the size of the container, O(log(size())).

3-4) Amortized constant if the insertion happens in the position just after the hint, logarithmic in the size of the container otherwise.	(until C++11)
3-4) Amortized constant if the insertion happens in the position just before the hint, logarithmic in the size of the container otherwise.	(since C++11)

5-6) O(N*log(size() + N)), where N is the number of elements to insert.

Notes

The hinted insert (3,4) does not return a boolean in order to be signature-compatible with positional insert on sequential containers, such as std::vector::insert. This makes it possible to create generic inserters such as std::inserter. One way to check success of a hinted insert is to compare size() before and after.

emplace (C++11)	constructs element in-place (public member function)
emplace_hint (C++11)	constructs elements in-place using a hint (public member function)