The insert
members (Table 11.4 (overleaf)) add one element or a range of elements. Because map
and set
(and the corresponding unordered types) contain unique keys, inserting an element that is already present has no effect:
vector<int> ivec = {2,4,6,8,2,4,6,8}; // ivec has eight elements
set<int> set2; // empty set
set2.insert(ivec.cbegin(), ivec.cend()); // set2 has four elements
set2.insert({1,3,5,7,1,3,5,7}); // set2 now has eight elements
The versions of insert
that take a pair of iterators or an initializer list work similarly to the corresponding constructors (§ 11.2.1, p. 423)—only the first element with a given key is inserted.
map
When we insert
into a map
, we must remember that the element type is a pair
. Often, we don’t have a pair
object that we want to insert. Instead, we create a pair
in the argument list to insert
:
// four ways to add word to word_count
word_count.insert({word, 1});
word_count.insert(make_pair(word, 1));
word_count.insert(pair<string, size_t>(word, 1));
word_count.insert(map<string, size_t>::value_type(word, 1));
As we’ve seen, under the new standard the easiest way to create a pair
is to use brace initialization inside the argument list. Alternatively, we can call make_pair
or explicitly construct the pair
. The argument in the last call to insert
:
map<string, size_t>::value_type(s, 1)
constructs a new object of the appropriate pair
type to insert into the map
.
insert
The value returned by insert
(or emplace
) depends on the container type and the parameters. For the containers that have unique keys, the versions of insert
and emplace
that add a single element return a pair
that lets us know whether the insertion happened. The first
member of the pair
is an iterator to the element with the given key; the second
is a bool
indicating whether that element was inserted, or was already there. If the key is already in the container, then insert
does nothing, and the bool
portion of the return value is false
. If the key isn’t present, then the element is inserted and the bool
is true
.
As an example, we’ll rewrite our word-counting program to use insert
:
// more verbose way to count number of times each word occurs in the input
map<string, size_t> word_count; // empty map from string to size_t
string word;
while (cin >> word) {
// inserts an element with key equal to word and value 1;
// if word is already in word_count, insert does nothing
auto ret = word_count.insert({word, 1});
if (!ret.second) // word was already in word_count
++ret.first->second; // increment the counter
}
For each word
, we attempt to insert
it with a value 1
. If word
is already in the map
, then nothing happens. In particular, the counter associated with word
is unchanged. If word
is not already in the map
, then that string
is added to the map
and its counter value is set to 1.
The if
test examines the bool
part of the return value. If that value is false
, then the insertion didn’t happen. In this case, word
was already in word_count
, so we must increment the value associated with that element.
The statement that increments the counter in this version of the word-counting program can be hard to understand. It will be easier to understand that expression by first parenthesizing it to reflect the precedence (§ 4.1.2, p. 136) of the operators:
++((ret.first)->second); // equivalent expression
Explaining this expression step by step:
ret
holds the value returned by insert
, which is a pair
.
ret.first
is the first
member of that pair
, which is a map
iterator referring to the element with the given key.
ret.first->
dereferences that iterator to fetch that element. Elements in the map
are also pair
s.
ret.first->second
is the value part of the map element pair
.
++ret.first->second
increments that value.
Putting it back together, the increment statement fetches the iterator for the element with the key word
and increments the counter associated with the key we tried to insert.
For readers using an older compiler or reading code that predates the new standard, declaring and initializing ret
is also somewhat tricky:
pair<map<string, size_t>::iterator, bool> ret =
word_count.insert(make_pair(word, 1));
It should be easy to see that we’re defining a pair
and that the second type of the pair
is bool
. The first type of that pair
is a bit harder to understand. It is the iterator
type defined by the map<string, size_t>
type.
multiset
or multimap
Our word-counting program depends on the fact that a given key can occur only once. That way, there is only one counter associated with any given word. Sometimes, we want to be able to add additional elements with the same key. For example, we might want to map authors to titles of the books they have written. In this case, there might be multiple entries for each author, so we’d use a multimap
rather than a map
. Because keys in a multi
container need not be unique, insert
on these types always inserts an element:
multimap<string, string> authors;
// adds the first element with the key Barth, John
authors.insert({"Barth, John", "Sot-Weed Factor"});
// ok: adds the second element with the key Barth, John
authors.insert({"Barth, John", "Lost in the Funhouse"});
For the containers that allow multiple keys, the insert
operation that takes a single element returns an iterator to the new element. There is no need to return a bool
, because insert
always adds a new element in these types.
Exercise 11.20: Rewrite the word-counting program from § 11.1 (p. 421) to use insert
instead of subscripting. Which program do you think is easier to write and read? Explain your reasoning.
Exercise 11.21: Assuming word_count
is a map
from string
to size_t
and word
is a string
, explain the following loop:
while (cin >> word)
++word_count.insert({word, 0}).first->second;
Exercise 11.22: Given a map<string, vector<int>>
, write the types used as an argument and as the return value for the version of insert
that inserts one element.
Exercise 11.23: Rewrite the map
that stored vector
s of children’s names with a key that is the family last name for the exercises in § 11.2.1 (p. 424) to use a multimap
.