4

最近我一直在分析不同标准库实现中的红黑树实现。令我感到奇怪的是，libstdc++ 似乎有不必要的大小开销。

稍微简化一下，这些类的组成如下：

// 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 有 40 个字节：1 个容器的 size_type，32 个字节用于堆栈分配的哨兵节点。

现在，真正让我吃惊的是 _Rb_tree_key_compare 是如何定义的：

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

这样定义后，_Rb_tree_impl 不能使用空基优化，并且由于对齐要求，这意味着没有非空成员的此类（对于无状态比较器）占用 8 个字节的空间（在 x64 构建上）。

为什么不是这样定义的？

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)
  { }

  /* ... */
};

（为了清楚起见，我删除了宏和 noexcept 说明符）

根据标准（如果我理解正确的话），初始化基类的规则与初始化成员的规则大致相同，因此作为基类，它也会被值初始化。

是否有一些我失踪的原因，迫使在这里使用组合而不是继承？似乎只是在标准容器中浪费了 8 个字节，这不是我怀疑的。（我知道由于 ABI 中断，它也无法修复）。

4

0 回答 0