boost/container/small_vector.hpp

0001 //////////////////////////////////////////////////////////////////////////////
0002 //
0003 // (C) Copyright Ion Gaztanaga 2015-2015. Distributed under the Boost
0004 // Software License, Version 1.0. (See accompanying file
0005 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0006 //
0007 // See http://www.boost.org/libs/container for documentation.
0008 //
0009 //////////////////////////////////////////////////////////////////////////////
0010
0011 #ifndef BOOST_CONTAINER_CONTAINER_SMALL_VECTOR_HPP
0012 #define BOOST_CONTAINER_CONTAINER_SMALL_VECTOR_HPP
0013
0014 #ifndef BOOST_CONFIG_HPP
0015 #  include <boost/config.hpp>
0016 #endif
0017
0018 #if defined(BOOST_HAS_PRAGMA_ONCE)
0019 #  pragma once
0020 #endif
0021
0022 #include <boost/container/detail/config_begin.hpp>
0023 #include <boost/container/detail/workaround.hpp>
0024
0025 // container
0026 #include <boost/container/container_fwd.hpp>
0027 #include <boost/container/vector.hpp>
0028 #include <boost/container/allocator_traits.hpp>
0029 #include <boost/container/new_allocator.hpp> //new_allocator
0030 // container/detail
0031 #include <boost/container/detail/type_traits.hpp>
0032 #include <boost/container/detail/version_type.hpp>
0033
0034 //move
0035 #include <boost/move/adl_move_swap.hpp>
0036 #include <boost/move/iterator.hpp>
0037
0038 //move/detail
0039 #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
0040 #include <boost/move/detail/fwd_macros.hpp>
0041 #endif
0042 #include <boost/move/detail/force_ptr.hpp>
0043
0044 //std
0045 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
0046 #include <initializer_list>   //for std::initializer_list
0047 #endif
0048
0049 namespace boost {
0050 namespace container {
0051
0052 namespace dtl{
0053
0054 template<class Options>
0055 struct get_small_vector_opt
0056 {
0057    typedef Options type;
0058 };
0059
0060 template<>
0061 struct get_small_vector_opt<void>
0062 {
0063    typedef small_vector_null_opt type;
0064 };
0065
0066 template<class Options>
0067 struct get_vopt_from_svopt
0068    : get_small_vector_opt<Options>::type
0069 {
0070    typedef typename get_small_vector_opt<Options>::type options_t;
0071    typedef vector_opt< typename options_t::growth_factor_type, void> type;
0072 };
0073
0074 template<>
0075 struct get_vopt_from_svopt<void>
0076 {
0077    typedef void type;
0078 };
0079
0080 template <class T, class SecAlloc, class Options>
0081 struct vector_for_small_vector
0082 {
0083    typedef vector
0084       < T
0085       , small_vector_allocator
0086          < T
0087          , typename allocator_traits<typename real_allocator<T, SecAlloc>::type>::template portable_rebind_alloc<void>::type
0088          , Options>
0089       , typename dtl::get_vopt_from_svopt<Options>::type
0090       > type;
0091 };
0092
0093 }  //namespace dtl
0094
0095 //! A non-standard allocator used to implement `small_vector`.
0096 //! Users should never use it directly. It is described here
0097 //! for documentation purposes.
0098 //!
0099 //! This allocator inherits from a standard-conforming allocator
0100 //! and forwards member functions to the standard allocator except
0101 //! when internal storage is being used as memory source.
0102 //!
0103 //! This allocator is a "partially_propagable" allocator and
0104 //! defines `is_partially_propagable` as true_type.
0105 //!
0106 //! A partially propagable allocator means that not all storage
0107 //! allocatod by an instance of `small_vector_allocator` can be
0108 //! deallocated by another instance of this type, even if both
0109 //! instances compare equal or an instance is propagated to another
0110 //! one using the copy/move constructor or assignment. The storage that
0111 //! can never be propagated is identified by `storage_is_unpropagable(p)`.
0112 //!
0113 //! `boost::container::vector` supports partially propagable allocators
0114 //! fallbacking to deep copy/swap/move operations when internal storage
0115 //! is being used to store vector elements.
0116 //!
0117 //! `small_vector_allocator` assumes that will be instantiated as
0118 //! `boost::container::vector< T, small_vector_allocator<T, Allocator> >`
0119 //! and internal storage can be obtained downcasting that vector
0120 //! to `small_vector_base<T>`.
0121 template<class T, class VoidAlloc BOOST_CONTAINER_DOCONLY(= void), class Options BOOST_CONTAINER_DOCONLY(= void)>
0122 class small_vector_allocator
0123    : public allocator_traits<VoidAlloc>::template portable_rebind_alloc<T>::type
0124 {
0125    typedef unsigned int allocation_type;
0126    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0127    private:
0128
0129    typedef typename allocator_traits<VoidAlloc>::template portable_rebind_alloc<T>::type allocator_type;
0130
0131    BOOST_COPYABLE_AND_MOVABLE(small_vector_allocator)
0132
0133    BOOST_CONTAINER_FORCEINLINE const allocator_type &as_base() const BOOST_NOEXCEPT
0134    {  return static_cast<const allocator_type&>(*this);  }
0135
0136    BOOST_CONTAINER_FORCEINLINE allocator_type &as_base() BOOST_NOEXCEPT
0137    {  return static_cast<allocator_type&>(*this);  }
0138
0139    #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0140
0141    public:
0142    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0143    typedef allocator_traits<allocator_type> allocator_traits_type;
0144    #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0145
0146    typedef typename allocator_traits<allocator_type>::value_type          value_type;
0147    typedef typename allocator_traits<allocator_type>::pointer             pointer;
0148    typedef typename allocator_traits<allocator_type>::const_pointer       const_pointer;
0149    typedef typename allocator_traits<allocator_type>::reference           reference;
0150    typedef typename allocator_traits<allocator_type>::const_reference     const_reference;
0151    typedef typename allocator_traits<allocator_type>::size_type           size_type;
0152    typedef typename allocator_traits<allocator_type>::difference_type     difference_type;
0153    typedef typename allocator_traits<allocator_type>::void_pointer        void_pointer;
0154    typedef typename allocator_traits<allocator_type>::const_void_pointer  const_void_pointer;
0155
0156    typedef typename allocator_traits<allocator_type>::propagate_on_container_copy_assignment   propagate_on_container_copy_assignment;
0157    typedef typename allocator_traits<allocator_type>::propagate_on_container_move_assignment   propagate_on_container_move_assignment;
0158    typedef typename allocator_traits<allocator_type>::propagate_on_container_swap              propagate_on_container_swap;
0159    //! An integral constant with member `value == false`
0160    typedef BOOST_CONTAINER_IMPDEF(dtl::bool_<false>)                         is_always_equal;
0161    //! An integral constant with member `value == true`
0162    typedef BOOST_CONTAINER_IMPDEF(dtl::bool_<true>)                          is_partially_propagable;
0163
0164    BOOST_CONTAINER_DOCIGN(typedef dtl::version_type<small_vector_allocator BOOST_CONTAINER_I 1>  version;)
0165
0166    //!Obtains an small_vector_allocator that allocates
0167    //!objects of type T2
0168    template<class T2>
0169    struct rebind
0170    {
0171       typedef typename allocator_traits<allocator_type>::template portable_rebind_alloc<T2>::type other;
0172    };
0173
0174    BOOST_CONTAINER_FORCEINLINE small_vector_allocator() BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<allocator_type>::value)
0175    {}
0176
0177    //!Constructor from other small_vector_allocator.
0178    //!Never throws
0179    BOOST_CONTAINER_FORCEINLINE small_vector_allocator
0180       (const small_vector_allocator &other) BOOST_NOEXCEPT_OR_NOTHROW
0181       : allocator_type(other.as_base())
0182    {}
0183
0184    //!Move constructor from small_vector_allocator.
0185    //!Never throws
0186    BOOST_CONTAINER_FORCEINLINE small_vector_allocator
0187       (BOOST_RV_REF(small_vector_allocator) other) BOOST_NOEXCEPT_OR_NOTHROW
0188       : allocator_type(::boost::move(other.as_base()))
0189    {}
0190
0191    //!Constructor from related small_vector_allocator.
0192    //!Never throws
0193    template<class U, class OtherVoidAllocator, class OtherOptions>
0194    BOOST_CONTAINER_FORCEINLINE small_vector_allocator
0195       (const small_vector_allocator<U, OtherVoidAllocator, OtherOptions> &other) BOOST_NOEXCEPT_OR_NOTHROW
0196       : allocator_type(other.as_base())
0197    {}
0198
0199    //!Move constructor from related small_vector_allocator.
0200    //!Never throws
0201    template<class U, class OtherVoidAllocator, class OtherOptions>
0202    BOOST_CONTAINER_FORCEINLINE small_vector_allocator
0203       (BOOST_RV_REF(small_vector_allocator<U BOOST_MOVE_I OtherVoidAllocator BOOST_MOVE_I OtherOptions>) other) BOOST_NOEXCEPT_OR_NOTHROW
0204       : allocator_type(::boost::move(other.as_base()))
0205    {}
0206
0207    //!Constructor from allocator_type.
0208    //!Never throws
0209    BOOST_CONTAINER_FORCEINLINE explicit small_vector_allocator
0210       (const allocator_type &other) BOOST_NOEXCEPT_OR_NOTHROW
0211       : allocator_type(other)
0212    {}
0213
0214    //!Assignment from other small_vector_allocator.
0215    //!Never throws
0216    BOOST_CONTAINER_FORCEINLINE small_vector_allocator &
0217       operator=(BOOST_COPY_ASSIGN_REF(small_vector_allocator) other) BOOST_NOEXCEPT_OR_NOTHROW
0218    {  return static_cast<small_vector_allocator&>(this->allocator_type::operator=(other.as_base()));  }
0219
0220    //!Move assignment from other small_vector_allocator.
0221    //!Never throws
0222    BOOST_CONTAINER_FORCEINLINE small_vector_allocator &
0223       operator=(BOOST_RV_REF(small_vector_allocator) other) BOOST_NOEXCEPT_OR_NOTHROW
0224    {  return static_cast<small_vector_allocator&>(this->allocator_type::operator=(::boost::move(other.as_base())));  }
0225
0226    //!Assignment from related small_vector_allocator.
0227    //!Never throws
0228    template<class U, class OtherVoidAllocator>
0229    BOOST_CONTAINER_FORCEINLINE small_vector_allocator &
0230       operator=(BOOST_COPY_ASSIGN_REF(small_vector_allocator<U BOOST_MOVE_I OtherVoidAllocator BOOST_MOVE_I Options>) other) BOOST_NOEXCEPT_OR_NOTHROW
0231    {  return static_cast<small_vector_allocator&>(this->allocator_type::operator=(other.as_base()));  }
0232
0233    //!Move assignment from related small_vector_allocator.
0234    //!Never throws
0235    template<class U, class OtherVoidAllocator>
0236    BOOST_CONTAINER_FORCEINLINE small_vector_allocator &
0237       operator=(BOOST_RV_REF(small_vector_allocator<U BOOST_MOVE_I OtherVoidAllocator BOOST_MOVE_I Options>) other) BOOST_NOEXCEPT_OR_NOTHROW
0238    {  return static_cast<small_vector_allocator&>(this->allocator_type::operator=(::boost::move(other.as_base())));  }
0239
0240    //!Move assignment from allocator_type.
0241    //!Never throws
0242    BOOST_CONTAINER_FORCEINLINE small_vector_allocator &
0243       operator=(const allocator_type &other) BOOST_NOEXCEPT_OR_NOTHROW
0244    {  return static_cast<small_vector_allocator&>(this->allocator_type::operator=(other));  }
0245
0246    //!Allocates storage from the standard-conforming allocator
0247    BOOST_CONTAINER_FORCEINLINE pointer allocate(size_type count, const_void_pointer hint = const_void_pointer())
0248    {  return allocator_traits_type::allocate(this->as_base(), count, hint);  }
0249
0250    //!Deallocates previously allocated memory.
0251    //!Never throws
0252    void deallocate(pointer ptr, size_type n) BOOST_NOEXCEPT_OR_NOTHROW
0253    {
0254       if(!this->is_internal_storage(ptr))
0255          allocator_traits_type::deallocate(this->as_base(), ptr, n);
0256    }
0257
0258    //!Returns the maximum number of elements that could be allocated.
0259    //!Never throws
0260    BOOST_CONTAINER_FORCEINLINE size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW
0261    {  return allocator_traits_type::max_size(this->as_base());   }
0262
0263    small_vector_allocator select_on_container_copy_construction() const
0264    {  return small_vector_allocator(allocator_traits_type::select_on_container_copy_construction(this->as_base())); }
0265
0266    bool storage_is_unpropagable(pointer p) const
0267    {  return this->is_internal_storage(p) || allocator_traits_type::storage_is_unpropagable(this->as_base(), p);  }
0268
0269    //!Swaps two allocators, does nothing
0270    //!because this small_vector_allocator is stateless
0271    BOOST_CONTAINER_FORCEINLINE friend void swap(small_vector_allocator &l, small_vector_allocator &r) BOOST_NOEXCEPT_OR_NOTHROW
0272    {  boost::adl_move_swap(l.as_base(), r.as_base());  }
0273
0274    //!An small_vector_allocator always compares to true, as memory allocated with one
0275    //!instance can be deallocated by another instance (except for unpropagable storage)
0276    BOOST_CONTAINER_FORCEINLINE friend bool operator==(const small_vector_allocator &l, const small_vector_allocator &r) BOOST_NOEXCEPT_OR_NOTHROW
0277    {  return allocator_traits_type::equal(l.as_base(), r.as_base());  }
0278
0279    //!An small_vector_allocator always compares to false, as memory allocated with one
0280    //!instance can be deallocated by another instance
0281    BOOST_CONTAINER_FORCEINLINE friend bool operator!=(const small_vector_allocator &l, const small_vector_allocator &r) BOOST_NOEXCEPT_OR_NOTHROW
0282    {  return !(l == r);   }
0283
0284    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0285    private:
0286
0287    typedef small_vector_base<value_type, allocator_type, Options>    derived_type;
0288    typedef typename dtl::vector_for_small_vector
0289       <value_type, allocator_type, Options>::type                    vector_type;
0290
0291    BOOST_CONTAINER_FORCEINLINE bool is_internal_storage(const_pointer p) const
0292    {  return this->internal_storage() == p;  }
0293
0294    public:
0295    BOOST_CONTAINER_FORCEINLINE const_pointer internal_storage() const BOOST_NOEXCEPT_OR_NOTHROW;
0296    BOOST_CONTAINER_FORCEINLINE pointer       internal_storage()       BOOST_NOEXCEPT_OR_NOTHROW;
0297    #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0298 };
0299
0300 template<class T, std::size_t N, std::size_t Alignment>
0301 struct small_vector_storage
0302 {
0303    typedef typename dtl::aligned_storage
0304       <sizeof(T)*N, Alignment>::type storage_type;
0305    storage_type m_storage;
0306    static const std::size_t sms_size = sizeof(storage_type)/sizeof(T);
0307 };
0308
0309 template<class T, std::size_t Alignment>
0310 struct small_vector_storage<T, 0u, Alignment>
0311 {
0312    static const std::size_t sms_size = 0u;
0313 };
0314
0315 //! This class consists of common code from all small_vector<T, N> types that don't depend on the
0316 //! "N" template parameter. This class is non-copyable and non-destructible, so this class typically
0317 //! used as reference argument to functions that read or write small vectors. Since `small_vector<T, N>`
0318 //! derives from `small_vector_base<T>`, the conversion to `small_vector_base` is implicit
0319 //! <pre>
0320 //!
0321 //! //Clients can pass any small_vector<Foo, N>.
0322 //! void read_any_small_vector_of_foo(const small_vector_base<Foo> &in_parameter);
0323 //!
0324 //! void modify_any_small_vector_of_foo(small_vector_base<Foo> &in_out_parameter);
0325 //!
0326 //! void some_function()
0327 //! {
0328 //!
0329 //!    small_vector<Foo, 8> myvector;
0330 //!
0331 //!    read_any_small_vector_of_foo(myvector);   // Reads myvector
0332 //!
0333 //!    modify_any_small_vector_of_foo(myvector); // Modifies myvector
0334 //!
0335 //! }
0336 //! </pre>
0337 //!
0338 //! All `boost::container:vector` member functions are inherited. See `vector` documentation for details.
0339 //!
0340 template <class T, class SecAlloc, class Options>
0341 class small_vector_base
0342    : public dtl::vector_for_small_vector<T, SecAlloc, Options>::type
0343 {
0344    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKEDVECTOR
0345    public:
0346    //Make it public as it will be inherited by small_vector and container
0347    //must have this public member
0348    typedef typename real_allocator<T, SecAlloc>::type                            secondary_allocator_t;
0349    typedef typename allocator_traits<secondary_allocator_t>::
0350       template portable_rebind_alloc<void>::type                                 void_allocator_t;
0351    typedef typename dtl::get_small_vector_opt<Options>::type                     options_t;
0352    typedef typename dtl::vector_for_small_vector
0353       <T, SecAlloc, Options>::type                                               base_type;
0354    typedef typename allocator_traits<secondary_allocator_t>::pointer             pointer;
0355    typedef typename allocator_traits<secondary_allocator_t>::const_pointer       const_pointer;
0356    typedef typename allocator_traits<secondary_allocator_t>::void_pointer        void_pointer;
0357    typedef typename allocator_traits<secondary_allocator_t>::const_void_pointer  const_void_pointer;
0358    typedef small_vector_allocator<T, void_allocator_t, Options>                  allocator_type;
0359
0360    private:
0361    BOOST_COPYABLE_AND_MOVABLE(small_vector_base)
0362
0363    friend class small_vector_allocator<T, void_allocator_t, Options>;
0364
0365    BOOST_CONTAINER_FORCEINLINE
0366    const_pointer internal_storage() const BOOST_NOEXCEPT_OR_NOTHROW
0367    {  return this->base_type::get_stored_allocator().internal_storage();   }
0368
0369    BOOST_CONTAINER_FORCEINLINE
0370    pointer internal_storage() BOOST_NOEXCEPT_OR_NOTHROW
0371    {  return this->base_type::get_stored_allocator().internal_storage();   }
0372
0373    private:
0374          base_type &as_base()       { return static_cast<base_type&>(*this); }
0375    const base_type &as_base() const { return static_cast<const base_type&>(*this); }
0376
0377    public:
0378
0379    protected:
0380
0381    BOOST_CONTAINER_FORCEINLINE explicit small_vector_base(initial_capacity_t, std::size_t initial_capacity)
0382       : base_type(initial_capacity_t(), this->internal_storage(), initial_capacity)
0383    {}
0384
0385    template<class AllocFwd>
0386    BOOST_CONTAINER_FORCEINLINE explicit small_vector_base(initial_capacity_t, std::size_t capacity, BOOST_FWD_REF(AllocFwd) a)
0387       : base_type(initial_capacity_t(), this->internal_storage(), capacity, ::boost::forward<AllocFwd>(a))
0388    {}
0389
0390    BOOST_CONTAINER_FORCEINLINE explicit small_vector_base(maybe_initial_capacity_t, std::size_t initial_capacity, std::size_t initial_size)
0391       : base_type( maybe_initial_capacity_t()
0392                  , (initial_capacity >= initial_size) ? this->internal_storage() : pointer()
0393                  , (initial_capacity >= initial_size) ? initial_capacity : initial_size
0394                  )
0395    {}
0396
0397    template<class AllocFwd>
0398    BOOST_CONTAINER_FORCEINLINE explicit small_vector_base(maybe_initial_capacity_t, std::size_t initial_capacity, std::size_t initial_size, BOOST_FWD_REF(AllocFwd) a)
0399       : base_type(maybe_initial_capacity_t()
0400                  , (initial_capacity >= initial_size) ? this->internal_storage() : pointer()
0401                  , (initial_capacity >= initial_size) ? initial_capacity : initial_size
0402                  , ::boost::forward<AllocFwd>(a)
0403       )
0404    {}
0405
0406    using base_type::protected_set_size;
0407
0408    //~small_vector_base(){}
0409    #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0410
0411    public:
0412    BOOST_CONTAINER_FORCEINLINE small_vector_base& operator=(BOOST_COPY_ASSIGN_REF(small_vector_base) other)
0413    {  return static_cast<small_vector_base&>(this->base_type::operator=(static_cast<base_type const&>(other)));  }
0414
0415    BOOST_CONTAINER_FORCEINLINE small_vector_base& operator=(BOOST_RV_REF(small_vector_base) other)
0416    {  return static_cast<small_vector_base&>(this->base_type::operator=(BOOST_MOVE_BASE(base_type, other))); }
0417
0418    BOOST_CONTAINER_FORCEINLINE void swap(small_vector_base &other)
0419    {  return this->base_type::swap(other);  }
0420
0421    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0422    protected:
0423    void move_construct_impl(base_type &x, const allocator_type &a)
0424    {
0425       if(base_type::is_propagable_from(x.get_stored_allocator(), x.data(), a, true)){
0426          this->steal_resources(x);
0427       }
0428       else{
0429          const typename base_type::size_type sz = x.size();
0430          ::boost::container::uninitialized_move_alloc_n_source
0431             (this->base_type::get_stored_allocator(), x.begin(), sz, this->begin());
0432          this->protected_set_size(sz);
0433          x.clear();
0434       }
0435    }
0436    #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0437 };
0438
0439 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0440
0441 /////////////////////////////////////////////////////
0442 //
0443 //          small_vector_storage_definer
0444 //
0445 /////////////////////////////////////////////////////
0446 template<class T, std::size_t N, class Options>
0447 struct small_vector_storage_definer
0448 {
0449    typedef typename dtl::get_small_vector_opt<Options>::type options_t;
0450    static const std::size_t final_alignment =
0451       options_t::inplace_alignment ? options_t::inplace_alignment : dtl::alignment_of<T>::value;
0452    typedef small_vector_storage<T, N, final_alignment> type;
0453 };
0454
0455 template <class T, class SecAlloc, class Options>
0456 struct small_vector_storage_strawman
0457    : public small_vector_base<T, SecAlloc, Options>
0458    , public small_vector_storage_definer<T, 1, Options>::type
0459 {
0460    typedef typename small_vector_storage_definer<T, 1, Options>::type sm_storage_t;
0461 };
0462
0463 //Internal storage hack
0464 template<class T, class VoidAlloc, class Options>
0465 BOOST_CONTAINER_FORCEINLINE typename small_vector_allocator<T, VoidAlloc, Options>::const_pointer
0466    small_vector_allocator<T, VoidAlloc, Options>::internal_storage() const BOOST_NOEXCEPT_OR_NOTHROW
0467 {
0468    typedef small_vector_storage_strawman<T, allocator_type, Options> strawman_t;
0469    typedef typename strawman_t::sm_storage_t sm_storage_t;
0470
0471    //These warnings are false positives, as we know the alignment is correct
0472    //and aligned storage is allowed to hold any type
0473    #if defined(BOOST_GCC) && (BOOST_GCC >= 40600)
0474    #pragma GCC diagnostic push
0475    #pragma GCC diagnostic ignored "-Wcast-align"
0476    #pragma GCC diagnostic ignored "-Wstrict-aliasing"
0477    #endif
0478    const vector_type& v = reinterpret_cast<const vector_type&>(*this);
0479    BOOST_ASSERT((std::size_t(this) % dtl::alignment_of<strawman_t>::value) == 0);
0480    const strawman_t &straw   = static_cast<const strawman_t&>(v);
0481    const sm_storage_t& stor = static_cast<const sm_storage_t&>(straw);
0482    return boost::intrusive::pointer_traits<const_pointer>::pointer_to(*((const T*)stor.m_storage.data));
0483    #if defined(BOOST_GCC) && (BOOST_GCC >= 40600)
0484    #pragma GCC diagnostic pop
0485    #endif
0486 }
0487
0488 template <class T, class VoidAlloc, class Options>
0489 BOOST_CONTAINER_FORCEINLINE typename small_vector_allocator<T, VoidAlloc, Options>::pointer
0490    small_vector_allocator<T, VoidAlloc, Options>::internal_storage() BOOST_NOEXCEPT_OR_NOTHROW
0491 {
0492    typedef small_vector_storage_strawman<T, allocator_type, Options> strawman_t;
0493    typedef typename strawman_t::sm_storage_t sm_storage_t;
0494
0495    #if defined(BOOST_GCC) && (BOOST_GCC >= 40600)
0496    #pragma GCC diagnostic push
0497    #pragma GCC diagnostic ignored "-Wcast-align"
0498    #pragma GCC diagnostic ignored "-Wstrict-aliasing"
0499    #endif
0500    vector_type& v = reinterpret_cast<vector_type&>(*this);
0501    BOOST_ASSERT((std::size_t(this) % dtl::alignment_of<strawman_t>::value) == 0);
0502    strawman_t &straw   = static_cast<strawman_t&>(v);
0503    sm_storage_t& stor = static_cast<sm_storage_t&>(straw);
0504    return boost::intrusive::pointer_traits<pointer>::pointer_to(*((T*)stor.m_storage.data));
0505    #if defined(BOOST_GCC) && (BOOST_GCC >= 40600)
0506    #pragma GCC diagnostic pop
0507    #endif
0508 }
0509
0510
0511 #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0512
0513 //! small_vector is a vector-like container optimized for the case when it contains few elements.
0514 //! It contains some preallocated elements in-place, which can avoid the use of dynamic storage allocation
0515 //! when the actual number of elements is below that preallocated threshold.
0516 //!
0517 //! `small_vector<T, N, Allocator, Options>` is convertible to `small_vector_base<T, Allocator, Options>` that is independent
0518 //! from the preallocated element capacity, so client code does not need to be templated on that N argument.
0519 //!
0520 //! All `boost::container::vector` member functions are inherited. See `vector` documentation for details.
0521 //!
0522 //! Any change to the capacity of the vector, including decreasing its size such as with the shrink_to_fit method, will
0523 //! cause the vector to permanently switch to dynamically allocated storage.
0524 //!
0525 //! \tparam T The type of object that is stored in the small_vector
0526 //! \tparam N The number of preallocated elements stored inside small_vector. It shall be less than Allocator::max_size();
0527 //! \tparam Allocator The allocator used for memory management when the number of elements exceeds N. Use void
0528 //!   for the default allocator
0529 //! \tparam Options A type produced from \c boost::container::small_vector_options.
0530 template <class T, std::size_t N, class Allocator BOOST_CONTAINER_DOCONLY(= void), class Options BOOST_CONTAINER_DOCONLY(= void) >
0531 class small_vector
0532    : public small_vector_base<T, Allocator, Options>
0533    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0534    , private small_vector_storage_definer<T, N, Options>::type
0535    #endif
0536 {
0537    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0538
0539    BOOST_COPYABLE_AND_MOVABLE(small_vector)
0540
0541    public:
0542    typedef small_vector_base<T, Allocator, Options>   base_type;
0543    typedef typename base_type::allocator_type   allocator_type;
0544    typedef typename base_type::size_type        size_type;
0545    typedef typename base_type::value_type       value_type;
0546
0547    BOOST_CONTAINER_FORCEINLINE static std::size_t internal_capacity()
0548    {  return static_capacity;  }
0549
0550    typedef allocator_traits<typename base_type::allocator_type> allocator_traits_type;
0551
0552    #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0553
0554    //! @brief The capacity/max size of the container
0555    static const size_type static_capacity = small_vector_storage_definer<T, N, Options>::type::sms_size;
0556
0557    public:
0558    BOOST_CONTAINER_FORCEINLINE small_vector()
0559       BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<allocator_type>::value)
0560       : base_type(initial_capacity_t(), internal_capacity())
0561    {}
0562
0563    BOOST_CONTAINER_FORCEINLINE explicit small_vector(const allocator_type &a)
0564       : base_type(initial_capacity_t(), internal_capacity(), a)
0565    {}
0566
0567    BOOST_CONTAINER_FORCEINLINE explicit small_vector(size_type n)
0568       : base_type(maybe_initial_capacity_t(), internal_capacity(), n)
0569    {  this->protected_init_n(n, value_init); }
0570
0571    BOOST_CONTAINER_FORCEINLINE small_vector(size_type n, const allocator_type &a)
0572       : base_type(maybe_initial_capacity_t(), internal_capacity(), n, a)
0573    {  this->protected_init_n(n, value_init); }
0574
0575    BOOST_CONTAINER_FORCEINLINE small_vector(size_type n, default_init_t)
0576       : base_type(maybe_initial_capacity_t(), internal_capacity(), n)
0577    {  this->protected_init_n(n, default_init_t()); }
0578
0579    BOOST_CONTAINER_FORCEINLINE small_vector(size_type n, default_init_t, const allocator_type &a)
0580       : base_type(maybe_initial_capacity_t(), internal_capacity(), n, a)
0581    {  this->protected_init_n(n, default_init_t()); }
0582
0583    BOOST_CONTAINER_FORCEINLINE small_vector(size_type n, const value_type &v)
0584       : base_type(maybe_initial_capacity_t(), internal_capacity(), n)
0585    {  this->protected_init_n(n, v); }
0586
0587    BOOST_CONTAINER_FORCEINLINE small_vector(size_type n, const value_type &v, const allocator_type &a)
0588       : base_type(maybe_initial_capacity_t(), internal_capacity(), n, a)
0589    {  this->protected_init_n(n, v); }
0590
0591    template <class InIt>
0592    BOOST_CONTAINER_FORCEINLINE small_vector(InIt first, InIt last
0593       BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_c
0594          < dtl::is_convertible<InIt BOOST_MOVE_I size_type>::value
0595          BOOST_MOVE_I dtl::nat >::type * = 0)
0596       )
0597       : base_type(initial_capacity_t(), internal_capacity())
0598    {  this->assign(first, last); }
0599
0600    template <class InIt>
0601    BOOST_CONTAINER_FORCEINLINE small_vector(InIt first, InIt last, const allocator_type& a
0602       BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_c
0603          < dtl::is_convertible<InIt BOOST_MOVE_I size_type>::value
0604          BOOST_MOVE_I dtl::nat >::type * = 0)
0605       )
0606       : base_type(initial_capacity_t(), internal_capacity(), a)
0607    {  this->assign(first, last); }
0608
0609    BOOST_CONTAINER_FORCEINLINE small_vector(const small_vector &other)
0610       : base_type( initial_capacity_t(), internal_capacity()
0611                  , allocator_traits_type::select_on_container_copy_construction(other.get_stored_allocator()))
0612    {  this->assign(other.cbegin(), other.cend());  }
0613
0614    BOOST_CONTAINER_FORCEINLINE small_vector(const small_vector &other, const allocator_type &a)
0615       : base_type(initial_capacity_t(), internal_capacity(), a)
0616    {  this->assign(other.cbegin(), other.cend());  }
0617
0618    BOOST_CONTAINER_FORCEINLINE explicit small_vector(const base_type &other)
0619       : base_type( initial_capacity_t(), internal_capacity()
0620                  , allocator_traits_type::select_on_container_copy_construction(other.get_stored_allocator()))
0621    {  this->assign(other.cbegin(), other.cend());  }
0622
0623    BOOST_CONTAINER_FORCEINLINE explicit small_vector(BOOST_RV_REF(base_type) other)
0624       : base_type(initial_capacity_t(), internal_capacity(), ::boost::move(other.get_stored_allocator()))
0625    {  this->move_construct_impl(other, other.get_stored_allocator());   }
0626
0627    BOOST_CONTAINER_FORCEINLINE small_vector(BOOST_RV_REF(small_vector) other)
0628       BOOST_NOEXCEPT_IF(boost::container::dtl::is_nothrow_move_constructible<value_type>::value)
0629       : base_type(initial_capacity_t(), internal_capacity(), ::boost::move(other.get_stored_allocator()))
0630    {  this->move_construct_impl(other, other.get_stored_allocator());   }
0631
0632    BOOST_CONTAINER_FORCEINLINE small_vector(BOOST_RV_REF(small_vector) other, const allocator_type &a)
0633       : base_type(initial_capacity_t(), internal_capacity(), a)
0634    {  this->move_construct_impl(other, a);   }
0635
0636    #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
0637    BOOST_CONTAINER_FORCEINLINE small_vector(std::initializer_list<value_type> il, const allocator_type& a = allocator_type())
0638       : base_type(initial_capacity_t(), internal_capacity(), a)
0639    {
0640       this->assign(il.begin(), il.end());
0641    }
0642    #endif
0643
0644    BOOST_CONTAINER_FORCEINLINE small_vector& operator=(BOOST_COPY_ASSIGN_REF(small_vector) other)
0645    {  return static_cast<small_vector&>(this->base_type::operator=(static_cast<base_type const&>(other)));  }
0646
0647    BOOST_CONTAINER_FORCEINLINE small_vector& operator=(BOOST_RV_REF(small_vector) other)
0648       BOOST_NOEXCEPT_IF(boost::container::dtl::is_nothrow_move_assignable<value_type>::value
0649          && (allocator_traits_type::propagate_on_container_move_assignment::value
0650              || allocator_traits_type::is_always_equal::value))
0651    {  return static_cast<small_vector&>(this->base_type::operator=(BOOST_MOVE_BASE(base_type, other))); }
0652
0653    BOOST_CONTAINER_FORCEINLINE small_vector& operator=(const base_type &other)
0654    {  return static_cast<small_vector&>(this->base_type::operator=(other));  }
0655
0656    BOOST_CONTAINER_FORCEINLINE small_vector& operator=(BOOST_RV_REF(base_type) other)
0657    {  return static_cast<small_vector&>(this->base_type::operator=(boost::move(other))); }
0658
0659    BOOST_CONTAINER_FORCEINLINE void swap(small_vector &other)
0660    {  return this->base_type::swap(other);  }
0661 };
0662
0663 }}
0664
0665 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0666 /*
0667 namespace boost {
0668
0669 //!has_trivial_destructor_after_move<> == true_type
0670 //!specialization for optimizations
0671 template <class T, class Allocator>
0672 struct has_trivial_destructor_after_move<boost::container::vector<T, Allocator> >
0673 {
0674    typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer;
0675    static const bool value = ::boost::has_trivial_destructor_after_move<Allocator>::value &&
0676                              ::boost::has_trivial_destructor_after_move<pointer>::value;
0677 };
0678
0679 }
0680 */
0681 #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0682
0683 #include <boost/container/detail/config_end.hpp>
0684
0685 #endif //   #ifndef  BOOST_CONTAINER_CONTAINER_SMALL_VECTOR_HPP