How to Modify a Key in a C++ Map or Set

Published May 1, 2020

Contrary to sequence containers like std::vector, you can’t just assign a new value to a key of a std::map in C++, like this:

auto myMap = std::map<std::string, int>{ {"one", 1}, {"two", 2}, {"three", 3} };
myMap.find("two")->first = "dos";

Doing so makes the compiler output a copious amount of errors:

error: no match for 'operator=' (operand types are 'const std::__cxx11::basic_string<char>' and 'const char [4]')
     myMap.find("two")->first = "dos";
                                ^~~~~
In file included from /usr/local/include/c++/8.1.0/string:52,
                 from /usr/local/include/c++/8.1.0/bits/locale_classes.h:40,
                 from /usr/local/include/c++/8.1.0/bits/ios_base.h:41,
                 from /usr/local/include/c++/8.1.0/ios:42,
                 from /usr/local/include/c++/8.1.0/ostream:38,
                 from /usr/local/include/c++/8.1.0/iostream:39,
                 from main.cpp:2:
/usr/local/include/c++/8.1.0/bits/basic_string.h:654:7: note: candidate: 'std::__cxx11::basic_string<_CharT, _Traits, _Alloc>& std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::operator=(const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&) [with _CharT = char; _Traits = std::char_traits<char>; _Alloc = std::allocator<char>]' <near match>
       operator=(const basic_string& __str)
       ^~~~~~~~
/usr/local/include/c++/8.1.0/bits/basic_string.h:654:7: note:   passing 'const std::__cxx11::basic_string<char>*' as 'this' argument discards qualifiers
/usr/local/include/c++/8.1.0/bits/basic_string.h:693:7: note: candidate: 'std::__cxx11::basic_string<_CharT, _Traits, _Alloc>& std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::operator=(const _CharT*) [with _CharT = char; _Traits = std::char_traits<char>; _Alloc = std::allocator<char>]' <near match>
       operator=(const _CharT* __s)
       ^~~~~~~~
/usr/local/include/c++/8.1.0/bits/basic_string.h:693:7: note:   passing 'const std::__cxx11::basic_string<char>*' as 'this' argument discards qualifiers
/usr/local/include/c++/8.1.0/bits/basic_string.h:704:7: note: candidate: 'std::__cxx11::basic_string<_CharT, _Traits, _Alloc>& std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::operator=(_CharT) [with _CharT = char; _Traits = std::char_traits<char>; _Alloc = std::allocator<char>]' <near match>
       operator=(_CharT __c)
       ^~~~~~~~
/usr/local/include/c++/8.1.0/bits/basic_string.h:704:7: note:   conversion of argument 1 would be ill-formed:
main.cpp:8:32: error: invalid conversion from 'const char*' to 'char' [-fpermissive]
     myMap.find("two")->first = "dos";
                                ^~~~~
In file included from /usr/local/include/c++/8.1.0/string:52,
                 from /usr/local/include/c++/8.1.0/bits/locale_classes.h:40,
                 from /usr/local/include/c++/8.1.0/bits/ios_base.h:41,
                 from /usr/local/include/c++/8.1.0/ios:42,
                 from /usr/local/include/c++/8.1.0/ostream:38,
                 from /usr/local/include/c++/8.1.0/iostream:39,
                 from main.cpp:2:
/usr/local/include/c++/8.1.0/bits/basic_string.h:722:7: note: candidate: 'std::__cxx11::basic_string<_CharT, _Traits, _Alloc>& std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::operator=(std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&&) [with _CharT = char; _Traits = std::char_traits<char>; _Alloc = std::allocator<char>]' <near match>
       operator=(basic_string&& __str)
       ^~~~~~~~
/usr/local/include/c++/8.1.0/bits/basic_string.h:722:7: note:   passing 'const std::__cxx11::basic_string<char>*' as 'this' argument discards qualifiers
/usr/local/include/c++/8.1.0/bits/basic_string.h:776:7: note: candidate: 'std::__cxx11::basic_string<_CharT, _Traits, _Alloc>& std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::operator=(std::initializer_list<_Tp>) [with _CharT = char; _Traits = std::char_traits<char>; _Alloc = std::allocator<char>]'
       operator=(initializer_list<_CharT> __l)
       ^~~~~~~~
/usr/local/include/c++/8.1.0/bits/basic_string.h:776:7: note:   no known conversion for argument 1 from 'const char [4]' to 'std::initializer_list<char>'
/usr/local/include/c++/8.1.0/bits/basic_string.h:790:8: note: candidate: 'template<class _Tp> std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::_If_sv<_Tp, std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&> std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::operator=(const _Tp&) [with _Tp = _Tp; _CharT = char; _Traits = std::char_traits<char>; _Alloc = std::allocator<char>]'
        operator=(const _Tp& __svt)
        ^~~~~~~~
/usr/local/include/c++/8.1.0/bits/basic_string.h:790:8: note:   template argument deduction/substitution failed:

The impressive volume of errors comes from the fact that the key is of type std::string as a key. With ints as key, the error message would be more explicit:

error: assignment of read-only member 'std::pair<const int, std::__cxx11::basic_string<char> >::first'
 myMap.find(2)->first = 22;
                        ^~

And for a user-defined structure X, we get the following compiler output:

error: passing 'const X' as 'this' argument discards qualifiers [-fpermissive]
 myMap.find(X{})->first = X{};
                            ^
main.cpp:5:8: note:   in call to 'constexpr X& X::operator=(X&&)'
 struct X
        ^

Whereas changing a value in a map compiles fine:

auto myMap = std::map<std::string, int>{ {"one", 1}, {"two", 2}, {"three", 3} };
myMap.find("two")->second = 22;

We also have the same issues when changing a value in a std::set. The following code doesn’t compile:

auto mySet = std::set<std::string>{"one", "two", "three"};
mySet.find("two") = "dos";

Let’s see why we can’t change the key in a std::map and the values in std::set, and how to proceed when we need to do it. In particular in C++17 where the STL gets a new feature, extracts, to do this job more easily.

The problem with changing the key of a `std::map` (or the value of a `std::set`)

Contrary to sequence containers such as std::vector, std::map and std::set offers 2 guarantees:

they maintain their elements in sorted order,
they ensure their elements are unique (except for std::multimap and std::multiset).

If you don’t need those invariants, you can just use a std::vector and be done with it. However in the case of a map, the sorted order is convenient to make find the value associated to a key in logarithmic complexity.

To maintain these invariants, the containers std::map and std::set need to keep some control about the relative positions of their values inside of the collection.

If you just go about and modify a value by using an iterator, like in the example above, the container won’t be notified. This will make its structure inconsistent and break the invariants.

How to do the job in C++17

In C++17 or before, the solution is to use the interface of the container, and not try to bypass it by using its iterators.

In C++17, associative containers provide a methods called extract, that gives you the node that holds the element of a container. For example:

auto myMap = std::map<std::string, int>{ {"one", 1}, {"two", 2}, {"three", 3} };

auto const node = myMap.extract("two");

For a std::map, this node holds a key and a value. (Note that we don’t declare the node const because our purpose is to modify it!)

extract has a modifying effect on the container: the map no longer contains the node. If we check the size before and after the call to extract:

auto myMap = std::map<std::string, int>{ {"one", 1}, {"two", 2}, {"three", 3} };

std::cout << myMap.size() << '\n';
auto node = myMap.extract("two");
std::cout << myMap.size() << '\n';

This program outputs:

3
2

The size was was reduced by one, which means that you’re now the sole owner of that node.

As a result, modifying the values inside of this node won’t break anything in the map, because they’re no longer connected. The node provide a non-const accessor to its key():

node.key() = "dos";

It is interesting to note that maps’s node doesn’t provide a value() accessor. If you need to change the value, it is more efficient to directly do so in the map. You don’t need to extract the node in the first place. The language prevents us from doing the inefficient solution, by restricting the interface of the node for maps.

After you’ve modified the key, you can now put the node back into the container by using the insert method that has an overload for node types since C++17:

myMap.insert(std::move(node));

Note the std::move. It is nice because it expresses that, after this line, the owner of the node becomes the container. What is even nicer is that the code wouldn’t compile if we just wrote:

myMap.insert(node);

Because node only have a move constructor, and not a copy constructor.

Using the insert method allows the container to position the node at the correct location in order to maintain its invariants.

The case where the requested node doesn’t exist

What if we try to extract a node that doesn’t exist:

auto myMap = std::map<std::string, int>{ {"one", 1}, {"two", 2}, {"three", 3} };

auto node = myMap.extract("four");

node is still a valid object, and we can even send it to insert. It would have no effect. However, we can’t access its key(). The following code is undefined behaviour (on the use case I tried, it crashed):

auto myMap = std::map<std::string, int>{ {"one", 1}, {"two", 2}, {"three", 3} };

auto node = myMap.extract("four");

auto key = node.key(); // UB!

Therefore, we need to check that the node is not empty. For this, no need to make a preliminary search before calling extract. We can just test the empty() method of the node.

All put together, the code to change a key in a std::map in C++17 looks like this:

auto myMap = std::map<std::string, int>{ {"one", 1}, {"two", 2}, {"three", 3} };

auto node = myMap.extract("two");
if (!node.empty())
{
    node.key() = "dos";
    myMap.insert(std::move(node));
}

Before C++17

But is this concept of removing an element from a map to put it back it at the right position such a new thing? Didn’t it exist before C++17?

It did, but it was less efficient and less straightforward.

To achieve the same effect before C++17, we have to erase the element from the container, and then reinsert a new one. Therefore we also lose the value of the erased element in the process. We need to backup this value:

auto myMap = std::map<std::string, int>{ {"one", 1}, {"two", 2}, {"three", 3} };

auto entry = myMap.find("two");
if (entry != end(myMap))
{
    auto const value = std::move(entry->second);
    myMap.erase(entry);
    myMap.insert({"two", std::move(value)});
}

What about sets?

So far we’ve only talked about maps. How do we go about changing a value in a std::set?

The difference between sets and maps here is that sets didn’t have a problem with the pre-C++17 technique, since they didn’t have any value to backup:

auto mySet = std::set<std::string>{"one", "two", "three"};

auto entry = mySet.find("two");
if (entry != end(mySet))
{
    mySet.erase(entry);
    mySet.insert("dos");
}

std::set also gets an extract function with C++17 that works like the one for std::map, except the node has a method called value(), not key():

auto node = mySet.extract("two");
if(!node.empty())
{
    node.value() = "dos";
    mySet.insert(std::move(node));
}

But contrary to std::map, the C++17 version for std::set is just as simple and efficient as the pre-C++17 version.

A nice cheat sheet

A nice take-away of this topic is summed up in one of Walletfox’s cheat sheets:

C++ map modify key

Walletfox crafts awesome cheat sheets every week, and I strongly suggest that, like me, you subscribe to their mailing list to be sure not to miss them.

Talking about mailing lists, why don’t you subscribe to the Fluent C++ mailing list too, at the bottom of this post? I recommend it as well 🙂

Encapsulating the details behind an interface

Nodes are a cool concept, but they are rather low-level details. In terms of levels of abstraction, this is not something you’d like to think about when you read business code.

Indeed, it would be clearer for code read like “modify the value of key” rather than “extract a node, modify its key and reinsert that node back into the collection”. The latter is how to implement the former, therefore it is at the level of abstraction below it.

Here is a function suggested by Walletfox to encapsulate the low-level details related to nodes. With the Container being a template parameters, it works for std::map and std::multimap:

template<typename Container>
void replaceKey(Container& container,
                const typename Container::key_type& oldKey,
                const typename Container::key_type& newKey)
{
    auto node = container.extract(oldKey);
    if(!node.empty())
    {
        node.key() = newKey;
        container.insert(std::move(node));
    }
}

Unfortunately, such a function doesn’t work for std::set (and std::unordered_set) because one type of nodes has key() and the other has value(). That leads to difficulties in overloading the replaceKey function for sets. We will dig into this subject in a future post.