वेक्टर :: libC++ में स्पष्ट रूप से विनाशकारी प्रकारों के लिए साफ़

Question

vector<T, std::allocator<T>>::clear()O(1)T बहुत ही विनाशकारी है?

bits/stl_vector.h में जीसीसी का कार्यान्वयन std::_Destroy (bits/stl_construct.h) कॉल करता है। यह कार्यान्वयन जो 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

सामान्य रूप से, एक अनुरूप कार्यान्वयन गैर-तुच्छ विनाशकों वाले प्रकारों के लिए ओ (1) में std::vector::clear लागू नहीं कर सकता है।

सी ++ 11 [container.requirements.general]/3 राज्यों:

घटकों इस उपखंड है कि एक allocator_type घोषित से प्रभावित के लिए, इन घटकों में संग्रहीत वस्तुओं allocator_traits<allocator_type>::construct समारोह का प्रयोग कर बनाया जाएगा और allocator_traits<allocator_type>::destroy फ़ंक्शन (20.6.8.2) का उपयोग करके नष्ट कर दिया गया।

clear के बाद से size() तत्वों को नष्ट करना होगा, यह जरूरी हे (एन) बनाने के लिए जुड़े संभाजक की destroy फ़ंक्शन पर कॉल की जरूरत है। अंत परिणाम, हालांकि, प्रभावी रूप से निरंतर समय ले सकता है यदि उनमें से प्रत्येक कॉल को शून्य करने के लिए शून्य समय लगता है (यानी, कुछ भी नहीं करता है)।

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 

(। इसलिए "को नष्ट करने" लाइनों किसी भी क्रम में हो सकता है, लेकिन सभी उपस्थित होना चाहिए तत्व विनाश के आदेश, अनिर्दिष्ट है) libstdC++ allocator<mytype>::construct और allocator<mytype>::destroy पर कॉल को गलत तरीके से "ऑप्टिमाइज़" करता है, लेकिन निश्चित रूप से libC++ इसे सही (DEMO) प्राप्त करता है।