ceph/src/boost/libs/container/include/boost/container/small_vector.hpp

   1 //////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga 2015-2015. Distributed under the Boost
   4 // Software License, Version 1.0. (See accompanying file
   5 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   6 //
   7 // See http://www.boost.org/libs/container for documentation.
   8 //
   9 //////////////////////////////////////////////////////////////////////////////
  10
  11 #ifndef BOOST_CONTAINER_CONTAINER_SMALL_VECTOR_HPP
  12 #define BOOST_CONTAINER_CONTAINER_SMALL_VECTOR_HPP
  13
  14 #ifndef BOOST_CONFIG_HPP
  15 #  include <boost/config.hpp>
  16 #endif
  17
  18 #if defined(BOOST_HAS_PRAGMA_ONCE)
  19 #  pragma once
  20 #endif
  21
  22 #include <boost/container/detail/config_begin.hpp>
  23 #include <boost/container/detail/workaround.hpp>
  24
  25 // container
  26 #include <boost/container/container_fwd.hpp>
  27 #include <boost/container/vector.hpp>
  28 #include <boost/container/allocator_traits.hpp>
  29 #include <boost/container/new_allocator.hpp> //new_allocator
  30 // container/detail
  31 #include <boost/container/detail/type_traits.hpp>
  32 #include <boost/container/detail/version_type.hpp>
  33
  34 //move
  35 #include <boost/move/adl_move_swap.hpp>
  36 #include <boost/move/iterator.hpp>
  37
  38 //move/detail
  39 #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
  40 #include <boost/move/detail/fwd_macros.hpp>
  41 #endif
  42
  43 //std
  44 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
  45 #include <initializer_list>   //for std::initializer_list
  46 #endif
  47
  48 namespace boost {
  49 namespace container {
  50
  51 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
  52
  53 template <class T, class Allocator = new_allocator<T> >
  54 class small_vector_base;
  55
  56 #endif
  57
  58 //! A non-standard allocator used to implement `small_vector`.
  59 //! Users should never use it directly. It is described here
  60 //! for documentation purposes.
  61 //!
  62 //! This allocator inherits from a standard-conforming allocator
  63 //! and forwards member functions to the standard allocator except
  64 //! when internal storage is being used as memory source.
  65 //!
  66 //! This allocator is a "partially_propagable" allocator and
  67 //! defines `is_partially_propagable` as true_type.
  68 //!
  69 //! A partially propagable allocator means that not all storage
  70 //! allocatod by an instance of `small_vector_allocator` can be
  71 //! deallocated by another instance of this type, even if both
  72 //! instances compare equal or an instance is propagated to another
  73 //! one using the copy/move constructor or assignment. The storage that
  74 //! can never be propagated is identified by `storage_is_unpropagable(p)`.
  75 //!
  76 //! `boost::container::vector` supports partially propagable allocators
  77 //! fallbacking to deep copy/swap/move operations when internal storage
  78 //! is being used to store vector elements.
  79 //!
  80 //! `small_vector_allocator` assumes that will be instantiated as
  81 //! `boost::container::vector< T, small_vector_allocator<Allocator> >`
  82 //! and internal storage can be obtained downcasting that vector
  83 //! to `small_vector_base<T>`.
  84 template<class Allocator>
  85 class small_vector_allocator
  86    : public Allocator
  87 {
  88    typedef unsigned int allocation_type;
  89    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
  90    private:
  91
  92    BOOST_COPYABLE_AND_MOVABLE(small_vector_allocator)
  93
  94    BOOST_CONTAINER_FORCEINLINE const Allocator &as_base() const
  95    {  return static_cast<const Allocator&>(*this);  }
  96
  97    BOOST_CONTAINER_FORCEINLINE Allocator &as_base()
  98    {  return static_cast<Allocator&>(*this);  }
  99
 100    #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 101
 102    public:
 103    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 104    typedef allocator_traits<Allocator> allocator_traits_type;
 105    #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 106
 107    typedef typename allocator_traits<Allocator>::value_type          value_type;
 108    typedef typename allocator_traits<Allocator>::pointer             pointer;
 109    typedef typename allocator_traits<Allocator>::const_pointer       const_pointer;
 110    typedef typename allocator_traits<Allocator>::reference           reference;
 111    typedef typename allocator_traits<Allocator>::const_reference     const_reference;
 112    typedef typename allocator_traits<Allocator>::size_type           size_type;
 113    typedef typename allocator_traits<Allocator>::difference_type     difference_type;
 114    typedef typename allocator_traits<Allocator>::void_pointer        void_pointer;
 115    typedef typename allocator_traits<Allocator>::const_void_pointer  const_void_pointer;
 116
 117    typedef typename allocator_traits<Allocator>::propagate_on_container_copy_assignment   propagate_on_container_copy_assignment;
 118    typedef typename allocator_traits<Allocator>::propagate_on_container_move_assignment   propagate_on_container_move_assignment;
 119    typedef typename allocator_traits<Allocator>::propagate_on_container_swap              propagate_on_container_swap;
 120    //! An integral constant with member `value == false`
 121    typedef BOOST_CONTAINER_IMPDEF(container_detail::bool_<false>)                         is_always_equal;
 122    //! An integral constant with member `value == true`
 123    typedef BOOST_CONTAINER_IMPDEF(container_detail::bool_<true>)                          is_partially_propagable;
 124
 125    BOOST_CONTAINER_DOCIGN(typedef container_detail::version_type<small_vector_allocator BOOST_CONTAINER_I 1>  version;)
 126
 127    //!Obtains an small_vector_allocator that allocates
 128    //!objects of type T2
 129    template<class T2>
 130    struct rebind
 131    {
 132       typedef typename allocator_traits<Allocator>::template rebind_alloc<T2>::type other;
 133    };
 134
 135    #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
 136       //!Constructor from arbitrary arguments
 137       template<class ...Args>
 138       BOOST_CONTAINER_FORCEINLINE explicit small_vector_allocator(BOOST_FWD_REF(Args) ...args)
 139          : Allocator(::boost::forward<Args>(args)...)
 140       {}
 141    #else
 142       #define BOOST_CONTAINER_SMALL_VECTOR_ALLOCATOR_CTOR_CODE(N) \
 143       BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
 144       BOOST_CONTAINER_FORCEINLINE explicit small_vector_allocator(BOOST_MOVE_UREF##N)\
 145          : Allocator(BOOST_MOVE_FWD##N)\
 146       {}\
 147       //
 148       BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_SMALL_VECTOR_ALLOCATOR_CTOR_CODE)
 149       #undef BOOST_CONTAINER_SMALL_VECTOR_ALLOCATOR_CTOR_CODE
 150    #endif
 151
 152    //!Constructor from other small_vector_allocator.
 153    //!Never throws
 154    BOOST_CONTAINER_FORCEINLINE small_vector_allocator
 155       (const small_vector_allocator &other) BOOST_NOEXCEPT_OR_NOTHROW
 156       : Allocator(other.as_base())
 157    {}
 158
 159    //!Move constructor from small_vector_allocator.
 160    //!Never throws
 161    BOOST_CONTAINER_FORCEINLINE small_vector_allocator
 162       (BOOST_RV_REF(small_vector_allocator) other) BOOST_NOEXCEPT_OR_NOTHROW
 163       : Allocator(::boost::move(other.as_base()))
 164    {}
 165
 166    //!Constructor from related small_vector_allocator.
 167    //!Never throws
 168    template<class OtherAllocator>
 169    BOOST_CONTAINER_FORCEINLINE small_vector_allocator
 170       (const small_vector_allocator<OtherAllocator> &other) BOOST_NOEXCEPT_OR_NOTHROW
 171       : Allocator(other.as_base())
 172    {}
 173
 174    //!Move constructor from related small_vector_allocator.
 175    //!Never throws
 176    template<class OtherAllocator>
 177    BOOST_CONTAINER_FORCEINLINE small_vector_allocator
 178       (BOOST_RV_REF(small_vector_allocator<OtherAllocator>) other) BOOST_NOEXCEPT_OR_NOTHROW
 179       : Allocator(::boost::move(other.as_base()))
 180    {}
 181
 182    //!Assignment from other small_vector_allocator.
 183    //!Never throws
 184    BOOST_CONTAINER_FORCEINLINE small_vector_allocator &
 185       operator=(BOOST_COPY_ASSIGN_REF(small_vector_allocator) other) BOOST_NOEXCEPT_OR_NOTHROW
 186    {  return static_cast<small_vector_allocator&>(this->Allocator::operator=(other.as_base()));  }
 187
 188    //!Move constructor from other small_vector_allocator.
 189    //!Never throws
 190    BOOST_CONTAINER_FORCEINLINE small_vector_allocator &
 191       operator=(BOOST_RV_REF(small_vector_allocator) other) BOOST_NOEXCEPT_OR_NOTHROW
 192    {  return static_cast<small_vector_allocator&>(this->Allocator::operator=(::boost::move(other.as_base())));  }
 193
 194    //!Assignment from related small_vector_allocator.
 195    //!Never throws
 196    template<class OtherAllocator>
 197    BOOST_CONTAINER_FORCEINLINE small_vector_allocator &
 198       operator=(BOOST_COPY_ASSIGN_REF(small_vector_allocator<OtherAllocator>) other) BOOST_NOEXCEPT_OR_NOTHROW
 199    {  return static_cast<small_vector_allocator&>(this->Allocator::operator=(other.as_base()));  }
 200
 201    //!Move assignment from related small_vector_allocator.
 202    //!Never throws
 203    template<class OtherAllocator>
 204    BOOST_CONTAINER_FORCEINLINE small_vector_allocator &
 205       operator=(BOOST_RV_REF(small_vector_allocator<OtherAllocator>) other) BOOST_NOEXCEPT_OR_NOTHROW
 206    {  return static_cast<small_vector_allocator&>(this->Allocator::operator=(::boost::move(other.as_base())));  }
 207
 208    //!Allocates storage from the standard-conforming allocator
 209    BOOST_CONTAINER_FORCEINLINE pointer allocate(size_type count, const_void_pointer hint = const_void_pointer())
 210    {  return allocator_traits_type::allocate(this->as_base(), count, hint);  }
 211
 212    //!Deallocates previously allocated memory.
 213    //!Never throws
 214    void deallocate(pointer ptr, size_type n) BOOST_NOEXCEPT_OR_NOTHROW
 215    {
 216       if(!this->is_internal_storage(ptr))
 217          allocator_traits_type::deallocate(this->as_base(), ptr, n);
 218    }
 219
 220    //!Returns the maximum number of elements that could be allocated.
 221    //!Never throws
 222    BOOST_CONTAINER_FORCEINLINE size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW
 223    {  return allocator_traits_type::max_size(this->as_base());   }
 224
 225    small_vector_allocator select_on_container_copy_construction() const
 226    {  return small_vector_allocator(allocator_traits_type::select_on_container_copy_construction(this->as_base())); }
 227
 228    bool storage_is_unpropagable(pointer p) const
 229    {  return this->is_internal_storage(p) || allocator_traits_type::storage_is_unpropagable(this->as_base(), p);  }
 230
 231    //!Swaps two allocators, does nothing
 232    //!because this small_vector_allocator is stateless
 233    BOOST_CONTAINER_FORCEINLINE friend void swap(small_vector_allocator &l, small_vector_allocator &r) BOOST_NOEXCEPT_OR_NOTHROW
 234    {  boost::adl_move_swap(l.as_base(), r.as_base());  }
 235
 236    //!An small_vector_allocator always compares to true, as memory allocated with one
 237    //!instance can be deallocated by another instance (except for unpropagable storage)
 238    BOOST_CONTAINER_FORCEINLINE friend bool operator==(const small_vector_allocator &l, const small_vector_allocator &r) BOOST_NOEXCEPT_OR_NOTHROW
 239    {  return allocator_traits_type::equal(l.as_base(), r.as_base());  }
 240
 241    //!An small_vector_allocator always compares to false, as memory allocated with one
 242    //!instance can be deallocated by another instance
 243    BOOST_CONTAINER_FORCEINLINE friend bool operator!=(const small_vector_allocator &l, const small_vector_allocator &r) BOOST_NOEXCEPT_OR_NOTHROW
 244    {  return !(l == r);   }
 245
 246    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 247    /*
 248    //!An advanced function that offers in-place expansion shrink to fit and new allocation
 249    //!capabilities. Memory allocated with this function can only be deallocated with deallocate()
 250    //!or deallocate_many().
 251    //!This function is available only with Version == 2
 252    pointer allocation_command(allocation_type command,
 253                          size_type limit_size,
 254                          size_type &prefer_in_recvd_out_size,
 255                          pointer &reuse)
 256    {  return allocator_traits_type::allocation_command(command, limit_size, prefer_in_recvd_out_size, reuse);  }
 257
 258    //!Returns maximum the number of objects the previously allocated memory
 259    //!pointed by p can hold.
 260    //!Memory must not have been allocated with
 261    //!allocate_one or allocate_individual.
 262    //!This function is available only with Version == 2
 263    size_type size(pointer p) const BOOST_NOEXCEPT_OR_NOTHROW
 264    {  return allocator_traits_type::size(p);  }
 265    */
 266    private:
 267    /*
 268    //!Allocates just one object. Memory allocated with this function
 269    //!must be deallocated only with deallocate_one().
 270    //!Throws bad_alloc if there is no enough memory
 271    //!This function is available only with Version == 2
 272    using Allocator::allocate_one;
 273    using Allocator::allocate_individual;
 274    using Allocator::deallocate_one;
 275    using Allocator::deallocate_individual;
 276    using Allocator::allocate_many;
 277    using Allocator::deallocate_many;*/
 278
 279    BOOST_CONTAINER_FORCEINLINE bool is_internal_storage(pointer p) const
 280    {  return this->internal_storage() == p;  }
 281
 282    pointer internal_storage() const
 283    {
 284       typedef typename Allocator::value_type                                              value_type;
 285       typedef container_detail::vector_alloc_holder< small_vector_allocator<Allocator> >  vector_alloc_holder_t;
 286       typedef vector<value_type, small_vector_allocator<Allocator> >                      vector_base;
 287       typedef small_vector_base<value_type, Allocator>                                    derived_type;
 288       //
 289       const vector_alloc_holder_t &v_holder = static_cast<const vector_alloc_holder_t &>(*this);
 290       const vector_base &v_base = reinterpret_cast<const vector_base &>(v_holder);
 291       const derived_type &d_base = static_cast<const derived_type &>(v_base);
 292       return d_base.internal_storage();
 293    }
 294    #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 295 };
 296
 297 //! This class consists of common code from all small_vector<T, N> types that don't depend on the
 298 //! "N" template parameter. This class is non-copyable and non-destructible, so this class typically
 299 //! used as reference argument to functions that read or write small vectors. Since `small_vector<T, N>`
 300 //! derives from `small_vector_base<T>`, the conversion to `small_vector_base` is implicit
 301 //! <pre>
 302 //!
 303 //! //Clients can pass any small_vector<Foo, N>.
 304 //! void read_any_small_vector_of_foo(const small_vector_base<Foo> &in_parameter);
 305 //!
 306 //! void modify_any_small_vector_of_foo(small_vector_base<Foo> &in_out_parameter);
 307 //!
 308 //! void some_function()
 309 //! {
 310 //!
 311 //!    small_vector<Foo, 8> myvector;
 312 //!
 313 //!    read_any_small_vector_of_foo(myvector);   // Reads myvector
 314 //!
 315 //!    modify_any_small_vector_of_foo(myvector); // Modifies myvector
 316 //!
 317 //! }
 318 //! </pre>
 319 //!
 320 //! All `boost::container:vector` member functions are inherited. See `vector` documentation for details.
 321 //!
 322 template <class T, class SecondaryAllocator>
 323 class small_vector_base
 324    : public vector<T, small_vector_allocator<SecondaryAllocator> >
 325 {
 326    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 327    public:
 328    //Make it public as it will be inherited by small_vector and container
 329    //must have this public member
 330    typedef typename allocator_traits<SecondaryAllocator>::pointer pointer;
 331
 332    private:
 333    BOOST_COPYABLE_AND_MOVABLE(small_vector_base)
 334
 335    friend class small_vector_allocator<SecondaryAllocator>;
 336
 337    pointer internal_storage() const BOOST_NOEXCEPT_OR_NOTHROW
 338    {
 339       return boost::intrusive::pointer_traits<pointer>::pointer_to
 340          (*const_cast<T*>(static_cast<const T*>(static_cast<const void*>(&m_storage_start))));
 341    }
 342
 343    typedef vector<T, small_vector_allocator<SecondaryAllocator> > base_type;
 344          base_type &as_base()       { return static_cast<base_type&>(*this); }
 345    const base_type &as_base() const { return static_cast<const base_type&>(*this); }
 346
 347    public:
 348    typedef typename container_detail::aligned_storage
 349       <sizeof(T), container_detail::alignment_of<T>::value>::type storage_type;
 350    typedef small_vector_allocator<SecondaryAllocator>             allocator_type;
 351
 352    protected:
 353    typedef typename base_type::initial_capacity_t initial_capacity_t;
 354
 355    BOOST_CONTAINER_FORCEINLINE explicit small_vector_base(initial_capacity_t, std::size_t initial_capacity)
 356       : base_type(initial_capacity_t(), this->internal_storage(), initial_capacity)
 357    {}
 358
 359    template<class AllocFwd>
 360    BOOST_CONTAINER_FORCEINLINE explicit small_vector_base(initial_capacity_t, std::size_t capacity, BOOST_FWD_REF(AllocFwd) a)
 361       : base_type(initial_capacity_t(), this->internal_storage(), capacity, ::boost::forward<AllocFwd>(a))
 362    {}
 363
 364    //~small_vector_base(){}
 365
 366    private:
 367    //The only member
 368    storage_type m_storage_start;
 369
 370    #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 371
 372    public:
 373    BOOST_CONTAINER_FORCEINLINE small_vector_base& operator=(BOOST_COPY_ASSIGN_REF(small_vector_base) other)
 374    {  return static_cast<small_vector_base&>(this->base_type::operator=(static_cast<base_type const&>(other)));  }
 375
 376    BOOST_CONTAINER_FORCEINLINE small_vector_base& operator=(BOOST_RV_REF(small_vector_base) other)
 377    {  return static_cast<small_vector_base&>(this->base_type::operator=(BOOST_MOVE_BASE(base_type, other))); }
 378
 379    BOOST_CONTAINER_FORCEINLINE void swap(small_vector_base &other)
 380    {  return this->base_type::swap(other);  }
 381
 382    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 383    protected:
 384    void move_construct_impl(base_type &x, const allocator_type &a)
 385    {
 386       if(base_type::is_propagable_from(x.get_stored_allocator(), x.data(), a, true)){
 387          this->steal_resources(x);
 388       }
 389       else{
 390          this->assign( boost::make_move_iterator(container_detail::iterator_to_raw_pointer(x.begin()))
 391                      , boost::make_move_iterator(container_detail::iterator_to_raw_pointer(x.end  ()))
 392                      );
 393       }
 394    }
 395    #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 396 };
 397
 398 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 399
 400 /////////////////////////////////////////////////////
 401 //
 402 //          small_vector_storage_calculator
 403 //
 404 /////////////////////////////////////////////////////
 405 template<std::size_t Needed, std::size_t Hdr, std::size_t SSize, bool NeedsZero = (0u == Needed || Needed <= Hdr)>
 406 struct small_vector_storage_calculator_helper
 407 {
 408    static const std::size_t value = (Needed - Hdr - 1u)/SSize + 1u;
 409 };
 410
 411 template<std::size_t Needed, std::size_t Hdr, std::size_t SSize>
 412 struct small_vector_storage_calculator_helper<Needed, Hdr, SSize, true>
 413 {
 414    static const std::size_t value = 0u;
 415 };
 416
 417 template<class Storage, class Allocator, class T, std::size_t N>
 418 struct small_vector_storage_calculator
 419 {
 420    typedef small_vector_base<T, Allocator> svh_type;
 421    typedef vector<T, small_vector_allocator<Allocator> > svhb_type;
 422    static const std::size_t s_align = container_detail::alignment_of<Storage>::value;
 423    static const std::size_t s_size = sizeof(Storage);
 424    static const std::size_t svh_sizeof = sizeof(svh_type);
 425    static const std::size_t svhb_sizeof = sizeof(svhb_type);
 426    static const std::size_t s_start = ((svhb_sizeof-1)/s_align+1)*s_align;
 427    static const std::size_t header_bytes = svh_sizeof-s_start;
 428    static const std::size_t needed_bytes = sizeof(T)*N;
 429    static const std::size_t needed_extra_storages =
 430       small_vector_storage_calculator_helper<needed_bytes, header_bytes, s_size>::value;
 431 };
 432
 433 /////////////////////////////////////////////////////
 434 //
 435 //          small_vector_storage_definer
 436 //
 437 /////////////////////////////////////////////////////
 438 template<class Storage, std::size_t N>
 439 struct small_vector_storage
 440 {
 441    Storage m_rest_of_storage[N];
 442 };
 443
 444 template<class Storage>
 445 struct small_vector_storage<Storage, 0>
 446 {};
 447
 448 template<class Allocator, std::size_t N>
 449 struct small_vector_storage_definer
 450 {
 451    typedef typename Allocator::value_type                                  value_type;
 452    typedef typename small_vector_base<value_type, Allocator>::storage_type storage_type;
 453    static const std::size_t needed_extra_storages =
 454       small_vector_storage_calculator<storage_type, Allocator, value_type, N>::needed_extra_storages;
 455    typedef small_vector_storage<storage_type, needed_extra_storages> type;
 456 };
 457
 458 #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 459
 460 //! small_vector is a vector-like container optimized for the case when it contains few elements.
 461 //! It contains some preallocated elements in-place, which can avoid the use of dynamic storage allocation
 462 //! when the actual number of elements is below that preallocated threshold.
 463 //!
 464 //! `small_vector<T, N, Allocator>` is convertible to `small_vector_base<T, Allocator>` that is independent
 465 //! from the preallocated element capacity, so client code does not need to be templated on that N argument.
 466 //!
 467 //! All `boost::container::vector` member functions are inherited. See `vector` documentation for details.
 468 //!
 469 //! \tparam T The type of object that is stored in the small_vector
 470 //! \tparam N The number of preallocated elements stored inside small_vector. It shall be less than Allocator::max_size();
 471 //! \tparam Allocator The allocator used for memory management when the number of elements exceeds N.
 472 template <class T, std::size_t N, class Allocator BOOST_CONTAINER_DOCONLY(= new_allocator<T>) >
 473 class small_vector : public small_vector_base<T, Allocator>
 474    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 475    , private small_vector_storage_definer<Allocator, N>::type
 476    #endif
 477 {
 478    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 479    typedef small_vector_base<T, Allocator> base_type;
 480    typedef typename small_vector_storage_definer<Allocator, N>::type remaining_storage_holder;
 481
 482    BOOST_COPYABLE_AND_MOVABLE(small_vector)
 483
 484    typedef typename base_type::initial_capacity_t initial_capacity_t;
 485    typedef allocator_traits<typename base_type::allocator_type> allocator_traits_type;
 486
 487    public:
 488    typedef small_vector_storage_calculator< typename small_vector_base<T, Allocator>
 489       ::storage_type, Allocator, T, N> storage_test;
 490
 491    static const std::size_t needed_extra_storages =  storage_test::needed_extra_storages;
 492    static const std::size_t needed_bytes =  storage_test::needed_bytes;
 493    static const std::size_t header_bytes =  storage_test::header_bytes;
 494    static const std::size_t s_start =  storage_test::s_start;
 495
 496    typedef typename base_type::allocator_type   allocator_type;
 497    typedef typename base_type::size_type        size_type;
 498    typedef typename base_type::value_type       value_type;
 499
 500    BOOST_CONTAINER_FORCEINLINE static std::size_t internal_capacity()
 501    {  return (sizeof(small_vector) - storage_test::s_start)/sizeof(T);  }
 502
 503    #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 504
 505    //! @brief The capacity/max size of the container
 506    static const size_type static_capacity = N;
 507
 508    public:
 509    BOOST_CONTAINER_FORCEINLINE small_vector()
 510            BOOST_NOEXCEPT_IF(container_detail::is_nothrow_default_constructible<Allocator>::value)
 511       : base_type(initial_capacity_t(), internal_capacity())
 512    {}
 513
 514    BOOST_CONTAINER_FORCEINLINE explicit small_vector(const allocator_type &a)
 515       : base_type(initial_capacity_t(), internal_capacity(), a)
 516    {}
 517
 518    BOOST_CONTAINER_FORCEINLINE explicit small_vector(size_type n)
 519       : base_type(initial_capacity_t(), internal_capacity())
 520    {  this->resize(n); }
 521
 522    BOOST_CONTAINER_FORCEINLINE small_vector(size_type n, const allocator_type &a)
 523       : base_type(initial_capacity_t(), internal_capacity(), a)
 524    {  this->resize(n); }
 525
 526    BOOST_CONTAINER_FORCEINLINE small_vector(size_type n, default_init_t)
 527       : base_type(initial_capacity_t(), internal_capacity())
 528    {  this->resize(n, default_init_t()); }
 529
 530    BOOST_CONTAINER_FORCEINLINE small_vector(size_type n, default_init_t, const allocator_type &a)
 531       : base_type(initial_capacity_t(), internal_capacity(), a)
 532    {  this->resize(n, default_init_t()); }
 533
 534    BOOST_CONTAINER_FORCEINLINE small_vector(size_type n, const value_type &v)
 535       : base_type(initial_capacity_t(), internal_capacity())
 536    {  this->resize(n, v); }
 537
 538    BOOST_CONTAINER_FORCEINLINE small_vector(size_type n, const value_type &v, const allocator_type &a)
 539       : base_type(initial_capacity_t(), internal_capacity(), a)
 540    {  this->resize(n, v); }
 541
 542    template <class InIt>
 543    BOOST_CONTAINER_FORCEINLINE small_vector(InIt first, InIt last
 544       BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename container_detail::disable_if_c
 545          < container_detail::is_convertible<InIt BOOST_MOVE_I size_type>::value
 546          BOOST_MOVE_I container_detail::nat >::type * = 0)
 547       )
 548       : base_type(initial_capacity_t(), internal_capacity())
 549    {  this->assign(first, last); }
 550
 551    template <class InIt>
 552    BOOST_CONTAINER_FORCEINLINE small_vector(InIt first, InIt last, const allocator_type& a
 553       BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename container_detail::disable_if_c
 554          < container_detail::is_convertible<InIt BOOST_MOVE_I size_type>::value
 555          BOOST_MOVE_I container_detail::nat >::type * = 0)
 556       )
 557       : base_type(initial_capacity_t(), internal_capacity(), a)
 558    {  this->assign(first, last); }
 559
 560    BOOST_CONTAINER_FORCEINLINE small_vector(const small_vector &other)
 561       : base_type( initial_capacity_t(), internal_capacity()
 562                  , allocator_traits_type::select_on_container_copy_construction(other.get_stored_allocator()))
 563    {  this->assign(other.cbegin(), other.cend());  }
 564
 565    BOOST_CONTAINER_FORCEINLINE small_vector(const small_vector &other, const allocator_type &a)
 566       : base_type(initial_capacity_t(), internal_capacity(), a)
 567    {  this->assign(other.cbegin(), other.cend());  }
 568
 569    BOOST_CONTAINER_FORCEINLINE explicit small_vector(const base_type &other)
 570       : base_type( initial_capacity_t(), internal_capacity()
 571                  , allocator_traits_type::select_on_container_copy_construction(other.get_stored_allocator()))
 572    {  this->assign(other.cbegin(), other.cend());  }
 573
 574    BOOST_CONTAINER_FORCEINLINE explicit small_vector(BOOST_RV_REF(base_type) other)
 575       : base_type(initial_capacity_t(), internal_capacity(), ::boost::move(other.get_stored_allocator()))
 576    {  this->move_construct_impl(other, other.get_stored_allocator());   }
 577
 578    BOOST_CONTAINER_FORCEINLINE small_vector(BOOST_RV_REF(small_vector) other)
 579       : base_type(initial_capacity_t(), internal_capacity(), ::boost::move(other.get_stored_allocator()))
 580    {  this->move_construct_impl(other, other.get_stored_allocator());   }
 581
 582    BOOST_CONTAINER_FORCEINLINE small_vector(BOOST_RV_REF(small_vector) other, const allocator_type &a)
 583       : base_type(initial_capacity_t(), internal_capacity(), a)
 584    {  this->move_construct_impl(other, a);   }
 585
 586    #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
 587    BOOST_CONTAINER_FORCEINLINE small_vector(std::initializer_list<value_type> il, const allocator_type& a = allocator_type())
 588       : base_type(initial_capacity_t(), internal_capacity(), a)
 589    {
 590       this->assign(il.begin(), il.end());
 591    }
 592    #endif
 593
 594    BOOST_CONTAINER_FORCEINLINE small_vector& operator=(BOOST_COPY_ASSIGN_REF(small_vector) other)
 595    {  return static_cast<small_vector&>(this->base_type::operator=(static_cast<base_type const&>(other)));  }
 596
 597    BOOST_CONTAINER_FORCEINLINE small_vector& operator=(BOOST_RV_REF(small_vector) other)
 598    {  return static_cast<small_vector&>(this->base_type::operator=(BOOST_MOVE_BASE(base_type, other))); }
 599
 600    BOOST_CONTAINER_FORCEINLINE small_vector& operator=(const base_type &other)
 601    {  return static_cast<small_vector&>(this->base_type::operator=(other));  }
 602
 603    BOOST_CONTAINER_FORCEINLINE small_vector& operator=(BOOST_RV_REF(base_type) other)
 604    {  return static_cast<small_vector&>(this->base_type::operator=(boost::move(other))); }
 605
 606    BOOST_CONTAINER_FORCEINLINE void swap(small_vector &other)
 607    {  return this->base_type::swap(other);  }
 608 };
 609
 610 }}
 611
 612 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 613 /*
 614 namespace boost {
 615
 616 //!has_trivial_destructor_after_move<> == true_type
 617 //!specialization for optimizations
 618 template <class T, class Allocator>
 619 struct has_trivial_destructor_after_move<boost::container::vector<T, Allocator> >
 620 {
 621    typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer;
 622    static const bool value = ::boost::has_trivial_destructor_after_move<Allocator>::value &&
 623                              ::boost::has_trivial_destructor_after_move<pointer>::value;
 624 };
 625
 626 }
 627 */
 628 #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 629
 630 #include <boost/container/detail/config_end.hpp>
 631
 632 #endif //   #ifndef  BOOST_CONTAINER_CONTAINER_SMALL_VECTOR_HPP