`noexcept` move constructors for `flex_vector` and other data-structures

[maierlars]

I looked into making the move constructor (and move-assignment) for flex_vector noexcept. This is something people (at least myself) want to ensure exception safety. Generally you want you types to be nothrow move constructible.

It turns out to be not that trivial: it allocates nodes. This is similar to what the MSVC implementation of std::unordered_map does and it caused me a lot of pain in the past. At least the swap operation is de facto noexcept, but not marked as such.

I propose two solutions:

1. do not allocate anything unless necessary. This would introduce some special cases, where nullptr to head and tail node would indicate an empty flex_vector.
2. This is similar to libstdc++ does for std::unordered_map: store the end nodes within the object itself. This would require to replace the end-nodes with the new end-nodes during a move operation.

I prefer approach 1. Any ideas or opinions? Maybe there is a good reason to not have flex_vectors move constructor and assignment noexcept.

[arximboldi]

Hmmm... it does allocate memory but only the first time it is ever invoked, to allocate the initial "empty" node. We could maybe add some statics to pre-initialize the empty node... but that could cause trouble when using the data-structures in statics itself. Maybe the option 1) is the best? Not sure about how 2) would look like (what's an end node? you mean the root node?). I agree having a noxexcept move can be rather crucial.

[maierlars]

I see, it's essentially this piece of code, that does an allocation.

Since the nodes are already shared between multiple flex-vectors, instead of keeping a pointer to an allocation in a static variable, one could instead keep the whole node as a static variable and return a pointer to it. 🤔 I might try that later today.

[maierlars]

https://github.com/arximboldi/immer/pull/246

[maierlars]

    /*!
     * Default constructor.  It creates a flex_vector of `size() == 0`.
     * It does not allocate memory and its complexity is @f$ O(1) @f$.
     */
    flex_vector() = default;

I just noticed that the comment is slightly incorrect.

[arximboldi]

I love the approach with a static allocation for the node. It's the cleanest approach. More comments in the PR, but thanks a lot for noticing and taking care of this!

[maierlars]

Issue can be close, because PR was merged.

Or do we want to keep it open to track progress for other data structures?

[arximboldi]

Renamed and left it open to keep track of this for other data-structures. Thanks!

[mvtec-richter]

We'd like immer::map to have nothrow move constructor and assignment as well. I guess, it's only necessary to add noexcept to champ(champ&& other) and champ& operator=(champ&& other).

[arximboldi]

@mvtec-richter you may need to apply the same techniques as in #246 in order to ensure that the default constructor is nothrow.