public member function
<set>
| single element (1) |
iterator insert (const value_type& val);
|
|---|
| with hint (2) |
iterator insert (iterator position, const value_type& val);
|
|---|
| range (3) |
template <class InputIterator>
void insert (InputIterator first, InputIterator last);
|
|---|
| single element (1) |
iterator insert (const value_type& val);
iterator insert (value_type&& val);
|
|---|
| with hint (2) |
iterator insert (const_iterator position, const value_type& val);
iterator insert (const_iterator position, value_type&& val);
|
|---|
| range (3) |
template <class InputIterator>
void insert (InputIterator first, InputIterator last);
|
|---|
| initializer list (4) |
void insert (initializer_list<value_type> il); |
|---|
Insert element
Extends the container by inserting new elements, effectively increasing the container size by the number of elements inserted.
Internally, multiset containers keep all their elements sorted following the criterion specified by its comparison object. The elements are always inserted in its respective position following this ordering.
There are no guarantees on the relative order of equivalent elements.
The relative ordering of equivalent elements is preserved, and newly inserted elements follow their equivalents already in the container.
The parameters determine how many elements are inserted and to which values they are initialized:
Parameters
- val
- Value to be copied (or moved) to the inserted elements.
Member type value_type is the type of the elements in the container, defined in multiset as an alias of its first template parameter (T).
- position
-
Hint for the position where the element can be inserted.
The function optimizes its insertion time if position points to the element that will precede the inserted element.
The function optimizes its insertion time if
position points to the element that will
follow the inserted element (or to the
end, if it would be the last).
Notice that this is just a hint and does not force the new element to be inserted at that position within the multiset container (the elements in a multiset always follow a specific order).
Member types iterator and const_iterator are defined in map as a bidirectional iterator type that point to elements.
- first, last
- Iterators specifying a range of elements. Copies of the elements in the range [first,last) are inserted in the container.
Notice that the range includes all the elements between first and last, including the element pointed by first but not the one pointed by last.
The function template argument InputIterator shall be an input iterator type that points to elements of a type from which value_type objects can be constructed.
- il
- An initializer_list object. Copies of these elements are inserted.
These objects are automatically constructed from initializer list declarators.
Member type value_type is the type of the elements in the container, defined in multiset as an alias of its first template parameter (T).
Return value
In the versions returning a value, this is an iterator pointing to the newly inserted element in the multiset.
Member type iterator is a bidirectional iterator type that points to elements.
Example
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
// multiset::insert (C++98)
#include <iostream>
#include <set>
int main ()
{
std::multiset<int> mymultiset;
std::multiset<int>::iterator it;
// set some initial values:
for (int i=1; i<=5; i++) mymultiset.insert(i*10); // 10 20 30 40 50
it=mymultiset.insert(25);
it=mymultiset.insert (it,27); // max efficiency inserting
it=mymultiset.insert (it,29); // max efficiency inserting
it=mymultiset.insert (it,24); // no max efficiency inserting (24<29)
int myints[]= {5,10,15};
mymultiset.insert (myints,myints+3);
std::cout << "mymultiset contains:";
for (it=mymultiset.begin(); it!=mymultiset.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
return 0;
}
| |
Output:
myset contains: 5 10 10 15 20 24 25 27 29 30 40 50
|
Complexity
For the first version (
insert(x) ), logarithmic.
For the second version (
insert(position,x) ), logarithmic in general, but amortized constant if
x is inserted right after the element pointed by
position.
For the third version (
insert (first,last) ),
Nlog(size+N) in general (where N is the distance between
first and
last, and
size the
size of the container before the insertion), but linear if the elements between
first and
last are already sorted according to the same ordering criterion used by the container.
Complexity
If a single element is inserted, logarithmic in size in general, but amortized constant if a hint is given and the position given is the optimal.
If N elements are inserted,
Nlog(size+N) in general, but linear in
size+N if the elements are already sorted according to the same ordering criterion used by the container.
If N elements are inserted,
Nlog(size+N).
Implementations may optimize if the range is already sorted.
Iterator validity
No changes.
Data races
The container is modified.
Concurrently accessing existing elements is safe, although iterating ranges in the container is not.
Exception safety
If a single element is to be inserted, there are no changes in the container in case of exception (strong guarantee).
Otherwise, the container is guaranteed to end in a valid state (basic guarantee).
If allocator_traits::construct is not supported with the appropriate arguments for the element constructions, or if an invalid position is specified, it causes undefined behavior.