c++ - 为什么libc++的map实现要用这个union？

Question

#if __cplusplus >= 201103L

template <class _Key, class _Tp>
union __value_type
{
    typedef _Key                                     key_type;
    typedef _Tp                                      mapped_type;
    typedef pair<const key_type, mapped_type>        value_type;
    typedef pair<key_type, mapped_type>              __nc_value_type;

    value_type __cc;
    __nc_value_type __nc;

    template <class ..._Args>
    _LIBCPP_INLINE_VISIBILITY
    __value_type(_Args&& ...__args)
        : __cc(std::forward<_Args>(__args)...) {}

    _LIBCPP_INLINE_VISIBILITY
    __value_type(const __value_type& __v)
        : __cc(__v.__cc) {}

    _LIBCPP_INLINE_VISIBILITY
    __value_type(__value_type& __v)
        : __cc(__v.__cc) {}

    _LIBCPP_INLINE_VISIBILITY
    __value_type(__value_type&& __v)
        : __nc(std::move(__v.__nc)) {}

    _LIBCPP_INLINE_VISIBILITY
    __value_type& operator=(const __value_type& __v)
        {__nc = __v.__cc; return *this;}

    _LIBCPP_INLINE_VISIBILITY
    __value_type& operator=(__value_type&& __v)
        {__nc = std::move(__v.__nc); return *this;}

    _LIBCPP_INLINE_VISIBILITY
    ~__value_type() {__cc.~value_type();}
};

#else
// definition for C++03...

看起来目的是制作__value_type可分配和移动，同时还能够将内容公开为 pair<const key_type, mapped_type> (这是迭代器的值类型等等)。但我不明白为什么它需要可分配或可移动，因为我看不出任何实现需要在 map 内复制或移动节点的原因，或者除了构造和销毁它们之外做任何事情-放置并重新配置指针。

Answer 1

这是为了支持 Potatoswatter的回答。我作为此 libc++ 代码的作者回答。

考虑:

int
main()
{
    std::map<A, int> m1;
    m1[A{1}] = 1;
    m1[A{2}] = 2;
    m1[A{3}] = 3;
    std::map<A, int> m2;
    m2[A{4}] = 4;
    m2[A{5}] = 5;
    m2[A{6}] = 6;
    std::cout << "start copy assignment\n";
    m2 = m1;
    std::cout << "end copy assignment\n";
}

在这种特殊情况下，我预见到需要回收 map 的节点，并重新分配“const”键以使节点回收高效。因此

http://cplusplus.github.io/LWG/lwg-defects.html#704

插入以下措辞以允许回收 map节点:

The associative containers meet all of the requirements of Allocator-aware containers (23.2.1 [container.requirements.general]), except for the containers map and multimap, the requirements placed on value_type in Table 93 apply instead directly to key_type and mapped_type. [Note: For example key_type and mapped_type are sometimes required to be CopyAssignable even though the value_type (pair) is not CopyAssignable. — end note]

因此允许容器非常量访问 map 的 key_type。迄今为止，只有 libc++ 利用了这一点。如果你仪器A在上面的示例中，您将获得 libc++:

start copy assignment
operator=(const A& a)
operator=(const A& a)
operator=(const A& a)
end copy assignment

对于 libstdc++ (gcc-5.2.0)

start copy assignment
~A()
A(A const& a)
~A()
A(A const& a)
~A()
A(A const& a)
end copy assignment

对于 VS-2015:

start copy assignment
~A()
~A()
~A()
A(A const& a)
A(A const& a)
A(A const& a)
end copy assignment

我断言当A是一种类型，例如 int , std::vector或 std::string ，或包含这些常见 std 类型之一的类型，赋值比先破坏后构造具有巨大的性能优势。分配可以利用 lhs 中的现有容量，通常会导致简单的 memcpy。而不是先释放内存再分配内存。

注意上面的~A()可能意味着整个节点的重新分配，而不仅仅是 A (虽然不一定)。无论如何，libc++ map复制赋值运算符针对回收内存进行了高度优化，并且该优化的许可得到了 C++11 和更高标准的支持。 union 技巧是实现该优化的一种(不一定是可移植的)方法。

当分配器不在移动分配上传播并且两个分配器比较不相等时，通过移动分配运算符的相同代码获得类似的优化:

clang /libc++:

start move assignment
operator=(A&& a)
operator=(A&& a)
operator=(A&& a)
end move assignment

gcc-5.2.0

start move assignment
~A()
A(A const& a)
~A()
A(A const& a)
~A()
A(A const& a)
~A()
~A()
~A()
end move assignment

VS-2015

start move assignment
~A()
~A()
~A()
A(A const& a)
A(A const& a)
A(A const& a)
end move assignment