How can I avoid wasteful copying of keys in a B-tree based STL-like map?

I'm replacing a use of std::map in a hot path with cpp-btree's btree_map. But with optimization enabled, GCC and Clang complain about a strict aliasing violation. The problem boils down to this:

template <typename Key, typename Value>
class btree_map {
public:
    // In order to match the standard library's container interfaces
    using value_type = std::pair<const Key, Value>;

private:
    using mutable_value_type = std::pair<Key, Value>;

    struct node_type {
        mutable_value_type values[N];
        // ...
    };

public:
    class iterator {
        // ...

        value_type& operator*() {
            // Here we cast from const std::pair<Key, Value>&
            // to const std::pair<const Key, Value>&
            return reinterpret_cast<value_type&>(node->values[i]);
        }
    };

    std::pair<iterator, bool> insert(const value_type& value) {
        // ...
        // At this point, we have to insert into the middle of a node.
        // Here we rely on nodes containing mutable_value_type, because
        // value_type isn't assignable due to the const Key member
        std::move_backward(node->values + i, node->values + j,
                           node->values + j + 1);
        node->values[i] = value;
        // ...
    }
};

This got me thinking, is there a way to do this as efficiently that doesn't rely on undefined behaviour? The keys I'm using are efficiently moveable but fairly slow to copy, so I'd love to avoid copying many keys on every insertion. I've considered

• Using value_type values[N], then const_cast<Key&>(values[i].first) = std::move(key) to move the key around, but I'm pretty sure that's still undefined


• Returning std::pair<const Key&, Value&> instead of std::pair<const Key, Value>& when appropriate, but I'm not sure this would still satisfy the container requirements (I hear ...::reference is supposed to really be a reference type)


• Not caring. The code works as-is, but I'm curious if it can be done in a standard-compliant way. There's also the chance that future compilers do different things with the UB, and I don't know of a way to apply -fno-strict-aliasing to only a single class.

Any other ideas?