|
iterator insert ( const value_type& x );
iterator insert ( iterator position, const value_type& x );
template <class InputIterator>
void insert ( InputIterator first, InputIterator last );
Insert element
The container is extended by inserting a single new element (if parameter x is used) or a sequence of elements (if input iterators are used).
This effectively increases the container size by the amount of elements inserted.
Internally, multiset containers keep all their elements sorted following the criterion specified by its comparison object on construction. Each element is inserted in its respective position following this ordering.
Efficiency of this operation can be dramatically improved by providing the appropriate value as parameter position.
Parameters
- x
- Value to be used to initialize the inserted element.
value_type is a member type defined in multiset containers as an alias of Key, which is the first template parameter and the type of the elements stored in the container.
- position
- Position of the first element to be compared for the insertion operation.
Notice that this does not force the new element to be in that position within the multiset container (elements in a multiset always follow a specific ordering), but this is actually an indication of a possible insertion position in the container that, if set to the element that immediately precedes the actual location where the element is inserted, makes for a very efficient insertion operation.
iterator is a member type, defined as a bidirectional iterator type.
- first, last
- Iterators specifying a range of elements. Copies of the elements in the range [first,last) are inserted in the multiset.
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 template type can be any type of input iterator.
Return value
In the versions returning a value, this is an iterator pointing to the newly inserted element in the multiset.
iterator is a member type, defined as a bidirectional iterator type.
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
29
|
// multiset::insert
#include <iostream>
#include <set>
using namespace std;
int main ()
{
multiset<int> mymultiset;
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);
cout << "mymultiset contains:";
for (it=mymultiset.begin(); it!=mymultiset.end(); it++)
cout << " " << *it;
cout << endl;
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.
See also
|