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?

Larrisa

Possible duplicate of Why aren't container move assignment operators noexcept? – Facsimile

There is one overload that takes an allocator argument. That presumably needs to allocate new nodes and move-construct the contents, so allocation could fail. This doesn't explain the other overload though, since the allocator itself should be move constructible. – Steddman

Not a duplicate of Why aren't container move assignment operators noexcept? because a move constructor is not the same thing as a move assignment operator. Furthermore the answer for these two different special members is different. – Marquettamarquette

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.

Marquettamarquette

looking at the survey, it seems like MSVC's std::map implementation isn't noexcept movable. I'm curious what is special about MSVC's implementation that std::map can't be noexcept moved? – Larrisa

For the move constructor, they put their end node on the heap, thus they always have to allocate an end node during move construction. – Marquettamarquette

If the end node is on the heap, why can't it copy the pointer to end node during move? – Larrisa

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. After the move construction there must exist two end nodes. If the design is that end nodes go on the heap, then a new one must be allocated. If the design is that end nodes are embedded within the map, then the end node "allocation" is "on the stack". – Marquettamarquette

Thx. That's the answer I'm looking for. Would you edit your answer to include this comment? – Larrisa

Done. If that's still not right, just let me know how I can improve it, thanks. – Marquettamarquette

So this means I cannot create a noexcept move constructor for any class that contains map instances. Correct? – Distal

You could make your move constructor conditionally noexcept, conditioned on if map is is_nothrow_move_constructible. This would create a noexcept move constructor on 2 out of 3 major implementations. – Marquettamarquette

I stumbled upon this before seeing the stackoverflow post and made bug report for VS2019. developercommunity.visualstudio.com/t/…. – Checani

If one does not want an end iterator to be invalidated upon move construction, yet wants to provide the noexcept guarantee, should the end node be static/global? I see in LWG 2321 there's a note in the proposed changes: Note: The end() iterator does not refer to any element, so it may be invalidated. — end note. Is there any good reason to avoid invalidating end iterators? The reason I ask is that I'm implementing a customized trie and am trying to make it as standards-conforming as possible, using std::map as a model. – Darmit

In my proposed static/global end node above, I think it would lead to problems with shared libraries having their own separate instance of the end node. – Darmit

I think a static/global end node would be fine for a container with forward iterators. But for bidirectional iterators the end iterator has to know how to decrement to the previous node. It usually gets this information from the end node, which of course would be different for each container. Perhaps that information could be stored in the iterator itself? – Marquettamarquette

@HowardHinnant, My trie is indeed only forward traverse-able, but I don't want to paint myself in a corner if I later decide to make it bidirectional. I was too afraid to get the static/global node wrong with shared libraries, so I ended up forsaking the guarantee not to invalidate end iterators, which is permitted anyway (as I understand it). BTW your answers on allocator-aware containers have been invaluable in me making my trie-based container allocator-aware. Thank you! – Darmit