1 ////////////////////////////////////////////////////////////////////////////// 2 // 3 // (C) Copyright Ion Gaztanaga 2005-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_VECTOR_HPP 12 #define BOOST_CONTAINER_CONTAINER_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/allocator_traits.hpp> 28 #include <boost/container/new_allocator.hpp> //new_allocator 29 #include <boost/container/throw_exception.hpp> 30 #include <boost/container/options.hpp> 31 // container detail 32 #include <boost/container/detail/advanced_insert_int.hpp> 33 #include <boost/container/detail/algorithm.hpp> //equal() 34 #include <boost/container/detail/alloc_helpers.hpp> 35 #include <boost/container/detail/allocation_type.hpp> 36 #include <boost/container/detail/copy_move_algo.hpp> 37 #include <boost/container/detail/destroyers.hpp> 38 #include <boost/container/detail/iterator.hpp> 39 #include <boost/container/detail/iterators.hpp> 40 #include <boost/move/detail/iterator_to_raw_pointer.hpp> 41 #include <boost/container/detail/mpl.hpp> 42 #include <boost/container/detail/next_capacity.hpp> 43 #include <boost/container/detail/value_functors.hpp> 44 #include <boost/move/detail/to_raw_pointer.hpp> 45 #include <boost/container/detail/type_traits.hpp> 46 #include <boost/container/detail/version_type.hpp> 47 // intrusive 48 #include <boost/intrusive/pointer_traits.hpp> 49 // move 50 #include <boost/move/adl_move_swap.hpp> 51 #include <boost/move/iterator.hpp> 52 #include <boost/move/traits.hpp> 53 #include <boost/move/utility_core.hpp> 54 // move/detail 55 #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 56 #include <boost/move/detail/fwd_macros.hpp> 57 #endif 58 #include <boost/move/detail/move_helpers.hpp> 59 // move/algo 60 #include <boost/move/algo/adaptive_merge.hpp> 61 #include <boost/move/algo/unique.hpp> 62 #include <boost/move/algo/predicate.hpp> 63 #include <boost/move/algo/detail/set_difference.hpp> 64 // other 65 #include <boost/core/no_exceptions_support.hpp> 66 #include <boost/assert.hpp> 67 #include <boost/cstdint.hpp> 68 69 //std 70 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 71 #include <initializer_list> //for std::initializer_list 72 #endif 73 74 namespace boost { 75 namespace container { 76 77 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 78 79 80 template <class Pointer, bool IsConst> 81 class vec_iterator 82 { 83 public: 84 typedef std::random_access_iterator_tag iterator_category; 85 typedef typename boost::intrusive::pointer_traits<Pointer>::element_type value_type; 86 typedef typename boost::intrusive::pointer_traits<Pointer>::difference_type difference_type; 87 typedef typename dtl::if_c 88 < IsConst 89 , typename boost::intrusive::pointer_traits<Pointer>::template 90 rebind_pointer<const value_type>::type 91 , Pointer 92 >::type pointer; 93 typedef typename boost::intrusive::pointer_traits<pointer> ptr_traits; 94 typedef typename ptr_traits::reference reference; 95 96 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 97 private: 98 Pointer m_ptr; 99 100 class nat 101 { 102 public: 103 Pointer get_ptr() const 104 { return Pointer(); } 105 }; 106 typedef typename dtl::if_c< IsConst 107 , vec_iterator<Pointer, false> 108 , nat>::type nonconst_iterator; 109 110 public: 111 BOOST_CONTAINER_FORCEINLINE const Pointer &get_ptr() const BOOST_NOEXCEPT_OR_NOTHROW 112 { return m_ptr; } 113 114 BOOST_CONTAINER_FORCEINLINE Pointer &get_ptr() BOOST_NOEXCEPT_OR_NOTHROW 115 { return m_ptr; } 116 117 BOOST_CONTAINER_FORCEINLINE explicit vec_iterator(Pointer ptr) BOOST_NOEXCEPT_OR_NOTHROW 118 : m_ptr(ptr) 119 {} 120 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 121 122 public: 123 124 //Constructors 125 BOOST_CONTAINER_FORCEINLINE vec_iterator() BOOST_NOEXCEPT_OR_NOTHROW 126 : m_ptr() //Value initialization to achieve "null iterators" (N3644) 127 {} 128 129 BOOST_CONTAINER_FORCEINLINE vec_iterator(const vec_iterator& other) BOOST_NOEXCEPT_OR_NOTHROW 130 : m_ptr(other.get_ptr()) 131 {} 132 133 BOOST_CONTAINER_FORCEINLINE vec_iterator(const nonconst_iterator &other) BOOST_NOEXCEPT_OR_NOTHROW 134 : m_ptr(other.get_ptr()) 135 {} 136 137 BOOST_CONTAINER_FORCEINLINE vec_iterator & operator=(const vec_iterator& other) BOOST_NOEXCEPT_OR_NOTHROW 138 { m_ptr = other.get_ptr(); return *this; } 139 140 //Pointer like operators 141 BOOST_CONTAINER_FORCEINLINE reference operator*() const BOOST_NOEXCEPT_OR_NOTHROW 142 { BOOST_ASSERT(!!m_ptr); return *m_ptr; } 143 144 BOOST_CONTAINER_FORCEINLINE pointer operator->() const BOOST_NOEXCEPT_OR_NOTHROW 145 { return m_ptr; } 146 147 BOOST_CONTAINER_FORCEINLINE reference operator[](difference_type off) const BOOST_NOEXCEPT_OR_NOTHROW 148 { BOOST_ASSERT(!!m_ptr); return m_ptr[off]; } 149 150 //Increment / Decrement 151 BOOST_CONTAINER_FORCEINLINE vec_iterator& operator++() BOOST_NOEXCEPT_OR_NOTHROW 152 { BOOST_ASSERT(!!m_ptr); ++m_ptr; return *this; } 153 154 BOOST_CONTAINER_FORCEINLINE vec_iterator operator++(int) BOOST_NOEXCEPT_OR_NOTHROW 155 { BOOST_ASSERT(!!m_ptr); return vec_iterator(m_ptr++); } 156 157 BOOST_CONTAINER_FORCEINLINE vec_iterator& operator--() BOOST_NOEXCEPT_OR_NOTHROW 158 { BOOST_ASSERT(!!m_ptr); --m_ptr; return *this; } 159 160 BOOST_CONTAINER_FORCEINLINE vec_iterator operator--(int) BOOST_NOEXCEPT_OR_NOTHROW 161 { BOOST_ASSERT(!!m_ptr); return vec_iterator(m_ptr--); } 162 163 //Arithmetic 164 BOOST_CONTAINER_FORCEINLINE vec_iterator& operator+=(difference_type off) BOOST_NOEXCEPT_OR_NOTHROW 165 { BOOST_ASSERT(m_ptr || !off); m_ptr += off; return *this; } 166 167 BOOST_CONTAINER_FORCEINLINE vec_iterator& operator-=(difference_type off) BOOST_NOEXCEPT_OR_NOTHROW 168 { BOOST_ASSERT(m_ptr || !off); m_ptr -= off; return *this; } 169 170 BOOST_CONTAINER_FORCEINLINE friend vec_iterator operator+(const vec_iterator &x, difference_type off) BOOST_NOEXCEPT_OR_NOTHROW 171 { BOOST_ASSERT(x.m_ptr || !off); return vec_iterator(x.m_ptr+off); } 172 173 BOOST_CONTAINER_FORCEINLINE friend vec_iterator operator+(difference_type off, vec_iterator right) BOOST_NOEXCEPT_OR_NOTHROW 174 { BOOST_ASSERT(right.m_ptr || !off); right.m_ptr += off; return right; } 175 176 BOOST_CONTAINER_FORCEINLINE friend vec_iterator operator-(vec_iterator left, difference_type off) BOOST_NOEXCEPT_OR_NOTHROW 177 { BOOST_ASSERT(left.m_ptr || !off); left.m_ptr -= off; return left; } 178 179 BOOST_CONTAINER_FORCEINLINE friend difference_type operator-(const vec_iterator &left, const vec_iterator& right) BOOST_NOEXCEPT_OR_NOTHROW 180 { return left.m_ptr - right.m_ptr; } 181 182 //Comparison operators 183 BOOST_CONTAINER_FORCEINLINE friend bool operator== (const vec_iterator& l, const vec_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW 184 { return l.m_ptr == r.m_ptr; } 185 186 BOOST_CONTAINER_FORCEINLINE friend bool operator!= (const vec_iterator& l, const vec_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW 187 { return l.m_ptr != r.m_ptr; } 188 189 BOOST_CONTAINER_FORCEINLINE friend bool operator< (const vec_iterator& l, const vec_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW 190 { return l.m_ptr < r.m_ptr; } 191 192 BOOST_CONTAINER_FORCEINLINE friend bool operator<= (const vec_iterator& l, const vec_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW 193 { return l.m_ptr <= r.m_ptr; } 194 195 BOOST_CONTAINER_FORCEINLINE friend bool operator> (const vec_iterator& l, const vec_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW 196 { return l.m_ptr > r.m_ptr; } 197 198 BOOST_CONTAINER_FORCEINLINE friend bool operator>= (const vec_iterator& l, const vec_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW 199 { return l.m_ptr >= r.m_ptr; } 200 }; 201 202 template<class BiDirPosConstIt, class BiDirValueIt> 203 struct vector_insert_ordered_cursor 204 { 205 typedef typename iterator_traits<BiDirPosConstIt>::value_type size_type; 206 typedef typename iterator_traits<BiDirValueIt>::reference reference; 207 208 BOOST_CONTAINER_FORCEINLINE vector_insert_ordered_cursor(BiDirPosConstIt posit, BiDirValueIt valueit) 209 : last_position_it(posit), last_value_it(valueit) 210 {} 211 212 void operator --() 213 { 214 --last_value_it; 215 --last_position_it; 216 while(this->get_pos() == size_type(-1)){ 217 --last_value_it; 218 --last_position_it; 219 } 220 } 221 222 BOOST_CONTAINER_FORCEINLINE size_type get_pos() const 223 { return *last_position_it; } 224 225 BOOST_CONTAINER_FORCEINLINE reference get_val() 226 { return *last_value_it; } 227 228 BiDirPosConstIt last_position_it; 229 BiDirValueIt last_value_it; 230 }; 231 232 struct initial_capacity_t{}; 233 234 template<class Pointer, bool IsConst> 235 BOOST_CONTAINER_FORCEINLINE const Pointer &vector_iterator_get_ptr(const vec_iterator<Pointer, IsConst> &it) BOOST_NOEXCEPT_OR_NOTHROW 236 { return it.get_ptr(); } 237 238 template<class Pointer, bool IsConst> 239 BOOST_CONTAINER_FORCEINLINE Pointer &get_ptr(vec_iterator<Pointer, IsConst> &it) BOOST_NOEXCEPT_OR_NOTHROW 240 { return it.get_ptr(); } 241 242 struct vector_uninitialized_size_t {}; 243 static const vector_uninitialized_size_t vector_uninitialized_size = vector_uninitialized_size_t(); 244 245 template <class T> 246 struct vector_value_traits_base 247 { 248 static const bool trivial_dctr = dtl::is_trivially_destructible<T>::value; 249 static const bool trivial_dctr_after_move = has_trivial_destructor_after_move<T>::value; 250 }; 251 252 template <class Allocator> 253 struct vector_value_traits 254 : public vector_value_traits_base<typename Allocator::value_type> 255 { 256 typedef vector_value_traits_base<typename Allocator::value_type> base_t; 257 //This is the anti-exception array destructor 258 //to deallocate values already constructed 259 typedef typename dtl::if_c 260 <base_t::trivial_dctr 261 ,dtl::null_scoped_destructor_n<Allocator> 262 ,dtl::scoped_destructor_n<Allocator> 263 >::type ArrayDestructor; 264 //This is the anti-exception array deallocator 265 typedef dtl::scoped_array_deallocator<Allocator> ArrayDeallocator; 266 }; 267 268 //!This struct deallocates and allocated memory 269 template < class Allocator 270 , class StoredSizeType 271 , class AllocatorVersion = typename dtl::version<Allocator>::type 272 > 273 struct vector_alloc_holder 274 : public Allocator 275 { 276 private: 277 BOOST_MOVABLE_BUT_NOT_COPYABLE(vector_alloc_holder) 278 279 public: 280 typedef Allocator allocator_type; 281 typedef StoredSizeType stored_size_type; 282 typedef boost::container::allocator_traits<allocator_type> allocator_traits_type; 283 typedef typename allocator_traits_type::pointer pointer; 284 typedef typename allocator_traits_type::size_type size_type; 285 typedef typename allocator_traits_type::value_type value_type; 286 287 BOOST_CONTAINER_FORCEINLINE static bool is_propagable_from(const allocator_type &from_alloc, pointer p, const allocator_type &to_alloc, bool const propagate_allocator) 288 { 289 (void)propagate_allocator; (void)p; (void)to_alloc; (void)from_alloc; 290 const bool all_storage_propagable = !allocator_traits_type::is_partially_propagable::value || 291 !allocator_traits_type::storage_is_unpropagable(from_alloc, p); 292 return all_storage_propagable && (propagate_allocator || allocator_traits_type::equal(from_alloc, to_alloc)); 293 } 294 295 BOOST_CONTAINER_FORCEINLINE static bool are_swap_propagable(const allocator_type &l_a, pointer l_p, const allocator_type &r_a, pointer r_p, bool const propagate_allocator) 296 { 297 (void)propagate_allocator; (void)l_p; (void)r_p; (void)l_a; (void)r_a; 298 const bool all_storage_propagable = !allocator_traits_type::is_partially_propagable::value || 299 !(allocator_traits_type::storage_is_unpropagable(l_a, l_p) || allocator_traits_type::storage_is_unpropagable(r_a, r_p)); 300 return all_storage_propagable && (propagate_allocator || allocator_traits_type::equal(l_a, r_a)); 301 } 302 303 //Constructor, does not throw 304 vector_alloc_holder() 305 BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<allocator_type>::value) 306 : allocator_type(), m_start(), m_size(), m_capacity() 307 {} 308 309 //Constructor, does not throw 310 template<class AllocConvertible> 311 explicit vector_alloc_holder(BOOST_FWD_REF(AllocConvertible) a) BOOST_NOEXCEPT_OR_NOTHROW 312 : allocator_type(boost::forward<AllocConvertible>(a)), m_start(), m_size(), m_capacity() 313 {} 314 315 //Constructor, does not throw 316 template<class AllocConvertible, class SizeType> 317 vector_alloc_holder(vector_uninitialized_size_t, BOOST_FWD_REF(AllocConvertible) a, SizeType initial_size) 318 : allocator_type(boost::forward<AllocConvertible>(a)) 319 , m_start() 320 //Size is initialized here so vector should only call uninitialized_xxx after this 321 , m_size(static_cast<stored_size_type>(initial_size)) 322 , m_capacity() 323 { 324 if (initial_size > size_type(-1)){ 325 boost::container::throw_length_error("get_next_capacity, allocator's max size reached"); 326 } 327 else if(initial_size){ 328 pointer reuse = pointer(); 329 size_type final_cap = static_cast<size_type>(initial_size); 330 m_start = this->allocation_command(allocate_new, final_cap, final_cap, reuse); 331 this->set_stored_capacity(final_cap); 332 } 333 } 334 335 //Constructor, does not throw 336 template<class SizeType> 337 vector_alloc_holder(vector_uninitialized_size_t, SizeType initial_size) 338 : allocator_type() 339 , m_start() 340 //Size is initialized here so vector should only call uninitialized_xxx after this 341 , m_size(static_cast<stored_size_type>(initial_size)) 342 , m_capacity() 343 { 344 if (initial_size > size_type(-1)){ 345 boost::container::throw_length_error("get_next_capacity, allocator's max size reached"); 346 } 347 else if(initial_size){ 348 pointer reuse = pointer(); 349 size_type final_cap = initial_size; 350 m_start = this->allocation_command(allocate_new, final_cap, final_cap, reuse); 351 this->set_stored_capacity(final_cap); 352 } 353 } 354 355 vector_alloc_holder(BOOST_RV_REF(vector_alloc_holder) holder) BOOST_NOEXCEPT_OR_NOTHROW 356 : allocator_type(BOOST_MOVE_BASE(allocator_type, holder)) 357 , m_start(holder.m_start) 358 , m_size(holder.m_size) 359 , m_capacity(holder.m_capacity) 360 { 361 holder.m_start = pointer(); 362 holder.m_size = holder.m_capacity = 0; 363 } 364 365 vector_alloc_holder(initial_capacity_t, pointer p, size_type n) 366 BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<allocator_type>::value) 367 : allocator_type() 368 , m_start(p) 369 , m_size() 370 //n is guaranteed to fit into stored_size_type 371 , m_capacity(static_cast<stored_size_type>(n)) 372 {} 373 374 template<class AllocFwd> 375 vector_alloc_holder(initial_capacity_t, pointer p, size_type n, BOOST_FWD_REF(AllocFwd) a) 376 : allocator_type(::boost::forward<AllocFwd>(a)) 377 , m_start(p) 378 , m_size() 379 , m_capacity(n) 380 {} 381 382 BOOST_CONTAINER_FORCEINLINE ~vector_alloc_holder() BOOST_NOEXCEPT_OR_NOTHROW 383 { 384 if(this->m_capacity){ 385 this->deallocate(this->m_start, this->m_capacity); 386 } 387 } 388 389 BOOST_CONTAINER_FORCEINLINE void set_stored_size(size_type s) BOOST_NOEXCEPT_OR_NOTHROW 390 { this->m_size = static_cast<stored_size_type>(s); } 391 392 BOOST_CONTAINER_FORCEINLINE void dec_stored_size(size_type s) BOOST_NOEXCEPT_OR_NOTHROW 393 { this->m_size -= static_cast<stored_size_type>(s); } 394 395 BOOST_CONTAINER_FORCEINLINE void inc_stored_size(size_type s) BOOST_NOEXCEPT_OR_NOTHROW 396 { this->m_size += static_cast<stored_size_type>(s); } 397 398 BOOST_CONTAINER_FORCEINLINE void set_stored_capacity(size_type c) BOOST_NOEXCEPT_OR_NOTHROW 399 { this->m_capacity = static_cast<stored_size_type>(c); } 400 401 BOOST_CONTAINER_FORCEINLINE pointer allocation_command(boost::container::allocation_type command, 402 size_type limit_size, size_type &prefer_in_recvd_out_size, pointer &reuse) 403 { 404 typedef typename dtl::version<allocator_type>::type alloc_version; 405 return this->priv_allocation_command(alloc_version(), command, limit_size, prefer_in_recvd_out_size, reuse); 406 } 407 408 BOOST_CONTAINER_FORCEINLINE pointer allocate(size_type n) 409 { 410 const size_type max_alloc = allocator_traits_type::max_size(this->alloc()); 411 const size_type max = max_alloc <= stored_size_type(-1) ? max_alloc : stored_size_type(-1); 412 if ( max < n ) 413 boost::container::throw_length_error("get_next_capacity, allocator's max size reached"); 414 415 return allocator_traits_type::allocate(this->alloc(), n); 416 } 417 418 BOOST_CONTAINER_FORCEINLINE void deallocate(const pointer &p, size_type n) 419 { 420 allocator_traits_type::deallocate(this->alloc(), p, n); 421 } 422 423 bool try_expand_fwd(size_type at_least) 424 { 425 //There is not enough memory, try to expand the old one 426 const size_type new_cap = this->capacity() + at_least; 427 size_type real_cap = new_cap; 428 pointer reuse = this->start(); 429 bool const success = !!this->allocation_command(expand_fwd, new_cap, real_cap, reuse); 430 //Check for forward expansion 431 if(success){ 432 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS 433 ++this->num_expand_fwd; 434 #endif 435 this->capacity(real_cap); 436 } 437 return success; 438 } 439 440 template<class GrowthFactorType> 441 size_type next_capacity(size_type additional_objects) const 442 { 443 BOOST_ASSERT(additional_objects > size_type(this->m_capacity - this->m_size)); 444 size_type max = allocator_traits_type::max_size(this->alloc()); 445 (clamp_by_stored_size_type<size_type>)(max, stored_size_type()); 446 const size_type remaining_cap = max - size_type(this->m_capacity); 447 const size_type min_additional_cap = additional_objects - size_type(this->m_capacity - this->m_size); 448 449 if ( remaining_cap < min_additional_cap ) 450 boost::container::throw_length_error("get_next_capacity, allocator's max size reached"); 451 452 return GrowthFactorType()( size_type(this->m_capacity), min_additional_cap, max); 453 } 454 455 pointer m_start; 456 stored_size_type m_size; 457 stored_size_type m_capacity; 458 459 void swap_resources(vector_alloc_holder &x) BOOST_NOEXCEPT_OR_NOTHROW 460 { 461 boost::adl_move_swap(this->m_start, x.m_start); 462 boost::adl_move_swap(this->m_size, x.m_size); 463 boost::adl_move_swap(this->m_capacity, x.m_capacity); 464 } 465 466 void steal_resources(vector_alloc_holder &x) BOOST_NOEXCEPT_OR_NOTHROW 467 { 468 this->m_start = x.m_start; 469 this->m_size = x.m_size; 470 this->m_capacity = x.m_capacity; 471 x.m_start = pointer(); 472 x.m_size = x.m_capacity = 0; 473 } 474 475 BOOST_CONTAINER_FORCEINLINE allocator_type &alloc() BOOST_NOEXCEPT_OR_NOTHROW 476 { return *this; } 477 478 BOOST_CONTAINER_FORCEINLINE const allocator_type &alloc() const BOOST_NOEXCEPT_OR_NOTHROW 479 { return *this; } 480 481 BOOST_CONTAINER_FORCEINLINE const pointer &start() const BOOST_NOEXCEPT_OR_NOTHROW 482 { return m_start; } 483 BOOST_CONTAINER_FORCEINLINE size_type capacity() const BOOST_NOEXCEPT_OR_NOTHROW 484 { return m_capacity; } 485 BOOST_CONTAINER_FORCEINLINE void start(const pointer &p) BOOST_NOEXCEPT_OR_NOTHROW 486 { m_start = p; } 487 BOOST_CONTAINER_FORCEINLINE void capacity(const size_type &c) BOOST_NOEXCEPT_OR_NOTHROW 488 { BOOST_ASSERT( c <= stored_size_type(-1)); this->set_stored_capacity(c); } 489 490 static BOOST_CONTAINER_FORCEINLINE void on_capacity_overflow() 491 { } 492 493 private: 494 void priv_first_allocation(size_type cap) 495 { 496 if(cap){ 497 pointer reuse = pointer(); 498 m_start = this->allocation_command(allocate_new, cap, cap, reuse); 499 m_capacity = cap; 500 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS 501 ++this->num_alloc; 502 #endif 503 } 504 } 505 506 BOOST_CONTAINER_FORCEINLINE pointer priv_allocation_command(version_1, boost::container::allocation_type command, 507 size_type limit_size, 508 size_type &prefer_in_recvd_out_size, 509 pointer &reuse) 510 { 511 (void)command; 512 BOOST_ASSERT( (command & allocate_new)); 513 BOOST_ASSERT(!(command & nothrow_allocation)); 514 //First detect overflow on smaller stored_size_types 515 if (limit_size > stored_size_type(-1)){ 516 boost::container::throw_length_error("get_next_capacity, allocator's max size reached"); 517 } 518 (clamp_by_stored_size_type<size_type>)(prefer_in_recvd_out_size, stored_size_type()); 519 pointer const p = this->allocate(prefer_in_recvd_out_size); 520 reuse = pointer(); 521 return p; 522 } 523 524 pointer priv_allocation_command(version_2, boost::container::allocation_type command, 525 size_type limit_size, 526 size_type &prefer_in_recvd_out_size, 527 pointer &reuse) 528 { 529 //First detect overflow on smaller stored_size_types 530 if (limit_size > stored_size_type(-1)){ 531 boost::container::throw_length_error("get_next_capacity, allocator's max size reached"); 532 } 533 (clamp_by_stored_size_type<size_type>)(prefer_in_recvd_out_size, stored_size_type()); 534 //Allocate memory 535 pointer p = this->alloc().allocation_command(command, limit_size, prefer_in_recvd_out_size, reuse); 536 //If after allocation prefer_in_recvd_out_size is not representable by stored_size_type, truncate it. 537 (clamp_by_stored_size_type<size_type>)(prefer_in_recvd_out_size, stored_size_type()); 538 return p; 539 } 540 }; 541 542 //!This struct deallocates and allocated memory 543 template <class Allocator, class StoredSizeType> 544 struct vector_alloc_holder<Allocator, StoredSizeType, version_0> 545 : public Allocator 546 { 547 private: 548 BOOST_MOVABLE_BUT_NOT_COPYABLE(vector_alloc_holder) 549 550 public: 551 typedef Allocator allocator_type; 552 typedef boost::container:: 553 allocator_traits<allocator_type> allocator_traits_type; 554 typedef typename allocator_traits_type::pointer pointer; 555 typedef typename allocator_traits_type::size_type size_type; 556 typedef typename allocator_traits_type::value_type value_type; 557 typedef StoredSizeType stored_size_type; 558 559 template <class OtherAllocator, class OtherStoredSizeType, class OtherAllocatorVersion> 560 friend struct vector_alloc_holder; 561 562 //Constructor, does not throw 563 vector_alloc_holder() 564 BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<allocator_type>::value) 565 : allocator_type(), m_size() 566 {} 567 568 //Constructor, does not throw 569 template<class AllocConvertible> 570 explicit vector_alloc_holder(BOOST_FWD_REF(AllocConvertible) a) BOOST_NOEXCEPT_OR_NOTHROW 571 : allocator_type(boost::forward<AllocConvertible>(a)), m_size() 572 {} 573 574 //Constructor, does not throw 575 template<class AllocConvertible> 576 vector_alloc_holder(vector_uninitialized_size_t, BOOST_FWD_REF(AllocConvertible) a, size_type initial_size) 577 : allocator_type(boost::forward<AllocConvertible>(a)) 578 , m_size(initial_size) //Size is initialized here... 579 { 580 //... and capacity here, so vector, must call uninitialized_xxx in the derived constructor 581 this->priv_first_allocation(initial_size); 582 } 583 584 //Constructor, does not throw 585 vector_alloc_holder(vector_uninitialized_size_t, size_type initial_size) 586 : allocator_type() 587 , m_size(initial_size) //Size is initialized here... 588 { 589 //... and capacity here, so vector, must call uninitialized_xxx in the derived constructor 590 this->priv_first_allocation(initial_size); 591 } 592 593 vector_alloc_holder(BOOST_RV_REF(vector_alloc_holder) holder) 594 : allocator_type(BOOST_MOVE_BASE(allocator_type, holder)) 595 , m_size(holder.m_size) //Size is initialized here so vector should only call uninitialized_xxx after this 596 { 597 ::boost::container::uninitialized_move_alloc_n 598 (this->alloc(), boost::movelib::to_raw_pointer(holder.start()), m_size, boost::movelib::to_raw_pointer(this->start())); 599 ::boost::container::destroy_alloc_n 600 (this->alloc(), boost::movelib::to_raw_pointer(holder.start()), m_size); 601 holder.m_size = 0; 602 } 603 604 template<class OtherAllocator, class OtherStoredSizeType, class OtherAllocatorVersion> 605 vector_alloc_holder(BOOST_RV_REF_BEG vector_alloc_holder<OtherAllocator, OtherStoredSizeType, OtherAllocatorVersion> BOOST_RV_REF_END holder) 606 : allocator_type() 607 , m_size(holder.m_size) //Initialize it to m_size as first_allocation can only succeed or abort 608 { 609 //Different allocator type so we must check we have enough storage 610 const size_type n = holder.m_size; 611 this->priv_first_allocation(n); 612 ::boost::container::uninitialized_move_alloc_n 613 (this->alloc(), boost::movelib::to_raw_pointer(holder.start()), n, boost::movelib::to_raw_pointer(this->start())); 614 } 615 616 static BOOST_CONTAINER_FORCEINLINE void on_capacity_overflow() 617 { allocator_type::on_capacity_overflow(); } 618 619 BOOST_CONTAINER_FORCEINLINE void set_stored_size(size_type s) BOOST_NOEXCEPT_OR_NOTHROW 620 { this->m_size = static_cast<stored_size_type>(s); } 621 622 BOOST_CONTAINER_FORCEINLINE void dec_stored_size(size_type s) BOOST_NOEXCEPT_OR_NOTHROW 623 { this->m_size -= static_cast<stored_size_type>(s); } 624 625 BOOST_CONTAINER_FORCEINLINE void inc_stored_size(size_type s) BOOST_NOEXCEPT_OR_NOTHROW 626 { this->m_size += static_cast<stored_size_type>(s); } 627 628 BOOST_CONTAINER_FORCEINLINE void priv_first_allocation(size_type cap) 629 { 630 if(cap > allocator_type::internal_capacity){ 631 on_capacity_overflow(); 632 } 633 } 634 635 BOOST_CONTAINER_FORCEINLINE void deep_swap(vector_alloc_holder &x) 636 { 637 this->priv_deep_swap(x); 638 } 639 640 template<class OtherAllocator, class OtherStoredSizeType, class OtherAllocatorVersion> 641 void deep_swap(vector_alloc_holder<OtherAllocator, OtherStoredSizeType, OtherAllocatorVersion> &x) 642 { 643 typedef typename real_allocator<value_type, OtherAllocator>::type other_allocator_type; 644 if(this->m_size > other_allocator_type::internal_capacity || x.m_size > allocator_type::internal_capacity){ 645 on_capacity_overflow(); 646 } 647 this->priv_deep_swap(x); 648 } 649 650 BOOST_CONTAINER_FORCEINLINE void swap_resources(vector_alloc_holder &) BOOST_NOEXCEPT_OR_NOTHROW 651 { //Containers with version 0 allocators can't be moved without moving elements one by one 652 on_capacity_overflow(); 653 } 654 655 656 BOOST_CONTAINER_FORCEINLINE void steal_resources(vector_alloc_holder &) 657 { //Containers with version 0 allocators can't be moved without moving elements one by one 658 on_capacity_overflow(); 659 } 660 661 BOOST_CONTAINER_FORCEINLINE allocator_type &alloc() BOOST_NOEXCEPT_OR_NOTHROW 662 { return *this; } 663 664 BOOST_CONTAINER_FORCEINLINE const allocator_type &alloc() const BOOST_NOEXCEPT_OR_NOTHROW 665 { return *this; } 666 667 BOOST_CONTAINER_FORCEINLINE bool try_expand_fwd(size_type at_least) 668 { return !at_least; } 669 670 BOOST_CONTAINER_FORCEINLINE pointer start() const BOOST_NOEXCEPT_OR_NOTHROW 671 { return allocator_type::internal_storage(); } 672 673 BOOST_CONTAINER_FORCEINLINE size_type capacity() const BOOST_NOEXCEPT_OR_NOTHROW 674 { return allocator_type::internal_capacity; } 675 676 stored_size_type m_size; 677 678 private: 679 680 template<class OtherAllocator, class OtherStoredSizeType, class OtherAllocatorVersion> 681 void priv_deep_swap(vector_alloc_holder<OtherAllocator, OtherStoredSizeType, OtherAllocatorVersion> &x) 682 { 683 const size_type MaxTmpStorage = sizeof(value_type)*allocator_type::internal_capacity; 684 value_type *const first_this = boost::movelib::to_raw_pointer(this->start()); 685 value_type *const first_x = boost::movelib::to_raw_pointer(x.start()); 686 687 if(this->m_size < x.m_size){ 688 boost::container::deep_swap_alloc_n<MaxTmpStorage>(this->alloc(), first_this, this->m_size, first_x, x.m_size); 689 } 690 else{ 691 boost::container::deep_swap_alloc_n<MaxTmpStorage>(this->alloc(), first_x, x.m_size, first_this, this->m_size); 692 } 693 boost::adl_move_swap(this->m_size, x.m_size); 694 } 695 }; 696 697 struct growth_factor_60; 698 699 template<class Options, class AllocatorSizeType> 700 struct get_vector_opt 701 { 702 typedef vector_opt< typename default_if_void<typename Options::growth_factor_type, growth_factor_60>::type 703 , typename default_if_void<typename Options::stored_size_type, AllocatorSizeType>::type 704 > type; 705 }; 706 707 template<class AllocatorSizeType> 708 struct get_vector_opt<void, AllocatorSizeType> 709 { 710 typedef vector_opt<growth_factor_60, AllocatorSizeType> type; 711 }; 712 713 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 714 715 //! A vector is a sequence that supports random access to elements, constant 716 //! time insertion and removal of elements at the end, and linear time insertion 717 //! and removal of elements at the beginning or in the middle. The number of 718 //! elements in a vector may vary dynamically; memory management is automatic. 719 //! 720 //! \tparam T The type of object that is stored in the vector 721 //! \tparam A The allocator used for all internal memory management, use void 722 //! for the default allocator 723 //! \tparam Options A type produced from \c boost::container::vector_options. 724 template <class T, class A BOOST_CONTAINER_DOCONLY(= void), class Options BOOST_CONTAINER_DOCONLY(= void) > 725 class vector 726 { 727 public: 728 ////////////////////////////////////////////// 729 // 730 // types 731 // 732 ////////////////////////////////////////////// 733 typedef T value_type; 734 typedef BOOST_CONTAINER_IMPDEF 735 (typename real_allocator<T BOOST_MOVE_I A>::type) allocator_type; 736 typedef ::boost::container::allocator_traits<allocator_type> allocator_traits_t; 737 typedef typename allocator_traits<allocator_type>::pointer pointer; 738 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 739 typedef typename allocator_traits<allocator_type>::reference reference; 740 typedef typename allocator_traits<allocator_type>::const_reference const_reference; 741 typedef typename allocator_traits<allocator_type>::size_type size_type; 742 typedef typename allocator_traits<allocator_type>::difference_type difference_type; 743 typedef allocator_type stored_allocator_type; 744 typedef BOOST_CONTAINER_IMPDEF(vec_iterator<pointer BOOST_MOVE_I false>) iterator; 745 typedef BOOST_CONTAINER_IMPDEF(vec_iterator<pointer BOOST_MOVE_I true >) const_iterator; 746 typedef BOOST_CONTAINER_IMPDEF(boost::container::reverse_iterator<iterator>) reverse_iterator; 747 typedef BOOST_CONTAINER_IMPDEF(boost::container::reverse_iterator<const_iterator>) const_reverse_iterator; 748 749 private: 750 751 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 752 typedef typename boost::container:: 753 allocator_traits<allocator_type>::size_type alloc_size_type; 754 typedef typename get_vector_opt<Options, alloc_size_type>::type options_type; 755 typedef typename options_type::growth_factor_type growth_factor_type; 756 typedef typename options_type::stored_size_type stored_size_type; 757 typedef value_less<T> value_less_t; 758 759 //If provided the stored_size option must specify a type that is equal or a type that is smaller. 760 BOOST_STATIC_ASSERT( (sizeof(stored_size_type) < sizeof(alloc_size_type) || 761 dtl::is_same<stored_size_type, alloc_size_type>::value) ); 762 763 typedef typename dtl::version<allocator_type>::type alloc_version; 764 typedef boost::container::vector_alloc_holder 765 <allocator_type, stored_size_type> alloc_holder_t; 766 767 alloc_holder_t m_holder; 768 769 typedef allocator_traits<allocator_type> allocator_traits_type; 770 template <class U, class UA, class UOptions> 771 friend class vector; 772 773 774 protected: 775 BOOST_CONTAINER_FORCEINLINE 776 static bool is_propagable_from(const allocator_type &from_alloc, pointer p, const allocator_type &to_alloc, bool const propagate_allocator) 777 { return alloc_holder_t::is_propagable_from(from_alloc, p, to_alloc, propagate_allocator); } 778 779 BOOST_CONTAINER_FORCEINLINE 780 static bool are_swap_propagable( const allocator_type &l_a, pointer l_p 781 , const allocator_type &r_a, pointer r_p, bool const propagate_allocator) 782 { return alloc_holder_t::are_swap_propagable(l_a, l_p, r_a, r_p, propagate_allocator); } 783 784 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 785 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 786 private: 787 BOOST_COPYABLE_AND_MOVABLE(vector) 788 typedef vector_value_traits<allocator_type> value_traits; 789 typedef constant_iterator<T, difference_type> cvalue_iterator; 790 791 protected: 792 793 BOOST_CONTAINER_FORCEINLINE void steal_resources(vector &x) 794 { return this->m_holder.steal_resources(x.m_holder); } 795 796 template<class AllocFwd> 797 BOOST_CONTAINER_FORCEINLINE vector(initial_capacity_t, pointer initial_memory, size_type capacity, BOOST_FWD_REF(AllocFwd) a) 798 : m_holder(initial_capacity_t(), initial_memory, capacity, ::boost::forward<AllocFwd>(a)) 799 {} 800 801 BOOST_CONTAINER_FORCEINLINE vector(initial_capacity_t, pointer initial_memory, size_type capacity) 802 : m_holder(initial_capacity_t(), initial_memory, capacity) 803 {} 804 805 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 806 807 public: 808 ////////////////////////////////////////////// 809 // 810 // construct/copy/destroy 811 // 812 ////////////////////////////////////////////// 813 814 //! <b>Effects</b>: Constructs a vector taking the allocator as parameter. 815 //! 816 //! <b>Throws</b>: Nothing. 817 //! 818 //! <b>Complexity</b>: Constant. 819 vector() BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<allocator_type>::value) 820 : m_holder() 821 {} 822 823 //! <b>Effects</b>: Constructs a vector taking the allocator as parameter. 824 //! 825 //! <b>Throws</b>: Nothing 826 //! 827 //! <b>Complexity</b>: Constant. 828 explicit vector(const allocator_type& a) BOOST_NOEXCEPT_OR_NOTHROW 829 : m_holder(a) 830 {} 831 832 //! <b>Effects</b>: Constructs a vector and inserts n value initialized values. 833 //! 834 //! <b>Throws</b>: If allocator_type's allocation 835 //! throws or T's value initialization throws. 836 //! 837 //! <b>Complexity</b>: Linear to n. 838 explicit vector(size_type n) 839 : m_holder(vector_uninitialized_size, n) 840 { 841 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS 842 this->num_alloc += n != 0; 843 #endif 844 boost::container::uninitialized_value_init_alloc_n 845 (this->m_holder.alloc(), n, this->priv_raw_begin()); 846 } 847 848 //! <b>Effects</b>: Constructs a vector that will use a copy of allocator a 849 //! and inserts n value initialized values. 850 //! 851 //! <b>Throws</b>: If allocator_type's allocation 852 //! throws or T's value initialization throws. 853 //! 854 //! <b>Complexity</b>: Linear to n. 855 explicit vector(size_type n, const allocator_type &a) 856 : m_holder(vector_uninitialized_size, a, n) 857 { 858 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS 859 this->num_alloc += n != 0; 860 #endif 861 boost::container::uninitialized_value_init_alloc_n 862 (this->m_holder.alloc(), n, this->priv_raw_begin()); 863 } 864 865 //! <b>Effects</b>: Constructs a vector that will use a copy of allocator a 866 //! and inserts n default initialized values. 867 //! 868 //! <b>Throws</b>: If allocator_type's allocation 869 //! throws or T's default initialization throws. 870 //! 871 //! <b>Complexity</b>: Linear to n. 872 //! 873 //! <b>Note</b>: Non-standard extension 874 vector(size_type n, default_init_t) 875 : m_holder(vector_uninitialized_size, n) 876 { 877 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS 878 this->num_alloc += n != 0; 879 #endif 880 boost::container::uninitialized_default_init_alloc_n 881 (this->m_holder.alloc(), n, this->priv_raw_begin()); 882 } 883 884 //! <b>Effects</b>: Constructs a vector that will use a copy of allocator a 885 //! and inserts n default initialized values. 886 //! 887 //! <b>Throws</b>: If allocator_type's allocation 888 //! throws or T's default initialization throws. 889 //! 890 //! <b>Complexity</b>: Linear to n. 891 //! 892 //! <b>Note</b>: Non-standard extension 893 vector(size_type n, default_init_t, const allocator_type &a) 894 : m_holder(vector_uninitialized_size, a, n) 895 { 896 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS 897 this->num_alloc += n != 0; 898 #endif 899 boost::container::uninitialized_default_init_alloc_n 900 (this->m_holder.alloc(), n, this->priv_raw_begin()); 901 } 902 903 //! <b>Effects</b>: Constructs a vector 904 //! and inserts n copies of value. 905 //! 906 //! <b>Throws</b>: If allocator_type's allocation 907 //! throws or T's copy constructor throws. 908 //! 909 //! <b>Complexity</b>: Linear to n. 910 vector(size_type n, const T& value) 911 : m_holder(vector_uninitialized_size, n) 912 { 913 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS 914 this->num_alloc += n != 0; 915 #endif 916 boost::container::uninitialized_fill_alloc_n 917 (this->m_holder.alloc(), value, n, this->priv_raw_begin()); 918 } 919 920 //! <b>Effects</b>: Constructs a vector that will use a copy of allocator a 921 //! and inserts n copies of value. 922 //! 923 //! <b>Throws</b>: If allocation 924 //! throws or T's copy constructor throws. 925 //! 926 //! <b>Complexity</b>: Linear to n. 927 vector(size_type n, const T& value, const allocator_type& a) 928 : m_holder(vector_uninitialized_size, a, n) 929 { 930 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS 931 this->num_alloc += n != 0; 932 #endif 933 boost::container::uninitialized_fill_alloc_n 934 (this->m_holder.alloc(), value, n, this->priv_raw_begin()); 935 } 936 937 //! <b>Effects</b>: Constructs a vector 938 //! and inserts a copy of the range [first, last) in the vector. 939 //! 940 //! <b>Throws</b>: If allocator_type's allocation 941 //! throws or T's constructor taking a dereferenced InIt throws. 942 //! 943 //! <b>Complexity</b>: Linear to the range [first, last). 944 // template <class InIt> 945 // vector(InIt first, InIt last 946 // BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_c 947 // < dtl::is_convertible<InIt BOOST_MOVE_I size_type>::value 948 // BOOST_MOVE_I dtl::nat >::type * = 0) 949 // ) -> vector<typename iterator_traits<InIt>::value_type, new_allocator<typename iterator_traits<InIt>::value_type>>; 950 template <class InIt> 951 vector(InIt first, InIt last 952 BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_c 953 < dtl::is_convertible<InIt BOOST_MOVE_I size_type>::value 954 BOOST_MOVE_I dtl::nat >::type * = 0) 955 ) 956 : m_holder() 957 { this->assign(first, last); } 958 959 //! <b>Effects</b>: Constructs a vector that will use a copy of allocator a 960 //! and inserts a copy of the range [first, last) in the vector. 961 //! 962 //! <b>Throws</b>: If allocator_type's allocation 963 //! throws or T's constructor taking a dereferenced InIt throws. 964 //! 965 //! <b>Complexity</b>: Linear to the range [first, last). 966 template <class InIt> 967 vector(InIt first, InIt last, const allocator_type& a 968 BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_c 969 < dtl::is_convertible<InIt BOOST_MOVE_I size_type>::value 970 BOOST_MOVE_I dtl::nat >::type * = 0) 971 ) 972 : m_holder(a) 973 { this->assign(first, last); } 974 975 //! <b>Effects</b>: Copy constructs a vector. 976 //! 977 //! <b>Postcondition</b>: x == *this. 978 //! 979 //! <b>Throws</b>: If allocator_type's allocation 980 //! throws or T's copy constructor throws. 981 //! 982 //! <b>Complexity</b>: Linear to the elements x contains. 983 vector(const vector &x) 984 : m_holder( vector_uninitialized_size 985 , allocator_traits_type::select_on_container_copy_construction(x.m_holder.alloc()) 986 , x.size()) 987 { 988 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS 989 this->num_alloc += x.size() != 0; 990 #endif 991 ::boost::container::uninitialized_copy_alloc_n 992 ( this->m_holder.alloc(), x.priv_raw_begin() 993 , x.size(), this->priv_raw_begin()); 994 } 995 996 //! <b>Effects</b>: Move constructor. Moves x's resources to *this. 997 //! 998 //! <b>Throws</b>: Nothing 999 //! 1000 //! <b>Complexity</b>: Constant. 1001 vector(BOOST_RV_REF(vector) x) BOOST_NOEXCEPT_OR_NOTHROW 1002 : m_holder(boost::move(x.m_holder)) 1003 { BOOST_STATIC_ASSERT((!allocator_traits_type::is_partially_propagable::value)); } 1004 1005 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 1006 //! <b>Effects</b>: Constructs a vector that will use a copy of allocator a 1007 //! and inserts a copy of the range [il.begin(), il.last()) in the vector 1008 //! 1009 //! <b>Throws</b>: If T's constructor taking a dereferenced initializer_list iterator throws. 1010 //! 1011 //! <b>Complexity</b>: Linear to the range [il.begin(), il.end()). 1012 vector(std::initializer_list<value_type> il, const allocator_type& a = allocator_type()) 1013 : m_holder(vector_uninitialized_size, a, il.size()) 1014 { 1015 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS 1016 this->num_alloc += il.size() != 0; 1017 #endif 1018 ::boost::container::uninitialized_copy_alloc_n_source 1019 ( this->m_holder.alloc(), il.begin() 1020 , static_cast<size_type>(il.size()), this->priv_raw_begin()); 1021 } 1022 #endif 1023 1024 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1025 1026 //! <b>Effects</b>: Move constructor. Moves x's resources to *this. 1027 //! 1028 //! <b>Throws</b>: If T's move constructor or allocation throws 1029 //! 1030 //! <b>Complexity</b>: Linear. 1031 //! 1032 //! <b>Note</b>: Non-standard extension to support static_vector 1033 template<class OtherA> 1034 vector(BOOST_RV_REF_BEG vector<T, OtherA, Options> BOOST_RV_REF_END x 1035 , typename dtl::enable_if_c 1036 < dtl::is_version<typename real_allocator<T, OtherA>::type, 0>::value>::type * = 0 1037 ) 1038 : m_holder(boost::move(x.m_holder)) 1039 {} 1040 1041 #endif //!defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1042 1043 //! <b>Effects</b>: Copy constructs a vector using the specified allocator. 1044 //! 1045 //! <b>Postcondition</b>: x == *this. 1046 //! 1047 //! <b>Throws</b>: If allocation 1048 //! throws or T's copy constructor throws. 1049 //! 1050 //! <b>Complexity</b>: Linear to the elements x contains. 1051 vector(const vector &x, const allocator_type &a) 1052 : m_holder(vector_uninitialized_size, a, x.size()) 1053 { 1054 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS 1055 this->num_alloc += x.size() != 0; 1056 #endif 1057 ::boost::container::uninitialized_copy_alloc_n_source 1058 ( this->m_holder.alloc(), x.priv_raw_begin() 1059 , x.size(), this->priv_raw_begin()); 1060 } 1061 1062 //! <b>Effects</b>: Move constructor using the specified allocator. 1063 //! Moves x's resources to *this if a == allocator_type(). 1064 //! Otherwise copies values from x to *this. 1065 //! 1066 //! <b>Throws</b>: If allocation or T's copy constructor throws. 1067 //! 1068 //! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise. 1069 vector(BOOST_RV_REF(vector) x, const allocator_type &a) 1070 : m_holder( vector_uninitialized_size, a 1071 //In this allocator move constructor the allocator won't be propagated --v 1072 , is_propagable_from(x.get_stored_allocator(), x.m_holder.start(), a, false) ? 0 : x.size() 1073 ) 1074 { 1075 //In this allocator move constructor the allocator won't be propagated ---v 1076 if(is_propagable_from(x.get_stored_allocator(), x.m_holder.start(), a, false)){ 1077 this->m_holder.steal_resources(x.m_holder); 1078 } 1079 else{ 1080 const size_type n = x.size(); 1081 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS 1082 this->num_alloc += n != 0; 1083 #endif 1084 ::boost::container::uninitialized_move_alloc_n_source 1085 ( this->m_holder.alloc(), x.priv_raw_begin() 1086 , n, this->priv_raw_begin()); 1087 } 1088 } 1089 1090 //! <b>Effects</b>: Destroys the vector. All stored values are destroyed 1091 //! and used memory is deallocated. 1092 //! 1093 //! <b>Throws</b>: Nothing. 1094 //! 1095 //! <b>Complexity</b>: Linear to the number of elements. 1096 ~vector() BOOST_NOEXCEPT_OR_NOTHROW 1097 { 1098 boost::container::destroy_alloc_n 1099 (this->get_stored_allocator(), this->priv_raw_begin(), this->m_holder.m_size); 1100 //vector_alloc_holder deallocates the data 1101 } 1102 1103 //! <b>Effects</b>: Makes *this contain the same elements as x. 1104 //! 1105 //! <b>Postcondition</b>: this->size() == x.size(). *this contains a copy 1106 //! of each of x's elements. 1107 //! 1108 //! <b>Throws</b>: If memory allocation throws or T's copy/move constructor/assignment throws. 1109 //! 1110 //! <b>Complexity</b>: Linear to the number of elements in x. 1111 BOOST_CONTAINER_FORCEINLINE vector& operator=(BOOST_COPY_ASSIGN_REF(vector) x) 1112 { 1113 if (BOOST_LIKELY(&x != this)){ 1114 this->priv_copy_assign(x); 1115 } 1116 return *this; 1117 } 1118 1119 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 1120 //! <b>Effects</b>: Make *this container contains elements from il. 1121 //! 1122 //! <b>Complexity</b>: Linear to the range [il.begin(), il.end()). 1123 BOOST_CONTAINER_FORCEINLINE vector& operator=(std::initializer_list<value_type> il) 1124 { 1125 this->assign(il.begin(), il.end()); 1126 return *this; 1127 } 1128 #endif 1129 1130 //! <b>Effects</b>: Move assignment. All x's values are transferred to *this. 1131 //! 1132 //! <b>Postcondition</b>: x.empty(). *this contains a the elements x had 1133 //! before the function. 1134 //! 1135 //! <b>Throws</b>: If allocator_traits_type::propagate_on_container_move_assignment 1136 //! is false and (allocation throws or value_type's move constructor throws) 1137 //! 1138 //! <b>Complexity</b>: Constant if allocator_traits_type:: 1139 //! propagate_on_container_move_assignment is true or 1140 //! this->get>allocator() == x.get_allocator(). Linear otherwise. 1141 BOOST_CONTAINER_FORCEINLINE vector& operator=(BOOST_RV_REF(vector) x) 1142 BOOST_NOEXCEPT_IF(allocator_traits_type::propagate_on_container_move_assignment::value 1143 || allocator_traits_type::is_always_equal::value) 1144 { 1145 if (BOOST_LIKELY(&x != this)){ 1146 this->priv_move_assign(boost::move(x)); 1147 } 1148 return *this; 1149 } 1150 1151 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1152 1153 //! <b>Effects</b>: Move assignment. All x's values are transferred to *this. 1154 //! 1155 //! <b>Postcondition</b>: x.empty(). *this contains a the elements x had 1156 //! before the function. 1157 //! 1158 //! <b>Throws</b>: If move constructor/assignment of T throws or allocation throws 1159 //! 1160 //! <b>Complexity</b>: Linear. 1161 //! 1162 //! <b>Note</b>: Non-standard extension to support static_vector 1163 template<class OtherA> 1164 BOOST_CONTAINER_FORCEINLINE typename dtl::enable_if_and 1165 < vector& 1166 , dtl::is_version<typename real_allocator<T, OtherA>::type, 0> 1167 , dtl::is_different<typename real_allocator<T, OtherA>::type, allocator_type> 1168 >::type 1169 operator=(BOOST_RV_REF_BEG vector<value_type, OtherA, Options> BOOST_RV_REF_END x) 1170 { 1171 this->priv_move_assign(boost::move(x)); 1172 return *this; 1173 } 1174 1175 //! <b>Effects</b>: Copy assignment. All x's values are copied to *this. 1176 //! 1177 //! <b>Postcondition</b>: x.empty(). *this contains a the elements x had 1178 //! before the function. 1179 //! 1180 //! <b>Throws</b>: If move constructor/assignment of T throws or allocation throws 1181 //! 1182 //! <b>Complexity</b>: Linear. 1183 //! 1184 //! <b>Note</b>: Non-standard extension to support static_vector 1185 template<class OtherA> 1186 BOOST_CONTAINER_FORCEINLINE typename dtl::enable_if_and 1187 < vector& 1188 , dtl::is_version<typename real_allocator<T, OtherA>::type, 0> 1189 , dtl::is_different<typename real_allocator<T, OtherA>::type, allocator_type> 1190 >::type 1191 operator=(const vector<value_type, OtherA, Options> &x) 1192 { 1193 this->priv_copy_assign(x); 1194 return *this; 1195 } 1196 1197 #endif 1198 1199 //! <b>Effects</b>: Assigns the the range [first, last) to *this. 1200 //! 1201 //! <b>Throws</b>: If memory allocation throws or T's copy/move constructor/assignment or 1202 //! T's constructor/assignment from dereferencing InpIt throws. 1203 //! 1204 //! <b>Complexity</b>: Linear to n. 1205 template <class InIt> 1206 void assign(InIt first, InIt last 1207 //Input iterators or version 0 allocator 1208 BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_or 1209 < void 1210 BOOST_MOVE_I dtl::is_convertible<InIt BOOST_MOVE_I size_type> 1211 BOOST_MOVE_I dtl::and_ 1212 < dtl::is_different<alloc_version BOOST_MOVE_I version_0> 1213 BOOST_MOVE_I dtl::is_not_input_iterator<InIt> 1214 > 1215 >::type * = 0) 1216 ) 1217 { 1218 //Overwrite all elements we can from [first, last) 1219 iterator cur = this->begin(); 1220 const iterator end_it = this->end(); 1221 for ( ; first != last && cur != end_it; ++cur, ++first){ 1222 *cur = *first; 1223 } 1224 1225 if (first == last){ 1226 //There are no more elements in the sequence, erase remaining 1227 T* const end_pos = this->priv_raw_end(); 1228 const size_type n = static_cast<size_type>(end_pos - boost::movelib::iterator_to_raw_pointer(cur)); 1229 this->priv_destroy_last_n(n); 1230 } 1231 else{ 1232 //There are more elements in the range, insert the remaining ones 1233 this->insert(this->cend(), first, last); 1234 } 1235 } 1236 1237 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 1238 //! <b>Effects</b>: Assigns the the range [il.begin(), il.end()) to *this. 1239 //! 1240 //! <b>Throws</b>: If memory allocation throws or 1241 //! T's constructor from dereferencing iniializer_list iterator throws. 1242 //! 1243 BOOST_CONTAINER_FORCEINLINE void assign(std::initializer_list<T> il) 1244 { 1245 this->assign(il.begin(), il.end()); 1246 } 1247 #endif 1248 1249 //! <b>Effects</b>: Assigns the the range [first, last) to *this. 1250 //! 1251 //! <b>Throws</b>: If memory allocation throws or T's copy/move constructor/assignment or 1252 //! T's constructor/assignment from dereferencing InpIt throws. 1253 //! 1254 //! <b>Complexity</b>: Linear to n. 1255 template <class FwdIt> 1256 void assign(FwdIt first, FwdIt last 1257 //Forward iterators and version > 0 allocator 1258 BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_or 1259 < void 1260 BOOST_MOVE_I dtl::is_same<alloc_version BOOST_MOVE_I version_0> 1261 BOOST_MOVE_I dtl::is_convertible<FwdIt BOOST_MOVE_I size_type> 1262 BOOST_MOVE_I dtl::is_input_iterator<FwdIt> 1263 >::type * = 0) 1264 ) 1265 { 1266 //For Fwd iterators the standard only requires EmplaceConstructible and assignable from *first 1267 //so we can't do any backwards allocation 1268 const typename iterator_traits<FwdIt>::size_type sz = boost::container::iterator_distance(first, last); 1269 if (sz > size_type(-1)){ 1270 boost::container::throw_length_error("vector::assign, FwdIt's max length reached"); 1271 } 1272 1273 const size_type input_sz = static_cast<size_type>(sz); 1274 const size_type old_capacity = this->capacity(); 1275 if(input_sz > old_capacity){ //If input range is too big, we need to reallocate 1276 size_type real_cap = 0; 1277 pointer reuse(this->m_holder.start()); 1278 pointer const ret(this->m_holder.allocation_command(allocate_new|expand_fwd, input_sz, real_cap = input_sz, reuse)); 1279 if(!reuse){ //New allocation, just emplace new values 1280 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS 1281 ++this->num_alloc; 1282 #endif 1283 pointer const old_p = this->m_holder.start(); 1284 if(old_p){ 1285 this->priv_destroy_all(); 1286 this->m_holder.deallocate(old_p, old_capacity); 1287 } 1288 this->m_holder.start(ret); 1289 this->m_holder.capacity(real_cap); 1290 this->m_holder.m_size = 0; 1291 this->priv_uninitialized_construct_at_end(first, last); 1292 return; 1293 } 1294 else{ 1295 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS 1296 ++this->num_expand_fwd; 1297 #endif 1298 this->m_holder.capacity(real_cap); 1299 //Forward expansion, use assignment + back deletion/construction that comes later 1300 } 1301 } 1302 1303 boost::container::copy_assign_range_alloc_n(this->m_holder.alloc(), first, input_sz, this->priv_raw_begin(), this->size()); 1304 m_holder.set_stored_size(input_sz); 1305 } 1306 1307 //! <b>Effects</b>: Assigns the n copies of val to *this. 1308 //! 1309 //! <b>Throws</b>: If memory allocation throws or 1310 //! T's copy/move constructor/assignment throws. 1311 //! 1312 //! <b>Complexity</b>: Linear to n. 1313 BOOST_CONTAINER_FORCEINLINE void assign(size_type n, const value_type& val) 1314 { this->assign(cvalue_iterator(val, n), cvalue_iterator()); } 1315 1316 //! <b>Effects</b>: Returns a copy of the internal allocator. 1317 //! 1318 //! <b>Throws</b>: If allocator's copy constructor throws. 1319 //! 1320 //! <b>Complexity</b>: Constant. 1321 allocator_type get_allocator() const BOOST_NOEXCEPT_OR_NOTHROW 1322 { return this->m_holder.alloc(); } 1323 1324 //! <b>Effects</b>: Returns a reference to the internal allocator. 1325 //! 1326 //! <b>Throws</b>: Nothing 1327 //! 1328 //! <b>Complexity</b>: Constant. 1329 //! 1330 //! <b>Note</b>: Non-standard extension. 1331 BOOST_CONTAINER_FORCEINLINE stored_allocator_type &get_stored_allocator() BOOST_NOEXCEPT_OR_NOTHROW 1332 { return this->m_holder.alloc(); } 1333 1334 //! <b>Effects</b>: Returns a reference to the internal allocator. 1335 //! 1336 //! <b>Throws</b>: Nothing 1337 //! 1338 //! <b>Complexity</b>: Constant. 1339 //! 1340 //! <b>Note</b>: Non-standard extension. 1341 BOOST_CONTAINER_FORCEINLINE const stored_allocator_type &get_stored_allocator() const BOOST_NOEXCEPT_OR_NOTHROW 1342 { return this->m_holder.alloc(); } 1343 1344 ////////////////////////////////////////////// 1345 // 1346 // iterators 1347 // 1348 ////////////////////////////////////////////// 1349 1350 //! <b>Effects</b>: Returns an iterator to the first element contained in the vector. 1351 //! 1352 //! <b>Throws</b>: Nothing. 1353 //! 1354 //! <b>Complexity</b>: Constant. 1355 BOOST_CONTAINER_FORCEINLINE iterator begin() BOOST_NOEXCEPT_OR_NOTHROW 1356 { return iterator(this->m_holder.start()); } 1357 1358 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the vector. 1359 //! 1360 //! <b>Throws</b>: Nothing. 1361 //! 1362 //! <b>Complexity</b>: Constant. 1363 BOOST_CONTAINER_FORCEINLINE const_iterator begin() const BOOST_NOEXCEPT_OR_NOTHROW 1364 { return const_iterator(this->m_holder.start()); } 1365 1366 //! <b>Effects</b>: Returns an iterator to the end of the vector. 1367 //! 1368 //! <b>Throws</b>: Nothing. 1369 //! 1370 //! <b>Complexity</b>: Constant. 1371 BOOST_CONTAINER_FORCEINLINE iterator end() BOOST_NOEXCEPT_OR_NOTHROW 1372 { 1373 iterator it (this->m_holder.start()); 1374 it += this->m_holder.m_size; 1375 return it; //Adding zero to null pointer is allowed (non-UB) 1376 } 1377 1378 //! <b>Effects</b>: Returns a const_iterator to the end of the vector. 1379 //! 1380 //! <b>Throws</b>: Nothing. 1381 //! 1382 //! <b>Complexity</b>: Constant. 1383 BOOST_CONTAINER_FORCEINLINE const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW 1384 { return this->cend(); } 1385 1386 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning 1387 //! of the reversed vector. 1388 //! 1389 //! <b>Throws</b>: Nothing. 1390 //! 1391 //! <b>Complexity</b>: Constant. 1392 BOOST_CONTAINER_FORCEINLINE reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW 1393 { return reverse_iterator(this->end()); } 1394 1395 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning 1396 //! of the reversed vector. 1397 //! 1398 //! <b>Throws</b>: Nothing. 1399 //! 1400 //! <b>Complexity</b>: Constant. 1401 BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW 1402 { return this->crbegin(); } 1403 1404 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end 1405 //! of the reversed vector. 1406 //! 1407 //! <b>Throws</b>: Nothing. 1408 //! 1409 //! <b>Complexity</b>: Constant. 1410 BOOST_CONTAINER_FORCEINLINE reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW 1411 { return reverse_iterator(this->begin()); } 1412 1413 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end 1414 //! of the reversed vector. 1415 //! 1416 //! <b>Throws</b>: Nothing. 1417 //! 1418 //! <b>Complexity</b>: Constant. 1419 BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW 1420 { return this->crend(); } 1421 1422 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the vector. 1423 //! 1424 //! <b>Throws</b>: Nothing. 1425 //! 1426 //! <b>Complexity</b>: Constant. 1427 BOOST_CONTAINER_FORCEINLINE const_iterator cbegin() const BOOST_NOEXCEPT_OR_NOTHROW 1428 { return const_iterator(this->m_holder.start()); } 1429 1430 //! <b>Effects</b>: Returns a const_iterator to the end of the vector. 1431 //! 1432 //! <b>Throws</b>: Nothing. 1433 //! 1434 //! <b>Complexity</b>: Constant. 1435 BOOST_CONTAINER_FORCEINLINE const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW 1436 { 1437 const_iterator it (this->m_holder.start()); 1438 it += this->m_holder.m_size; 1439 return it; //Adding zero to null pointer is allowed (non-UB) 1440 } 1441 1442 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning 1443 //! of the reversed vector. 1444 //! 1445 //! <b>Throws</b>: Nothing. 1446 //! 1447 //! <b>Complexity</b>: Constant. 1448 BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW 1449 { return const_reverse_iterator(this->end());} 1450 1451 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end 1452 //! of the reversed vector. 1453 //! 1454 //! <b>Throws</b>: Nothing. 1455 //! 1456 //! <b>Complexity</b>: Constant. 1457 BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW 1458 { return const_reverse_iterator(this->begin()); } 1459 1460 ////////////////////////////////////////////// 1461 // 1462 // capacity 1463 // 1464 ////////////////////////////////////////////// 1465 1466 //! <b>Effects</b>: Returns true if the vector contains no elements. 1467 //! 1468 //! <b>Throws</b>: Nothing. 1469 //! 1470 //! <b>Complexity</b>: Constant. 1471 BOOST_CONTAINER_FORCEINLINE bool empty() const BOOST_NOEXCEPT_OR_NOTHROW 1472 { return !this->m_holder.m_size; } 1473 1474 //! <b>Effects</b>: Returns the number of the elements contained in the vector. 1475 //! 1476 //! <b>Throws</b>: Nothing. 1477 //! 1478 //! <b>Complexity</b>: Constant. 1479 BOOST_CONTAINER_FORCEINLINE size_type size() const BOOST_NOEXCEPT_OR_NOTHROW 1480 { return this->m_holder.m_size; } 1481 1482 //! <b>Effects</b>: Returns the largest possible size of the vector. 1483 //! 1484 //! <b>Throws</b>: Nothing. 1485 //! 1486 //! <b>Complexity</b>: Constant. 1487 BOOST_CONTAINER_FORCEINLINE size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW 1488 { return allocator_traits_type::max_size(this->m_holder.alloc()); } 1489 1490 //! <b>Effects</b>: Inserts or erases elements at the end such that 1491 //! the size becomes n. New elements are value initialized. 1492 //! 1493 //! <b>Throws</b>: If memory allocation throws, or T's copy/move or value initialization throws. 1494 //! 1495 //! <b>Complexity</b>: Linear to the difference between size() and new_size. 1496 BOOST_CONTAINER_FORCEINLINE void resize(size_type new_size) 1497 { this->priv_resize(new_size, value_init, alloc_version()); } 1498 1499 //! <b>Effects</b>: Inserts or erases elements at the end such that 1500 //! the size becomes n. New elements are default initialized. 1501 //! 1502 //! <b>Throws</b>: If memory allocation throws, or T's copy/move or default initialization throws. 1503 //! 1504 //! <b>Complexity</b>: Linear to the difference between size() and new_size. 1505 //! 1506 //! <b>Note</b>: Non-standard extension 1507 BOOST_CONTAINER_FORCEINLINE void resize(size_type new_size, default_init_t) 1508 { this->priv_resize(new_size, default_init, alloc_version()); } 1509 1510 //! <b>Effects</b>: Inserts or erases elements at the end such that 1511 //! the size becomes n. New elements are copy constructed from x. 1512 //! 1513 //! <b>Throws</b>: If memory allocation throws, or T's copy/move constructor throws. 1514 //! 1515 //! <b>Complexity</b>: Linear to the difference between size() and new_size. 1516 BOOST_CONTAINER_FORCEINLINE void resize(size_type new_size, const T& x) 1517 { this->priv_resize(new_size, x, alloc_version()); } 1518 1519 //! <b>Effects</b>: Number of elements for which memory has been allocated. 1520 //! capacity() is always greater than or equal to size(). 1521 //! 1522 //! <b>Throws</b>: Nothing. 1523 //! 1524 //! <b>Complexity</b>: Constant. 1525 BOOST_CONTAINER_FORCEINLINE size_type capacity() const BOOST_NOEXCEPT_OR_NOTHROW 1526 { return this->m_holder.capacity(); } 1527 1528 //! <b>Effects</b>: If n is less than or equal to capacity(), this call has no 1529 //! effect. Otherwise, it is a request for allocation of additional memory. 1530 //! If the request is successful, then capacity() is greater than or equal to 1531 //! n; otherwise, capacity() is unchanged. In either case, size() is unchanged. 1532 //! 1533 //! <b>Throws</b>: If memory allocation allocation throws or T's copy/move constructor throws. 1534 BOOST_CONTAINER_FORCEINLINE void reserve(size_type new_cap) 1535 { 1536 if (this->capacity() < new_cap){ 1537 this->priv_move_to_new_buffer(new_cap, alloc_version()); 1538 } 1539 } 1540 1541 //! <b>Effects</b>: Tries to deallocate the excess of memory created 1542 //! with previous allocations. The size of the vector is unchanged 1543 //! 1544 //! <b>Throws</b>: If memory allocation throws, or T's copy/move constructor throws. 1545 //! 1546 //! <b>Complexity</b>: Linear to size(). 1547 BOOST_CONTAINER_FORCEINLINE void shrink_to_fit() 1548 { this->priv_shrink_to_fit(alloc_version()); } 1549 1550 ////////////////////////////////////////////// 1551 // 1552 // element access 1553 // 1554 ////////////////////////////////////////////// 1555 1556 //! <b>Requires</b>: !empty() 1557 //! 1558 //! <b>Effects</b>: Returns a reference to the first 1559 //! element of the container. 1560 //! 1561 //! <b>Throws</b>: Nothing. 1562 //! 1563 //! <b>Complexity</b>: Constant. 1564 BOOST_CONTAINER_FORCEINLINE reference front() BOOST_NOEXCEPT_OR_NOTHROW 1565 { 1566 BOOST_ASSERT(!this->empty()); 1567 return *this->m_holder.start(); 1568 } 1569 1570 //! <b>Requires</b>: !empty() 1571 //! 1572 //! <b>Effects</b>: Returns a const reference to the first 1573 //! element of the container. 1574 //! 1575 //! <b>Throws</b>: Nothing. 1576 //! 1577 //! <b>Complexity</b>: Constant. 1578 BOOST_CONTAINER_FORCEINLINE const_reference front() const BOOST_NOEXCEPT_OR_NOTHROW 1579 { 1580 BOOST_ASSERT(!this->empty()); 1581 return *this->m_holder.start(); 1582 } 1583 1584 //! <b>Requires</b>: !empty() 1585 //! 1586 //! <b>Effects</b>: Returns a reference to the last 1587 //! element of the container. 1588 //! 1589 //! <b>Throws</b>: Nothing. 1590 //! 1591 //! <b>Complexity</b>: Constant. 1592 BOOST_CONTAINER_FORCEINLINE reference back() BOOST_NOEXCEPT_OR_NOTHROW 1593 { 1594 BOOST_ASSERT(!this->empty()); 1595 return this->m_holder.start()[this->m_holder.m_size - 1]; 1596 } 1597 1598 //! <b>Requires</b>: !empty() 1599 //! 1600 //! <b>Effects</b>: Returns a const reference to the last 1601 //! element of the container. 1602 //! 1603 //! <b>Throws</b>: Nothing. 1604 //! 1605 //! <b>Complexity</b>: Constant. 1606 BOOST_CONTAINER_FORCEINLINE const_reference back() const BOOST_NOEXCEPT_OR_NOTHROW 1607 { 1608 BOOST_ASSERT(!this->empty()); 1609 return this->m_holder.start()[this->m_holder.m_size - 1]; 1610 } 1611 1612 //! <b>Requires</b>: size() > n. 1613 //! 1614 //! <b>Effects</b>: Returns a reference to the nth element 1615 //! from the beginning of the container. 1616 //! 1617 //! <b>Throws</b>: Nothing. 1618 //! 1619 //! <b>Complexity</b>: Constant. 1620 BOOST_CONTAINER_FORCEINLINE reference operator[](size_type n) BOOST_NOEXCEPT_OR_NOTHROW 1621 { 1622 BOOST_ASSERT(this->m_holder.m_size > n); 1623 return this->m_holder.start()[n]; 1624 } 1625 1626 //! <b>Requires</b>: size() > n. 1627 //! 1628 //! <b>Effects</b>: Returns a const reference to the nth element 1629 //! from the beginning of the container. 1630 //! 1631 //! <b>Throws</b>: Nothing. 1632 //! 1633 //! <b>Complexity</b>: Constant. 1634 BOOST_CONTAINER_FORCEINLINE const_reference operator[](size_type n) const BOOST_NOEXCEPT_OR_NOTHROW 1635 { 1636 BOOST_ASSERT(this->m_holder.m_size > n); 1637 return this->m_holder.start()[n]; 1638 } 1639 1640 //! <b>Requires</b>: size() >= n. 1641 //! 1642 //! <b>Effects</b>: Returns an iterator to the nth element 1643 //! from the beginning of the container. Returns end() 1644 //! if n == size(). 1645 //! 1646 //! <b>Throws</b>: Nothing. 1647 //! 1648 //! <b>Complexity</b>: Constant. 1649 //! 1650 //! <b>Note</b>: Non-standard extension 1651 BOOST_CONTAINER_FORCEINLINE iterator nth(size_type n) BOOST_NOEXCEPT_OR_NOTHROW 1652 { 1653 BOOST_ASSERT(this->m_holder.m_size >= n); 1654 return iterator(this->m_holder.start()+n); 1655 } 1656 1657 //! <b>Requires</b>: size() >= n. 1658 //! 1659 //! <b>Effects</b>: Returns a const_iterator to the nth element 1660 //! from the beginning of the container. Returns end() 1661 //! if n == size(). 1662 //! 1663 //! <b>Throws</b>: Nothing. 1664 //! 1665 //! <b>Complexity</b>: Constant. 1666 //! 1667 //! <b>Note</b>: Non-standard extension 1668 BOOST_CONTAINER_FORCEINLINE const_iterator nth(size_type n) const BOOST_NOEXCEPT_OR_NOTHROW 1669 { 1670 BOOST_ASSERT(this->m_holder.m_size >= n); 1671 return const_iterator(this->m_holder.start()+n); 1672 } 1673 1674 //! <b>Requires</b>: begin() <= p <= end(). 1675 //! 1676 //! <b>Effects</b>: Returns the index of the element pointed by p 1677 //! and size() if p == end(). 1678 //! 1679 //! <b>Throws</b>: Nothing. 1680 //! 1681 //! <b>Complexity</b>: Constant. 1682 //! 1683 //! <b>Note</b>: Non-standard extension 1684 BOOST_CONTAINER_FORCEINLINE size_type index_of(iterator p) BOOST_NOEXCEPT_OR_NOTHROW 1685 { 1686 //Range check assert done in priv_index_of 1687 return this->priv_index_of(vector_iterator_get_ptr(p)); 1688 } 1689 1690 //! <b>Requires</b>: begin() <= p <= end(). 1691 //! 1692 //! <b>Effects</b>: Returns the index of the element pointed by p 1693 //! and size() if p == end(). 1694 //! 1695 //! <b>Throws</b>: Nothing. 1696 //! 1697 //! <b>Complexity</b>: Constant. 1698 //! 1699 //! <b>Note</b>: Non-standard extension 1700 BOOST_CONTAINER_FORCEINLINE size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW 1701 { 1702 //Range check assert done in priv_index_of 1703 return this->priv_index_of(vector_iterator_get_ptr(p)); 1704 } 1705 1706 //! <b>Requires</b>: size() > n. 1707 //! 1708 //! <b>Effects</b>: Returns a reference to the nth element 1709 //! from the beginning of the container. 1710 //! 1711 //! <b>Throws</b>: std::range_error if n >= size() 1712 //! 1713 //! <b>Complexity</b>: Constant. 1714 BOOST_CONTAINER_FORCEINLINE reference at(size_type n) 1715 { 1716 this->priv_throw_if_out_of_range(n); 1717 return this->m_holder.start()[n]; 1718 } 1719 1720 //! <b>Requires</b>: size() > n. 1721 //! 1722 //! <b>Effects</b>: Returns a const reference to the nth element 1723 //! from the beginning of the container. 1724 //! 1725 //! <b>Throws</b>: std::range_error if n >= size() 1726 //! 1727 //! <b>Complexity</b>: Constant. 1728 BOOST_CONTAINER_FORCEINLINE const_reference at(size_type n) const 1729 { 1730 this->priv_throw_if_out_of_range(n); 1731 return this->m_holder.start()[n]; 1732 } 1733 1734 ////////////////////////////////////////////// 1735 // 1736 // data access 1737 // 1738 ////////////////////////////////////////////// 1739 1740 //! <b>Returns</b>: A pointer such that [data(),data() + size()) is a valid range. 1741 //! For a non-empty vector, data() == &front(). 1742 //! 1743 //! <b>Throws</b>: Nothing. 1744 //! 1745 //! <b>Complexity</b>: Constant. 1746 BOOST_CONTAINER_FORCEINLINE T* data() BOOST_NOEXCEPT_OR_NOTHROW 1747 { return this->priv_raw_begin(); } 1748 1749 //! <b>Returns</b>: A pointer such that [data(),data() + size()) is a valid range. 1750 //! For a non-empty vector, data() == &front(). 1751 //! 1752 //! <b>Throws</b>: Nothing. 1753 //! 1754 //! <b>Complexity</b>: Constant. 1755 BOOST_CONTAINER_FORCEINLINE const T * data() const BOOST_NOEXCEPT_OR_NOTHROW 1756 { return this->priv_raw_begin(); } 1757 1758 ////////////////////////////////////////////// 1759 // 1760 // modifiers 1761 // 1762 ////////////////////////////////////////////// 1763 1764 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1765 //! <b>Effects</b>: Inserts an object of type T constructed with 1766 //! std::forward<Args>(args)... in the end of the vector. 1767 //! 1768 //! <b>Returns</b>: A reference to the created object. 1769 //! 1770 //! <b>Throws</b>: If memory allocation throws or the in-place constructor throws or 1771 //! T's copy/move constructor throws. 1772 //! 1773 //! <b>Complexity</b>: Amortized constant time. 1774 template<class ...Args> 1775 BOOST_CONTAINER_FORCEINLINE reference emplace_back(BOOST_FWD_REF(Args)...args) 1776 { 1777 T* const p = this->priv_raw_end(); 1778 if (BOOST_LIKELY(this->room_enough())){ 1779 //There is more memory, just construct a new object at the end 1780 allocator_traits_type::construct(this->m_holder.alloc(), p, ::boost::forward<Args>(args)...); 1781 ++this->m_holder.m_size; 1782 return *p; 1783 } 1784 else{ 1785 typedef dtl::insert_emplace_proxy<allocator_type, T*, Args...> proxy_t; 1786 return *this->priv_insert_forward_range_no_capacity 1787 (p, 1, proxy_t(::boost::forward<Args>(args)...), alloc_version()); 1788 } 1789 } 1790 1791 //! <b>Effects</b>: Inserts an object of type T constructed with 1792 //! std::forward<Args>(args)... in the end of the vector. 1793 //! 1794 //! <b>Throws</b>: If the in-place constructor throws. 1795 //! 1796 //! <b>Complexity</b>: Constant time. 1797 //! 1798 //! <b>Note</b>: Non-standard extension. 1799 template<class ...Args> 1800 BOOST_CONTAINER_FORCEINLINE bool stable_emplace_back(BOOST_FWD_REF(Args)...args) 1801 { 1802 const bool is_room_enough = this->room_enough() || (alloc_version::value == 2 && this->m_holder.try_expand_fwd(1u)); 1803 if (BOOST_LIKELY(is_room_enough)){ 1804 //There is more memory, just construct a new object at the end 1805 allocator_traits_type::construct(this->m_holder.alloc(), this->priv_raw_end(), ::boost::forward<Args>(args)...); 1806 ++this->m_holder.m_size; 1807 } 1808 return is_room_enough; 1809 } 1810 1811 //! <b>Requires</b>: position must be a valid iterator of *this. 1812 //! 1813 //! <b>Effects</b>: Inserts an object of type T constructed with 1814 //! std::forward<Args>(args)... before position 1815 //! 1816 //! <b>Throws</b>: If memory allocation throws or the in-place constructor throws or 1817 //! T's copy/move constructor/assignment throws. 1818 //! 1819 //! <b>Complexity</b>: If position is end(), amortized constant time 1820 //! Linear time otherwise. 1821 template<class ...Args> 1822 BOOST_CONTAINER_FORCEINLINE iterator emplace(const_iterator position, BOOST_FWD_REF(Args) ...args) 1823 { 1824 BOOST_ASSERT(this->priv_in_range_or_end(position)); 1825 //Just call more general insert(pos, size, value) and return iterator 1826 typedef dtl::insert_emplace_proxy<allocator_type, T*, Args...> proxy_t; 1827 return this->priv_insert_forward_range( vector_iterator_get_ptr(position), 1 1828 , proxy_t(::boost::forward<Args>(args)...)); 1829 } 1830 1831 #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 1832 1833 #define BOOST_CONTAINER_VECTOR_EMPLACE_CODE(N) \ 1834 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 1835 BOOST_CONTAINER_FORCEINLINE reference emplace_back(BOOST_MOVE_UREF##N)\ 1836 {\ 1837 T* const p = this->priv_raw_end();\ 1838 if (BOOST_LIKELY(this->room_enough())){\ 1839 allocator_traits_type::construct (this->m_holder.alloc()\ 1840 , this->priv_raw_end() BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ 1841 ++this->m_holder.m_size;\ 1842 return *p;\ 1843 }\ 1844 else{\ 1845 typedef dtl::insert_emplace_proxy_arg##N<allocator_type, T* BOOST_MOVE_I##N BOOST_MOVE_TARG##N> proxy_t;\ 1846 return *this->priv_insert_forward_range_no_capacity\ 1847 ( p, 1, proxy_t(BOOST_MOVE_FWD##N), alloc_version());\ 1848 }\ 1849 }\ 1850 \ 1851 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 1852 BOOST_CONTAINER_FORCEINLINE bool stable_emplace_back(BOOST_MOVE_UREF##N)\ 1853 {\ 1854 const bool is_room_enough = this->room_enough() || (alloc_version::value == 2 && this->m_holder.try_expand_fwd(1u));\ 1855 if (BOOST_LIKELY(is_room_enough)){\ 1856 allocator_traits_type::construct (this->m_holder.alloc()\ 1857 , this->priv_raw_end() BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ 1858 ++this->m_holder.m_size;\ 1859 }\ 1860 return is_room_enough;\ 1861 }\ 1862 \ 1863 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 1864 BOOST_CONTAINER_FORCEINLINE iterator emplace(const_iterator pos BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ 1865 {\ 1866 BOOST_ASSERT(this->priv_in_range_or_end(pos));\ 1867 typedef dtl::insert_emplace_proxy_arg##N<allocator_type, T* BOOST_MOVE_I##N BOOST_MOVE_TARG##N> proxy_t;\ 1868 return this->priv_insert_forward_range(vector_iterator_get_ptr(pos), 1, proxy_t(BOOST_MOVE_FWD##N));\ 1869 }\ 1870 // 1871 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_VECTOR_EMPLACE_CODE) 1872 #undef BOOST_CONTAINER_VECTOR_EMPLACE_CODE 1873 1874 #endif 1875 1876 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1877 //! <b>Effects</b>: Inserts a copy of x at the end of the vector. 1878 //! 1879 //! <b>Throws</b>: If memory allocation throws or 1880 //! T's copy/move constructor throws. 1881 //! 1882 //! <b>Complexity</b>: Amortized constant time. 1883 void push_back(const T &x); 1884 1885 //! <b>Effects</b>: Constructs a new element in the end of the vector 1886 //! and moves the resources of x to this new element. 1887 //! 1888 //! <b>Throws</b>: If memory allocation throws or 1889 //! T's copy/move constructor throws. 1890 //! 1891 //! <b>Complexity</b>: Amortized constant time. 1892 void push_back(T &&x); 1893 #else 1894 BOOST_MOVE_CONVERSION_AWARE_CATCH(push_back, T, void, priv_push_back) 1895 #endif 1896 1897 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1898 //! <b>Requires</b>: position must be a valid iterator of *this. 1899 //! 1900 //! <b>Effects</b>: Insert a copy of x before position. 1901 //! 1902 //! <b>Throws</b>: If memory allocation throws or T's copy/move constructor/assignment throws. 1903 //! 1904 //! <b>Complexity</b>: If position is end(), amortized constant time 1905 //! Linear time otherwise. 1906 iterator insert(const_iterator position, const T &x); 1907 1908 //! <b>Requires</b>: position must be a valid iterator of *this. 1909 //! 1910 //! <b>Effects</b>: Insert a new element before position with x's resources. 1911 //! 1912 //! <b>Throws</b>: If memory allocation throws. 1913 //! 1914 //! <b>Complexity</b>: If position is end(), amortized constant time 1915 //! Linear time otherwise. 1916 iterator insert(const_iterator position, T &&x); 1917 #else 1918 BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, T, iterator, priv_insert, const_iterator, const_iterator) 1919 #endif 1920 1921 //! <b>Requires</b>: p must be a valid iterator of *this. 1922 //! 1923 //! <b>Effects</b>: Insert n copies of x before pos. 1924 //! 1925 //! <b>Returns</b>: an iterator to the first inserted element or p if n is 0. 1926 //! 1927 //! <b>Throws</b>: If memory allocation throws or T's copy/move constructor throws. 1928 //! 1929 //! <b>Complexity</b>: Linear to n. 1930 BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, size_type n, const T& x) 1931 { 1932 BOOST_ASSERT(this->priv_in_range_or_end(p)); 1933 dtl::insert_n_copies_proxy<allocator_type, T*> proxy(x); 1934 return this->priv_insert_forward_range(vector_iterator_get_ptr(p), n, proxy); 1935 } 1936 1937 //! <b>Requires</b>: p must be a valid iterator of *this. 1938 //! 1939 //! <b>Effects</b>: Insert a copy of the [first, last) range before pos. 1940 //! 1941 //! <b>Returns</b>: an iterator to the first inserted element or pos if first == last. 1942 //! 1943 //! <b>Throws</b>: If memory allocation throws, T's constructor from a 1944 //! dereferenced InpIt throws or T's copy/move constructor/assignment throws. 1945 //! 1946 //! <b>Complexity</b>: Linear to boost::container::iterator_distance [first, last). 1947 template <class InIt> 1948 iterator insert(const_iterator pos, InIt first, InIt last 1949 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1950 , typename dtl::disable_if_or 1951 < void 1952 , dtl::is_convertible<InIt, size_type> 1953 , dtl::is_not_input_iterator<InIt> 1954 >::type * = 0 1955 #endif 1956 ) 1957 { 1958 BOOST_ASSERT(this->priv_in_range_or_end(pos)); 1959 const size_type n_pos = pos - this->cbegin(); 1960 iterator it(vector_iterator_get_ptr(pos)); 1961 for(;first != last; ++first){ 1962 it = this->emplace(it, *first); 1963 ++it; 1964 } 1965 return iterator(this->m_holder.start() + n_pos); 1966 } 1967 1968 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1969 template <class FwdIt> 1970 BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator pos, FwdIt first, FwdIt last 1971 , typename dtl::disable_if_or 1972 < void 1973 , dtl::is_convertible<FwdIt, size_type> 1974 , dtl::is_input_iterator<FwdIt> 1975 >::type * = 0 1976 ) 1977 { 1978 BOOST_ASSERT(this->priv_in_range_or_end(pos)); 1979 const typename iterator_traits<FwdIt>::size_type sz = boost::container::iterator_distance(first, last); 1980 if (sz > size_type(-1)){ 1981 boost::container::throw_length_error("vector::insert, FwdIt's max length reached"); 1982 } 1983 1984 dtl::insert_range_proxy<allocator_type, FwdIt, T*> proxy(first); 1985 return this->priv_insert_forward_range(vector_iterator_get_ptr(pos), static_cast<size_type>(sz), proxy); 1986 } 1987 #endif 1988 1989 //! <b>Requires</b>: p must be a valid iterator of *this. num, must 1990 //! be equal to boost::container::iterator_distance(first, last) 1991 //! 1992 //! <b>Effects</b>: Insert a copy of the [first, last) range before pos. 1993 //! 1994 //! <b>Returns</b>: an iterator to the first inserted element or pos if first == last. 1995 //! 1996 //! <b>Throws</b>: If memory allocation throws, T's constructor from a 1997 //! dereferenced InpIt throws or T's copy/move constructor/assignment throws. 1998 //! 1999 //! <b>Complexity</b>: Linear to boost::container::iterator_distance [first, last). 2000 //! 2001 //! <b>Note</b>: This function avoids a linear operation to calculate boost::container::iterator_distance[first, last) 2002 //! for forward and bidirectional iterators, and a one by one insertion for input iterators. This is a 2003 //! a non-standard extension. 2004 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 2005 template <class InIt> 2006 BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator pos, size_type num, InIt first, InIt last) 2007 { 2008 BOOST_ASSERT(this->priv_in_range_or_end(pos)); 2009 BOOST_ASSERT(dtl::is_input_iterator<InIt>::value || 2010 num == static_cast<size_type>(boost::container::iterator_distance(first, last))); 2011 (void)last; 2012 dtl::insert_range_proxy<allocator_type, InIt, T*> proxy(first); 2013 return this->priv_insert_forward_range(vector_iterator_get_ptr(pos), num, proxy); 2014 } 2015 #endif 2016 2017 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 2018 //! <b>Requires</b>: position must be a valid iterator of *this. 2019 //! 2020 //! <b>Effects</b>: Insert a copy of the [il.begin(), il.end()) range before position. 2021 //! 2022 //! <b>Returns</b>: an iterator to the first inserted element or position if first == last. 2023 //! 2024 //! <b>Complexity</b>: Linear to the range [il.begin(), il.end()). 2025 BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator position, std::initializer_list<value_type> il) 2026 { 2027 //Assertion done in insert() 2028 return this->insert(position, il.begin(), il.end()); 2029 } 2030 #endif 2031 2032 //! <b>Effects</b>: Removes the last element from the container. 2033 //! 2034 //! <b>Throws</b>: Nothing. 2035 //! 2036 //! <b>Complexity</b>: Constant time. 2037 BOOST_CONTAINER_FORCEINLINE void pop_back() BOOST_NOEXCEPT_OR_NOTHROW 2038 { 2039 BOOST_ASSERT(!this->empty()); 2040 //Destroy last element 2041 allocator_traits_type::destroy(this->get_stored_allocator(), this->priv_raw_end() - 1); 2042 --this->m_holder.m_size; 2043 } 2044 2045 //! <b>Effects</b>: Erases the element at position pos. 2046 //! 2047 //! <b>Throws</b>: Nothing. 2048 //! 2049 //! <b>Complexity</b>: Linear to the elements between pos and the 2050 //! last element. Constant if pos is the last element. 2051 iterator erase(const_iterator position) 2052 { 2053 BOOST_ASSERT(this->priv_in_range(position)); 2054 const pointer p = vector_iterator_get_ptr(position); 2055 T *const pos_ptr = boost::movelib::to_raw_pointer(p); 2056 T *const end_ptr = this->priv_raw_end(); 2057 2058 //Move elements forward and destroy last 2059 (void)::boost::container::move(pos_ptr + 1, end_ptr, pos_ptr); 2060 2061 T *const last_ptr = end_ptr-1; 2062 if(!value_traits::trivial_dctr_after_move || pos_ptr == last_ptr){ 2063 allocator_traits_type::destroy(this->get_stored_allocator(), last_ptr); 2064 } 2065 --this->m_holder.m_size; 2066 return iterator(p); 2067 } 2068 2069 //! <b>Effects</b>: Erases the elements pointed by [first, last). 2070 //! 2071 //! <b>Throws</b>: Nothing. 2072 //! 2073 //! <b>Complexity</b>: Linear to the distance between first and last 2074 //! plus linear to the elements between pos and the last element. 2075 iterator erase(const_iterator first, const_iterator last) 2076 { 2077 BOOST_ASSERT(this->priv_in_range_or_end(first)); 2078 BOOST_ASSERT(this->priv_in_range_or_end(last)); 2079 BOOST_ASSERT(first <= last); 2080 if(first != last){ 2081 T* const old_end_ptr = this->priv_raw_end(); 2082 T* const first_ptr = boost::movelib::to_raw_pointer(vector_iterator_get_ptr(first)); 2083 T* const last_ptr = boost::movelib::to_raw_pointer(vector_iterator_get_ptr(last)); 2084 T* const new_last_ptr = boost::movelib::to_raw_pointer(boost::container::move(last_ptr, old_end_ptr, first_ptr)); 2085 const size_type n = static_cast<size_type>(old_end_ptr - new_last_ptr); 2086 if(!value_traits::trivial_dctr_after_move || old_end_ptr == last_ptr){ 2087 boost::container::destroy_alloc_n(this->get_stored_allocator(), new_last_ptr, n); 2088 } 2089 this->m_holder.dec_stored_size(n); 2090 } 2091 return iterator(vector_iterator_get_ptr(first)); 2092 } 2093 2094 //! <b>Effects</b>: Swaps the contents of *this and x. 2095 //! 2096 //! <b>Throws</b>: Nothing. 2097 //! 2098 //! <b>Complexity</b>: Constant. 2099 BOOST_CONTAINER_FORCEINLINE void swap(vector& x) 2100 BOOST_NOEXCEPT_IF( ((allocator_traits_type::propagate_on_container_swap::value 2101 || allocator_traits_type::is_always_equal::value) && 2102 !dtl::is_version<allocator_type, 0>::value)) 2103 { 2104 this->priv_swap(x, dtl::bool_<dtl::is_version<allocator_type, 0>::value>()); 2105 } 2106 2107 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 2108 2109 //! <b>Effects</b>: Swaps the contents of *this and x. 2110 //! 2111 //! <b>Throws</b>: Nothing. 2112 //! 2113 //! <b>Complexity</b>: Linear 2114 //! 2115 //! <b>Note</b>: Non-standard extension to support static_vector 2116 template<class OtherA> 2117 BOOST_CONTAINER_FORCEINLINE void swap(vector<T, OtherA, Options> & x 2118 , typename dtl::enable_if_and 2119 < void 2120 , dtl::is_version<typename real_allocator<T, OtherA>::type, 0> 2121 , dtl::is_different<typename real_allocator<T, OtherA>::type, allocator_type> 2122 >::type * = 0 2123 ) 2124 { this->m_holder.deep_swap(x.m_holder); } 2125 2126 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 2127 2128 //! <b>Effects</b>: Erases all the elements of the vector. 2129 //! 2130 //! <b>Throws</b>: Nothing. 2131 //! 2132 //! <b>Complexity</b>: Linear to the number of elements in the container. 2133 BOOST_CONTAINER_FORCEINLINE void clear() BOOST_NOEXCEPT_OR_NOTHROW 2134 { this->priv_destroy_all(); } 2135 2136 //! <b>Effects</b>: Returns true if x and y are equal 2137 //! 2138 //! <b>Complexity</b>: Linear to the number of elements in the container. 2139 BOOST_CONTAINER_FORCEINLINE friend bool operator==(const vector& x, const vector& y) 2140 { return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin()); } 2141 2142 //! <b>Effects</b>: Returns true if x and y are unequal 2143 //! 2144 //! <b>Complexity</b>: Linear to the number of elements in the container. 2145 BOOST_CONTAINER_FORCEINLINE friend bool operator!=(const vector& x, const vector& y) 2146 { return !(x == y); } 2147 2148 //! <b>Effects</b>: Returns true if x is less than y 2149 //! 2150 //! <b>Complexity</b>: Linear to the number of elements in the container. 2151 friend bool operator<(const vector& x, const vector& y) 2152 { return boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); } 2153 2154 //! <b>Effects</b>: Returns true if x is greater than y 2155 //! 2156 //! <b>Complexity</b>: Linear to the number of elements in the container. 2157 BOOST_CONTAINER_FORCEINLINE friend bool operator>(const vector& x, const vector& y) 2158 { return y < x; } 2159 2160 //! <b>Effects</b>: Returns true if x is equal or less than y 2161 //! 2162 //! <b>Complexity</b>: Linear to the number of elements in the container. 2163 BOOST_CONTAINER_FORCEINLINE friend bool operator<=(const vector& x, const vector& y) 2164 { return !(y < x); } 2165 2166 //! <b>Effects</b>: Returns true if x is equal or greater than y 2167 //! 2168 //! <b>Complexity</b>: Linear to the number of elements in the container. 2169 BOOST_CONTAINER_FORCEINLINE friend bool operator>=(const vector& x, const vector& y) 2170 { return !(x < y); } 2171 2172 //! <b>Effects</b>: x.swap(y) 2173 //! 2174 //! <b>Complexity</b>: Constant. 2175 BOOST_CONTAINER_FORCEINLINE friend void swap(vector& x, vector& y) 2176 { x.swap(y); } 2177 2178 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 2179 //! <b>Effects</b>: If n is less than or equal to capacity(), this call has no 2180 //! effect. Otherwise, it is a request for allocation of additional memory 2181 //! (memory expansion) that will not invalidate iterators. 2182 //! If the request is successful, then capacity() is greater than or equal to 2183 //! n; otherwise, capacity() is unchanged. In either case, size() is unchanged. 2184 //! 2185 //! <b>Throws</b>: If memory allocation allocation throws or T's copy/move constructor throws. 2186 //! 2187 //! <b>Note</b>: Non-standard extension. 2188 bool stable_reserve(size_type new_cap) 2189 { 2190 const size_type cp = this->capacity(); 2191 return cp >= new_cap || (alloc_version::value == 2 && this->m_holder.try_expand_fwd(new_cap - cp)); 2192 } 2193 2194 //Absolutely experimental. This function might change, disappear or simply crash! 2195 template<class BiDirPosConstIt, class BiDirValueIt> 2196 BOOST_CONTAINER_FORCEINLINE void insert_ordered_at(const size_type element_count, BiDirPosConstIt last_position_it, BiDirValueIt last_value_it) 2197 { 2198 typedef vector_insert_ordered_cursor<BiDirPosConstIt, BiDirValueIt> inserter_t; 2199 return this->priv_insert_ordered_at(element_count, inserter_t(last_position_it, last_value_it)); 2200 } 2201 2202 template<class InputIt> 2203 BOOST_CONTAINER_FORCEINLINE void merge(InputIt first, InputIt last) 2204 { this->merge(first, last, value_less_t()); } 2205 2206 template<class InputIt, class Compare> 2207 BOOST_CONTAINER_FORCEINLINE void merge(InputIt first, InputIt last, Compare comp) 2208 { 2209 size_type const s = this->size(); 2210 size_type const c = this->capacity(); 2211 size_type n = 0; 2212 size_type const free_cap = c - s; 2213 //If not input iterator and new elements don't fit in the remaining capacity, merge in new buffer 2214 if(!dtl::is_input_iterator<InputIt>::value && 2215 free_cap < (n = static_cast<size_type>(boost::container::iterator_distance(first, last)))){ 2216 this->priv_merge_in_new_buffer(first, n, comp, alloc_version()); 2217 } 2218 else{ 2219 this->insert(this->cend(), first, last); 2220 T *const raw_beg = this->priv_raw_begin(); 2221 T *const raw_end = this->priv_raw_end(); 2222 T *const raw_pos = raw_beg + s; 2223 boost::movelib::adaptive_merge(raw_beg, raw_pos, raw_end, comp, raw_end, free_cap - n); 2224 } 2225 } 2226 2227 template<class InputIt> 2228 BOOST_CONTAINER_FORCEINLINE void merge_unique(InputIt first, InputIt last) 2229 { this->merge_unique(first, last, value_less_t()); } 2230 2231 template<class InputIt, class Compare> 2232 BOOST_CONTAINER_FORCEINLINE void merge_unique(InputIt first, InputIt last, Compare comp) 2233 { 2234 size_type const old_size = this->size(); 2235 this->priv_set_difference_back(first, last, comp); 2236 T *const raw_beg = this->priv_raw_begin(); 2237 T *const raw_end = this->priv_raw_end(); 2238 T *raw_pos = raw_beg + old_size; 2239 boost::movelib::adaptive_merge(raw_beg, raw_pos, raw_end, comp, raw_end, this->capacity() - this->size()); 2240 } 2241 2242 private: 2243 template<class PositionValue> 2244 void priv_insert_ordered_at(const size_type element_count, PositionValue position_value) 2245 { 2246 const size_type old_size_pos = this->size(); 2247 this->reserve(old_size_pos + element_count); 2248 T* const begin_ptr = this->priv_raw_begin(); 2249 size_type insertions_left = element_count; 2250 size_type prev_pos = old_size_pos; 2251 size_type old_hole_size = element_count; 2252 2253 //Exception rollback. If any copy throws before the hole is filled, values 2254 //already inserted/copied at the end of the buffer will be destroyed. 2255 typename value_traits::ArrayDestructor past_hole_values_destroyer 2256 (begin_ptr + old_size_pos + element_count, this->m_holder.alloc(), size_type(0u)); 2257 //Loop for each insertion backwards, first moving the elements after the insertion point, 2258 //then inserting the element. 2259 while(insertions_left){ 2260 --position_value; 2261 size_type const pos = position_value.get_pos(); 2262 BOOST_ASSERT(pos != size_type(-1) && pos <= old_size_pos && pos <= prev_pos); 2263 //If needed shift the range after the insertion point and the previous insertion point. 2264 //Function will take care if the shift crosses the size() boundary, using copy/move 2265 //or uninitialized copy/move if necessary. 2266 size_type new_hole_size = (pos != prev_pos) 2267 ? priv_insert_ordered_at_shift_range(pos, prev_pos, this->size(), insertions_left) 2268 : old_hole_size 2269 ; 2270 if(new_hole_size){ 2271 //The hole was reduced by priv_insert_ordered_at_shift_range so expand exception rollback range backwards 2272 past_hole_values_destroyer.increment_size_backwards(prev_pos - pos); 2273 //Insert the new value in the hole 2274 allocator_traits_type::construct(this->m_holder.alloc(), begin_ptr + pos + insertions_left - 1, position_value.get_val()); 2275 if(--new_hole_size){ 2276 //The hole was reduced by the new insertion by one 2277 past_hole_values_destroyer.increment_size_backwards(size_type(1u)); 2278 } 2279 else{ 2280 //Hole was just filled, disable exception rollback and change vector size 2281 past_hole_values_destroyer.release(); 2282 this->m_holder.inc_stored_size(element_count); 2283 } 2284 } 2285 else{ 2286 if(old_hole_size){ 2287 //Hole was just filled by priv_insert_ordered_at_shift_range, disable exception rollback and change vector size 2288 past_hole_values_destroyer.release(); 2289 this->m_holder.inc_stored_size(element_count); 2290 } 2291 //Insert the new value in the already constructed range 2292 begin_ptr[pos + insertions_left - 1] = position_value.get_val(); 2293 } 2294 --insertions_left; 2295 old_hole_size = new_hole_size; 2296 prev_pos = pos; 2297 } 2298 } 2299 2300 template<class InputIt, class Compare> 2301 void priv_set_difference_back(InputIt first1, InputIt last1, Compare comp) 2302 { 2303 T * old_first2 = this->priv_raw_begin(); 2304 T * first2 = old_first2; 2305 T * last2 = this->priv_raw_end(); 2306 2307 while (first1 != last1) { 2308 if (first2 == last2){ 2309 this->insert(this->cend(), first1, last1); 2310 return; 2311 } 2312 2313 if (comp(*first1, *first2)) { 2314 this->emplace_back(*first1); 2315 T * const raw_begin = this->priv_raw_begin(); 2316 if(old_first2 != raw_begin) 2317 { 2318 //Reallocation happened, update range 2319 first2 = raw_begin + (first2 - old_first2); 2320 last2 = raw_begin + (last2 - old_first2); 2321 old_first2 = raw_begin; 2322 } 2323 ++first1; 2324 } 2325 else { 2326 if (!comp(*first2, *first1)) { 2327 ++first1; 2328 } 2329 ++first2; 2330 } 2331 } 2332 } 2333 2334 template<class FwdIt, class Compare> 2335 BOOST_CONTAINER_FORCEINLINE void priv_merge_in_new_buffer(FwdIt, size_type, Compare, version_0) 2336 { 2337 alloc_holder_t::on_capacity_overflow(); 2338 } 2339 2340 template<class FwdIt, class Compare, class Version> 2341 void priv_merge_in_new_buffer(FwdIt first, size_type n, Compare comp, Version) 2342 { 2343 size_type const new_size = this->size() + n; 2344 size_type new_cap = new_size; 2345 pointer p = pointer(); 2346 pointer const new_storage = this->m_holder.allocation_command(allocate_new, new_size, new_cap, p); 2347 2348 BOOST_ASSERT((new_cap >= this->size() ) && (new_cap - this->size()) >= n); 2349 allocator_type &a = this->m_holder.alloc(); 2350 typename value_traits::ArrayDeallocator new_buffer_deallocator(new_storage, a, new_cap); 2351 typename value_traits::ArrayDestructor new_values_destroyer(new_storage, a, 0u); 2352 T* pbeg = this->priv_raw_begin(); 2353 size_type const old_size = this->size(); 2354 T* const pend = pbeg + old_size; 2355 T* d_first = boost::movelib::to_raw_pointer(new_storage); 2356 size_type added = n; 2357 //Merge in new buffer loop 2358 while(1){ 2359 if(!n) { 2360 ::boost::container::uninitialized_move_alloc(this->m_holder.alloc(), pbeg, pend, d_first); 2361 break; 2362 } 2363 else if(pbeg == pend) { 2364 ::boost::container::uninitialized_move_alloc_n(this->m_holder.alloc(), first, n, d_first); 2365 break; 2366 } 2367 //maintain stability moving external values only if they are strictly less 2368 else if(comp(*first, *pbeg)) { 2369 allocator_traits_type::construct( this->m_holder.alloc(), d_first, *first ); 2370 new_values_destroyer.increment_size(1u); 2371 ++first; 2372 --n; 2373 ++d_first; 2374 } 2375 else{ 2376 allocator_traits_type::construct( this->m_holder.alloc(), d_first, boost::move(*pbeg) ); 2377 new_values_destroyer.increment_size(1u); 2378 ++pbeg; 2379 ++d_first; 2380 } 2381 } 2382 2383 //Nothrow operations 2384 pointer const old_p = this->m_holder.start(); 2385 size_type const old_cap = this->m_holder.capacity(); 2386 boost::container::destroy_alloc_n(a, boost::movelib::to_raw_pointer(old_p), old_size); 2387 if (old_cap > 0) { 2388 this->m_holder.deallocate(old_p, old_cap); 2389 } 2390 m_holder.set_stored_size(old_size + added); 2391 this->m_holder.start(new_storage); 2392 this->m_holder.capacity(new_cap); 2393 new_buffer_deallocator.release(); 2394 new_values_destroyer.release(); 2395 } 2396 2397 BOOST_CONTAINER_FORCEINLINE bool room_enough() const 2398 { return this->m_holder.m_size != this->m_holder.capacity(); } 2399 2400 BOOST_CONTAINER_FORCEINLINE pointer back_ptr() const 2401 { return this->m_holder.start() + this->m_holder.m_size; } 2402 2403 BOOST_CONTAINER_FORCEINLINE size_type priv_index_of(pointer p) const 2404 { 2405 BOOST_ASSERT(this->m_holder.start() <= p); 2406 BOOST_ASSERT(p <= (this->m_holder.start()+this->size())); 2407 return static_cast<size_type>(p - this->m_holder.start()); 2408 } 2409 2410 template<class OtherA> 2411 void priv_move_assign(BOOST_RV_REF_BEG vector<T, OtherA, Options> BOOST_RV_REF_END x 2412 , typename dtl::enable_if_c 2413 < dtl::is_version<typename real_allocator<T, OtherA>::type, 0>::value >::type * = 0) 2414 { 2415 if(!dtl::is_same<typename real_allocator<T, OtherA>::type, allocator_type>::value && 2416 this->capacity() < x.size()){ 2417 alloc_holder_t::on_capacity_overflow(); 2418 } 2419 T* const this_start = this->priv_raw_begin(); 2420 T* const other_start = x.priv_raw_begin(); 2421 const size_type this_sz = m_holder.m_size; 2422 const size_type other_sz = static_cast<size_type>(x.m_holder.m_size); 2423 boost::container::move_assign_range_alloc_n(this->m_holder.alloc(), other_start, other_sz, this_start, this_sz); 2424 m_holder.set_stored_size(other_sz); 2425 //Not emptying the source container seems to be confusing for users as drop-in 2426 //replacement for non-static vectors, so clear it. 2427 x.clear(); 2428 } 2429 2430 template<class OtherA> 2431 void priv_move_assign(BOOST_RV_REF_BEG vector<T, OtherA, Options> BOOST_RV_REF_END x 2432 , typename dtl::disable_if_or 2433 < void 2434 , dtl::is_version<typename real_allocator<T, OtherA>::type, 0> 2435 , dtl::is_different<typename real_allocator<T, OtherA>::type, allocator_type> 2436 >::type * = 0) 2437 { 2438 //for move assignment, no aliasing (&x != this) is assumed. 2439 //x.size() == 0 is allowed for buggy std libraries. 2440 BOOST_ASSERT(this != &x || x.size() == 0); 2441 allocator_type &this_alloc = this->m_holder.alloc(); 2442 allocator_type &x_alloc = x.m_holder.alloc(); 2443 const bool propagate_alloc = allocator_traits_type::propagate_on_container_move_assignment::value; 2444 2445 //In this allocator move constructor the allocator maybe will be propagated -----------------------v 2446 const bool is_propagable_from_x = is_propagable_from(x_alloc, x.m_holder.start(), this_alloc, propagate_alloc); 2447 2448 //Resources can be transferred if both allocators are 2449 //going to be equal after this function (either propagated or already equal) 2450 if(is_propagable_from_x){ 2451 this->clear(); 2452 if(BOOST_LIKELY(!!this->m_holder.m_start)) 2453 this->m_holder.deallocate(this->m_holder.m_start, this->m_holder.m_capacity); 2454 this->m_holder.steal_resources(x.m_holder); 2455 } 2456 //Else do a one by one move. Also, clear the source as users find confusing 2457 //elements are still alive in the source container. 2458 else{ 2459 this->assign( boost::make_move_iterator(boost::movelib::iterator_to_raw_pointer(x.begin())) 2460 , boost::make_move_iterator(boost::movelib::iterator_to_raw_pointer(x.end() )) 2461 ); 2462 x.clear(); 2463 } 2464 //Move allocator if needed 2465 dtl::move_alloc(this_alloc, x_alloc, dtl::bool_<propagate_alloc>()); 2466 } 2467 2468 template<class OtherA> 2469 void priv_copy_assign(const vector<T, OtherA, Options> &x 2470 , typename dtl::enable_if_c 2471 < dtl::is_version<typename real_allocator<T, OtherA>::type, 0>::value >::type * = 0) 2472 { 2473 if(!dtl::is_same<typename real_allocator<T, OtherA>::type, allocator_type>::value && 2474 this->capacity() < x.size()){ 2475 alloc_holder_t::on_capacity_overflow(); 2476 } 2477 T* const this_start = this->priv_raw_begin(); 2478 T* const other_start = x.priv_raw_begin(); 2479 const size_type this_sz = m_holder.m_size; 2480 const size_type other_sz = static_cast<size_type>(x.m_holder.m_size); 2481 boost::container::copy_assign_range_alloc_n(this->m_holder.alloc(), other_start, other_sz, this_start, this_sz); 2482 m_holder.set_stored_size(other_sz); 2483 } 2484 2485 template<class OtherA> 2486 typename dtl::disable_if_or 2487 < void 2488 , dtl::is_version<typename real_allocator<T, OtherA>::type, 0> 2489 , dtl::is_different<typename real_allocator<T, OtherA>::type, allocator_type> 2490 >::type 2491 priv_copy_assign(const vector<T, OtherA, Options> &x) 2492 { 2493 allocator_type &this_alloc = this->m_holder.alloc(); 2494 const allocator_type &x_alloc = x.m_holder.alloc(); 2495 dtl::bool_<allocator_traits_type:: 2496 propagate_on_container_copy_assignment::value> flag; 2497 if(flag && this_alloc != x_alloc){ 2498 this->clear(); 2499 this->shrink_to_fit(); 2500 } 2501 dtl::assign_alloc(this_alloc, x_alloc, flag); 2502 this->assign( x.priv_raw_begin(), x.priv_raw_end() ); 2503 } 2504 2505 template<class Vector> //Template it to avoid it in explicit instantiations 2506 BOOST_CONTAINER_FORCEINLINE void priv_swap(Vector &x, dtl::true_type) //version_0 2507 { this->m_holder.deep_swap(x.m_holder); } 2508 2509 template<class Vector> //Template it to avoid it in explicit instantiations 2510 void priv_swap(Vector &x, dtl::false_type) //version_N 2511 { 2512 const bool propagate_alloc = allocator_traits_type::propagate_on_container_swap::value; 2513 if(are_swap_propagable( this->get_stored_allocator(), this->m_holder.start() 2514 , x.get_stored_allocator(), x.m_holder.start(), propagate_alloc)){ 2515 //Just swap internals 2516 this->m_holder.swap_resources(x.m_holder); 2517 } 2518 else{ 2519 if (BOOST_UNLIKELY(&x == this)) 2520 return; 2521 2522 //Else swap element by element... 2523 bool const t_smaller = this->size() < x.size(); 2524 vector &sml = t_smaller ? *this : x; 2525 vector &big = t_smaller ? x : *this; 2526 2527 size_type const common_elements = sml.size(); 2528 for(size_type i = 0; i != common_elements; ++i){ 2529 boost::adl_move_swap(sml[i], big[i]); 2530 } 2531 //... and move-insert the remaining range 2532 sml.insert( sml.cend() 2533 , boost::make_move_iterator(boost::movelib::iterator_to_raw_pointer(big.nth(common_elements))) 2534 , boost::make_move_iterator(boost::movelib::iterator_to_raw_pointer(big.end())) 2535 ); 2536 //Destroy remaining elements 2537 big.erase(big.nth(common_elements), big.cend()); 2538 } 2539 //And now swap the allocator 2540 dtl::swap_alloc(this->m_holder.alloc(), x.m_holder.alloc(), dtl::bool_<propagate_alloc>()); 2541 } 2542 2543 BOOST_CONTAINER_FORCEINLINE void priv_move_to_new_buffer(size_type, version_0) 2544 { alloc_holder_t::on_capacity_overflow(); } 2545 2546 BOOST_CONTAINER_FORCEINLINE dtl::insert_range_proxy<allocator_type, boost::move_iterator<T*>, T*> priv_dummy_empty_proxy() 2547 { 2548 return dtl::insert_range_proxy<allocator_type, boost::move_iterator<T*>, T*> 2549 (::boost::make_move_iterator((T *)0)); 2550 } 2551 2552 BOOST_CONTAINER_FORCEINLINE void priv_move_to_new_buffer(size_type new_cap, version_1) 2553 { 2554 //There is not enough memory, allocate a new buffer 2555 //Pass the hint so that allocators can take advantage of this. 2556 pointer const p = this->m_holder.allocate(new_cap); 2557 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS 2558 ++this->num_alloc; 2559 #endif 2560 //We will reuse insert code, so create a dummy input iterator 2561 this->priv_insert_forward_range_new_allocation 2562 ( boost::movelib::to_raw_pointer(p), new_cap, this->priv_raw_end(), 0, this->priv_dummy_empty_proxy()); 2563 } 2564 2565 void priv_move_to_new_buffer(size_type new_cap, version_2) 2566 { 2567 //There is not enough memory, allocate a new 2568 //buffer or expand the old one. 2569 bool same_buffer_start; 2570 size_type real_cap = 0; 2571 pointer reuse(this->m_holder.start()); 2572 pointer const ret(this->m_holder.allocation_command(allocate_new | expand_fwd | expand_bwd, new_cap, real_cap = new_cap, reuse)); 2573 2574 //Check for forward expansion 2575 same_buffer_start = reuse && this->m_holder.start() == ret; 2576 if(same_buffer_start){ 2577 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS 2578 ++this->num_expand_fwd; 2579 #endif 2580 this->m_holder.capacity(real_cap); 2581 } 2582 else{ //If there is no forward expansion, move objects, we will reuse insertion code 2583 T * const new_mem = boost::movelib::to_raw_pointer(ret); 2584 T * const ins_pos = this->priv_raw_end(); 2585 if(reuse){ //Backwards (and possibly forward) expansion 2586 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS 2587 ++this->num_expand_bwd; 2588 #endif 2589 this->priv_insert_forward_range_expand_backwards 2590 ( new_mem , real_cap, ins_pos, 0, this->priv_dummy_empty_proxy()); 2591 } 2592 else{ //New buffer 2593 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS 2594 ++this->num_alloc; 2595 #endif 2596 this->priv_insert_forward_range_new_allocation 2597 ( new_mem, real_cap, ins_pos, 0, this->priv_dummy_empty_proxy()); 2598 } 2599 } 2600 } 2601 2602 void priv_destroy_last_n(const size_type n) BOOST_NOEXCEPT_OR_NOTHROW 2603 { 2604 BOOST_ASSERT(n <= this->m_holder.m_size); 2605 boost::container::destroy_alloc_n(this->get_stored_allocator(), this->priv_raw_end() - n, n); 2606 this->m_holder.dec_stored_size(n); 2607 } 2608 2609 template<class InpIt> 2610 void priv_uninitialized_construct_at_end(InpIt first, InpIt last) 2611 { 2612 T* const old_end_pos = this->priv_raw_end(); 2613 T* const new_end_pos = boost::container::uninitialized_copy_alloc(this->m_holder.alloc(), first, last, old_end_pos); 2614 this->m_holder.inc_stored_size(static_cast<size_type>(new_end_pos - old_end_pos)); 2615 } 2616 2617 void priv_destroy_all() BOOST_NOEXCEPT_OR_NOTHROW 2618 { 2619 boost::container::destroy_alloc_n 2620 (this->get_stored_allocator(), this->priv_raw_begin(), this->m_holder.m_size); 2621 this->m_holder.m_size = 0; 2622 } 2623 2624 template<class U> 2625 BOOST_CONTAINER_FORCEINLINE iterator priv_insert(const const_iterator &p, BOOST_FWD_REF(U) u) 2626 { 2627 return this->emplace(p, ::boost::forward<U>(u)); 2628 } 2629 2630 template <class U> 2631 BOOST_CONTAINER_FORCEINLINE void priv_push_back(BOOST_FWD_REF(U) u) 2632 { 2633 this->emplace_back(::boost::forward<U>(u)); 2634 } 2635 2636 //Overload to support compiler errors that instantiate too much 2637 BOOST_CONTAINER_FORCEINLINE void priv_push_back(::boost::move_detail::nat) 2638 {} 2639 2640 BOOST_CONTAINER_FORCEINLINE iterator priv_insert(const_iterator, ::boost::move_detail::nat) 2641 { return iterator(); } 2642 2643 BOOST_CONTAINER_FORCEINLINE dtl::insert_n_copies_proxy<allocator_type, T*> priv_resize_proxy(const T &x) 2644 { return dtl::insert_n_copies_proxy<allocator_type, T*>(x); } 2645 2646 BOOST_CONTAINER_FORCEINLINE dtl::insert_default_initialized_n_proxy<allocator_type, T*> priv_resize_proxy(default_init_t) 2647 { return dtl::insert_default_initialized_n_proxy<allocator_type, T*>(); } 2648 2649 BOOST_CONTAINER_FORCEINLINE dtl::insert_value_initialized_n_proxy<allocator_type, T*> priv_resize_proxy(value_init_t) 2650 { return dtl::insert_value_initialized_n_proxy<allocator_type, T*>(); } 2651 2652 BOOST_CONTAINER_FORCEINLINE void priv_shrink_to_fit(version_0) BOOST_NOEXCEPT_OR_NOTHROW 2653 {} 2654 2655 void priv_shrink_to_fit(version_1) 2656 { 2657 const size_type cp = this->m_holder.capacity(); 2658 if(cp){ 2659 const size_type sz = this->size(); 2660 if(!sz){ 2661 if(BOOST_LIKELY(!!this->m_holder.m_start)) 2662 this->m_holder.deallocate(this->m_holder.m_start, cp); 2663 this->m_holder.m_start = pointer(); 2664 this->m_holder.m_capacity = 0; 2665 } 2666 else if(sz < cp){ 2667 this->priv_move_to_new_buffer(sz, alloc_version()); 2668 } 2669 } 2670 } 2671 2672 void priv_shrink_to_fit(version_2) BOOST_NOEXCEPT_OR_NOTHROW 2673 { 2674 const size_type cp = this->m_holder.capacity(); 2675 if(cp){ 2676 const size_type sz = this->size(); 2677 if(!sz){ 2678 if(BOOST_LIKELY(!!this->m_holder.m_start)) 2679 this->m_holder.deallocate(this->m_holder.m_start, cp); 2680 this->m_holder.m_start = pointer(); 2681 this->m_holder.m_capacity = 0; 2682 } 2683 else{ 2684 size_type received_size = sz; 2685 pointer reuse(this->m_holder.start()); 2686 if(this->m_holder.allocation_command 2687 (shrink_in_place | nothrow_allocation, cp, received_size, reuse)){ 2688 this->m_holder.capacity(received_size); 2689 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS 2690 ++this->num_shrink; 2691 #endif 2692 } 2693 } 2694 } 2695 } 2696 2697 template <class InsertionProxy> 2698 BOOST_CONTAINER_FORCEINLINE iterator priv_insert_forward_range_no_capacity 2699 (T * const, const size_type, const InsertionProxy , version_0) 2700 { 2701 return alloc_holder_t::on_capacity_overflow(), iterator(); 2702 } 2703 2704 template <class InsertionProxy> 2705 BOOST_CONTAINER_NOINLINE iterator priv_insert_forward_range_no_capacity 2706 (T *const raw_pos, const size_type n, const InsertionProxy insert_range_proxy, version_1) 2707 { 2708 //Check if we have enough memory or try to expand current memory 2709 const size_type n_pos = static_cast<size_type>(raw_pos - this->priv_raw_begin()); 2710 2711 const size_type new_cap = this->m_holder.template next_capacity<growth_factor_type>(n); 2712 //Pass the hint so that allocators can take advantage of this. 2713 T * const new_buf = boost::movelib::to_raw_pointer(this->m_holder.allocate(new_cap)); 2714 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS 2715 ++this->num_alloc; 2716 #endif 2717 this->priv_insert_forward_range_new_allocation(new_buf, new_cap, raw_pos, n, insert_range_proxy); 2718 return iterator(this->m_holder.start() + n_pos); 2719 } 2720 2721 template <class InsertionProxy> 2722 BOOST_CONTAINER_NOINLINE iterator priv_insert_forward_range_no_capacity 2723 (T *const raw_pos, const size_type n, const InsertionProxy insert_range_proxy, version_2) 2724 { 2725 //Check if we have enough memory or try to expand current memory 2726 const size_type n_pos = raw_pos - this->priv_raw_begin(); 2727 2728 //There is not enough memory, allocate a new 2729 //buffer or expand the old one. 2730 size_type real_cap = this->m_holder.template next_capacity<growth_factor_type>(n); 2731 pointer reuse(this->m_holder.start()); 2732 pointer const ret (this->m_holder.allocation_command 2733 (allocate_new | expand_fwd | expand_bwd, this->m_holder.m_size + n, real_cap, reuse)); 2734 2735 //Buffer reallocated 2736 if(reuse){ 2737 //Forward expansion, delay insertion 2738 if(this->m_holder.start() == ret){ 2739 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS 2740 ++this->num_expand_fwd; 2741 #endif 2742 this->m_holder.capacity(real_cap); 2743 //Expand forward 2744 this->priv_insert_forward_range_expand_forward 2745 (raw_pos, n, insert_range_proxy, dtl::bool_<dtl::is_single_value_proxy<InsertionProxy>::value>()); 2746 } 2747 //Backwards (and possibly forward) expansion 2748 else{ 2749 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS 2750 ++this->num_expand_bwd; 2751 #endif 2752 this->priv_insert_forward_range_expand_backwards 2753 (boost::movelib::to_raw_pointer(ret), real_cap, raw_pos, n, insert_range_proxy); 2754 } 2755 } 2756 //New buffer 2757 else{ 2758 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS 2759 ++this->num_alloc; 2760 #endif 2761 this->priv_insert_forward_range_new_allocation 2762 ( boost::movelib::to_raw_pointer(ret), real_cap, raw_pos, n, insert_range_proxy); 2763 } 2764 2765 return iterator(this->m_holder.start() + n_pos); 2766 } 2767 2768 template <class InsertionProxy> 2769 BOOST_CONTAINER_FORCEINLINE iterator priv_insert_forward_range 2770 (const pointer &pos, const size_type n, const InsertionProxy insert_range_proxy) 2771 { 2772 BOOST_ASSERT(this->m_holder.capacity() >= this->m_holder.m_size); 2773 T *const p = boost::movelib::to_raw_pointer(pos); 2774 //Check if we have enough memory or try to expand current memory 2775 if (BOOST_LIKELY(n <= (this->m_holder.capacity() - this->m_holder.m_size))){ 2776 //Expand forward 2777 this->priv_insert_forward_range_expand_forward 2778 (p, n, insert_range_proxy, dtl::bool_<dtl::is_single_value_proxy<InsertionProxy>::value>()); 2779 return iterator(pos); 2780 } 2781 else{ 2782 return this->priv_insert_forward_range_no_capacity(p, n, insert_range_proxy, alloc_version()); 2783 } 2784 } 2785 2786 template <class U> 2787 void priv_resize(const size_type new_size, const U &u, version_0) 2788 { 2789 const size_type sz = this->m_holder.m_size; 2790 if (new_size > this->capacity()){ 2791 //This will trigger an error 2792 alloc_holder_t::on_capacity_overflow(); 2793 } 2794 else if (new_size < sz){ 2795 //Destroy last elements 2796 this->priv_destroy_last_n(sz - new_size); 2797 } 2798 else{ 2799 T* const old_finish = this->priv_raw_end(); 2800 this->priv_resize_proxy(u).uninitialized_copy_n_and_update(this->m_holder.alloc(), old_finish, new_size - sz); 2801 this->m_holder.set_stored_size(new_size); 2802 } 2803 } 2804 2805 template <class U, class AllocVersion> 2806 void priv_resize(const size_type new_size, const U &u, AllocVersion) 2807 { 2808 const size_type sz = this->m_holder.m_size; 2809 if (new_size < sz){ 2810 //Destroy last elements 2811 this->priv_destroy_last_n(sz - new_size); 2812 } 2813 else { 2814 this->priv_insert_forward_range(this->back_ptr(), new_size - sz, this->priv_resize_proxy(u)); 2815 } 2816 } 2817 2818 //Takes the range pointed by [first_pos, last_pos) and shifts it to the right 2819 //by 'shift_count'. 'limit_pos' marks the end of constructed elements. 2820 // 2821 //Precondition: first_pos <= last_pos <= limit_pos 2822 // 2823 //The shift operation might cross limit_pos so elements to moved beyond limit_pos 2824 //are uninitialized_moved with an allocator. Other elements are moved. 2825 // 2826 //The shift operation might left uninitialized elements after limit_pos 2827 //and the number of uninitialized elements is returned by the function. 2828 // 2829 //Old situation: 2830 // first_pos last_pos old_limit 2831 // | | | 2832 // ____________V_______V__________________V_____________ 2833 //| prefix | range | suffix |raw_mem ~ 2834 //|____________|_______|__________________|_____________~ 2835 // 2836 //New situation in Case A (hole_size == 0): 2837 // range is moved through move assignments 2838 // 2839 // first_pos last_pos limit_pos 2840 // | | | 2841 // ____________V_______V__________________V_____________ 2842 //| prefix' | | | range |suffix'|raw_mem ~ 2843 //|________________+______|___^___|_______|_____________~ 2844 // | | 2845 // |_>_>_>_>_>^ 2846 // 2847 // 2848 //New situation in Case B (hole_size >= 0): 2849 // range is moved through uninitialized moves 2850 // 2851 // first_pos last_pos limit_pos 2852 // | | | 2853 // ____________V_______V__________________V________________ 2854 //| prefix' | | | [hole] | range | 2855 //|_______________________________________|________|___^___| 2856 // | | 2857 // |_>_>_>_>_>_>_>_>_>_>_>_>_>_>_>_>_>_^ 2858 // 2859 //New situation in Case C (hole_size == 0): 2860 // range is moved through move assignments and uninitialized moves 2861 // 2862 // first_pos last_pos limit_pos 2863 // | | | 2864 // ____________V_______V__________________V___ 2865 //| prefix' | | | range | 2866 //|___________________________________|___^___| 2867 // | | 2868 // |_>_>_>_>_>_>_>_>_>_>_>^ 2869 size_type priv_insert_ordered_at_shift_range 2870 (size_type first_pos, size_type last_pos, size_type limit_pos, size_type shift_count) 2871 { 2872 BOOST_ASSERT(first_pos <= last_pos); 2873 BOOST_ASSERT(last_pos <= limit_pos); 2874 // 2875 T* const begin_ptr = this->priv_raw_begin(); 2876 T* const first_ptr = begin_ptr + first_pos; 2877 T* const last_ptr = begin_ptr + last_pos; 2878 2879 size_type hole_size = 0; 2880 //Case A: 2881 if((last_pos + shift_count) <= limit_pos){ 2882 //All move assigned 2883 boost::container::move_backward(first_ptr, last_ptr, last_ptr + shift_count); 2884 } 2885 //Case B: 2886 else if((first_pos + shift_count) >= limit_pos){ 2887 //All uninitialized_moved 2888 ::boost::container::uninitialized_move_alloc 2889 (this->m_holder.alloc(), first_ptr, last_ptr, first_ptr + shift_count); 2890 hole_size = first_pos + shift_count - limit_pos; 2891 } 2892 //Case C: 2893 else{ 2894 //Some uninitialized_moved 2895 T* const limit_ptr = begin_ptr + limit_pos; 2896 T* const boundary_ptr = limit_ptr - shift_count; 2897 ::boost::container::uninitialized_move_alloc(this->m_holder.alloc(), boundary_ptr, last_ptr, limit_ptr); 2898 //The rest is move assigned 2899 boost::container::move_backward(first_ptr, boundary_ptr, limit_ptr); 2900 } 2901 return hole_size; 2902 } 2903 2904 private: 2905 BOOST_CONTAINER_FORCEINLINE T *priv_raw_begin() const 2906 { return boost::movelib::to_raw_pointer(m_holder.start()); } 2907 2908 BOOST_CONTAINER_FORCEINLINE T* priv_raw_end() const 2909 { return this->priv_raw_begin() + this->m_holder.m_size; } 2910 2911 template <class InsertionProxy> //inline single-element version as it is significantly smaller 2912 BOOST_CONTAINER_FORCEINLINE void priv_insert_forward_range_expand_forward 2913 (T* const raw_pos, const size_type, InsertionProxy insert_range_proxy, dtl::true_type) 2914 { 2915 BOOST_ASSERT(this->room_enough()); 2916 //There is enough memory 2917 T* const old_finish = this->priv_raw_end(); 2918 allocator_type & a = this->m_holder.alloc(); 2919 2920 if (old_finish == raw_pos){ 2921 insert_range_proxy.uninitialized_copy_n_and_update(a, old_finish, 1); 2922 ++this->m_holder.m_size; 2923 } 2924 else{ 2925 //New elements can be just copied. 2926 //Move to uninitialized memory last objects 2927 T * const before_old_finish = old_finish-1; 2928 2929 allocator_traits_type::construct(a, old_finish, ::boost::move(*before_old_finish)); 2930 ++this->m_holder.m_size; 2931 //Copy previous to last objects to the initialized end 2932 boost::container::move_backward(raw_pos, before_old_finish, old_finish); 2933 //Insert new objects in the raw_pos 2934 insert_range_proxy.copy_n_and_update(a, raw_pos, 1); 2935 } 2936 } 2937 2938 template <class InsertionProxy> 2939 BOOST_CONTAINER_FORCEINLINE void priv_insert_forward_range_expand_forward(T* const raw_pos, const size_type n, InsertionProxy insert_range_proxy, dtl::false_type) 2940 { 2941 //There is enough memory 2942 boost::container::expand_forward_and_insert_alloc 2943 ( this->m_holder.alloc(), raw_pos, this->priv_raw_end(), n, insert_range_proxy); 2944 this->m_holder.inc_stored_size(n); 2945 } 2946 2947 template <class InsertionProxy> 2948 void priv_insert_forward_range_new_allocation 2949 (T* const new_start, size_type new_cap, T* const pos, const size_type n, InsertionProxy insert_range_proxy) 2950 { 2951 //n can be zero, if we want to reallocate! 2952 allocator_type &a = this->m_holder.alloc(); 2953 T * const raw_old_buffer = this->priv_raw_begin(); 2954 2955 typename value_traits::ArrayDeallocator new_buffer_deallocator(new_start, a, new_cap); 2956 boost::container::uninitialized_move_and_insert_alloc 2957 (a, raw_old_buffer, pos, this->priv_raw_end(), new_start, n, insert_range_proxy); 2958 new_buffer_deallocator.release(); 2959 2960 //Destroy and deallocate old elements 2961 if(raw_old_buffer){ 2962 BOOST_IF_CONSTEXPR(!has_trivial_destructor_after_move<value_type>::value) 2963 boost::container::destroy_alloc_n(a, raw_old_buffer, this->m_holder.m_size); 2964 this->m_holder.deallocate(this->m_holder.start(), this->m_holder.capacity()); 2965 } 2966 2967 this->m_holder.start(new_start); 2968 this->m_holder.inc_stored_size(n); 2969 this->m_holder.capacity(new_cap); 2970 } 2971 2972 template <class InsertionProxy> 2973 void priv_insert_forward_range_expand_backwards 2974 (T* const new_start, const size_type new_capacity, 2975 T* const pos, const size_type n, InsertionProxy insert_range_proxy) 2976 { 2977 //n can be zero to just expand capacity 2978 //Backup old data 2979 T* const old_start = this->priv_raw_begin(); 2980 const size_type old_size = this->m_holder.m_size; 2981 T* const old_finish = old_start + old_size; 2982 allocator_type &a = this->m_holder.alloc(); 2983 2984 //Update the vector buffer information to a safe state 2985 this->m_holder.start(new_start); 2986 this->m_holder.capacity(new_capacity); 2987 this->m_holder.m_size = 0; 2988 2989 //We can have 8 possibilities: 2990 const size_type elemsbefore = static_cast<size_type>(pos - old_start); 2991 const size_type s_before = static_cast<size_type>(old_start - new_start); 2992 const size_type before_plus_new = elemsbefore + n; 2993 2994 typedef typename value_traits::ArrayDestructor array_destructor_t; 2995 2996 //If anything goes wrong, this object will destroy 2997 //all the old objects to fulfill previous vector state 2998 array_destructor_t old_values_destroyer(old_start, a, old_size); 2999 //Check if s_before is big enough to hold the beginning of old data + new data 3000 if(s_before >= before_plus_new){ 3001 //Copy first old values before pos, after that the new objects 3002 T *const new_elem_pos = 3003 ::boost::container::uninitialized_move_alloc(a, old_start, pos, new_start); 3004 this->m_holder.set_stored_size(elemsbefore); 3005 insert_range_proxy.uninitialized_copy_n_and_update(a, new_elem_pos, n); 3006 this->m_holder.set_stored_size(before_plus_new); 3007 const size_type new_size = old_size + n; 3008 //Check if s_before is so big that even copying the old data + new data 3009 //there is a gap between the new data and the old data 3010 if(s_before >= new_size){ 3011 //Old situation: 3012 // _________________________________________________________ 3013 //| raw_mem | old_begin | old_end | 3014 //| __________________________________|___________|_________| 3015 // 3016 //New situation: 3017 // _________________________________________________________ 3018 //| old_begin | new | old_end | raw_mem | 3019 //|___________|__________|_________|________________________| 3020 // 3021 //Now initialize the rest of memory with the last old values 3022 if(before_plus_new != new_size){ //Special case to avoid operations in back insertion 3023 ::boost::container::uninitialized_move_alloc(a, pos, old_finish, new_start + before_plus_new); 3024 //All new elements correctly constructed, avoid new element destruction 3025 this->m_holder.set_stored_size(new_size); 3026 } 3027 //Old values destroyed automatically with "old_values_destroyer" 3028 //when "old_values_destroyer" goes out of scope unless the have trivial 3029 //destructor after move. 3030 BOOST_IF_CONSTEXPR(value_traits::trivial_dctr_after_move) 3031 old_values_destroyer.release(); 3032 } 3033 //s_before is so big that divides old_end 3034 else{ 3035 //Old situation: 3036 // __________________________________________________ 3037 //| raw_mem | old_begin | old_end | 3038 //| ___________________________|___________|_________| 3039 // 3040 //New situation: 3041 // __________________________________________________ 3042 //| old_begin | new | old_end | raw_mem | 3043 //|___________|__________|_________|_________________| 3044 // 3045 //Now initialize the rest of memory with the last old values 3046 //All new elements correctly constructed, avoid new element destruction 3047 BOOST_IF_CONSTEXPR(!value_traits::trivial_dctr){ 3048 const size_type raw_gap = s_before - before_plus_new; 3049 //Now initialize the rest of s_before memory with the 3050 //first of elements after new values 3051 ::boost::container::uninitialized_move_alloc_n(a, pos, raw_gap, new_start + before_plus_new); 3052 //Now we have a contiguous buffer so program trailing element destruction 3053 //and update size to the final size. 3054 old_values_destroyer.shrink_forward(new_size-s_before); 3055 this->m_holder.set_stored_size(new_size); 3056 //Now move remaining last objects in the old buffer begin 3057 T * const remaining_pos = pos + raw_gap; 3058 if(remaining_pos != old_start){ //Make sure data has to be moved 3059 ::boost::container::move(remaining_pos, old_finish, old_start); 3060 } 3061 //Once moved, avoid calling the destructors if trivial after move 3062 BOOST_IF_CONSTEXPR(value_traits::trivial_dctr_after_move){ 3063 old_values_destroyer.release(); 3064 } 3065 } 3066 else{ //If trivial destructor, we can uninitialized copy + copy in a single uninitialized copy 3067 ::boost::container::uninitialized_move_alloc_n 3068 (a, pos, static_cast<size_type>(old_finish - pos), new_start + before_plus_new); 3069 this->m_holder.set_stored_size(new_size); 3070 old_values_destroyer.release(); 3071 } 3072 } 3073 } 3074 else{ 3075 //Check if we have to do the insertion in two phases 3076 //since maybe s_before is not big enough and 3077 //the buffer was expanded both sides 3078 // 3079 //Old situation: 3080 // _________________________________________________ 3081 //| raw_mem | old_begin + old_end | raw_mem | 3082 //|_________|_____________________|_________________| 3083 // 3084 //New situation with do_after: 3085 // _________________________________________________ 3086 //| old_begin + new + old_end | raw_mem | 3087 //|___________________________________|_____________| 3088 // 3089 //New without do_after: 3090 // _________________________________________________ 3091 //| old_begin + new + old_end | raw_mem | 3092 //|____________________________|____________________| 3093 // 3094 const bool do_after = n > s_before; 3095 3096 //Now we can have two situations: the raw_mem of the 3097 //beginning divides the old_begin, or the new elements: 3098 if (s_before <= elemsbefore) { 3099 //The raw memory divides the old_begin group: 3100 // 3101 //If we need two phase construction (do_after) 3102 //new group is divided in new = new_beg + new_end groups 3103 //In this phase only new_beg will be inserted 3104 // 3105 //Old situation: 3106 // _________________________________________________ 3107 //| raw_mem | old_begin | old_end | raw_mem | 3108 //|_________|___________|_________|_________________| 3109 // 3110 //New situation with do_after(1): 3111 //This is not definitive situation, the second phase 3112 //will include 3113 // _________________________________________________ 3114 //| old_begin | new_beg | old_end | raw_mem | 3115 //|___________|_________|_________|_________________| 3116 // 3117 //New situation without do_after: 3118 // _________________________________________________ 3119 //| old_begin | new | old_end | raw_mem | 3120 //|___________|_____|_________|_____________________| 3121 // 3122 //Copy the first part of old_begin to raw_mem 3123 ::boost::container::uninitialized_move_alloc_n(a, old_start, s_before, new_start); 3124 //The buffer is all constructed until old_end, 3125 //so program trailing destruction and assign final size 3126 //if !do_after, s_before+n otherwise. 3127 size_type new_1st_range; 3128 if(do_after){ 3129 new_1st_range = s_before; 3130 //release destroyer and update size 3131 old_values_destroyer.release(); 3132 } 3133 else{ 3134 new_1st_range = n; 3135 BOOST_IF_CONSTEXPR(value_traits::trivial_dctr_after_move){ 3136 old_values_destroyer.release(); 3137 } 3138 else{ 3139 old_values_destroyer.shrink_forward(old_size - (s_before - n)); 3140 } 3141 } 3142 this->m_holder.set_stored_size(old_size + new_1st_range); 3143 //Now copy the second part of old_begin overwriting itself 3144 T *const next = ::boost::container::move(old_start + s_before, pos, old_start); 3145 //Now copy the new_beg elements 3146 insert_range_proxy.copy_n_and_update(a, next, new_1st_range); 3147 3148 //If there is no after work and the last old part needs to be moved to front, do it 3149 if(!do_after && (n != s_before)){ 3150 //Now displace old_end elements 3151 ::boost::container::move(pos, old_finish, next + new_1st_range); 3152 } 3153 } 3154 else { 3155 //If we have to expand both sides, 3156 //we will play if the first new values so 3157 //calculate the upper bound of new values 3158 3159 //The raw memory divides the new elements 3160 // 3161 //If we need two phase construction (do_after) 3162 //new group is divided in new = new_beg + new_end groups 3163 //In this phase only new_beg will be inserted 3164 // 3165 //Old situation: 3166 // _______________________________________________________ 3167 //| raw_mem | old_begin | old_end | raw_mem | 3168 //|_______________|___________|_________|_________________| 3169 // 3170 //New situation with do_after(): 3171 // ____________________________________________________ 3172 //| old_begin | new_beg | old_end | raw_mem | 3173 //|___________|_______________|_________|______________| 3174 // 3175 //New situation without do_after: 3176 // ______________________________________________________ 3177 //| old_begin | new | old_end | raw_mem | 3178 //|___________|_____|_________|__________________________| 3179 // 3180 //First copy whole old_begin and part of new to raw_mem 3181 T * const new_pos = ::boost::container::uninitialized_move_alloc 3182 (a, old_start, pos, new_start); 3183 this->m_holder.set_stored_size(elemsbefore); 3184 const size_type mid_n = s_before - elemsbefore; 3185 insert_range_proxy.uninitialized_copy_n_and_update(a, new_pos, mid_n); 3186 //The buffer is all constructed until old_end, 3187 //release destroyer 3188 this->m_holder.set_stored_size(old_size + s_before); 3189 old_values_destroyer.release(); 3190 3191 if(do_after){ 3192 //Copy new_beg part 3193 insert_range_proxy.copy_n_and_update(a, old_start, elemsbefore); 3194 } 3195 else{ 3196 //Copy all new elements 3197 const size_type rest_new = n - mid_n; 3198 insert_range_proxy.copy_n_and_update(a, old_start, rest_new); 3199 3200 T* const move_start = old_start + rest_new; 3201 //Displace old_end, but make sure data has to be moved 3202 T* const move_end = move_start != pos ? ::boost::container::move(pos, old_finish, move_start) 3203 : old_finish; 3204 (void)move_end; //To avoid warnings of unused initialization for move_end in case 3205 //trivial_dctr_after_move is true 3206 //Destroy remaining moved elements from old_end except if they 3207 //have trivial destructor after being moved 3208 const size_type n_destroy = s_before - n; 3209 BOOST_IF_CONSTEXPR(!value_traits::trivial_dctr_after_move){ 3210 boost::container::destroy_alloc_n(a, move_end, n_destroy); 3211 } 3212 this->m_holder.dec_stored_size(n_destroy); 3213 } 3214 } 3215 3216 //This is only executed if two phase construction is needed 3217 if(do_after){ 3218 //The raw memory divides the new elements 3219 // 3220 //Old situation: 3221 // ______________________________________________________ 3222 //| raw_mem | old_begin | old_end | raw_mem | 3223 //|______________|___________|____________|______________| 3224 // 3225 //New situation with do_after(1): 3226 // _______________________________________________________ 3227 //| old_begin + new_beg | new_end |old_end | raw_mem | 3228 //|__________________________|_________|________|_________| 3229 // 3230 //New situation with do_after(2): 3231 // ______________________________________________________ 3232 //| old_begin + new | old_end |raw | 3233 //|_______________________________________|_________|____| 3234 // 3235 const size_type n_after = n - s_before; 3236 const size_type elemsafter = old_size - elemsbefore; 3237 3238 //We can have two situations: 3239 if (elemsafter >= n_after){ 3240 //The raw_mem from end will divide displaced old_end 3241 // 3242 //Old situation: 3243 // ______________________________________________________ 3244 //| raw_mem | old_begin | old_end | raw_mem | 3245 //|______________|___________|____________|______________| 3246 // 3247 //New situation with do_after(1): 3248 // _______________________________________________________ 3249 //| old_begin + new_beg | new_end |old_end | raw_mem | 3250 //|__________________________|_________|________|_________| 3251 // 3252 //First copy the part of old_end raw_mem 3253 T* finish_n = old_finish - n_after; 3254 ::boost::container::uninitialized_move_alloc(a, finish_n, old_finish, old_finish); 3255 this->m_holder.inc_stored_size(n_after); 3256 //Displace the rest of old_end to the new position 3257 boost::container::move_backward(pos, finish_n, old_finish); 3258 //Now overwrite with new_end 3259 //The new_end part is [first + (n - n_after), last) 3260 insert_range_proxy.copy_n_and_update(a, pos, n_after); 3261 } 3262 else { 3263 //The raw_mem from end will divide new_end part 3264 // 3265 //Old situation: 3266 // _____________________________________________________________ 3267 //| raw_mem | old_begin | old_end | raw_mem | 3268 //|______________|___________|____________|_____________________| 3269 // 3270 //New situation with do_after(2): 3271 // _____________________________________________________________ 3272 //| old_begin + new_beg | new_end |old_end | raw_mem | 3273 //|__________________________|_______________|________|_________| 3274 3275 //First initialize data in raw memory 3276 const size_type mid_last_dist = n_after - elemsafter; 3277 3278 //Copy to the old_end part to the uninitialized zone leaving a gap. 3279 ::boost::container::uninitialized_move_alloc(a, pos, old_finish, old_finish + mid_last_dist); 3280 3281 array_destructor_t old_end_destroyer(old_finish + mid_last_dist, a, static_cast<size_type>(old_finish - pos)); 3282 3283 //Copy the first part to the already constructed old_end zone 3284 insert_range_proxy.copy_n_and_update(a, pos, elemsafter); 3285 //Copy the rest to the uninitialized zone filling the gap 3286 insert_range_proxy.uninitialized_copy_n_and_update(a, old_finish, mid_last_dist); 3287 this->m_holder.inc_stored_size(n_after); 3288 old_end_destroyer.release(); 3289 } 3290 } 3291 } 3292 } 3293 3294 void priv_throw_if_out_of_range(size_type n) const 3295 { 3296 //If n is out of range, throw an out_of_range exception 3297 if (n >= this->size()){ 3298 throw_out_of_range("vector::at out of range"); 3299 } 3300 } 3301 3302 BOOST_CONTAINER_FORCEINLINE bool priv_in_range(const_iterator pos) const 3303 { 3304 return (this->begin() <= pos) && (pos < this->end()); 3305 } 3306 3307 BOOST_CONTAINER_FORCEINLINE bool priv_in_range_or_end(const_iterator pos) const 3308 { 3309 return (this->begin() <= pos) && (pos <= this->end()); 3310 } 3311 3312 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS 3313 public: 3314 unsigned int num_expand_fwd; 3315 unsigned int num_expand_bwd; 3316 unsigned int num_shrink; 3317 unsigned int num_alloc; 3318 void reset_alloc_stats() 3319 { num_expand_fwd = num_expand_bwd = num_alloc = 0, num_shrink = 0; } 3320 #endif 3321 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 3322 }; 3323 3324 #ifndef BOOST_CONTAINER_NO_CXX17_CTAD 3325 3326 template <typename InputIterator> 3327 vector(InputIterator, InputIterator) -> 3328 vector<typename iterator_traits<InputIterator>::value_type>; 3329 3330 template <typename InputIterator, typename Allocator> 3331 vector(InputIterator, InputIterator, Allocator const&) -> 3332 vector<typename iterator_traits<InputIterator>::value_type, Allocator>; 3333 3334 #endif 3335 3336 3337 }} //namespace boost::container 3338 3339 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 3340 3341 namespace boost { 3342 3343 //!has_trivial_destructor_after_move<> == true_type 3344 //!specialization for optimizations 3345 template <class T, class Allocator, class Options> 3346 struct has_trivial_destructor_after_move<boost::container::vector<T, Allocator, Options> > 3347 { 3348 typedef typename boost::container::vector<T, Allocator, Options>::allocator_type allocator_type; 3349 typedef typename ::boost::container::allocator_traits<allocator_type>::pointer pointer; 3350 static const bool value = ::boost::has_trivial_destructor_after_move<allocator_type>::value && 3351 ::boost::has_trivial_destructor_after_move<pointer>::value; 3352 }; 3353 3354 } 3355 3356 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 3357 3358 #include <boost/container/detail/config_end.hpp> 3359 3360 #endif // #ifndef BOOST_CONTAINER_CONTAINER_VECTOR_HPP 3361