|
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 multimap 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, multimap 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 in parameter position.
Parameters
- x
- Value to be used to initialize the inserted element.
value_type is a member type defined in multimap containers as pair<const Key,T>, where Key is the first template parameter (the key type) and T is the second template parameter (the mapped type).
- 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 multimap container (elements in a multimap 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 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 multimap 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 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 multimap.
iterator is a member type, defined as a bidirectional iterator type.
Dereferencing this iterator accesses the element's value, which is of type pair<const Key,T>.
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
30
31
32
33
34
|
// multimap::insert
#include <iostream>
#include <map>
using namespace std;
int main ()
{
multimap<char,int> mymultimap;
multimap<char,int>::iterator it;
// first insert function version (single parameter):
mymultimap.insert ( pair<char,int>('a',100) );
mymultimap.insert ( pair<char,int>('z',150) );
it=mymultimap.insert ( pair<char,int>('b',75) );
// second insert function version (with hint position):
mymultimap.insert (it, pair<char,int>('c',300)); // max efficiency inserting
mymultimap.insert (it, pair<char,int>('z',400)); // no max efficiency inserting
// third insert function version (range insertion):
multimap<char,int> anothermultimap;
anothermultimap.insert(mymultimap.begin(),mymultimap.find('c'));
// showing contents:
cout << "mymultimap contains:\n";
for ( it=mymultimap.begin() ; it != mymultimap.end(); it++ )
cout << (*it).first << " => " << (*it).second << endl;
cout << "anothermultimap contains:\n";
for ( it=anothermultimap.begin() ; it != anothermultimap.end(); it++ )
cout << (*it).first << " => " << (*it).second << endl;
return 0;
}
|
Output:
element 'z' already existed with a value of 200
mymultimap contains:
a => 100
b => 75
c => 300
z => 150
z => 400
anothermap contains:
a => 100
b => 75
|
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
|