为什么libc++的map实现要用这个union?
Why does libc++'s implementation of map use this union?
#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>
(这是迭代器的值类型等)。但我不明白为什么它需要可分配或可移动,因为我看不出任何实现需要在地图内复制或移动节点的原因,或者除了构造和销毁它们之外做任何事情-放置并重新配置指针。
当您使用自定义分配器时,可能需要将地图(及其内容)移动到新的资源池中。在这种情况下,此重载将提供对键的可移动访问:
__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
和 __nc
,将其留给构造函数来访问包含 first
和 [=21 的公共子序列=].标准布局类型的 requirements 有点限制,但许多常见的键和值类型(例如,std::string
)可能会满足它们。
这支持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
个节点:
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]
因此允许容器非常量访问地图的 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 和更高标准的支持。联合技巧是实现该优化的一种(不一定是可移植的)方法。
当分配器不在移动分配上传播并且两个分配器比较不相等时,通过移动分配运算符的相同代码获得类似的优化:
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
#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>
(这是迭代器的值类型等)。但我不明白为什么它需要可分配或可移动,因为我看不出任何实现需要在地图内复制或移动节点的原因,或者除了构造和销毁它们之外做任何事情-放置并重新配置指针。
当您使用自定义分配器时,可能需要将地图(及其内容)移动到新的资源池中。在这种情况下,此重载将提供对键的可移动访问:
__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
和 __nc
,将其留给构造函数来访问包含 first
和 [=21 的公共子序列=].标准布局类型的 requirements 有点限制,但许多常见的键和值类型(例如,std::string
)可能会满足它们。
这支持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
个节点:
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]
因此允许容器非常量访问地图的 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 和更高标准的支持。联合技巧是实现该优化的一种(不一定是可移植的)方法。
当分配器不在移动分配上传播并且两个分配器比较不相等时,通过移动分配运算符的相同代码获得类似的优化:
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