In this blog post, I’d like to show you examples of several handy “map” functions from Modern C++. Associative containers like std::map, std::set, and their “unordered” counterparts are essential for many algorithms and techniques. With this new functionality, you can save the creation of temporary objects, write smaller and, what’s more, safer code.

Background code  

To illustrate all the mechanics of a map, especially in terms of what happens with our objects, I have the following helper custom class:

struct User {
    std::string name {"default"};
    
    User() {
        std::cout << "User::User() " << name << '\n';
    }

    explicit User(std::string str) : name(std::move(str)) {
        std::cout << "User::User(std::string str) " << name << '\n';
    }

    ~User() {
        std::cout << "User::~User " << name << '\n';
    }

    User(const User& other) : name(other.name) {
        std::cout << "User::User(const User&) " << name << '\n';
    }

    User(User&& other) noexcept : name(std::move(other.name)) {
        std::cout << "User::User(User&&) " << name << '\n';
    }

    User& operator=(const User& other) {
        if (this != &other)
            name = other.name;
        std::cout << "User::operator=(const User&) " << name << '\n';
        return *this;
    }

    User& operator=(User&& other) noexcept {
        if (this != &other)
            name = std::move(other.name);
        std::cout << "User::operator=(User&&) " << name << '\n';
        return *this;
    }

    friend bool operator<(const User& u1, const User& u2) {
        return u1.name < u2.name;
    }
};

Thanks to this additional code in special member functions, we can see when and how an object is created.

Saving Temporaries with Emplace  

With C++11, we got move semantics and lots of “emplace” functions.

To understand how can it help with insertion into map, let’s consider a following example:

std::map<std::string, User> mapNicks;
mapNicks["Johnny"] = User("John Doe");
std::cout << "after[]...\n";

Simple and easy… but do you know how many temporary objects will be created with this single map insertion?

Let’s see the output (live @Compiler Explorer)

User::User(std::string str) John Doe
User::User() default
User::operator=(User&&) John Doe
User::~User 
after[]...
User::~User John Doe

The crucial part is to notice that operator[] requires the class type to be default constructible, as it has to call T() before the assignment. We can notice that there’s one temporary object created (as there’s a call to destructor before ater[]... is printed out).

How about insert() member function? Is it better?

std::map<std::string, User> mapNicks;
mapNicks.insert({"Johnny", User("John Doe")});
std::cout << "after[]...\n";

And the output (live @Compiler Explorer):

User::User(std::string str) John Doe
User::User(User&&) John Doe
User::User(User&&) John Doe
User::~User 
User::~User 
after insert()...
User::~User John Doe

This time it’s even worse! Two extra objects were created!

Ok, so let’s try with the emplace():

std::map<std::string, User> mapNicks;
mapNicks.emplace("Johnny", User("John Doe"));
std::cout << "after[]...\n";

This time we have:

User::User(std::string str) John Doe
User::User(User&&) John Doe
User::~User 
after emplace()...
User::~User John Doe

But we can do better and save a temporary:

std::map<std::string, User> mapNicks;
mapNicks.emplace("Johnny", "John Doe");
std::cout << "after[]...\n";

And here’s the output (live @Compiler Explorer):

User::User(std::string str) John Doe
after emplace()...
User::~User John Doe

This code is possible as emplace takes arguments and passes it to to create std::pair<const Key, T> with the same arguments passes to emplace() and perfectly forwarded:

template< class... Args > std::pair<iterator,bool> emplace( Args&&... args );

Even more control with try_emplace, C++17  

As we can see so far, it looks like emplace is superior to insert, yet since it’s C++, things are not as clear :)

Have a look at the following example:

std::map<std::string, std::string> m;
m["Hello"] = "World";

We have a map of strings with one value inside.

How about trying to add a new value?

std::string s = "C++";
m.emplace("Hello", std::move(s));

We try (by mistake or by design) to push a new value and use move semantics.

emplace() cannot overwrite existing keys, so it should do nothing… but what happens with s? Was it moved or not?

See the output from GCC:

std::cout << "string s = " << s << '\n';
std::cout << "m[\"Hello\"] = " << m["Hello"] << '\n';

Output:

string s = 
m["Hello"] = World

As you can see, the value of s was moved, even though the insertion didn’t happen. It’s unspecified what happens in that case, which becomes an issue for emplace functions.

With C++17 we have new member function that should solve this problem:

s = "C++";
m.try_emplace("Hello", std::move(s));
std::cout << "string s = " << s << '\n';
std::cout << "m[\"Hello\"] = " << m["Hello"] << '\n';

In the basic form the new function try_emplace:

template< class... Args >
pair<iterator, bool> try_emplace( const Key& k, Args&&... args );

The main advantage is that it takes separate arguments for key and args… and it can the first lookup the key without the need to construct the pair of <const Key, Val> object. This way, it can prevent “stealing” from the object if the key is already present. For emplace(), you could only guarantee that by looking up the key first (via find or contains) and then making the emplacement.

You can play with the example @Compiler Explorer

The example with strings was a bit contrived, but it was handy to show the state of the moving string. But this problem is important for things like moveable only types that could be in the container. For example, map of unique_ptr:

std::map<std::string, std::unique_ptr<User>> mapNicks;
mapNicks["Johnny"] = std::make_unique<User>("John Doe");

auto pNewUser = std::make_unique<User>("Meggy Sue");
mapNicks.try_emplace("Johnny", std::move(pNewUser));
std::cout << "after insertions...\n";
std::cout << pNewUser->name << " still present!\n";

Play @Compiler Explorer

More information with insert_or_assign, C++17  

There’s also one more function.

std::map<std::string, User> mapNicks;
auto [it, inserted] = mapNicks.insert_or_assign("Johnny", User("John Doe"));
std::cout << "after insert_or_assign...\n";
std::cout << "inserted: " << inserted << '\n';
auto [it2, inserted2] = mapNicks.insert_or_assign("Johnny", User("Another John"));
std::cout << "after insert_or_assign 2...\n";
std::cout << "inserted: " << inserted2 << '\n';

output:

User::User(std::string str) John Doe
User::User(User&&) John Doe
User::~User 
after insert_or_assign...
inserted: 1
User::User(std::string str) Another John
User::operator=(User&&) Another John
User::~User 
after insert_or_assign 2...
inserted: 0
User::~User Another John

Play @Compiler Explorer

Guidelines for insertion functions  

Scott Meyers, in his book “Effective Modern C++”, in item 42, has a long discussion about the efficiency of “emplace.”

In general, with insert() you pass an object that should be added into the container, but with emplace(), you pass arguments that will be used to construct such object.

In many places, emplace could be more efficient and save temporary objects, but in some edge cases, you need to be aware of some limitations:

  • For example, when you pass new T() and the container will construct some smart pointer. In some cases, you could generate a memory leak when new happened, but the final construction didn’t.
  • In edge cases where passed arguments to emplace could create an invalid object, for example, passing nullptr to a vector of regex objects.

You can also have a look at Abseil guideline: abseil / Tip of the Week #112: emplace vs. push_back

Extracting and Merging, C++17  

So far, we’ve discussed several different ways of adding elements to containers, but that’s not all in Modern C++.

For example, with C++17, we got functions to manipulate “handles” and efficiently move them from one container to another (compatible).

See below:

std::map<std::string, User> mapShortcuts {
    { "Johnny", User {"John D."}},
    { "X", User {"Mark X."}},
    { "M", User {"Marry Jones"}},
};
std::map<std::string, User> outMap;

std::cout << "move X...\n";
// move John to the outSet
auto handle = mapShortcuts.extract("X");
outMap.insert(std::move(handle));

std::cout << "outMap contains:\n";

for (auto& [key, val] : outMap)
    std::cout << key << " : " << val.name << '\n';

std::cout << "cleanup...\n";

The output:

// skipping initialization of maps...
move X...
outMap contains:
X : Mark X.
cleanup...
User::~User Mark X.
User::~User Marry Jones
User::~User John D.

Play with the example @Compiler Explorer

As you can see in the output, there’s no extra temporary object created when I moved an element from mapShortcuts into outMap. Before C++17, there was no way to achieve such behavior. You’d have to remove elements from one container and then insert them into the output.

But that’s not all; there’s also one function, merge(), that allows you to transfer all matching elements from one container into another efficiently.

Have a look:

std::map<std::string, User> mapShortcuts {
    { "Johnny", User {"John D."}},
    { "X", User {"Mark X."}},
    { "M", User {"Marry Jones"}},
};
std::map<std::string, User> outMap {
    { "M", User {"Michael M."}},   
};

std::cout << "merging all...\n";
outMap.merge(mapShortcuts);

std::cout << "outMap contains:\n";

for (auto& [key, val] : outMap)
std::cout << key << " : " << val.name << '\n';

std::cout << "cleanup...\n";

In the example above, I merged all elements from mapShortcuts into outMap. And the output is:

// skipping initialization of maps...
merging all...
outMap contains:
Johnny : John D.
M : Michael M.
X : Mark X.
mapShortcut contains:
M : Marry Jones
cleanup...
User::~User Mark X.
User::~User Michael M.
User::~User John D.
User::~User Marry Jones

No temporary objects were created - as there’s no trace of them in the output.

Please notice that "M : Marry Jones" was not extracted because there was a conflicting node in outMap - "M : Michael M.".

Play with the example @Compiler Explorer.

Would you like to see more?
I wrote a Trie custom container! The first part is free and the other three are available for C++ Stories Patreon members. See all Premium benefits here.

Contains, C++20  

Before we complete the article, I’d like to mention two important functionalities in the recent revision of the language and the Standard Library.

First of all, we have a function called .contains().

This basically saves us from making mistakes when checking for the existence of some key in the container.

I still remember when I commited the similar code into production code years ago:

void TexMan::someFn(const std::map<std::string, Texture>& textures) {
    if (textures.find("global") == nullptr) { // !!!
        loadExtraData();
    }
    
    // some code...
}

Obviously you cannot compare against nullptr! you should always check against container.end():

if (textures.find("global") == textures.end()) {
    loadExtraData();
}

Thanks to C++20 you can now use the following code:

if (!textures.contains("global")) {
    loadExtraData();
}

It’s more explicit and easier to read!

See the example:

std::map<std::string, User> mapShortcuts {
    { "Johnny", User {"John D."}},
    { "X", User {"Mark X."}},
    { "M", User {"Marry Jones"}},
};

if (mapShortcuts.contains("X")) {
    std::cout << "X is present\n";
}

And small demo @Compiler Explorer

See the proposal in P0458R2

Standard Erase, C++20  

And one more feature.

C++20 has a consistent technique for erasing elements from various containers!

There is no more error-prone “remove erase” idiom, separate code paths for associative containers. Now we can just call non-member function overloads called std::erase or std::erase_if.

One note, associative containers have their member function .erase(), so the C++20 feature only added non-member erase_if in that case to avoid confusion.

std::erase_if(associative_container c, predicate pred) is equivalent to:

for (auto i = c.begin(), last = c.end(); i != last; ) {
  if (pred(*i)) {
    i = c.erase(i);
  } else {
    ++i;
  }
}

See the example code:

std::map<std::string, User> mapShortcuts {
    { "Johnny", User {"John D."}},
    { "X", User {"Mark X."}},
    { "M", User {"Marry Jones"}},
};

auto print = [](const std::string& str, const std::map<std::string, User>& container) {
    std::cout << str;
    for (const auto& [key, val] : container)
        std::cout << key << " : " << val.name << '\n';
};

print("before\n", mapShortcuts);

std::cout << "erasing...\n";

std::erase_if(mapShortcuts, [](auto& elem) {
    return elem.first == "X";
});

print("after erase...\n", mapShortcuts);

And the output:

before
Johnny : John D.
M : Marry Jones
X : Mark X.
erasing...
User::~User Mark X.
after erase...
Johnny : John D.
M : Marry Jones

See the code @Compile Explorer

See the proposal and the entire motivation in Adopt Consistent Container Erasure from Library Fundamentals 2 for C++20.

Summary  

From efficient insertions with emplace() and try_emplace(), full control with insert_or_assign() and even moving internal handles between containers. We covered a lot!

And what’s most important, I hope you can now apply those techniques in your projects.

And I forgot to mention unless stated; all the mentioned functions are available in all ordered and unordered containers. So not only std::map, but std::set, std::unordered_map, std::unordered_set and their multi* counterparts.

Back to you

  • What’s your favorite addition to “map” containers in Modern C++?

Share your feedback in the comments below the article.