Reputation: 1163
Lately I've been analyzing red-black tree implementations in different standard library implementations. What struck me as odd, is that libstdc++ seems to have unnecessary size overhead.
Simplifying a little, the classes are composed like that:
// std::set
template </*...*/>
class set {
_Rb_tree</*...*/> _M_t;
};
// stl_tree.h:434
template </*...*/>
class _Rb_tree {
// stl_tree.h:670
template </*...*/>
struct _Rb_tree_impl
: public _Node_allocator
, public _Rb_tree_key_compare<_Key_compare>
, public _Rb_tree_header {};
_Rb_tree_impl</*...*/> _M_impl;
};
Header has 40 bytes: 1 size_type of the container, and 32 bytes for stack-allocated sentinel node.
Now, what really was a surprise for me, is how _Rb_tree_key_compare is defined:
// stl_tree.h:140
// Helper type offering value initialization guarantee on the compare functor.
template <typename _Key_compare>
struct _Rb_tree_key_compare
{
_Key_compare _M_key_compare;
_Rb_tree_key_compare()
_GLIBCXX_NOEXCEPT_IF(
is_nothrow_default_constructible<_Key_compare>::value)
: _M_key_compare()
{ }
_Rb_tree_key_compare(const _Key_compare& __comp)
: _M_key_compare(__comp)
{ }
#if __cplusplus >= 201103L
// Copy constructor added for consistency with C++98 mode.
_Rb_tree_key_compare(const _Rb_tree_key_compare&) = default;
_Rb_tree_key_compare(_Rb_tree_key_compare&& __x)
noexcept(is_nothrow_copy_constructible<_Key_compare>::value)
: _M_key_compare(__x._M_key_compare)
{ }
#endif
};
With it defined like that, _Rb_tree_impl cannot use empty base optimization, and due to alignment requirements it means that this class with no non-empty members (for stateless comparators) takes up 8 bytes of space (on x64 builds).
Why wasn't it defined like that?
template <typename _Key_compare>
struct _Rb_tree_key_compare : _Key_compare
{
_Rb_tree_key_compare()
: _Key_compare()
{ }
_Rb_tree_key_compare(const _Key_compare& __comp)
: _Key_compare(__comp)
{ }
/* ... */
};
(I removed macros and noexcept specifiers for clarity)
According to standard (if I understand it correctly), the rules for initializing base classes are roughly the same as for initializing members, so as a base class it will be value-initialized as well.
Is there some reason I'm missing, that forced the use of composition instead of inheritance here? It seems like simply wasted 8 bytes in standard container, and it's not something I would suspect. (I know it can't be fixed either due to ABI break).
Upvotes: 4
Views: 201