Chris@102: //////////////////////////////////////////////////////////////////////////////
Chris@102: //
Chris@102: // (C) Copyright Ion Gaztanaga 2015-2015. Distributed under the Boost
Chris@102: // Software License, Version 1.0. (See accompanying file
Chris@102: // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
Chris@102: //
Chris@102: // See http://www.boost.org/libs/container for documentation.
Chris@102: //
Chris@102: //////////////////////////////////////////////////////////////////////////////
Chris@102: 
Chris@102: #ifndef BOOST_CONTAINER_CONTAINER_SMALL_VECTOR_HPP
Chris@102: #define BOOST_CONTAINER_CONTAINER_SMALL_VECTOR_HPP
Chris@102: 
Chris@102: #ifndef BOOST_CONFIG_HPP
Chris@102: #  include <boost/config.hpp>
Chris@102: #endif
Chris@102: 
Chris@102: #if defined(BOOST_HAS_PRAGMA_ONCE)
Chris@102: #  pragma once
Chris@102: #endif
Chris@102: 
Chris@102: #include <boost/container/detail/config_begin.hpp>
Chris@102: #include <boost/container/detail/workaround.hpp>
Chris@102: 
Chris@102: // container
Chris@102: #include <boost/container/container_fwd.hpp>
Chris@102: #include <boost/container/vector.hpp>
Chris@102: #include <boost/container/allocator_traits.hpp>
Chris@102: #include <boost/container/new_allocator.hpp> //new_allocator
Chris@102: // container/detail
Chris@102: #include <boost/container/detail/type_traits.hpp>
Chris@102: #include <boost/container/detail/version_type.hpp>
Chris@102: 
Chris@102: //move
Chris@102: #include <boost/move/adl_move_swap.hpp>
Chris@102: #include <boost/move/iterator.hpp>
Chris@102: 
Chris@102: //move/detail
Chris@102: #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
Chris@102: #include <boost/move/detail/fwd_macros.hpp>
Chris@102: #endif
Chris@102: 
Chris@102: //std
Chris@102: #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
Chris@102: #include <initializer_list>   //for std::initializer_list
Chris@102: #endif
Chris@102: 
Chris@102: namespace boost {
Chris@102: namespace container {
Chris@102: 
Chris@102: #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
Chris@102: 
Chris@102: template <class T, class Allocator = new_allocator<T> >
Chris@102: class small_vector_base;
Chris@102: 
Chris@102: #endif
Chris@102: 
Chris@102: //! A non-standard allocator used to implement `small_vector`.
Chris@102: //! Users should never use it directly. It is described here
Chris@102: //! for documentation purposes.
Chris@102: //! 
Chris@102: //! This allocator inherits from a standard-conforming allocator
Chris@102: //! and forwards member functiond to the standard allocator except
Chris@102: //! when internal storage is being used as memory source.
Chris@102: //!
Chris@102: //! This allocator is a "partially_propagable" allocator and
Chris@102: //! defines `is_partially_propagable` as true_type.
Chris@102: //! 
Chris@102: //! A partially propagable allocator means that not all storage
Chris@102: //! allocatod by an instance of `small_vector_allocator` can be
Chris@102: //! deallocated by another instance of this type, even is both
Chris@102: //! instances compare equal or an instance is propagated to another
Chris@102: //! one using the copy/move constructor or assignment. The storage that
Chris@102: //! can never be propagated is identified by `storage_is_unpropagable(p)`.
Chris@102: //!
Chris@102: //! `boost::container::vector` supports partially propagable allocators
Chris@102: //! fallbacking to deep copy/swap/move operations when internal storage
Chris@102: //! is being used to store vector elements.
Chris@102: //!
Chris@102: //! `small_vector_allocator` assumes that will be instantiated as
Chris@102: //! `boost::container::vector< T, small_vector_allocator<Allocator> >`
Chris@102: //! and internal storage can be obtained downcasting that vector
Chris@102: //! to `small_vector_base<T>`.
Chris@102: template<class Allocator>
Chris@102: class small_vector_allocator
Chris@102:    : public Allocator
Chris@102: {
Chris@102:    typedef unsigned int allocation_type;
Chris@102:    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
Chris@102:    private:
Chris@102: 
Chris@102:    BOOST_COPYABLE_AND_MOVABLE(small_vector_allocator)
Chris@102: 
Chris@102:    const Allocator &as_base() const
Chris@102:    {  return static_cast<const Allocator&>(*this);  }
Chris@102: 
Chris@102:    Allocator &as_base() 
Chris@102:    {  return static_cast<Allocator&>(*this);  }
Chris@102: 
Chris@102:    #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
Chris@102: 
Chris@102:    public:
Chris@102:    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
Chris@102:    typedef allocator_traits<Allocator> allocator_traits_type;
Chris@102:    #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
Chris@102: 
Chris@102:    typedef typename allocator_traits<Allocator>::value_type          value_type;
Chris@102:    typedef typename allocator_traits<Allocator>::pointer             pointer;
Chris@102:    typedef typename allocator_traits<Allocator>::const_pointer       const_pointer;
Chris@102:    typedef typename allocator_traits<Allocator>::reference           reference;
Chris@102:    typedef typename allocator_traits<Allocator>::const_reference     const_reference;
Chris@102:    typedef typename allocator_traits<Allocator>::size_type           size_type;
Chris@102:    typedef typename allocator_traits<Allocator>::difference_type     difference_type;
Chris@102:    typedef typename allocator_traits<Allocator>::void_pointer        void_pointer;
Chris@102:    typedef typename allocator_traits<Allocator>::const_void_pointer  const_void_pointer;
Chris@102: 
Chris@102:    typedef typename allocator_traits<Allocator>::propagate_on_container_copy_assignment   propagate_on_container_copy_assignment;
Chris@102:    typedef typename allocator_traits<Allocator>::propagate_on_container_move_assignment   propagate_on_container_move_assignment;
Chris@102:    typedef typename allocator_traits<Allocator>::propagate_on_container_swap              propagate_on_container_swap;
Chris@102:    //! An integral constant with member `::value == false`
Chris@102:    typedef BOOST_CONTAINER_IMPDEF(container_detail::bool_<false>)                         is_always_equal;
Chris@102:    //! An integral constant with member `::value == true`
Chris@102:    typedef BOOST_CONTAINER_IMPDEF(container_detail::bool_<true>)                          is_partially_propagable;
Chris@102: 
Chris@102:    BOOST_CONTAINER_DOCIGN(typedef container_detail::version_type<small_vector_allocator BOOST_CONTAINER_I 1>  version;)
Chris@102: 
Chris@102:    //!Obtains an small_vector_allocator that allocates
Chris@102:    //!objects of type T2
Chris@102:    template<class T2>
Chris@102:    struct rebind
Chris@102:    {
Chris@102:       typedef typename allocator_traits<Allocator>::template rebind_alloc<T2>::type other;
Chris@102:    };
Chris@102: 
Chris@102:    #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
Chris@102:       //!Constructor from arbitrary arguments
Chris@102:       template<class ...Args>
Chris@102:       explicit small_vector_allocator(BOOST_FWD_REF(Args) ...args)
Chris@102:          : Allocator(::boost::forward<Args>(args)...)
Chris@102:       {}
Chris@102:    #else
Chris@102:       #define BOOST_CONTAINER_SMALL_VECTOR_ALLOCATOR_CTOR_CODE(N) \
Chris@102:       BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
Chris@102:       explicit small_vector_allocator(BOOST_MOVE_UREF##N)\
Chris@102:          : Allocator(BOOST_MOVE_FWD##N)\
Chris@102:       {}\
Chris@102:       //
Chris@102:       BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_SMALL_VECTOR_ALLOCATOR_CTOR_CODE)
Chris@102:       #undef BOOST_CONTAINER_SMALL_VECTOR_ALLOCATOR_CTOR_CODE
Chris@102:    #endif
Chris@102: 
Chris@102:    //!Constructor from other small_vector_allocator.
Chris@102:    //!Never throws
Chris@102:    small_vector_allocator(const small_vector_allocator &other) BOOST_NOEXCEPT_OR_NOTHROW
Chris@102:       : Allocator(other.as_base())
Chris@102:    {}
Chris@102: 
Chris@102:    //!Move constructor from small_vector_allocator.
Chris@102:    //!Never throws
Chris@102:    small_vector_allocator(BOOST_RV_REF(small_vector_allocator) other) BOOST_NOEXCEPT_OR_NOTHROW
Chris@102:       : Allocator(::boost::move(other.as_base()))
Chris@102:    {}
Chris@102: 
Chris@102:    //!Constructor from related small_vector_allocator.
Chris@102:    //!Never throws
Chris@102:    template<class OtherAllocator>
Chris@102:    small_vector_allocator(const small_vector_allocator<OtherAllocator> &other) BOOST_NOEXCEPT_OR_NOTHROW
Chris@102:       : Allocator(other.as_base())
Chris@102:    {}
Chris@102: 
Chris@102:    //!Move constructor from related small_vector_allocator.
Chris@102:    //!Never throws
Chris@102:    template<class OtherAllocator>
Chris@102:    small_vector_allocator(BOOST_RV_REF(small_vector_allocator<OtherAllocator>) other) BOOST_NOEXCEPT_OR_NOTHROW
Chris@102:       : Allocator(::boost::move(other.as_base()))
Chris@102:    {}
Chris@102: 
Chris@102:    //!Assignment from other small_vector_allocator.
Chris@102:    //!Never throws
Chris@102:    small_vector_allocator & operator=(BOOST_COPY_ASSIGN_REF(small_vector_allocator) other) BOOST_NOEXCEPT_OR_NOTHROW
Chris@102:    {  return static_cast<small_vector_allocator&>(this->Allocator::operator=(other.as_base()));  }
Chris@102: 
Chris@102:    //!Move constructor from other small_vector_allocator.
Chris@102:    //!Never throws
Chris@102:    small_vector_allocator & operator=(BOOST_RV_REF(small_vector_allocator) other) BOOST_NOEXCEPT_OR_NOTHROW
Chris@102:    {  return static_cast<small_vector_allocator&>(this->Allocator::operator=(::boost::move(other.as_base())));  }
Chris@102: 
Chris@102:    //!Assignment from related small_vector_allocator.
Chris@102:    //!Never throws
Chris@102:    template<class OtherAllocator>
Chris@102:    small_vector_allocator & operator=(BOOST_COPY_ASSIGN_REF(small_vector_allocator<OtherAllocator>) other) BOOST_NOEXCEPT_OR_NOTHROW
Chris@102:    {  return static_cast<small_vector_allocator&>(this->Allocator::operator=(other.as_base()));  }
Chris@102: 
Chris@102:    //!Move assignment from related small_vector_allocator.
Chris@102:    //!Never throws
Chris@102:    template<class OtherAllocator>
Chris@102:    small_vector_allocator & operator=(BOOST_RV_REF(small_vector_allocator<OtherAllocator>) other) BOOST_NOEXCEPT_OR_NOTHROW
Chris@102:    {  return static_cast<small_vector_allocator&>(this->Allocator::operator=(::boost::move(other.as_base())));  }
Chris@102: 
Chris@102:    //!Allocates storage from the standard-conforming allocator
Chris@102:    pointer allocate(size_type count, const_void_pointer hint = const_void_pointer())
Chris@102:    {  return allocator_traits_type::allocate(this->as_base(), count, hint);  }
Chris@102: 
Chris@102:    //!Deallocates previously allocated memory.
Chris@102:    //!Never throws
Chris@102:    void deallocate(pointer ptr, size_type n) BOOST_NOEXCEPT_OR_NOTHROW
Chris@102:    {
Chris@102:       if(!this->is_internal_storage(ptr))
Chris@102:          allocator_traits_type::deallocate(this->as_base(), ptr, n);
Chris@102:    }
Chris@102: 
Chris@102:    //!Returns the maximum number of elements that could be allocated.
Chris@102:    //!Never throws
Chris@102:    size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW
Chris@102:    {  return allocator_traits_type::max_size(this->as_base());   }
Chris@102: 
Chris@102:    small_vector_allocator select_on_container_copy_construction() const
Chris@102:    {  return small_vector_allocator(allocator_traits_type::select_on_container_copy_construction(this->as_base())); }
Chris@102: 
Chris@102:    bool storage_is_unpropagable(pointer p) const
Chris@102:    {  return this->is_internal_storage(p) || allocator_traits_type::storage_is_unpropagable(this->as_base(), p);  }
Chris@102: 
Chris@102:    //!Swaps two allocators, does nothing
Chris@102:    //!because this small_vector_allocator is stateless
Chris@102:    friend void swap(small_vector_allocator &l, small_vector_allocator &r) BOOST_NOEXCEPT_OR_NOTHROW
Chris@102:    {  boost::adl_move_swap(l.as_base(), r.as_base());  }
Chris@102: 
Chris@102:    //!An small_vector_allocator always compares to true, as memory allocated with one
Chris@102:    //!instance can be deallocated by another instance (except for unpropagable storage)
Chris@102:    friend bool operator==(const small_vector_allocator &l, const small_vector_allocator &r) BOOST_NOEXCEPT_OR_NOTHROW
Chris@102:    {  return allocator_traits_type::equal(l.as_base(), r.as_base());  }
Chris@102: 
Chris@102:    //!An small_vector_allocator always compares to false, as memory allocated with one
Chris@102:    //!instance can be deallocated by another instance
Chris@102:    friend bool operator!=(const small_vector_allocator &l, const small_vector_allocator &r) BOOST_NOEXCEPT_OR_NOTHROW
Chris@102:    {  return !(l == r);   }
Chris@102: 
Chris@102:    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
Chris@102:    /*
Chris@102:    //!An advanced function that offers in-place expansion shrink to fit and new allocation
Chris@102:    //!capabilities. Memory allocated with this function can only be deallocated with deallocate()
Chris@102:    //!or deallocate_many().
Chris@102:    //!This function is available only with Version == 2
Chris@102:    pointer allocation_command(allocation_type command,
Chris@102:                          size_type limit_size,
Chris@102:                          size_type &prefer_in_recvd_out_size,
Chris@102:                          pointer &reuse)
Chris@102:    {  return allocator_traits_type::allocation_command(command, limit_size, prefer_in_recvd_out_size, reuse);  }
Chris@102: 
Chris@102:    //!Returns maximum the number of objects the previously allocated memory
Chris@102:    //!pointed by p can hold.
Chris@102:    //!Memory must not have been allocated with
Chris@102:    //!allocate_one or allocate_individual.
Chris@102:    //!This function is available only with Version == 2
Chris@102:    size_type size(pointer p) const BOOST_NOEXCEPT_OR_NOTHROW
Chris@102:    {  return allocator_traits_type::size(p);  }
Chris@102:    */
Chris@102:    private:
Chris@102:    /*
Chris@102:    //!Allocates just one object. Memory allocated with this function
Chris@102:    //!must be deallocated only with deallocate_one().
Chris@102:    //!Throws bad_alloc if there is no enough memory
Chris@102:    //!This function is available only with Version == 2
Chris@102:    using Allocator::allocate_one;
Chris@102:    using Allocator::allocate_individual;
Chris@102:    using Allocator::deallocate_one;
Chris@102:    using Allocator::deallocate_individual;
Chris@102:    using Allocator::allocate_many;
Chris@102:    using Allocator::deallocate_many;*/
Chris@102: 
Chris@102:    bool is_internal_storage(pointer p) const
Chris@102:    {  return this->internal_storage() == p;  }
Chris@102: 
Chris@102:    pointer internal_storage() const
Chris@102:    {
Chris@102:       typedef typename Allocator::value_type                                              value_type;
Chris@102:       typedef container_detail::vector_alloc_holder< small_vector_allocator<Allocator> >  vector_alloc_holder_t;
Chris@102:       typedef vector<value_type, small_vector_allocator<Allocator> >                      vector_base;
Chris@102:       typedef small_vector_base<value_type, Allocator>                                    derived_type;
Chris@102:       //
Chris@102:       const vector_alloc_holder_t &v_holder = static_cast<const vector_alloc_holder_t &>(*this);
Chris@102:       const vector_base &v_base = reinterpret_cast<const vector_base &>(v_holder);
Chris@102:       const derived_type &d_base = static_cast<const derived_type &>(v_base);
Chris@102:       return d_base.internal_storage();
Chris@102:    }
Chris@102:    #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
Chris@102: };
Chris@102: 
Chris@102: //! This class consists of common code from all small_vector<T, N> types that don't depend on the
Chris@102: //! "N" template parameter. This class is non-copyable and non-destructible, so this class tipically
Chris@102: //! used as reference argument to functions that read or write small vectors. Since `small_vector<T, N>`
Chris@102: //! derives from `small_vector_base<T>`, the conversion to `small_vector_base` is implicit:
Chris@102: //! <code>
Chris@102: //!
Chris@102: //! //Clients can pass any small_vector<Foo, N>.
Chris@102: //! void read_any_small_vector_of_foo(const small_vector_base<Foo> &in_parameter);
Chris@102: //! void modify_any_small_vector_of_foo(small_vector_base<Foo> &out_parameter);
Chris@102: //! 
Chris@102: //! void some_function()
Chris@102: //! {
Chris@102: //!    small_vector<Foo, 8> myvector;
Chris@102: //!    read_any_small_vector_of_foo(myvector);   // Reads myvector
Chris@102: //!    modify_any_small_vector_of_foo(myvector); // Modifies myvector
Chris@102: //! }
Chris@102: //! </code>
Chris@102: //!
Chris@102: //! All `boost::container:vector` member functions are inherited. See `vector` documentation for details.
Chris@102: //!
Chris@102: template <class T, class SecondaryAllocator>
Chris@102: class small_vector_base
Chris@102:    : public vector<T, small_vector_allocator<SecondaryAllocator> >
Chris@102: {
Chris@102:    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
Chris@102:    typedef typename allocator_traits<SecondaryAllocator>::pointer pointer;
Chris@102: 
Chris@102:    BOOST_COPYABLE_AND_MOVABLE(small_vector_base)
Chris@102: 
Chris@102:    friend class small_vector_allocator<SecondaryAllocator>;
Chris@102: 
Chris@102:    pointer internal_storage() const BOOST_NOEXCEPT_OR_NOTHROW
Chris@102:    {
Chris@102:       return boost::intrusive::pointer_traits<pointer>::pointer_to
Chris@102:          (*const_cast<T*>(static_cast<const T*>(static_cast<const void*>(&m_storage_start))));
Chris@102:    }
Chris@102: 
Chris@102:    typedef vector<T, small_vector_allocator<SecondaryAllocator> > base_type;
Chris@102:          base_type &as_base()       { return static_cast<base_type&>(*this); }
Chris@102:    const base_type &as_base() const { return static_cast<const base_type&>(*this); }
Chris@102: 
Chris@102:    public:
Chris@102:    typedef typename container_detail::aligned_storage
Chris@102:       <sizeof(T), container_detail::alignment_of<T>::value>::type storage_type;
Chris@102:    typedef small_vector_allocator<SecondaryAllocator>             allocator_type;
Chris@102: 
Chris@102:    protected:
Chris@102:    typedef typename base_type::initial_capacity_t initial_capacity_t;
Chris@102: 
Chris@102:    explicit small_vector_base(initial_capacity_t, std::size_t initial_capacity)
Chris@102:       : base_type(initial_capacity_t(), this->internal_storage(), initial_capacity)
Chris@102:    {}
Chris@102: 
Chris@102:    template<class AllocFwd>
Chris@102:    explicit small_vector_base(initial_capacity_t, std::size_t capacity, BOOST_FWD_REF(AllocFwd) a)
Chris@102:       : base_type(initial_capacity_t(), this->internal_storage(), capacity, ::boost::forward<AllocFwd>(a))
Chris@102:    {}
Chris@102: 
Chris@102:    ~small_vector_base(){}
Chris@102: 
Chris@102:    using base_type::is_propagable_from;
Chris@102:    using base_type::steal_resources;
Chris@102: 
Chris@102:    private:
Chris@102:    //The only member
Chris@102:    storage_type m_storage_start;
Chris@102: 
Chris@102:    #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
Chris@102: 
Chris@102:    public:
Chris@102:    small_vector_base& operator=(BOOST_COPY_ASSIGN_REF(small_vector_base) other)
Chris@102:    {  return static_cast<small_vector_base&>(this->base_type::operator=(static_cast<base_type const&>(other)));  }
Chris@102: 
Chris@102:    small_vector_base& operator=(BOOST_RV_REF(small_vector_base) other)
Chris@102:    {  return static_cast<small_vector_base&>(this->base_type::operator=(BOOST_MOVE_BASE(base_type, other))); }
Chris@102: 
Chris@102:    void swap(small_vector_base &other)
Chris@102:    {  return this->base_type::swap(other);  }
Chris@102: };
Chris@102: 
Chris@102: #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
Chris@102: 
Chris@102: /////////////////////////////////////////////////////
Chris@102: //
Chris@102: //          small_vector_storage_calculator
Chris@102: //
Chris@102: /////////////////////////////////////////////////////
Chris@102: template<std::size_t Needed, std::size_t Hdr, std::size_t SSize, bool NeedsZero = (0u == Needed || Needed <= Hdr)>
Chris@102: struct small_vector_storage_calculator_helper
Chris@102: {
Chris@102:    static const std::size_t value = (Needed - Hdr - 1u)/SSize + 1u;
Chris@102: };
Chris@102: 
Chris@102: template<std::size_t Needed, std::size_t Hdr, std::size_t SSize>
Chris@102: struct small_vector_storage_calculator_helper<Needed, Hdr, SSize, true>
Chris@102: {
Chris@102:    static const std::size_t value = 0u;
Chris@102: };
Chris@102: 
Chris@102: template<class Storage, class Allocator, class T, std::size_t N>
Chris@102: struct small_vector_storage_calculator
Chris@102: {
Chris@102:    typedef small_vector_base<T, Allocator> svh_type;
Chris@102:    typedef vector<T, small_vector_allocator<Allocator> > svhb_type;
Chris@102:    static const std::size_t s_align = container_detail::alignment_of<Storage>::value;
Chris@102:    static const std::size_t s_size = sizeof(Storage);
Chris@102:    static const std::size_t svh_sizeof = sizeof(svh_type);
Chris@102:    static const std::size_t svhb_sizeof = sizeof(svhb_type);
Chris@102:    static const std::size_t s_start = ((svhb_sizeof-1)/s_align+1)*s_align;
Chris@102:    static const std::size_t header_bytes = svh_sizeof-s_start;
Chris@102:    static const std::size_t needed_bytes = sizeof(T)*N;
Chris@102:    static const std::size_t needed_extra_storages =
Chris@102:       small_vector_storage_calculator_helper<needed_bytes, header_bytes, s_size>::value;
Chris@102: };
Chris@102: 
Chris@102: /////////////////////////////////////////////////////
Chris@102: //
Chris@102: //          small_vector_storage_definer
Chris@102: //
Chris@102: /////////////////////////////////////////////////////
Chris@102: template<class Storage, std::size_t N>
Chris@102: struct small_vector_storage
Chris@102: {
Chris@102:    Storage m_rest_of_storage[N];
Chris@102: };
Chris@102: 
Chris@102: template<class Storage>
Chris@102: struct small_vector_storage<Storage, 0>
Chris@102: {};
Chris@102: 
Chris@102: template<class Allocator, std::size_t N>
Chris@102: struct small_vector_storage_definer
Chris@102: {
Chris@102:    typedef typename Allocator::value_type                                  value_type;
Chris@102:    typedef typename small_vector_base<value_type, Allocator>::storage_type storage_type;
Chris@102:    static const std::size_t needed_extra_storages =
Chris@102:       small_vector_storage_calculator<storage_type, Allocator, value_type, N>::needed_extra_storages;
Chris@102:    typedef small_vector_storage<storage_type, needed_extra_storages> type;
Chris@102: };
Chris@102: 
Chris@102: #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
Chris@102: 
Chris@102: //! small_vector a vector-like container optimized for the case when it contains few elements.
Chris@102: //! It contains some preallocated elements in-place, which allows it to avoid the use of dynamic storage allocation
Chris@102: //! when the actual number of elements is below that preallocated threshold.
Chris@102: //!
Chris@102: //! `small_vector<T, N, Allocator>` is convertible to `small_vector_base<T, Allocator>` that is independent
Chris@102: //! from the preallocated element capacity, so client code does not need to be templated on that N argument.
Chris@102: //!
Chris@102: //! All `boost::container::vector` member functions are inherited. See `vector` documentation for details.
Chris@102: //!
Chris@102: //! \tparam T The type of object that is stored in the small_vector
Chris@102: //! \tparam N The number of preallocated elements stored inside small_vector. It shall be less than Allocator::max_size();
Chris@102: //! \tparam Allocator The allocator used for memory management when the number of elements exceeds N.
Chris@102: template <class T, std::size_t N, class Allocator BOOST_CONTAINER_DOCONLY(= new_allocator<T>) >
Chris@102: class small_vector : public small_vector_base<T, Allocator>
Chris@102:    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
Chris@102:    , private small_vector_storage_definer<Allocator, N>::type
Chris@102:    #endif
Chris@102: {
Chris@102:    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
Chris@102:    typedef small_vector_base<T, Allocator> base_type;
Chris@102:    typedef typename small_vector_storage_definer<Allocator, N>::type remaining_storage_holder;
Chris@102: 
Chris@102:    BOOST_COPYABLE_AND_MOVABLE(small_vector)
Chris@102: 
Chris@102:    typedef typename base_type::initial_capacity_t initial_capacity_t;
Chris@102:    typedef allocator_traits<typename base_type::allocator_type> allocator_traits_type;
Chris@102: 
Chris@102:    public:
Chris@102:    typedef small_vector_storage_calculator< typename small_vector_base<T, Allocator>
Chris@102:       ::storage_type, Allocator, T, N> storage_test;
Chris@102: 
Chris@102:    static const std::size_t needed_extra_storages =  storage_test::needed_extra_storages;
Chris@102:    static const std::size_t needed_bytes =  storage_test::needed_bytes;
Chris@102:    static const std::size_t header_bytes =  storage_test::header_bytes;
Chris@102:    static const std::size_t s_start =  storage_test::s_start;
Chris@102: 
Chris@102:    typedef typename base_type::allocator_type   allocator_type;
Chris@102:    typedef typename base_type::size_type        size_type;
Chris@102:    typedef typename base_type::value_type       value_type;
Chris@102: 
Chris@102:    static std::size_t internal_capacity()
Chris@102:    {  return (sizeof(small_vector) - storage_test::s_start)/sizeof(T);  }
Chris@102: 
Chris@102:    #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
Chris@102: 
Chris@102:    public:
Chris@102:    small_vector()
Chris@102:       : base_type(initial_capacity_t(), internal_capacity())
Chris@102:    {}
Chris@102: 
Chris@102:    explicit small_vector(size_type n)
Chris@102:       : base_type(initial_capacity_t(), internal_capacity())
Chris@102:    {  this->resize(n); }
Chris@102: 
Chris@102:    explicit small_vector(const allocator_type &a)
Chris@102:       : base_type(initial_capacity_t(), internal_capacity(), a)
Chris@102:    {}
Chris@102: 
Chris@102:    small_vector(size_type n, const allocator_type &a)
Chris@102:       : base_type(initial_capacity_t(), internal_capacity(), a)
Chris@102:    {  this->resize(n); }
Chris@102: 
Chris@102:    small_vector(const small_vector &other)
Chris@102:       : base_type( initial_capacity_t(), internal_capacity()
Chris@102:                  , allocator_traits_type::select_on_container_copy_construction(other.get_stored_allocator()))
Chris@102:    {  this->assign(other.cbegin(), other.cend());  }
Chris@102: 
Chris@102:    small_vector(const small_vector &other, const allocator_type &a)
Chris@102:       : base_type(initial_capacity_t(), internal_capacity(), a)
Chris@102:    {  this->assign(other.cbegin(), other.cend());  }
Chris@102: 
Chris@102:    small_vector(BOOST_RV_REF(small_vector) other)
Chris@102:       : base_type(initial_capacity_t(), internal_capacity(), ::boost::move(other.get_stored_allocator()))
Chris@102:    {  this->move_construct_impl(other, other.get_stored_allocator());   }
Chris@102: 
Chris@102:    small_vector(BOOST_RV_REF(small_vector) other, const allocator_type &a)
Chris@102:       : base_type(initial_capacity_t(), internal_capacity(), a)
Chris@102:    {  this->move_construct_impl(other, a);   }
Chris@102: 
Chris@102:    #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
Chris@102:    small_vector(std::initializer_list<value_type> il, const allocator_type& a = allocator_type())
Chris@102:       : base_type(initial_capacity_t(), internal_capacity(), a)
Chris@102:    {
Chris@102:       this->assign(il.begin(), il.end());
Chris@102:    }
Chris@102:    #endif
Chris@102: 
Chris@102:    small_vector& operator=(BOOST_COPY_ASSIGN_REF(small_vector) other)
Chris@102:    {  return static_cast<small_vector&>(this->base_type::operator=(static_cast<base_type const&>(other)));  }
Chris@102: 
Chris@102:    small_vector& operator=(BOOST_RV_REF(small_vector) other)
Chris@102:    {  return static_cast<small_vector&>(this->base_type::operator=(BOOST_MOVE_BASE(base_type, other))); }
Chris@102: 
Chris@102:    void swap(small_vector &other)
Chris@102:    {  return this->base_type::swap(other);  }
Chris@102: 
Chris@102:    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
Chris@102:    private:
Chris@102:    void move_construct_impl(small_vector &x, const allocator_type &a)
Chris@102:    {
Chris@102:       if(base_type::is_propagable_from(x.get_stored_allocator(), x.data(), a, true)){
Chris@102:          this->steal_resources(x);
Chris@102:       }
Chris@102:       else{
Chris@102:          this->assign( boost::make_move_iterator(container_detail::iterator_to_raw_pointer(x.begin()))
Chris@102:                      , boost::make_move_iterator(container_detail::iterator_to_raw_pointer(x.end  ()))
Chris@102:                      );
Chris@102:       }
Chris@102:    }
Chris@102:    #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
Chris@102: };
Chris@102: 
Chris@102: }}
Chris@102: 
Chris@102: #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
Chris@102: /*
Chris@102: namespace boost {
Chris@102: 
Chris@102: //!has_trivial_destructor_after_move<> == true_type
Chris@102: //!specialization for optimizations
Chris@102: template <class T, class Allocator>
Chris@102: struct has_trivial_destructor_after_move<boost::container::vector<T, Allocator> >
Chris@102: {
Chris@102:    typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer;
Chris@102:    static const bool value = ::boost::has_trivial_destructor_after_move<Allocator>::value &&
Chris@102:                              ::boost::has_trivial_destructor_after_move<pointer>::value;
Chris@102: };
Chris@102: 
Chris@102: }
Chris@102: */
Chris@102: #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
Chris@102: 
Chris@102: #include <boost/container/detail/config_end.hpp>
Chris@102: 
Chris@102: #endif //   #ifndef  BOOST_CONTAINER_CONTAINER_SMALL_VECTOR_HPP