如何避免在基于B树的类似STL的地图中浪费复制密钥？

Question

我更换使用std::map与热路径CPP-B树的btree_map.但是在启用优化的情况下,GCC和Clang抱怨严格的别名违规.问题归结为:

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;
        // ...
    }
};

这让我想到,有没有办法有效地做到这一点,不依赖于未定义的行为？我正在使用的按键是高效可移动的,但复制起来相当慢,所以我希望避免在每次插入时复制许多按键.我考虑过了

• 使用value_type values[N],然后const_cast<Key&>(values[i].first) = std::move(key)移动键,但我很确定仍然未定义
• 返回std::pair<const Key&, Value&>而不是std::pair<const Key, Value>&在适当的时候,但我不确定这仍然会满足容器要求(我听说...::reference应该真的是一个参考类型)
• 不在乎.代码按原样运行,但我很好奇它是否可以以符合标准的方式完成.未来的编译器也有可能与UB做不同的事情,我不知道-fno-strict-aliasing如何只应用于一个类.

还有其他想法吗？

Answer 1

引用严格的别名规则,

如果程序试图通过不同于以下类型之一的左值访问对象的存储值,则行为未定义:

• ...

• 一种聚合或联合类型,包括其成员中的上述类型之一(包括递归地,子聚合或包含联合的成员),......

因此,从std :: pair <Key,Value>到std :: pair <const Key,Value>通过中间强制转换为一个union或一个包含两个类型作为成员的结构将不会破坏严格的别名规则.

警告:联合中的std :: pair在C++ 11之前是不允许的,可以使用结构代替.

警告:假设两对类型具有兼容的布局可能不成立.想象一下,根据Key类型的常量,以不同的顺序排序第一个和第二个的实现.