Why is std::map's move constructor not noexcept?

Question

As said by cppreference.com,

Maps are usually implemented as red-black trees.

So moving a std::map is just moving the pointer to the root node + other information such as size. Why is std::map's move constructor not marked as noexcept?

Answer 1

It is because I couldn't talk all of the implementors into a resource-less state that the map could be put into. For example an implementation needs to have an end-node to point to, even in the default-constructed state. Implementations are allowed, but not required, to put that end-node on the heap.

A moved-from map must be in a valid state. I.e. a moved-from map must have an end node to point to when end() gets called. Before the move construction, there exists one end node in the map that you're about to move from. After the move construction there must exist two end nodes: one in the new map and one in the moved-from `map.

If the end node goes on the heap, that means that the move constructor either doesn't transfer ownership of the end node, and thus has to allocate a new end node for the new `map. Or does transfer the end node, but then has to allocate a new one to leave in the moved-from source.

If the end node is instead embedded within the map data structure itself, then it never need be allocated on the heap. It is automatically "allocated on the stack" as the map gets constructed.

Implementations are allowed to make the map move constructor noexcept if they want to, they just aren't required to.

Here is a survey of the noexcept-state of the default constructor, move constructor and move assignment operator of the containers among the implementations that I took several years ago. This survey assumes std::allocator for each container. I just spot checked it for map and the results haven't changed.

If you would like to run this survey yourself, here is the code:

#include "type_name.h"
#include <iostream>
#include <type_traits>

#include <deque>
#include <forward_list>
#include <list>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

template <class C>
void
report()
{
    using namespace std;
    const auto name = type_name<C>();
    if (is_nothrow_default_constructible<C>::value)
        std::cout << name << " is noexcept default constructible\n";
    else
        std::cout << name << " is NOT noexcept default constructible\n";
    if (is_nothrow_move_constructible<C>::value)
        std::cout << name << " is noexcept move constructible\n";
    else
        std::cout << name << " is NOT noexcept move constructible\n";
    if (is_nothrow_move_assignable<C>::value)
        std::cout << name << " is noexcept move assignable\n\n";
    else
        std::cout << name << " is NOT noexcept move assignable\n\n";
}

int
main()
{
    using namespace std;
    report<deque<int>>();
    report<forward_list<int>>();
    report<list<int>>();
    report<vector<int>>();
    report<string>();
    report<map<int, int>>();
    report<set<int>>();
    report<unordered_map<int, int>>();
    report<unordered_set<int>>();
}

where "type_name.h" comes from this answer.