It's a good thing I'm not using tuples: c++ std::map and in-place construction

stdMapCPPSurprise.md

It's a good thing I'm not using tuples

Everybody who writes software will eventually become acquainted with the principle of least astonishment. Often when something doesn't behave the way we expect, we go to debug, or perhaps look for a helpful error message. In some cases, something is failing behind the scenes that results in an error message we don't expect.

Who said anything about tuples, std::map?

Suppose we want to organize a group of employees so they can easily be found by their employee id. We can use std::map<int, Employee> to contain our employees information. At this point, the only information we want on our employees is their name. So we write this class

#include <string>

class Employee
{
public:
   Employee( std::string name )
   {
      m_Name = name;
   }

   std::string GetName()
   {
      return m_Name;
   }

private:
   std::string m_Name;
};

The constructor of employee takes a name and stores it. Now we simply want to store some employees in a map and then print out their name to make sure we have it. Don't forget to include #include <map> and #include <iostream>

int main()
{
   const int employeeIds[5] = { 34, 12, 32, 99, 101 };
   const std::string employeeNames[5] = { "bob", "lisa", "joe", "mary", "mike" };

   std::map<int, Employee> mapEmployees;

   for( int i = 0; i < 5; i++ )
   {
      mapEmployees[employeeIds[i]] = Employee( employeeNames[i] );
   }

   for( int i = 0; i < 5; i++ )
   {
      std::cout << mapEmployees[employeeIds[i]].GetName() << std::endl;
   }

   return 0;
}

Now we eagerly compile and run our code. Uh oh! Error C2512 'Employee::Employee': no appropriate default constructor in file tuple

But nobody said anything about tuples?! What gives?

C++ Default constructor

Normally, you do not have to specifically declare the default constructor; the compiler will automaticall generate one for you. You can easily declare a class like below and call the constructor of it.

class Employee
{
public:
    int Age;
};

int main()
{
    Employee bob; // Default constructor!
    bob.Age = 45;
    return bob.Age;
}

The catch is if you declare another constructor, the compiler does not provide a default constructor! So in the first example the Employee( std::string name ) constructor will prevent the generation of a default constructor.

So the error is right! There really is no default constructor. But why does it even need a default constructor?

std::map and in-place construction

Take a look at the following code

int main()
{
    std::map<std::string, std::string> mapNames;
    std::string name = "Mr. Skelington";
    
    mapNames["Pumpkin King"] = name;
    
    // Look at whats in the map!
    std::cout << mapNames["Pumpkin King"] << std::endl;
    std::cin.get(); // So our console doesn't close on use.
    
    return 0;
}

We declare the string name and assigned "Mr. Skelington" as its value. Then we put it into a map mapNames["Pumpkin King"] = name;. When we do this, there is a lot going on behind the scenes. The details of its inner-workings can be found in the reference for std::map::operator. But golly all that info is confusing. So let's break it down.

First thing to notice is the the operator[] is a function. Like many functions it has a return value. That return value is a reference to the value stored at the input key... It might help if we write our code another way.

int main()
{
    std::map<std::string, std::string> mapNames;
    std::string name = "Mr. Skelington";
    
    std::string& pumpkinKing = mapNames["Pumpkin King"];
    pumpkinKing = name;
    
    // Look at whats in the map!
    std::cout << mapNames["Pumpkin King"] << std::endl;
    std::cin.get(); // So our console doesn't close on use.
    
    return 0;
}

The output is the same.

mapNames["Pumpkin King"] = name;

// is equivalent to

std::string& pumpkinKing = mapNames["Pumpkin King"]
pumpkinKing = name;

In both cases, C++ has two do at least two things.

1. First, find out what mapNames["Pumpkin King"] is referring to.
2. Second, assign the value of name to whatever mapNames["Pumpkin King"] is referring to.

Here's the catch! If there is no key "Pumpkin King" in the std::map, then we can't just return nothing! Our code would fail when we try to assign name to nothing. Instead of returning nothing, mapNames["Pumpkin King"] creates a new entry for the key "Pumpkin King" so it can return something. In order to do this, it calls the default constructor of the "mapped type", in the first example, Employee, in this example, std::string. From the documents...

std::map::operator[]...
Inserts a value_type object constructed in-place ... if the key does not exist.

Let's focus on the constructed part (ignoring "in-place"). If the std::map does not yet contain the key - in our case it doesn't contain "Pumpkin King" - then the std::map constructs an empty std::string to allocate the memory for that key. This explains why we get the error Employee::Employee': no appropriate default constructor in our first example! std::map is trying to use the default constructor to allocate memory for an Employee! Going back, we ignored an important part of the reference document, the full reference states

Inserts a 'value_type' object constructed in-place from 'std::piecewise_construct, std::forward_as_tuple(key), std::tuple<>()'
if the key does not exist. This function is equivalent to return this->try_emplace(key).first->second;. (since C++17) 
When the default allocator is used, this results in the key being copy constructed from key and the mapped value being
value-initialized. 

For clarity 'value_type' is defined in the std::map reference, in our first example, it is std::pair<int, Employee> used as the 'value_type'. More on that in a moment.

The presence of std::tuple<>() in this definition indicates we are on the right track. The phrase constructed in-place from 'std::piecewise_construct, std::forward_as_tuple(key), std::tuple<>()' is mighty confusing though. Lets break it down. std::map is a container of std::pair. That is, all of its elements are std::pair. When we access a map's element by a key, it returns pair.second of the std::pair whose pair.first is the input key. (Note: std::pair is a struct with fields pair.first and pair.second) In the reference, it states std::pair is a special case of std::tuple<>(). So we can see that this error would occur in the tuple file if our pair construction tried to use the default constructor of Employee!

Since std::map is a container of std::pair, it might be obvious to say that a std::pair is constructed each time an element is added to the map regardless of the method of adding to the map. Constructing "in-place" is a topic for another gist but it is suffice to say that we are simply constructing a std::pair when we add an element to a std::map.

But all that doesn't explain constructed from std::piecewise_construct, std::forward_as_tuple(key), std::tuple<>()! Again we look to the reference document, specifically overload 6 of the std::pair constructor. That list of comma separated things in the std::map::operator[] definition is a list of arguments for std::pair constructor! Those are the arguments that std::map is using to allocate and construct the Employee element at each key. Reading the details, it states it forwards the first tuple, std::forward_as_tuple(key), to the key's type constructor, and it forwards the second tuple, std::tuple<>(), to the mapped's type constructor... in our case Employee. Note here that the word forward basically means it uses all the entries in the tuple as arguments to the constructors... e.g. the first element in the tuple would be the first argument to Employee(). So it is saying that it is trying to pass no arguments (because it's forwarding an empty std::tuple<>()) to an Employee class constructor. But there is no Employee class constructor that takes no arguments (the default constructor would if it existed)! So we get a compiler error!

Long story short

1. std::map is a container of std::pair

2. std::pair is a special kind of std::tuple

3. std::map::operator[] creates a std::pair with the input key and a default constructed mapped item. e.g.

   std::map<int, std::string> myMap;
   
   myMap[2]; // This creates a std::pair<int, std::string> with key = 2 and std::string()
   

4. The Employee class does not have a default constructor because another constructor is provided.

5. std::pair construction fails because it cannot find a default constructor for Employee.

These have been notes on a mystery. C++ sure does a lot behind the scenes, for better or worse.

Hi, great post!

Just for the sake of completeness, I wanted to mention these issues can be avoided if using emplace for insertion since it constructs the object in place with the provided arguments and at for retrieval since it is const and therefore has no chance of constructing.

In other words, the following code:

for( int i = 0; i < 5; i++ )
{
    mapEmployees.emplace(employeeIds[i], employeeNames[i]);
}

for( int i = 0; i < 5; i++ )
{
    std::cout << mapEmployees.at(employeeIds[i]).GetName() << std::endl;
}

will work as intended without a default constructor. Consequently, both of these are recommended as emplace is (generally!) the more optimal way to insert and at ensures an element will not accidently be created if only retrieval was intended.

I understand the point of the post was to highlight some interesting implementation details of C++, but I figured this is worth mentioning for people who happen to stumble upon this like I did!