|
map::insert
public member function
pair<iterator,bool> 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 map 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.
Because map containers do not allow for duplicate key values, the insertion operation checks for each element inserted whether another element exists already in the container with the same key value, if so, the element is not inserted and its mapped value is not changed in any way.
For a similar container allowing for duplicate elements, see multimap.
Internally, map 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.
Map containers allow for direct access of the mapped values with a less verbose member function:
Parameters
- x
- Value to be used to initialize the inserted element.
value_type is a member type defined in map 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 map container (elements in a set 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 map 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
The first version returns a pair, with its member pair::first set to an iterator pointing to either the newly inserted element or to the element that already had its same value in the map. The pair::second element in the pair is set to true if a new element was inserted or false if an element with the same value existed.
The second version returns an iterator pointing to either the newly inserted element or to the element that already had its same value in the map.
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
35
36
37
38
39
40
41
|
// map::insert
#include <iostream>
#include <map>
using namespace std;
int main ()
{
map<char,int> mymap;
map<char,int>::iterator it;
pair<map<char,int>::iterator,bool> ret;
// first insert function version (single parameter):
mymap.insert ( pair<char,int>('a',100) );
mymap.insert ( pair<char,int>('z',200) );
ret=mymap.insert (pair<char,int>('z',500) );
if (ret.second==false)
{
cout << "element 'z' already existed";
cout << " with a value of " << ret.first->second << endl;
}
// second insert function version (with hint position):
it=mymap.begin();
mymap.insert (it, pair<char,int>('b',300)); // max efficiency inserting
mymap.insert (it, pair<char,int>('c',400)); // no max efficiency inserting
// third insert function version (range insertion):
map<char,int> anothermap;
anothermap.insert(mymap.begin(),mymap.find('c'));
// showing contents:
cout << "mymap contains:\n";
for ( it=mymap.begin() ; it != mymap.end(); it++ )
cout << (*it).first << " => " << (*it).second << endl;
cout << "anothermap contains:\n";
for ( it=anothermap.begin() ; it != anothermap.end(); it++ )
cout << (*it).first << " => " << (*it).second << endl;
return 0;
}
|
Output:
element 'z' already existed with a value of 200
mymap contains:
a => 100
b => 300
c => 400
z => 200
anothermap contains:
a => 100
b => 300
|
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
| map::find | Get iterator to element (public member function) |
| map::erase | Erase elements (public member function) |
|