为什么libc ++的map实现使用了这个联合？

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>(这是迭代器的值类型等).但我不明白为什么它需要可分配或可移动,因为我看不出任何理由为什么实现需要复制或移动地图内的节点,或者实际上做除了构造和销毁之外的任何事情-place,并重新配置指针.

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";
}

在这种特殊情况下,我预见到需要循环地图的节点,并重新分配"const"键以使节点的循环有效.因此

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

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

关联容器满足Allocator感知容器的所有要求(23.2.1 [container.requirements.general]),除容器map和multimap外,表93中value_type的要求直接应用于key_type和mapped_type.[注意:例如,即使value_type(pair)不是CopyAssignable,有时也需要key_type和mapped_type为CopyAssignable. - 结束说明]

从而允许容器非const访问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,或包含这些常见标准类型之一的类型时,分配优于销毁,然后构造,具有巨大的性能优势.赋值可以利用lhs中的现有容量,通常导致简单memcpy而不是释放内存,然后分配内存.

注意,上面~A()可能意味着整个节点的释放,而不仅仅是A(尽管不一定).无论如何,libc ++ map拷贝赋值运算符都经过高度优化以回收内存,并且该优化的许可由C++ 11及更高标准支持.联合技巧是实现该优化的一种(不一定是可移植的)方式.

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

铛/的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

Answer 2

使用自定义分配器时,可能需要将映射(及其内容)移动到新的资源池中.在这种情况下,此重载将提供对键的可移动访问:

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

密钥已被移动并不重要,因为接下来发生的事情是释放所有节点.

请注意,此用法可能会导致未定义的行为.你通常不能写一个联盟的一个成员然后读另一个.只要可以在内部保证它不会导致问题(或错误诊断),Clang和libc ++就可以做到这一点.

不过,他们可能就是这样做的,因为没有合适的替代品.至少,我想不出一个.标准要求value_type::first_type是真正const合格的,所以即使const_cast是不允许的.

诀窍是在该情况下符合key_type和mapped_type都是标准的布局,以便std::pair<key_type, mapped_type>与std::pair<key_type const, mapped_type>是布局兼容,每[class.mem]第9.2节/ 16.这看起来有点奇怪,因为函数指的是直接成员__cc和__ncunion,将它留给构造函数来访问包含first和的公共子序列second.标准布局类型的要求有些限制,但许多常见的键和值类型(例如std::string)可能会满足它们.