vector::clear 在 libc++ 中用于简单可破坏的类型

Question

如果 T 是微不足道的可破坏的，vector<T, std::allocator<T>>::clear() 会是 O(1) 吗？

gcc 在 bits/stl_vector.h 中的实现调用 std::_Destroy(bits/stl_construct.h)。此实现优化了 T 通过 std::is_trivially_destructible<T>.

上的标签分派可轻易破坏的情况

查看 llvm(3.5.0) 的实现，vector::clear 在每个元素上调用 std::allocator<T>::destroy，这又会调用析构函数。

 _LIBCPP_INLINE_VISIBILITY void destroy(pointer __p) {__p->~_Tp();}

这最终会在 libc++ 中得到优化而不是制作 vector::clear() O(1) 吗？

Answer 1

一般来说，对于具有非平凡析构函数的类型，符合规范的实现无法在 O(1) 中实现 std::vector::clear。

C++11 [container.requirements.general]/3 状态：

For the components affected by this subclause that declare an allocator_type, objects stored in these components shall be constructed using the allocator_traits<allocator_type>::construct function and destroyed using the allocator_traits<allocator_type>::destroy function (20.6.8.2).

由于 clear 必须销毁 size() 个元素，因此它必然需要对关联分配器的 destroy 函数进行 O(N) 次调用。然而，如果这些调用中的每一个都花费零时间完成（即什么都不做），最终结果实际上可以花费常数时间。

快速查看 the current revision of libstdc++'s bits/stl_construct.h 中 _Destroy 的实现表明它仅尝试在使用默认分配器时执行此优化：

  /**
   * Destroy the object pointed to by a pointer type.
   */
  template<typename _Tp>
    inline void
    _Destroy(_Tp* __pointer)
    { __pointer->~_Tp(); }

  template<bool>
    struct _Destroy_aux
    {
      template<typename _ForwardIterator>
        static void
        __destroy(_ForwardIterator __first, _ForwardIterator __last)
      {
        for (; __first != __last; ++__first)
          std::_Destroy(std::__addressof(*__first));
      }
    };

  template<>
    struct _Destroy_aux<true>
    {
      template<typename _ForwardIterator>
        static void
        __destroy(_ForwardIterator, _ForwardIterator) { }
    };

  /**
   * Destroy a range of objects.  If the value_type of the object has
   * a trivial destructor, the compiler should optimize all of this
   * away, otherwise the objects' destructors must be invoked.
   */
  template<typename _ForwardIterator>
    inline void
    _Destroy(_ForwardIterator __first, _ForwardIterator __last)
    {
      typedef typename iterator_traits<_ForwardIterator>::value_type
                       _Value_type;
      std::_Destroy_aux<__has_trivial_destructor(_Value_type)>::
        __destroy(__first, __last);
    }

  /**
   * Destroy a range of objects using the supplied allocator.  For
   * nondefault allocators we do not optimize away invocation of 
   * destroy() even if _Tp has a trivial destructor.
   */

  template<typename _ForwardIterator, typename _Allocator>
    void
    _Destroy(_ForwardIterator __first, _ForwardIterator __last,
         _Allocator& __alloc)
    {
      typedef __gnu_cxx::__alloc_traits<_Allocator> __traits;
      for (; __first != __last; ++__first)
        __traits::destroy(__alloc, std::__addressof(*__first));
    }

  template<typename _ForwardIterator, typename _Tp>
    inline void
    _Destroy(_ForwardIterator __first, _ForwardIterator __last,
         allocator<_Tp>&)
    {
      _Destroy(__first, __last);
    }

但不幸的是，它并没有完全正确，因为该标准允许 std 命名空间中的模板专门化，这些模板依赖于用户定义的类型 ([namespace.std]/1)。例如这个程序：

struct mytype {
    int value;

    mytype(int v) : value{v} {}

    operator int() const { return value; }
};

namespace std {
template <>
struct allocator<::mytype> {
    using value_type = mytype;

    allocator() = default;
    template <typename U>
    allocator(const allocator<U>&) {}

    mytype* allocate(std::size_t n) {
        auto result = ::operator new(n * sizeof(mytype));
        if (!result) throw bad_alloc();
        return static_cast<mytype*>(result);
    }

    void deallocate(mytype* ptr, std::size_t) noexcept {
        ::operator delete(ptr);
    }

    template <typename U, typename...Args>
    void construct(U* ptr, Args&&...args) {
        ::new ((void*)ptr) U(std::forward<Args>(args)...);
        std::cout << "constructed " << *ptr << '\n';
    }

    template <typename U>
    void destroy(U* ptr) noexcept {
        std::cout << "destroying " << *ptr << '\n';
        ptr->~U();
    }

    friend constexpr bool operator == (const allocator&, const allocator&) noexcept {
        return true;
    }
    friend constexpr bool operator != (const allocator&, const allocator&) noexcept {
        return false;
    }
};
} // namespace std

int main() {
    std::vector<mytype>{1,2,3};
}

应该输出：

constructed 1
constructed 2
constructed 3
destroying 3
destroying 2
destroying 1

（未指定元素销毁的顺序，因此 "destroying" 行可以按任何顺序排列但必须全部存在。）libstdc++ 错误地 "optimizes" 调用了 allocator<mytype>::construct和 allocator<mytype>::destroy，当然 libc++ 做对了 (DEMO)。

vector::clear 在 libc++ 中用于简单可破坏的类型

vector::clear in libc++ for trivially destructible types

c++

llvm

clang

stdvector

c++11