C++

C++ map emplace

In C++ , emplace() and insert() functions do a similar thing. When the programmer does not care about the advantages that emplace has, he can use insert(). Emplace constructs the element of interest within the container of interest while inserting copies of the element from somewhere or moving the element into the container of interest.

Copy Notion

Consider the following two lists of characters:

list<char> lA = {'A', 'B', 'C', 'D'};

list<char> lB = {'E', 'F', 'G', 'H'};

āGā in lB can be copied and placed in front of āDā in lA, to have,

list<char> lA = {'A', 'B', 'C', 'G', 'D'};
list<char> lB = {'E', 'F', 'G', 'H'};

Move Notion

āGā in lB can be removed and placed in front of āDā in lA, to have,

list<char> lA = {'A', 'B', 'C', 'G', 'D'};
list<char> lB = {'E', 'F', 'H'};

Value in Element

Copying and moving are not as blunt as shown above. In a real situation, each value (e.g., character) is in an element. So, if a list of chars has four characters, then the list has four elements. If a list of chars has three characters, then the list has three elements.

An element can be a struct with 3 data members. The first data member is a pointer that points to the previous element in the list. The second data member holds the value, in this case, the character. The third data member is a pointer that points to the next element in the list.

So, each character, such as āGā above, would be held by the second data member of a struct. In the case of the original list, lB above, and for āGā, the first data member of the struct, would point to the element that has āFā, and the third data member of the struct would point to the element that has āHā.

Insert and Emplace

When insert() has to copy as expressed above, the element of āGā, i.e., the complete struct, will be copied and placed in front of the āDā element, in theory. In practice, after a new corresponding element is considered to be placed in front of the āDā element, the third data member of the new Gās struct will be made to point to the āDā element; and the first data member of the new Gās struct will be made to point to the āCā element (of list lA).

When insert() has to move as expressed above, the copying as explained here is done, then the āGā element in list lB is removed.

Emplace(), on the other hand, does not really have to copy or move any element. It just has to be indicated to the program that the value of interest is the character, āGā. The program will then construct a new element with āGā as the value in front of the āDā element in the list, lA. That is, it will create a new āGā struct in front of the āDā element, with the third data member pointing to the āDā element and the first data member pointing to the āCā element, as part of the construction procedure.

So, the main difference between insert() and emplace() is that emplace() constructs the inserting element on the spot, while insert() has to copy or move the element.

This article explains what map-emplace is and how to use the two main emplace member functions of map.

The map Element

The following are four fruit names and their outer colors:

banana => yellow
passion fruit => purple
watermelon => green
grape => pink

A map consists of key/value pairs. In this ordinary list, the names of the fruits are the keys, and the names of the outer colors are the values. However, this is a list of pairs, not a list of values alone, and not a list of keys alone. It is a list of key/value pairs. The keys of a map are unique.

In code, a key and its value are coded as an element, called a pair. Each element would be pointed to by an iterator. So, a map element sees a key as a value, and the key corresponds to another value. So, a map element needs two values to create an element; not one as expressed in the introduction above. These two values are in some code, called a pair.

The template for the map element is:

pair<const key_type, mapped_type>

The first parameter is for the key, and it is indicated as key_type. The second parameter is for the value that corresponds to the key. It is indicated as mapped_type and not value_type. value_type is actually:

pair<const key_type, mapped_type>

the element template. With the array, indexes are to values. With the map, iterators are to pairs. A pair is a value, which can be held by the second data member of a struct, and the third data member pointing to the next element, which also has a pair as value; and the first data member pointing to the previous element, whose value is some other pair.

In the fruit/color list above, the first pair can be coded as follows:

{"banana", "yellow"}

“banana” is the key, and “yellow” is the value, forming a key/value pair. The whole shortlist of two values is a value of value_type, and can be held by the middle data member of a struct element. The first data member of the struct will point to the previous element, and the third data member of the struct will point to the next element.

Now, a pair is an object whose key has the member name first and whose value has the member name second.

The following program puts the above list of fruits/colors into a map:

#include <iostream>
#include <map>
using namespace std;

int main()
{
map<const char*, const char*> mp = {{"banana","yellow"}, {"passion fruit","purple"}, {"watermelon","green"}, {"grape","pink"}};

for (map<const char*, const char*>::iterator it = mp.begin(); it != mp.end(); it++)
cout << it->first << " => " << it->second << endl;

return 0;
}

The output is:

banana => yellow
passion fruit => purple
watermelon => green
grape => pink

Note that the map library had to be included.

Heterogeneous Pair

A pair must not necessarily have a key and value that makes sense to the ordinary user. It can also have a key and value that does not make sense to the ordinary user but makes sense to the programmer. As an example for a key/value pair that makes sense to the programmer, the key may be an iterator, and the value, a bool type.

a_uniq.emplace(args)

Here, a_uniq is the name of the map. args are the key and value for the pair, separated by a comma. The member function returns a pair, whose first value is an iterator (value_type); and whose second value is a bool, to indicate whether the insertion (constructed on the spot) was successful (true for success). The returned iterator points to the inserted element. The C++ specification does not indicate where the insertion should take place within the list (or in front or behind) for this function. The following program illustrates the use of the function:

#include <iostream>
#include <map>
using namespace std;

int main()
{
map<const char*, const char*> mp = {{"banana","yellow"}, {"passion fruit","purple"}, {"watermelon","green"}, {"grape","pink"}};

pair<map<const char*, const char*>::iterator, bool> pr = mp.emplace("strawberry","red");

cout << (pr.first)->first << " => " << (pr.first)->second << " : " << pr.second << endl;
cout << endl;

for (map<const char*, const char*>::iterator it = mp.begin(); it != mp.end(); it++)
cout << it->first << " => " << it->second << endl;

return 0;
}

The output is:

strawberry => red : 1

strawberry => red
banana => yellow
passion fruit => purple
watermelon => green
grape => pink

1 in the first output line means true. Note how args was coded as (“strawberry”,”red”). Do not confuse between value_type and mapped _type.

a.emplace_hint(p, args)

Here, āaā is the name of the map. This member function is similar to the above, but the position where emplacement has to take place in the map list is suggested. It is an iterator, p pointing to the element prior to, and near to which, the insertion (emplacement) will be placed, in memory. The function returns an iterator and not a pair. The iterator points to the newly inserted element (pair). The following program illustrates this:

#include <iostream>
#include <map>
using namespace std;

int main()
{
map<const char*, const char*> mp = {{"banana","yellow"}, {"passion fruit","purple"}, {"watermelon","green"}, {"grape","pink"}};

map<const char*, const char*>::iterator p = mp.end();
p--;

map<const char*, const char*>::iterator iter = mp.emplace_hint(p, "strawberry","red");

cout << iter->first << " => " << iter->second << endl;
cout << endl;

for (map<const char*, const char*>::iterator it = mp.begin(); it != mp.end(); it++)
cout << it->first << " => " << it->second << endl;

return 0;
}

The output is:

strawberry => red

strawberry => red
banana => yellow
passion fruit => purple
watermelon => green
grape => pink

Conclusion

Emplace and Insert are similar. Emplace constructs its element on the spot in the list, after obtaining the value, somehow. On the other hand, Insert copies its element into the list from somewhere or moves the element into the list from somewhere.

Note: a map is normally created sorted by keys. To achieve this for the above map, use string objects for the keys instead of constant-pointers-to-chars.