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