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

Question

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

gcc 在 bits/stl_vector.h 中的实现电话 std::_Destroy (bits/stl_construct.h)。此实现优化了 T 可通过在 std::is_trivially_destructible<T> 上进行标签分派(dispatch)而被轻易破坏的情况。 .

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

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

这最终会得到优化吗 vector::clear() O(1)也在 libc++ 中？

Answer 1

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

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) 次调用相关分配器的功能。然而，如果这些调用中的每一个都花费零时间完成(即什么都不做)，最终结果实际上可以花费常数时间。

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

  /**
   * 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 1constructed 2constructed 3destroying 3destroying 2destroying 1

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