1 ////////////////////////////////////////////////////////////////////////////// 2 // 3 // (C) Copyright Benedek Thaler 2015-2016 4 // (C) Copyright Ion Gaztanaga 2019-2020. Distributed under the Boost 5 // Software License, Version 1.0. (See accompanying file 6 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 7 // 8 // See http://www.boost.org/libs/container for documentation. 9 // 10 ////////////////////////////////////////////////////////////////////////////// 11 12 #ifndef BOOST_CONTAINER_DEVECTOR_HPP 13 #define BOOST_CONTAINER_DEVECTOR_HPP 14 15 #include <boost/container/detail/config_begin.hpp> 16 #include <boost/container/detail/workaround.hpp> 17 18 //#include <algorithm> 19 #include <cstring> // memcpy 20 21 #include <boost/assert.hpp> 22 #include <boost/aligned_storage.hpp> 23 24 #include <boost/container/detail/copy_move_algo.hpp> 25 #include <boost/container/new_allocator.hpp> //new_allocator 26 #include <boost/container/allocator_traits.hpp> //allocator_traits 27 #include <boost/container/detail/algorithm.hpp> //equal() 28 #include <boost/container/throw_exception.hpp> 29 #include <boost/container/options.hpp> 30 31 #include <boost/container/detail/guards_dended.hpp> 32 #include <boost/container/detail/iterator.hpp> 33 #include <boost/container/detail/iterators.hpp> 34 #include <boost/container/detail/destroyers.hpp> 35 #include <boost/container/detail/min_max.hpp> 36 #include <boost/container/detail/next_capacity.hpp> 37 #include <boost/container/detail/alloc_helpers.hpp> 38 39 // move 40 #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 41 #include <boost/move/detail/fwd_macros.hpp> 42 #endif 43 #include <boost/move/detail/move_helpers.hpp> 44 #include <boost/move/adl_move_swap.hpp> 45 #include <boost/move/iterator.hpp> 46 #include <boost/move/traits.hpp> 47 #include <boost/move/utility_core.hpp> 48 #include <boost/move/detail/to_raw_pointer.hpp> 49 #include <boost/move/algo/detail/merge.hpp> 50 51 #include <boost/type_traits/is_nothrow_move_constructible.hpp> 52 53 //std 54 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 55 #include <initializer_list> //for std::initializer_list 56 #endif 57 58 namespace boost { 59 namespace container { 60 61 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 62 63 struct growth_factor_60; 64 65 template<class Options, class AllocatorSizeType> 66 struct get_devector_opt 67 { 68 typedef devector_opt< typename default_if_void<typename Options::growth_factor_type, growth_factor_60>::type 69 , typename default_if_void<typename Options::stored_size_type, AllocatorSizeType>::type 70 > type; 71 }; 72 73 template<class AllocatorSizeType> 74 struct get_devector_opt<void, AllocatorSizeType> 75 { 76 typedef vector_opt<growth_factor_60, AllocatorSizeType> type; 77 }; 78 79 #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 80 81 struct reserve_only_tag_t {}; 82 //struct unsafe_uninitialized_tag_t {}; 83 84 /** 85 * A vector-like sequence container providing front and back operations 86 * (e.g: `push_front`/`pop_front`/`push_back`/`pop_back`) with amortized constant complexity 87 * and unsafe methods geared towards additional performance. 88 * 89 * Models the [SequenceContainer], [ReversibleContainer], and [AllocatorAwareContainer] concepts. 90 * 91 * **Requires**: 92 * - `T` shall be [MoveInsertable] into the devector. 93 * - `T` shall be [Erasable] from any `devector<T, allocator_type, GP>`. 94 * - `GrowthFactor`, and `Allocator` must model the concepts with the same names or be void. 95 * 96 * **Definition**: `T` is `NothrowConstructible` if it's either nothrow move constructible or 97 * nothrow copy constructible. 98 * 99 * **Definition**: `T` is `NothrowAssignable` if it's either nothrow move assignable or 100 * nothrow copy assignable. 101 * 102 * **Exceptions**: The exception specifications assume `T` is nothrow [Destructible]. 103 * 104 * Most methods providing the strong exception guarantee assume `T` either has a move 105 * constructor marked noexcept or is [CopyInsertable] into the devector. If it isn't true, 106 * and the move constructor throws, the guarantee is waived and the effects are unspecified. 107 * 108 * In addition to the exceptions specified in the **Throws** clause, the following operations 109 * of `T` can throw when any of the specified concept is required: 110 * - [DefaultInsertable][]: Default constructor 111 * - [MoveInsertable][]: Move constructor 112 * - [CopyInsertable][]: Copy constructor 113 * - [DefaultConstructible][]: Default constructor 114 * - [EmplaceConstructible][]: Constructor selected by the given arguments 115 * - [MoveAssignable][]: Move assignment operator 116 * - [CopyAssignable][]: Copy assignment operator 117 * 118 * Furthermore, not `noexcept` methods throws whatever the allocator throws 119 * if memory allocation fails. Such methods also throw `length_error` if the capacity 120 * exceeds `max_size()`. 121 * 122 * **Remark**: If a method invalidates some iterators, it also invalidates references 123 * and pointers to the elements pointed by the invalidated iterators. 124 * 125 * **Policies**: 126 * 127 * @ref devector_growth_policy models the `GrowthFactor` concept. 128 * 129 * [SequenceContainer]: http://en.cppreference.com/w/cpp/concept/SequenceContainer 130 * [ReversibleContainer]: http://en.cppreference.com/w/cpp/concept/ReversibleContainer 131 * [AllocatorAwareContainer]: http://en.cppreference.com/w/cpp/concept/AllocatorAwareContainer 132 * [DefaultInsertable]: http://en.cppreference.com/w/cpp/concept/DefaultInsertable 133 * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable 134 * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable 135 * [Erasable]: http://en.cppreference.com/w/cpp/concept/Erasable 136 * [DefaultConstructible]: http://en.cppreference.com/w/cpp/concept/DefaultConstructible 137 * [Destructible]: http://en.cppreference.com/w/cpp/concept/Destructible 138 * [EmplaceConstructible]: http://en.cppreference.com/w/cpp/concept/EmplaceConstructible 139 * [MoveAssignable]: http://en.cppreference.com/w/cpp/concept/MoveAssignable 140 * [CopyAssignable]: http://en.cppreference.com/w/cpp/concept/CopyAssignable 141 */ 142 template < typename T, class A BOOST_CONTAINER_DOCONLY(= void), class Options BOOST_CONTAINER_DOCONLY(= void)> 143 class devector 144 { 145 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 146 typedef boost::container::allocator_traits 147 <typename real_allocator<T, A>::type> allocator_traits_type; 148 typedef typename allocator_traits_type::size_type alloc_size_type; 149 typedef typename get_devector_opt<Options, alloc_size_type>::type options_type; 150 typedef typename options_type::growth_factor_type growth_factor_type; 151 typedef typename options_type::stored_size_type stored_size_type; 152 153 #endif // ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 154 155 public: 156 // Standard Interface Types: 157 typedef T value_type; 158 typedef BOOST_CONTAINER_IMPDEF 159 (typename real_allocator<T BOOST_MOVE_I A>::type) allocator_type; 160 typedef allocator_type stored_allocator_type; 161 typedef typename allocator_traits<allocator_type>::pointer pointer; 162 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 163 typedef typename allocator_traits<allocator_type>::reference reference; 164 typedef typename allocator_traits<allocator_type>::const_reference const_reference; 165 typedef typename allocator_traits<allocator_type>::size_type size_type; 166 typedef typename allocator_traits<allocator_type>::difference_type difference_type; 167 typedef pointer iterator; 168 typedef const_pointer const_iterator; 169 typedef BOOST_CONTAINER_IMPDEF 170 (boost::container::reverse_iterator<iterator>) reverse_iterator; 171 typedef BOOST_CONTAINER_IMPDEF 172 (boost::container::reverse_iterator<const_iterator>) const_reverse_iterator; 173 174 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 175 private: 176 BOOST_COPYABLE_AND_MOVABLE(devector) 177 178 // Guard to deallocate buffer on exception 179 typedef typename detail::allocation_guard<allocator_type> allocation_guard; 180 181 // Random access pseudo iterator always yielding to the same result 182 typedef constant_iterator<T, difference_type> cvalue_iterator; 183 184 #endif // ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 185 186 // Standard Interface 187 public: 188 // construct/copy/destroy 189 190 /** 191 * **Effects**: Constructs an empty devector. 192 * 193 * **Postcondition**: `empty() && front_free_capacity() == 0 194 * && back_free_capacity() == 0`. 195 * 196 * **Complexity**: Constant. 197 */ devector()198 devector() BOOST_NOEXCEPT 199 : m_() 200 {} 201 202 /** 203 * **Effects**: Constructs an empty devector, using the specified allocator. 204 * 205 * **Postcondition**: `empty() && front_free_capacity() == 0 206 * && back_free_capacity() == 0`. 207 * 208 * **Complexity**: Constant. 209 */ devector(const allocator_type & allocator)210 explicit devector(const allocator_type& allocator) BOOST_NOEXCEPT 211 : m_(allocator) 212 {} 213 214 /** 215 * **Effects**: Constructs an empty devector, using the specified allocator 216 * and reserves `n` slots as if `reserve(n)` was called. 217 * 218 * **Postcondition**: `empty() && front_free_capacity() == 0 219 * && back_free_capacity() >= n`. 220 * 221 * **Exceptions**: Strong exception guarantee. 222 * 223 * **Complexity**: Constant. 224 */ devector(size_type n,reserve_only_tag_t,const allocator_type & allocator=allocator_type ())225 devector(size_type n, reserve_only_tag_t, const allocator_type& allocator = allocator_type()) 226 : m_(allocator, this->allocate(n), 0u, 0u, n) 227 {} 228 229 /** 230 * **Effects**: Constructs an empty devector, using the specified allocator 231 * and reserves `front_cap + back_cap` slots as if `reserve_front(front_cap)` and 232 * `reserve_back(back_cap)` was called. 233 * 234 * **Postcondition**: `empty() && front_free_capacity() == front_cap 235 * && back_free_capacity() >= back_cap`. 236 * 237 * **Exceptions**: Strong exception guarantee. 238 * 239 * **Complexity**: Constant. 240 */ devector(size_type front_cap,size_type back_cap,reserve_only_tag_t,const allocator_type & allocator=allocator_type ())241 devector(size_type front_cap, size_type back_cap, reserve_only_tag_t, const allocator_type& allocator = allocator_type()) 242 : m_(allocator, this->allocate(front_cap + back_cap), front_cap, front_cap, front_cap + back_cap) 243 {} 244 245 /** 246 * [DefaultInsertable]: http://en.cppreference.com/w/cpp/concept/DefaultInsertable 247 * 248 * **Effects**: Constructs a devector with `n` default-inserted elements using the specified allocator. 249 * 250 * **Requires**: `T` shall be [DefaultInsertable] into `*this`. 251 * 252 * **Postcondition**: `size() == n && front_free_capacity() == 0`. 253 * 254 * **Exceptions**: Strong exception guarantee. 255 * 256 * **Complexity**: Linear in `n`. 257 */ devector(size_type n,const allocator_type & allocator=allocator_type ())258 explicit devector(size_type n, const allocator_type& allocator = allocator_type()) 259 : m_(allocator, n ? allocate(n): pointer(), 0u, n, n) 260 { 261 // Cannot use construct_from_range/constant_iterator and copy_range, 262 // because we are not allowed to default construct T 263 allocation_guard buffer_guard(m_.buffer, m_.capacity, get_allocator_ref()); 264 detail::construction_guard<allocator_type> copy_guard(m_.buffer, get_allocator_ref()); 265 266 for (size_type i = 0; i < n; ++i) 267 { 268 this->alloc_construct(m_.buffer + i); 269 copy_guard.extend(); 270 } 271 272 copy_guard.release(); 273 buffer_guard.release(); 274 275 BOOST_ASSERT(invariants_ok()); 276 } 277 278 /** 279 * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable 280 * 281 * **Effects**: Constructs a devector with `n` copies of `value`, using the specified allocator. 282 * 283 * **Requires**: `T` shall be [CopyInsertable] into `*this`. 284 * 285 * **Postcondition**: `size() == n && front_free_capacity() == 0`. 286 * 287 * **Exceptions**: Strong exception guarantee. 288 * 289 * **Complexity**: Linear in `n`. 290 */ devector(size_type n,const T & value,const allocator_type & allocator=allocator_type ())291 devector(size_type n, const T& value, const allocator_type& allocator = allocator_type()) 292 : m_(allocator, n ? allocate(n): pointer(), 0u, n, n) 293 { 294 construct_from_range(cvalue_iterator(value, n), cvalue_iterator()); 295 BOOST_ASSERT(invariants_ok()); 296 } 297 298 /** 299 * **Effects**: Constructs a devector equal to the range `[first,last)`, using the specified allocator. 300 * 301 * **Requires**: `T` shall be [EmplaceConstructible] into `*this` from `*first`. If the specified 302 * iterator does not meet the forward iterator requirements, `T` shall also be [MoveInsertable] 303 * into `*this`. 304 * 305 * **Postcondition**: `size() == boost::container::iterator_distance(first, last) 306 * 307 * **Exceptions**: Strong exception guarantee. 308 * 309 * **Complexity**: Makes only `N` calls to the copy constructor of `T` (where `N` is the distance between `first` 310 * and `last`), at most one allocation and no reallocations if iterators first and last are of forward, 311 * bidirectional, or random access categories. It makes `O(N)` calls to the copy constructor of `T` 312 * and `O(log(N)) reallocations if they are just input iterators. 313 * 314 * **Remarks**: Each iterator in the range `[first,last)` shall be dereferenced exactly once, 315 * unless an exception is thrown. 316 * 317 * [EmplaceConstructible]: http://en.cppreference.com/w/cpp/concept/EmplaceConstructible 318 * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable 319 */ 320 template <class InputIterator> devector(InputIterator first,InputIterator last,const allocator_type & allocator=allocator_type ()BOOST_CONTAINER_DOCIGN (BOOST_MOVE_I typename dtl::disable_if_or<void BOOST_MOVE_I dtl::is_convertible<InputIterator BOOST_MOVE_I size_type> BOOST_MOVE_I dtl::is_not_input_iterator<InputIterator>>::type * =0))321 devector(InputIterator first, InputIterator last, const allocator_type& allocator = allocator_type() 322 //Input iterators 323 BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_or 324 < void 325 BOOST_MOVE_I dtl::is_convertible<InputIterator BOOST_MOVE_I size_type> 326 BOOST_MOVE_I dtl::is_not_input_iterator<InputIterator> 327 >::type * = 0) 328 ) 329 : m_(allocator, pointer(), 0u, 0u, 0u) 330 { 331 while (first != last) { 332 this->emplace_back(*first++); 333 } 334 335 BOOST_ASSERT(invariants_ok()); 336 } 337 338 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 339 340 template <class ForwardIterator> devector(ForwardIterator first,ForwardIterator last,const allocator_type & allocator=allocator_type ()BOOST_CONTAINER_DOCIGN (BOOST_MOVE_I typename dtl::disable_if_or<void BOOST_MOVE_I dtl::is_convertible<ForwardIterator BOOST_MOVE_I size_type> BOOST_MOVE_I dtl::is_input_iterator<ForwardIterator>>::type * =0))341 devector(ForwardIterator first, ForwardIterator last, const allocator_type& allocator = allocator_type() 342 //Other iterators 343 BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_or 344 < void 345 BOOST_MOVE_I dtl::is_convertible<ForwardIterator BOOST_MOVE_I size_type> 346 BOOST_MOVE_I dtl::is_input_iterator<ForwardIterator> 347 >::type * = 0) 348 ) 349 : m_(allocator, pointer(), 0u, 0u, 0u) 350 { 351 const size_type n = boost::container::iterator_distance(first, last); 352 m_.buffer = n ? allocate(n) : pointer(); 353 m_.front_idx = 0u; 354 //this->allocate(n) will take care of overflows 355 m_.set_back_idx(n); 356 m_.set_capacity(n); 357 //construct_from_range releases memory on failure 358 this->construct_from_range(first, last); 359 BOOST_ASSERT(invariants_ok()); 360 } 361 362 #endif // ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 363 364 /** 365 * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable 366 * 367 * **Effects**: Copy constructs a devector. 368 * 369 * **Requires**: `T` shall be [CopyInsertable] into `*this`. 370 * 371 * **Postcondition**: `this->size() == x.size() && front_free_capacity() == 0`. 372 * 373 * **Exceptions**: Strong exception guarantee. 374 * 375 * **Complexity**: Linear in the size of `x`. 376 */ devector(const devector & x)377 devector(const devector& x) 378 : m_( allocator_traits_type::select_on_container_copy_construction(x.get_allocator_ref()) 379 , pointer(), 0u, 0u, 0u) 380 { 381 const size_type n = x.size(); 382 m_.buffer = n ? allocate(n) : pointer(); 383 m_.front_idx = 0u; 384 //this->allocate(n) will take care of overflows 385 m_.set_back_idx(n); 386 m_.set_capacity(n); 387 this->construct_from_range(x.begin(), x.end()); 388 BOOST_ASSERT(invariants_ok()); 389 } 390 391 /** 392 * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable 393 * 394 * **Effects**: Copy constructs a devector, using the specified allocator. 395 * 396 * **Requires**: `T` shall be [CopyInsertable] into `*this`. 397 * 398 * **Postcondition**: `this->size() == x.size() && front_free_capacity() == 0`. 399 * 400 * **Exceptions**: Strong exception guarantee. 401 * 402 * **Complexity**: Linear in the size of `x`. 403 */ devector(const devector & x,const allocator_type & allocator)404 devector(const devector& x, const allocator_type& allocator) 405 : m_(allocator, pointer(), 0u, 0u, 0u) 406 { 407 const size_type n = x.size(); 408 m_.buffer = n ? this->allocate(n) : pointer(); 409 m_.front_idx = 0u; 410 //this->allocate(n) will take care of overflows 411 m_.set_back_idx(n); 412 m_.set_capacity(n); 413 this->construct_from_range(x.begin(), x.end()); 414 BOOST_ASSERT(invariants_ok()); 415 } 416 417 /** 418 * **Effects**: Moves `rhs`'s resources to `*this`. 419 * 420 * **Throws**: Nothing. 421 * 422 * **Postcondition**: `rhs` is left in an unspecified but valid state. 423 * 424 * **Exceptions**: Strong exception guarantee if not `noexcept`. 425 * 426 * **Complexity**: Constant. 427 */ devector(BOOST_RV_REF (devector)rhs)428 devector(BOOST_RV_REF(devector) rhs) BOOST_NOEXCEPT_OR_NOTHROW 429 : m_(::boost::move(rhs.get_allocator_ref()), rhs.m_.buffer, rhs.m_.front_idx, rhs.m_.back_idx, rhs.capacity()) 430 { 431 // buffer is already acquired, reset rhs 432 rhs.m_.capacity = 0u; 433 rhs.m_.buffer = pointer(); 434 rhs.m_.front_idx = 0; 435 rhs.m_.back_idx = 0; 436 BOOST_ASSERT( invariants_ok()); 437 BOOST_ASSERT(rhs.invariants_ok()); 438 } 439 440 /** 441 * **Effects**: Moves `rhs`'s resources to `*this`, using the specified allocator. 442 * 443 * **Throws**: If allocation or T's move constructor throws. 444 * 445 * **Postcondition**: `rhs` is left in an unspecified but valid state. 446 * 447 * **Exceptions**: Strong exception guarantee if not `noexcept`. 448 * 449 * **Complexity**: Linear if allocator != rhs.get_allocator(), otherwise constant. 450 */ devector(BOOST_RV_REF (devector)rhs,const allocator_type & allocator)451 devector(BOOST_RV_REF(devector) rhs, const allocator_type& allocator) 452 : m_(allocator, rhs.m_.buffer, rhs.m_.front_idx, rhs.m_.back_idx, rhs.capacity()) 453 { 454 // TODO should move elems-by-elems if the two allocators differ 455 // buffer is already acquired, reset rhs 456 rhs.m_.capacity = 0u; 457 rhs.m_.buffer = pointer(); 458 rhs.m_.front_idx = 0; 459 rhs.m_.back_idx = 0; 460 BOOST_ASSERT( invariants_ok()); 461 BOOST_ASSERT(rhs.invariants_ok()); 462 } 463 464 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 465 /** 466 * **Equivalent to**: `devector(il.begin(), il.end())` or `devector(il.begin(), il.end(), allocator)`. 467 */ devector(const std::initializer_list<T> & il,const allocator_type & allocator=allocator_type ())468 devector(const std::initializer_list<T>& il, const allocator_type& allocator = allocator_type()) 469 : m_(allocator, pointer(), 0u, 0u, 0u) 470 { 471 const size_type n = il.size(); 472 m_.buffer = n ? allocate(n) : pointer(); 473 m_.front_idx = 0u; 474 //this->allocate(n) will take care of overflows 475 m_.set_back_idx(n); 476 m_.set_capacity(n); 477 //construct_from_range releases memory on failure 478 this->construct_from_range(il.begin(), il.end()); 479 BOOST_ASSERT(invariants_ok()); 480 } 481 #endif 482 483 /** 484 * **Effects**: Destroys the devector. All stored values are destroyed and 485 * used memory, if any, deallocated. 486 * 487 * **Complexity**: Linear in the size of `*this`. 488 */ ~devector()489 ~devector() BOOST_NOEXCEPT 490 { 491 destroy_elements(m_.buffer + m_.front_idx, m_.buffer + m_.back_idx); 492 deallocate_buffer(); 493 } 494 495 /** 496 * **Effects**: Copies elements of `x` to `*this`. Previously 497 * held elements get copy assigned to or destroyed. 498 * 499 * **Requires**: `T` shall be [CopyInsertable] into `*this`. 500 * 501 * **Postcondition**: `this->size() == x.size()`, the elements of 502 * `*this` are copies of elements in `x` in the same order. 503 * 504 * **Returns**: `*this`. 505 * 506 * **Exceptions**: Strong exception guarantee if `T` is `NothrowConstructible` 507 * and the allocator is allowed to be propagated 508 * ([propagate_on_container_copy_assignment] is true), 509 * Basic exception guarantee otherwise. 510 * 511 * **Complexity**: Linear in the size of `x` and `*this`. 512 * 513 * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable 514 * [propagate_on_container_copy_assignment]: http://en.cppreference.com/w/cpp/memory/allocator_traits 515 */ 516 operator =(BOOST_COPY_ASSIGN_REF (devector)rhs)517 BOOST_CONTAINER_FORCEINLINE devector& operator=(BOOST_COPY_ASSIGN_REF(devector) rhs) 518 { 519 const devector &x = rhs; 520 if (this == &x) { return *this; } // skip self 521 522 BOOST_IF_CONSTEXPR(allocator_traits_type::propagate_on_container_copy_assignment::value) 523 { 524 allocator_type &this_alloc = this->get_allocator_ref(); 525 const allocator_type &other_alloc = x.get_allocator_ref(); 526 if (this_alloc != other_alloc) 527 { 528 // new allocator cannot free existing storage 529 this->clear(); 530 this->deallocate_buffer(); 531 m_.capacity = 0u; 532 m_.buffer = pointer(); 533 } 534 535 this_alloc = other_alloc; 536 } 537 538 size_type n = x.size(); 539 if (capacity() >= n) 540 { 541 this->overwrite_buffer(x.begin(), x.end()); 542 } 543 else 544 { 545 this->allocate_and_copy_range(x.begin(), x.end()); 546 } 547 548 BOOST_ASSERT(invariants_ok()); 549 550 return *this; 551 } 552 553 /** 554 * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable 555 * 556 * **Effects**: Moves elements of `x` to `*this`. Previously 557 * held elements get move/copy assigned to or destroyed. 558 * 559 * **Requires**: `T` shall be [MoveInsertable] into `*this`. 560 * 561 * **Postcondition**: `x` is left in an unspecified but valid state. 562 * 563 * **Returns**: `*this`. 564 * 565 * **Exceptions**: Basic exception guarantee if not `noexcept`. 566 * 567 * **Complexity**: Constant if allocator_traits_type:: 568 * propagate_on_container_move_assignment is true or 569 * this->get>allocator() == x.get_allocator(). Linear otherwise. 570 */ operator =(BOOST_RV_REF (devector)x)571 devector& operator=(BOOST_RV_REF(devector) x) 572 BOOST_NOEXCEPT_IF(allocator_traits_type::propagate_on_container_move_assignment::value 573 || allocator_traits_type::is_always_equal::value) 574 { 575 BOOST_CONSTEXPR_OR_CONST bool copy_alloc = allocator_traits_type::propagate_on_container_move_assignment::value; 576 577 BOOST_IF_CONSTEXPR (copy_alloc || get_allocator_ref() == x.get_allocator_ref()) 578 { 579 this->clear(); 580 this->deallocate_buffer(); 581 582 if (copy_alloc) 583 { 584 this->get_allocator_ref() = boost::move(x.get_allocator_ref()); 585 } 586 587 m_.capacity = x.m_.capacity; 588 m_.buffer = x.m_.buffer; 589 m_.front_idx = x.m_.front_idx; 590 m_.back_idx = x.m_.back_idx; 591 592 // leave x in valid state 593 x.m_.capacity = 0u; 594 x.m_.buffer = pointer(); 595 x.m_.back_idx = x.m_.front_idx = 0; 596 } 597 else 598 { 599 // if the allocator shouldn't be copied and they do not compare equal 600 // we can't steal memory. 601 602 move_iterator<iterator> xbegin = boost::make_move_iterator(x.begin()); 603 move_iterator<iterator> xend = boost::make_move_iterator(x.end()); 604 605 if (copy_alloc) 606 { 607 get_allocator_ref() = boost::move(x.get_allocator_ref()); 608 } 609 610 if (capacity() >= x.size()) 611 { 612 overwrite_buffer(xbegin, xend); 613 } 614 else 615 { 616 allocate_and_copy_range(xbegin, xend); 617 } 618 } 619 620 BOOST_ASSERT(invariants_ok()); 621 622 return *this; 623 } 624 625 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 626 /** 627 * **Effects**: Copies elements of `il` to `*this`. Previously 628 * held elements get copy assigned to or destroyed. 629 * 630 * **Requires**: `T` shall be [CopyInsertable] into `*this` and [CopyAssignable]. 631 * 632 * **Postcondition**: `this->size() == il.size()`, the elements of 633 * `*this` are copies of elements in `il` in the same order. 634 * 635 * **Exceptions**: Strong exception guarantee if `T` is nothrow copy assignable 636 * from `T` and `NothrowConstructible`, Basic exception guarantee otherwise. 637 * 638 * **Returns**: `*this`. 639 * 640 * **Complexity**: Linear in the size of `il` and `*this`. 641 * 642 * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable 643 * [CopyAssignable]: http://en.cppreference.com/w/cpp/concept/CopyAssignable 644 */ operator =(std::initializer_list<T> il)645 devector& operator=(std::initializer_list<T> il) 646 { 647 assign(il.begin(), il.end()); 648 return *this; 649 } 650 #endif 651 652 /** 653 * **Effects**: Replaces elements of `*this` with a copy of `[first,last)`. 654 * Previously held elements get copy assigned to or destroyed. 655 * 656 * **Requires**: `T` shall be [EmplaceConstructible] from `*first`. If the specified iterator 657 * does not meet the forward iterator requirements, `T` shall be also [MoveInsertable] into `*this`. 658 * 659 * **Precondition**: `first` and `last` are not iterators into `*this`. 660 * 661 * **Postcondition**: `size() == N`, where `N` is the distance between `first` and `last`. 662 * 663 * **Exceptions**: Strong exception guarantee if `T` is nothrow copy assignable 664 * from `*first` and `NothrowConstructible`, Basic exception guarantee otherwise. 665 * 666 * **Complexity**: Linear in the distance between `first` and `last`. 667 * Makes a single reallocation at most if the iterators `first` and `last` 668 * are of forward, bidirectional, or random access categories. It makes 669 * `O(log(N))` reallocations if they are just input iterators. 670 * 671 * **Remarks**: Each iterator in the range `[first,last)` shall be dereferenced exactly once, 672 * unless an exception is thrown. 673 * 674 * [EmplaceConstructible]: http://en.cppreference.com/w/cpp/concept/EmplaceConstructible 675 * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable 676 */ 677 template <class InputIterator> 678 void assign(InputIterator first, InputIterator last 679 //Input iterators 680 BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_or 681 < void 682 BOOST_MOVE_I dtl::is_convertible<InputIterator BOOST_MOVE_I size_type> 683 BOOST_MOVE_I dtl::is_not_input_iterator<InputIterator> 684 >::type * = 0) 685 ) 686 { 687 first = overwrite_buffer_impl(first, last, dtl::false_()); 688 while (first != last) 689 { 690 this->emplace_back(*first++); 691 } 692 } 693 694 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 695 696 template <class ForwardIterator> 697 void assign(ForwardIterator first, ForwardIterator last 698 //Other iterators 699 BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_or 700 < void 701 BOOST_MOVE_I dtl::is_convertible<ForwardIterator BOOST_MOVE_I size_type> 702 BOOST_MOVE_I dtl::is_input_iterator<ForwardIterator> 703 >::type * = 0) 704 ) 705 { 706 const size_type n = boost::container::iterator_distance(first, last); 707 708 if (capacity() >= n) 709 { 710 overwrite_buffer(first, last); 711 } 712 else 713 { 714 allocate_and_copy_range(first, last); 715 } 716 717 BOOST_ASSERT(invariants_ok()); 718 } 719 720 #endif // ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 721 722 /** 723 * **Effects**: Replaces elements of `*this` with `n` copies of `u`. 724 * Previously held elements get copy assigned to or destroyed. 725 * 726 * **Requires**: `T` shall be [CopyInsertable] into `*this` and 727 * [CopyAssignable]. 728 * 729 * **Precondition**: `u` is not a reference into `*this`. 730 * 731 * **Postcondition**: `size() == n` and the elements of 732 * `*this` are copies of `u`. 733 * 734 * **Exceptions**: Strong exception guarantee if `T` is nothrow copy assignable 735 * from `u` and `NothrowConstructible`, Basic exception guarantee otherwise. 736 * 737 * **Complexity**: Linear in `n` and the size of `*this`. 738 * 739 * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable 740 * [CopyAssignable]: http://en.cppreference.com/w/cpp/concept/CopyAssignable 741 */ assign(size_type n,const T & u)742 void assign(size_type n, const T& u) 743 { 744 cvalue_iterator first(u, n); 745 cvalue_iterator last; 746 747 assign(first, last); 748 } 749 750 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 751 /** **Equivalent to**: `assign(il.begin(), il.end())`. */ assign(std::initializer_list<T> il)752 void assign(std::initializer_list<T> il) 753 { 754 assign(il.begin(), il.end()); 755 } 756 #endif 757 758 /** 759 * **Returns**: A copy of the allocator associated with the container. 760 * 761 * **Complexity**: Constant. 762 */ 763 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE get_allocator() const764 allocator_type get_allocator() const BOOST_NOEXCEPT 765 { 766 return static_cast<const allocator_type&>(m_); 767 } 768 769 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE get_stored_allocator() const770 const allocator_type &get_stored_allocator() const BOOST_NOEXCEPT 771 { 772 return static_cast<const allocator_type&>(m_); 773 } 774 775 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE get_stored_allocator()776 allocator_type &get_stored_allocator() BOOST_NOEXCEPT 777 { 778 return static_cast<allocator_type&>(m_); 779 } 780 781 // iterators 782 783 /** 784 * **Returns**: A iterator pointing to the first element in the devector, 785 * or the past the end iterator if the devector is empty. 786 * 787 * **Complexity**: Constant. 788 */ 789 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE begin()790 iterator begin() BOOST_NOEXCEPT 791 { 792 return m_.buffer + m_.front_idx; 793 } 794 795 /** 796 * **Returns**: A constant iterator pointing to the first element in the devector, 797 * or the past the end iterator if the devector is empty. 798 * 799 * **Complexity**: Constant. 800 */ 801 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE begin() const802 const_iterator begin() const BOOST_NOEXCEPT 803 { 804 return m_.buffer + m_.front_idx; 805 } 806 807 /** 808 * **Returns**: An iterator pointing past the last element of the container. 809 * 810 * **Complexity**: Constant. 811 */ 812 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE end()813 iterator end() BOOST_NOEXCEPT 814 { 815 return m_.buffer + m_.back_idx; 816 } 817 818 /** 819 * **Returns**: A constant iterator pointing past the last element of the container. 820 * 821 * **Complexity**: Constant. 822 */ 823 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE end() const824 const_iterator end() const BOOST_NOEXCEPT 825 { 826 return m_.buffer + m_.back_idx; 827 } 828 829 /** 830 * **Returns**: A reverse iterator pointing to the first element in the reversed devector, 831 * or the reverse past the end iterator if the devector is empty. 832 * 833 * **Complexity**: Constant. 834 */ 835 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE rbegin()836 reverse_iterator rbegin() BOOST_NOEXCEPT 837 { 838 return reverse_iterator(m_.buffer + m_.back_idx); 839 } 840 841 /** 842 * **Returns**: A constant reverse iterator 843 * pointing to the first element in the reversed devector, 844 * or the reverse past the end iterator if the devector is empty. 845 * 846 * **Complexity**: Constant. 847 */ 848 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE rbegin() const849 const_reverse_iterator rbegin() const BOOST_NOEXCEPT 850 { 851 return const_reverse_iterator(m_.buffer + m_.back_idx); 852 } 853 854 /** 855 * **Returns**: A reverse iterator pointing past the last element in the 856 * reversed container, or to the beginning of the reversed container if it's empty. 857 * 858 * **Complexity**: Constant. 859 */ 860 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE rend()861 reverse_iterator rend() BOOST_NOEXCEPT 862 { 863 return reverse_iterator(m_.buffer + m_.front_idx); 864 } 865 866 /** 867 * **Returns**: A constant reverse iterator pointing past the last element in the 868 * reversed container, or to the beginning of the reversed container if it's empty. 869 * 870 * **Complexity**: Constant. 871 */ 872 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE rend() const873 const_reverse_iterator rend() const BOOST_NOEXCEPT 874 { 875 return const_reverse_iterator(m_.buffer + m_.front_idx); 876 } 877 878 /** 879 * **Returns**: A constant iterator pointing to the first element in the devector, 880 * or the past the end iterator if the devector is empty. 881 * 882 * **Complexity**: Constant. 883 */ 884 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE cbegin() const885 const_iterator cbegin() const BOOST_NOEXCEPT 886 { 887 return m_.buffer + m_.front_idx; 888 } 889 890 /** 891 * **Returns**: A constant iterator pointing past the last element of the container. 892 * 893 * **Complexity**: Constant. 894 */ cend() const895 const_iterator cend() const BOOST_NOEXCEPT 896 { 897 return m_.buffer + m_.back_idx; 898 } 899 900 /** 901 * **Returns**: A constant reverse iterator 902 * pointing to the first element in the reversed devector, 903 * or the reverse past the end iterator if the devector is empty. 904 * 905 * **Complexity**: Constant. 906 */ 907 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE crbegin() const908 const_reverse_iterator crbegin() const BOOST_NOEXCEPT 909 { 910 return const_reverse_iterator(m_.buffer + m_.back_idx); 911 } 912 913 /** 914 * **Returns**: A constant reverse iterator pointing past the last element in the 915 * reversed container, or to the beginning of the reversed container if it's empty. 916 * 917 * **Complexity**: Constant. 918 */ 919 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE crend() const920 const_reverse_iterator crend() const BOOST_NOEXCEPT 921 { 922 return const_reverse_iterator(m_.buffer + m_.front_idx); 923 } 924 925 // capacity 926 927 /** 928 * **Returns**: True, if `size() == 0`, false otherwise. 929 * 930 * **Complexity**: Constant. 931 */ 932 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE empty() const933 bool empty() const BOOST_NOEXCEPT 934 { 935 return m_.front_idx == m_.back_idx; 936 } 937 938 /** 939 * **Returns**: The number of elements the devector contains. 940 * 941 * **Complexity**: Constant. 942 */ 943 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE size() const944 size_type size() const BOOST_NOEXCEPT 945 { 946 return m_.back_idx - m_.front_idx; 947 } 948 949 /** 950 * **Returns**: The maximum number of elements the devector could possibly hold. 951 * 952 * **Complexity**: Constant. 953 */ 954 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE max_size() const955 size_type max_size() const BOOST_NOEXCEPT 956 { 957 size_type alloc_max = allocator_traits_type::max_size(get_allocator_ref()); 958 size_type size_type_max = (size_type)-1; 959 return (alloc_max <= size_type_max) ? size_type(alloc_max) : size_type_max; 960 } 961 962 /** 963 * **Returns**: The total number of elements that the devector can hold without requiring reallocation. 964 * 965 * **Complexity**: Constant. 966 */ 967 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE capacity() const968 size_type capacity() const BOOST_NOEXCEPT 969 { 970 return m_.capacity; 971 } 972 973 /** 974 * **Returns**: The total number of elements that can be pushed to the front of the 975 * devector without requiring reallocation. 976 * 977 * **Complexity**: Constant. 978 */ 979 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE front_free_capacity() const980 size_type front_free_capacity() const BOOST_NOEXCEPT 981 { 982 return m_.front_idx; 983 } 984 985 /** 986 * **Returns**: The total number of elements that can be pushed to the back of the 987 * devector without requiring reallocation. 988 * 989 * **Complexity**: Constant. 990 */ 991 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE back_free_capacity() const992 size_type back_free_capacity() const BOOST_NOEXCEPT 993 { 994 return m_.capacity - m_.back_idx; 995 } 996 997 /** **Equivalent to**: `resize_back(sz)` */ resize(size_type sz)998 void resize(size_type sz) { resize_back(sz); } 999 1000 /** **Equivalent to**: `resize_back(sz, c)` */ resize(size_type sz,const T & c)1001 void resize(size_type sz, const T& c) { resize_back(sz, c); } 1002 1003 /** 1004 * **Effects**: If `sz` is greater than the size of `*this`, 1005 * additional value-initialized elements are inserted 1006 * to the front. Invalidates iterators if reallocation is needed. 1007 * If `sz` is smaller than than the size of `*this`, 1008 * elements are popped from the front. 1009 * 1010 * **Requires**: T shall be [MoveInsertable] into *this and [DefaultConstructible]. 1011 * 1012 * **Postcondition**: `sz == size()`. 1013 * 1014 * **Exceptions**: Strong exception guarantee. 1015 * 1016 * **Complexity**: Linear in the size of `*this` and `sz`. 1017 * 1018 * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable 1019 * [DefaultConstructible]: http://en.cppreference.com/w/cpp/concept/DefaultConstructible 1020 */ resize_front(size_type sz)1021 void resize_front(size_type sz) 1022 { 1023 resize_front_impl(sz); 1024 BOOST_ASSERT(invariants_ok()); 1025 } 1026 1027 /** 1028 * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable 1029 * 1030 * **Effects**: If `sz` is greater than the size of `*this`, 1031 * copies of `c` are inserted to the front. 1032 * Invalidates iterators if reallocation is needed. 1033 * If `sz` is smaller than than the size of `*this`, 1034 * elements are popped from the front. 1035 * 1036 * **Postcondition**: `sz == size()`. 1037 * 1038 * **Requires**: `T` shall be [CopyInsertable] into `*this`. 1039 * 1040 * **Exceptions**: Strong exception guarantee. 1041 * 1042 * **Complexity**: Linear in the size of `*this` and `sz`. 1043 */ resize_front(size_type sz,const T & c)1044 void resize_front(size_type sz, const T& c) 1045 { 1046 resize_front_impl(sz, c); 1047 BOOST_ASSERT(invariants_ok()); 1048 } 1049 1050 /** 1051 * **Effects**: If `sz` is greater than the size of `*this`, 1052 * additional value-initialized elements are inserted 1053 * to the back. Invalidates iterators if reallocation is needed. 1054 * If `sz` is smaller than than the size of `*this`, 1055 * elements are popped from the back. 1056 * 1057 * **Requires**: T shall be [MoveInsertable] into *this and [DefaultConstructible]. 1058 * 1059 * **Postcondition**: `sz == size()`. 1060 * 1061 * **Exceptions**: Strong exception guarantee. 1062 * 1063 * **Complexity**: Linear in the size of `*this` and `sz`. 1064 * 1065 * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable 1066 * [DefaultConstructible]: http://en.cppreference.com/w/cpp/concept/DefaultConstructible 1067 */ resize_back(size_type sz)1068 void resize_back(size_type sz) 1069 { 1070 resize_back_impl(sz); 1071 BOOST_ASSERT(invariants_ok()); 1072 } 1073 1074 /** 1075 * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable 1076 * 1077 * **Effects**: If `sz` is greater than the size of `*this`, 1078 * copies of `c` are inserted to the back. 1079 * If `sz` is smaller than than the size of `*this`, 1080 * elements are popped from the back. 1081 * 1082 * **Postcondition**: `sz == size()`. 1083 * 1084 * **Requires**: `T` shall be [CopyInsertable] into `*this`. 1085 * 1086 * **Exceptions**: Strong exception guarantee. 1087 * 1088 * **Complexity**: Linear in the size of `*this` and `sz`. 1089 */ resize_back(size_type sz,const T & c)1090 void resize_back(size_type sz, const T& c) 1091 { 1092 resize_back_impl(sz, c); 1093 BOOST_ASSERT(invariants_ok()); 1094 } 1095 1096 // unsafe uninitialized resize methods 1097 1098 /** 1099 * **Unsafe method**, use with care. 1100 * 1101 * **Effects**: Changes the size of the devector without properly 1102 * initializing the extra or destroying the superfluous elements. 1103 * If `n < size()`, elements are removed from the front without 1104 * getting destroyed; if `n > size()`, uninitialized elements are added 1105 * before the first element at the front. 1106 * Invalidates iterators if reallocation is needed. 1107 * 1108 * **Postcondition**: `size() == n`. 1109 * 1110 * **Exceptions**: Strong exception guarantee. 1111 * 1112 * **Complexity**: Linear in `size()` if `capacity() < n`, constant otherwise. 1113 * 1114 * **Remarks**: The devector does not keep track of initialization of the elements: 1115 * Elements without a trivial destructor must be manually destroyed before shrinking, 1116 * elements without a trivial constructor must be initialized after growing. 1117 */ 1118 /* 1119 void unsafe_uninitialized_resize_front(size_type n) 1120 { 1121 if (n > size()) 1122 { 1123 unsafe_uninitialized_grow_front(n); 1124 } 1125 else 1126 { 1127 unsafe_uninitialized_shrink_front(n); 1128 } 1129 } 1130 */ 1131 /** 1132 * **Unsafe method**, use with care. 1133 * 1134 * **Effects**: Changes the size of the devector without properly 1135 * initializing the extra or destroying the superfluous elements. 1136 * If `n < size()`, elements are removed from the back without 1137 * getting destroyed; if `n > size()`, uninitialized elements are added 1138 * after the last element at the back. 1139 * Invalidates iterators if reallocation is needed. 1140 * 1141 * **Postcondition**: `size() == n`. 1142 * 1143 * **Exceptions**: Strong exception guarantee. 1144 * 1145 * **Complexity**: Linear in `size()` if `capacity() < n`, constant otherwise. 1146 * 1147 * **Remarks**: The devector does not keep track of initialization of the elements: 1148 * Elements without a trivial destructor must be manually destroyed before shrinking, 1149 * elements without a trivial constructor must be initialized after growing. 1150 */ 1151 /* 1152 void unsafe_uninitialized_resize_back(size_type n) 1153 { 1154 if (n > size()) 1155 { 1156 unsafe_uninitialized_grow_back(n); 1157 } 1158 else 1159 { 1160 unsafe_uninitialized_shrink_back(n); 1161 } 1162 } 1163 */ 1164 // reserve promise: 1165 // after reserve_[front,back](n), n - size() push_[front,back] will not allocate 1166 1167 /** **Equivalent to**: `reserve_back(new_capacity)` */ reserve(size_type new_capacity)1168 void reserve(size_type new_capacity) { reserve_back(new_capacity); } 1169 1170 /** 1171 * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable 1172 * 1173 * **Effects**: Ensures that `n` elements can be pushed to the front 1174 * without requiring reallocation, where `n` is `new_capacity - size()`, 1175 * if `n` is positive. Otherwise, there are no effects. 1176 * Invalidates iterators if reallocation is needed. 1177 * 1178 * **Requires**: `T` shall be [MoveInsertable] into `*this`. 1179 * 1180 * **Complexity**: Linear in the size of *this. 1181 * 1182 * **Exceptions**: Strong exception guarantee. 1183 * 1184 * **Throws**: `length_error` if `new_capacity > max_size()`. 1185 */ reserve_front(size_type new_capacity)1186 void reserve_front(size_type new_capacity) 1187 { 1188 if (front_capacity() >= new_capacity) { return; } 1189 1190 reallocate_at(new_capacity + back_free_capacity(), new_capacity - size()); 1191 1192 BOOST_ASSERT(invariants_ok()); 1193 } 1194 1195 /** 1196 * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable 1197 * 1198 * **Effects**: Ensures that `n` elements can be pushed to the back 1199 * without requiring reallocation, where `n` is `new_capacity - size()`, 1200 * if `n` is positive. Otherwise, there are no effects. 1201 * Invalidates iterators if reallocation is needed. 1202 * 1203 * **Requires**: `T` shall be [MoveInsertable] into `*this`. 1204 * 1205 * **Complexity**: Linear in the size of *this. 1206 * 1207 * **Exceptions**: Strong exception guarantee. 1208 * 1209 * **Throws**: length_error if `new_capacity > max_size()`. 1210 */ reserve_back(size_type new_capacity)1211 void reserve_back(size_type new_capacity) 1212 { 1213 if (back_capacity() >= new_capacity) { return; } 1214 1215 reallocate_at(new_capacity + front_free_capacity(), m_.front_idx); 1216 1217 BOOST_ASSERT(invariants_ok()); 1218 } 1219 1220 1221 /** 1222 * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable 1223 * 1224 * **Effects**: Reduces `capacity()` to `size()`. Invalidates iterators. 1225 * 1226 * **Requires**: `T` shall be [MoveInsertable] into `*this`. 1227 * 1228 * **Exceptions**: Strong exception guarantee. 1229 * 1230 * **Complexity**: Linear in the size of *this. 1231 */ shrink_to_fit()1232 void shrink_to_fit() 1233 { 1234 if(this->front_capacity() || this->back_capacity()) 1235 this->reallocate_at(size(), 0); 1236 } 1237 1238 // element access: 1239 1240 /** 1241 * **Returns**: A reference to the `n`th element in the devector. 1242 * 1243 * **Precondition**: `n < size()`. 1244 * 1245 * **Complexity**: Constant. 1246 */ 1247 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE operator [](size_type n)1248 reference operator[](size_type n) BOOST_NOEXCEPT 1249 { 1250 BOOST_ASSERT(n < size()); 1251 return *(begin() + n); 1252 } 1253 1254 /** 1255 * **Returns**: A constant reference to the `n`th element in the devector. 1256 * 1257 * **Precondition**: `n < size()`. 1258 * 1259 * **Complexity**: Constant. 1260 */ 1261 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE operator [](size_type n) const1262 const_reference operator[](size_type n) const BOOST_NOEXCEPT 1263 { 1264 BOOST_ASSERT(n < size()); 1265 1266 return *(begin() + n); 1267 } 1268 1269 /** 1270 * **Returns**: A reference to the `n`th element in the devector. 1271 * 1272 * **Throws**: `std::out_of_range`, if `n >= size()`. 1273 * 1274 * **Complexity**: Constant. 1275 */ 1276 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE at(size_type n)1277 reference at(size_type n) 1278 { 1279 if (size() <= n) 1280 throw_out_of_range("devector::at out of range"); 1281 return (*this)[n]; 1282 } 1283 1284 /** 1285 * **Returns**: A constant reference to the `n`th element in the devector. 1286 * 1287 * **Throws**: `std::out_of_range`, if `n >= size()`. 1288 * 1289 * **Complexity**: Constant. 1290 */ 1291 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE at(size_type n) const1292 const_reference at(size_type n) const 1293 { 1294 if (size() <= n) 1295 throw_out_of_range("devector::at out of range"); 1296 return (*this)[n]; 1297 } 1298 1299 /** 1300 * **Returns**: A reference to the first element in the devector. 1301 * 1302 * **Precondition**: `!empty()`. 1303 * 1304 * **Complexity**: Constant. 1305 */ 1306 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE front()1307 reference front() BOOST_NOEXCEPT 1308 { 1309 BOOST_ASSERT(!empty()); 1310 1311 return *(m_.buffer + m_.front_idx); 1312 } 1313 1314 /** 1315 * **Returns**: A constant reference to the first element in the devector. 1316 * 1317 * **Precondition**: `!empty()`. 1318 * 1319 * **Complexity**: Constant. 1320 */ 1321 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE front() const1322 const_reference front() const BOOST_NOEXCEPT 1323 { 1324 BOOST_ASSERT(!empty()); 1325 1326 return *(m_.buffer + m_.front_idx); 1327 } 1328 1329 /** 1330 * **Returns**: A reference to the last element in the devector. 1331 * 1332 * **Precondition**: `!empty()`. 1333 * 1334 * **Complexity**: Constant. 1335 */ 1336 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE back()1337 reference back() BOOST_NOEXCEPT 1338 { 1339 BOOST_ASSERT(!empty()); 1340 1341 return *(m_.buffer + m_.back_idx -1); 1342 } 1343 1344 /** 1345 * **Returns**: A constant reference to the last element in the devector. 1346 * 1347 * **Precondition**: `!empty()`. 1348 * 1349 * **Complexity**: Constant. 1350 */ 1351 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE back() const1352 const_reference back() const BOOST_NOEXCEPT 1353 { 1354 BOOST_ASSERT(!empty()); 1355 1356 return *(m_.buffer + m_.back_idx -1); 1357 } 1358 1359 /** 1360 * **Returns**: A pointer to the underlying array serving as element storage. 1361 * The range `[data(); data() + size())` is always valid. For a non-empty devector, 1362 * `data() == &front()`. 1363 * 1364 * **Complexity**: Constant. 1365 */ 1366 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE data()1367 T* data() BOOST_NOEXCEPT 1368 { 1369 return boost::movelib::to_raw_pointer(m_.buffer) + m_.front_idx; 1370 } 1371 1372 /** 1373 * **Returns**: A constant pointer to the underlying array serving as element storage. 1374 * The range `[data(); data() + size())` is always valid. For a non-empty devector, 1375 * `data() == &front()`. 1376 * 1377 * **Complexity**: Constant. 1378 */ 1379 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE data() const1380 const T* data() const BOOST_NOEXCEPT 1381 { 1382 return boost::movelib::to_raw_pointer(m_.buffer) + m_.front_idx; 1383 } 1384 1385 // modifiers: 1386 1387 /** 1388 * **Effects**: Pushes a new element to the front of the devector. 1389 * The element is constructed in-place, using the perfect forwarded `args` 1390 * as constructor arguments. Invalidates iterators if reallocation is needed. 1391 * (`front_free_capacity() == 0`) 1392 * 1393 * **Requires**: `T` shall be [EmplaceConstructible] from `args` and [MoveInsertable] into `*this`. 1394 * 1395 * **Exceptions**: Strong exception guarantee. 1396 * 1397 * **Complexity**: Amortized constant in the size of `*this`. 1398 * (Constant, if `front_free_capacity() > 0`) 1399 * 1400 * [EmplaceConstructible]: http://en.cppreference.com/w/cpp/concept/EmplaceConstructible 1401 * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable 1402 */ 1403 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1404 template <class... Args> emplace_front(Args &&...args)1405 void emplace_front(Args&&... args) 1406 { 1407 if (front_free_capacity()) // fast path 1408 { 1409 this->alloc_construct(m_.buffer + m_.front_idx - 1, boost::forward<Args>(args)...); 1410 --m_.front_idx; 1411 } 1412 else 1413 { 1414 this->emplace_reallocating_slow_path(true, 0, boost::forward<Args>(args)...); 1415 } 1416 1417 BOOST_ASSERT(invariants_ok()); 1418 } 1419 1420 #else //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1421 1422 #define BOOST_CONTAINER_DEVECTOR_EMPLACE_FRONT(N) \ 1423 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 1424 BOOST_CONTAINER_FORCEINLINE void emplace_front(BOOST_MOVE_UREF##N)\ 1425 {\ 1426 if (front_free_capacity())\ 1427 {\ 1428 this->alloc_construct(m_.buffer + m_.front_idx - 1 BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ 1429 --m_.front_idx;\ 1430 }\ 1431 else\ 1432 {\ 1433 this->emplace_reallocating_slow_path(true, 0 BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ 1434 }\ 1435 \ 1436 BOOST_ASSERT(invariants_ok());\ 1437 }\ 1438 // 1439 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_DEVECTOR_EMPLACE_FRONT) 1440 #undef BOOST_CONTAINER_DEVECTOR_EMPLACE_FRONT 1441 1442 #endif 1443 1444 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1445 /** 1446 * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable 1447 * 1448 * **Effects**: Pushes the copy of `x` to the front of the devector. 1449 * Invalidates iterators if reallocation is needed. 1450 * (`front_free_capacity() == 0`) 1451 * 1452 * **Requires**: `T` shall be [CopyInsertable] into `*this`. 1453 * 1454 * **Exceptions**: Strong exception guarantee. 1455 * 1456 * **Complexity**: Amortized constant in the size of `*this`. 1457 * (Constant, if `front_free_capacity() > 0`) 1458 */ 1459 void push_front(const T& x); 1460 1461 /** 1462 * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable 1463 * 1464 * **Effects**: Move constructs a new element at the front of the devector using `x`. 1465 * Invalidates iterators if reallocation is needed. 1466 * (`front_free_capacity() == 0`) 1467 * 1468 * **Requires**: `T` shall be [MoveInsertable] into `*this`. 1469 * 1470 * **Exceptions**: Strong exception guarantee, not regarding the state of `x`. 1471 * 1472 * **Complexity**: Amortized constant in the size of `*this`. 1473 * (Constant, if `front_free_capacity() > 0`) 1474 */ 1475 void push_front(T&& x); 1476 1477 #else 1478 BOOST_MOVE_CONVERSION_AWARE_CATCH(push_front, T, void, priv_push_front) 1479 #endif 1480 1481 /** 1482 * **Effects**: Removes the first element of `*this`. 1483 * 1484 * **Precondition**: `!empty()`. 1485 * 1486 * **Postcondition**: `front_free_capacity()` is incremented by 1. 1487 * 1488 * **Complexity**: Constant. 1489 */ pop_front()1490 void pop_front() BOOST_NOEXCEPT 1491 { 1492 BOOST_ASSERT(! empty()); 1493 allocator_traits_type::destroy(get_allocator_ref(), m_.buffer + m_.front_idx); 1494 ++m_.front_idx; 1495 BOOST_ASSERT(invariants_ok()); 1496 } 1497 1498 /** 1499 * **Effects**: Pushes a new element to the back of the devector. 1500 * The element is constructed in-place, using the perfect forwarded `args` 1501 * as constructor arguments. Invalidates iterators if reallocation is needed. 1502 * (`back_free_capacity() == 0`) 1503 * 1504 * **Requires**: `T` shall be [EmplaceConstructible] from `args` and [MoveInsertable] into `*this`, 1505 * and [MoveAssignable]. 1506 * 1507 * **Exceptions**: Strong exception guarantee. 1508 * 1509 * **Complexity**: Amortized constant in the size of `*this`. 1510 * (Constant, if `back_free_capacity() > 0`) 1511 * 1512 * [EmplaceConstructible]: http://en.cppreference.com/w/cpp/concept/EmplaceConstructible 1513 * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable 1514 * [MoveAssignable]: http://en.cppreference.com/w/cpp/concept/MoveAssignable 1515 */ 1516 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1517 template <class... Args> emplace_back(Args &&...args)1518 BOOST_CONTAINER_FORCEINLINE void emplace_back(Args&&... args) 1519 { 1520 if (this->back_free_capacity()){ 1521 this->alloc_construct(m_.buffer + m_.back_idx, boost::forward<Args>(args)...); 1522 ++m_.back_idx; 1523 } 1524 else { 1525 this->emplace_reallocating_slow_path(false, size(), boost::forward<Args>(args)...); 1526 } 1527 BOOST_ASSERT(invariants_ok()); 1528 } 1529 1530 #else //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1531 1532 #define BOOST_CONTAINER_DEVECTOR_EMPLACE_BACK(N) \ 1533 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 1534 BOOST_CONTAINER_FORCEINLINE void emplace_back(BOOST_MOVE_UREF##N)\ 1535 {\ 1536 if (this->back_free_capacity()){\ 1537 this->alloc_construct(m_.buffer + m_.back_idx BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ 1538 ++m_.back_idx;\ 1539 }\ 1540 else {\ 1541 this->emplace_reallocating_slow_path(false, size() BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ 1542 }\ 1543 BOOST_ASSERT(invariants_ok());\ 1544 }\ 1545 // 1546 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_DEVECTOR_EMPLACE_BACK) 1547 #undef BOOST_CONTAINER_DEVECTOR_EMPLACE_BACK 1548 1549 #endif //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1550 1551 1552 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1553 /** 1554 * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable 1555 * 1556 * **Effects**: Pushes the copy of `x` to the back of the devector. 1557 * Invalidates iterators if reallocation is needed. 1558 * (`back_free_capacity() == 0`) 1559 * 1560 * **Requires**: `T` shall be [CopyInsertable] into `*this`. 1561 * 1562 * **Exceptions**: Strong exception guarantee. 1563 * 1564 * **Complexity**: Amortized constant in the size of `*this`. 1565 * (Constant, if `back_free_capacity() > 0`) 1566 */ 1567 void push_back(const T& x); 1568 1569 /** 1570 * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable 1571 * 1572 * **Effects**: Move constructs a new element at the back of the devector using `x`. 1573 * Invalidates iterators if reallocation is needed. 1574 * (`back_free_capacity() == 0`) 1575 * 1576 * **Requires**: `T` shall be [MoveInsertable] into `*this`. 1577 * 1578 * **Exceptions**: Strong exception guarantee, not regarding the state of `x`. 1579 * 1580 * **Complexity**: Amortized constant in the size of `*this`. 1581 * (Constant, if `back_free_capacity() > 0`) 1582 */ 1583 void push_back(T&& x); 1584 1585 #else 1586 BOOST_MOVE_CONVERSION_AWARE_CATCH(push_back, T, void, priv_push_back) 1587 #endif 1588 1589 /** 1590 * **Effects**: Removes the last element of `*this`. 1591 * 1592 * **Precondition**: `!empty()`. 1593 * 1594 * **Postcondition**: `back_free_capacity()` is incremented by 1. 1595 * 1596 * **Complexity**: Constant. 1597 */ pop_back()1598 void pop_back() BOOST_NOEXCEPT 1599 { 1600 BOOST_ASSERT(! empty()); 1601 --m_.back_idx; 1602 allocator_traits_type::destroy(get_allocator_ref(), m_.buffer + m_.back_idx); 1603 BOOST_ASSERT(invariants_ok()); 1604 } 1605 1606 /** 1607 * **Effects**: Constructs a new element before the element pointed by `position`. 1608 * The element is constructed in-place, using the perfect forwarded `args` 1609 * as constructor arguments. Invalidates iterators if reallocation is needed. 1610 * 1611 * **Requires**: `T` shall be [EmplaceConstructible], and [MoveInsertable] into `*this`, 1612 * and [MoveAssignable]. 1613 * 1614 * **Returns**: Iterator pointing to the newly constructed element. 1615 * 1616 * **Exceptions**: Strong exception guarantee if `T` is `NothrowConstructible` 1617 * and `NothrowAssignable`, Basic exception guarantee otherwise. 1618 * 1619 * **Complexity**: Linear in the size of `*this`. 1620 * 1621 * [EmplaceConstructible]: http://en.cppreference.com/w/cpp/concept/EmplaceConstructible 1622 * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable 1623 * [MoveAssignable]: http://en.cppreference.com/w/cpp/concept/MoveAssignable 1624 */ 1625 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1626 template <class... Args> emplace(const_iterator position,Args &&...args)1627 iterator emplace(const_iterator position, Args&&... args) 1628 { 1629 BOOST_ASSERT(position >= begin()); 1630 BOOST_ASSERT(position <= end()); 1631 1632 if (position == end() && back_free_capacity()) // fast path 1633 { 1634 this->alloc_construct(m_.buffer + m_.back_idx, boost::forward<Args>(args)...); 1635 ++m_.back_idx; 1636 return end() - 1; 1637 } 1638 else if (position == begin() && front_free_capacity()) // secondary fast path 1639 { 1640 this->alloc_construct(m_.buffer + (m_.front_idx - 1), boost::forward<Args>(args)...); 1641 --m_.front_idx; 1642 return begin(); 1643 } 1644 else 1645 { 1646 size_type new_elem_index = position - begin(); 1647 return this->emplace_slow_path(new_elem_index, boost::forward<Args>(args)...); 1648 } 1649 } 1650 1651 #else //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1652 1653 #define BOOST_CONTAINER_DEVECTOR_EMPLACE(N) \ 1654 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 1655 iterator emplace(const_iterator position BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ 1656 {\ 1657 BOOST_ASSERT(position >= begin());\ 1658 BOOST_ASSERT(position <= end());\ 1659 \ 1660 if (position == end() && back_free_capacity()){\ 1661 this->alloc_construct(m_.buffer + m_.back_idx BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ 1662 ++m_.back_idx;\ 1663 return end() - 1;\ 1664 }\ 1665 else if (position == begin() && front_free_capacity()){\ 1666 this->alloc_construct(m_.buffer + m_.front_idx - 1 BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ 1667 --m_.front_idx;\ 1668 return begin();\ 1669 }\ 1670 else{\ 1671 size_type new_elem_index = position - begin();\ 1672 return this->emplace_slow_path(new_elem_index BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ 1673 }\ 1674 }\ 1675 // 1676 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_DEVECTOR_EMPLACE) 1677 #undef BOOST_CONTAINER_DEVECTOR_EMPLACE 1678 1679 #endif //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1680 1681 1682 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1683 /** 1684 * **Effects**: Copy constructs a new element before the element pointed by `position`, 1685 * using `x` as constructor argument. Invalidates iterators if reallocation is needed. 1686 * 1687 * **Requires**: `T` shall be [CopyInsertable] into `*this` and and [CopyAssignable]. 1688 * 1689 * **Returns**: Iterator pointing to the newly constructed element. 1690 * 1691 * **Exceptions**: Strong exception guarantee if `T` is `NothrowConstructible` 1692 * and `NothrowAssignable`, Basic exception guarantee otherwise. 1693 * 1694 * **Complexity**: Linear in the size of `*this`. 1695 * 1696 * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable 1697 * [CopyAssignable]: http://en.cppreference.com/w/cpp/concept/CopyAssignable 1698 */ 1699 iterator insert(const_iterator position, const T &x); 1700 1701 /** 1702 * **Effects**: Move constructs a new element before the element pointed by `position`, 1703 * using `x` as constructor argument. Invalidates iterators if reallocation is needed. 1704 * 1705 * **Requires**: `T` shall be [MoveInsertable] into `*this` and and [CopyAssignable]. 1706 * 1707 * **Returns**: Iterator pointing to the newly constructed element. 1708 * 1709 * **Exceptions**: Strong exception guarantee if `T` is `NothrowConstructible` 1710 * and `NothrowAssignable` (not regarding the state of `x`), 1711 * Basic exception guarantee otherwise. 1712 * 1713 * **Complexity**: Linear in the size of `*this`. 1714 * 1715 * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable 1716 * [CopyAssignable]: http://en.cppreference.com/w/cpp/concept/CopyAssignable 1717 */ 1718 iterator insert(const_iterator position, T &&x); 1719 #else 1720 BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, T, iterator, priv_insert, const_iterator, const_iterator) 1721 #endif 1722 1723 /** 1724 * **Effects**: Copy constructs `n` elements before the element pointed by `position`, 1725 * using `x` as constructor argument. Invalidates iterators if reallocation is needed. 1726 * 1727 * **Requires**: `T` shall be [CopyInsertable] into `*this` and and [CopyAssignable]. 1728 * 1729 * **Returns**: Iterator pointing to the first inserted element, or `position`, if `n` is zero. 1730 * 1731 * **Exceptions**: Strong exception guarantee if `T` is `NothrowConstructible` 1732 * and `NothrowAssignable`, Basic exception guarantee otherwise. 1733 * 1734 * **Complexity**: Linear in the size of `*this` and `n`. 1735 * 1736 * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable 1737 * [CopyAssignable]: http://en.cppreference.com/w/cpp/concept/CopyAssignable 1738 */ insert(const_iterator position,size_type n,const T & x)1739 iterator insert(const_iterator position, size_type n, const T& x) 1740 { 1741 cvalue_iterator first(x, n); 1742 cvalue_iterator last = first + n; 1743 return insert_range(position, first, last); 1744 } 1745 1746 /** 1747 * **Effects**: Copy constructs elements before the element pointed by position 1748 * using each element in the rage pointed by `first` and `last` as constructor arguments. 1749 * Invalidates iterators if reallocation is needed. 1750 * 1751 * **Requires**: `T` shall be [EmplaceConstructible] into `*this` from `*first`. If the specified iterator 1752 * does not meet the forward iterator requirements, `T` shall also be [MoveInsertable] into `*this` 1753 * and [MoveAssignable]. 1754 * 1755 * **Precondition**: `first` and `last` are not iterators into `*this`. 1756 * 1757 * **Returns**: Iterator pointing to the first inserted element, or `position`, if `first == last`. 1758 * 1759 * **Complexity**: Linear in the size of `*this` and `N` (where `N` is the distance between `first` and `last`). 1760 * Makes only `N` calls to the constructor of `T` and no reallocations if iterators `first` and `last` 1761 * are of forward, bidirectional, or random access categories. It makes 2N calls to the copy constructor of `T` 1762 * and allocates memory twice at most if they are just input iterators. 1763 * 1764 * **Exceptions**: Strong exception guarantee if `T` is `NothrowConstructible` 1765 * and `NothrowAssignable`, Basic exception guarantee otherwise. 1766 * 1767 * **Remarks**: Each iterator in the range `[first,last)` shall be dereferenced exactly once, 1768 * unless an exception is thrown. 1769 * 1770 * [EmplaceConstructible]: http://en.cppreference.com/w/cpp/concept/EmplaceConstructible 1771 * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable 1772 * [MoveAssignable]: http://en.cppreference.com/w/cpp/concept/MoveAssignable 1773 */ 1774 template <class InputIterator> 1775 iterator insert(const_iterator position, InputIterator first, InputIterator last 1776 //Input iterators 1777 BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_or 1778 < void 1779 BOOST_MOVE_I dtl::is_convertible<InputIterator BOOST_MOVE_I size_type> 1780 BOOST_MOVE_I dtl::is_not_input_iterator<InputIterator> 1781 >::type * = 0) 1782 ) 1783 { 1784 if (position == end()) 1785 { 1786 size_type insert_index = size(); 1787 1788 for (; first != last; ++first) 1789 { 1790 this->emplace_back(*first); 1791 } 1792 1793 return begin() + insert_index; 1794 } 1795 else 1796 { 1797 const size_type insert_index = static_cast<size_type>(position - this->cbegin()); 1798 const size_type old_size = static_cast<size_type>(this->size()); 1799 1800 for (; first != last; ++first) { 1801 this->emplace_back(*first); 1802 } 1803 iterator rit (this->begin() + insert_index); 1804 boost::movelib::rotate_gcd(rit, this->begin() + old_size, this->begin() + this->size()); 1805 return rit; 1806 } 1807 } 1808 1809 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 1810 1811 template <class ForwardIterator> 1812 iterator insert(const_iterator position, ForwardIterator first, ForwardIterator last 1813 //Other iterators 1814 BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_or 1815 < void 1816 BOOST_MOVE_I dtl::is_convertible<ForwardIterator BOOST_MOVE_I size_type> 1817 BOOST_MOVE_I dtl::is_input_iterator<ForwardIterator> 1818 >::type * = 0) 1819 ) 1820 { 1821 return insert_range(position, first, last); 1822 } 1823 1824 #endif // ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 1825 1826 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 1827 /** **Equivalent to**: `insert(position, il.begin(), il.end())` */ insert(const_iterator position,std::initializer_list<T> il)1828 iterator insert(const_iterator position, std::initializer_list<T> il) 1829 { 1830 return insert_range(position, il.begin(), il.end()); 1831 } 1832 #endif 1833 1834 /** 1835 * [MoveAssignable]: http://en.cppreference.com/w/cpp/concept/MoveAssignable 1836 * 1837 * **Effects**: Destroys the element pointed by `position` and removes it from the devector. 1838 * Invalidates iterators. 1839 * 1840 * **Requires**: `T` shall be [MoveAssignable]. 1841 * 1842 * **Precondition**: `position` must be in the range of `[begin(), end())`. 1843 * 1844 * **Returns**: Iterator pointing to the element immediately following the erased element 1845 * prior to its erasure. If no such element exists, `end()` is returned. 1846 * 1847 * **Exceptions**: Strong exception guarantee if `T` is `NothrowAssignable`, 1848 * Basic exception guarantee otherwise. 1849 * 1850 * **Complexity**: Linear in half the size of `*this`. 1851 */ erase(const_iterator position)1852 iterator erase(const_iterator position) 1853 { 1854 return erase(position, position + 1); 1855 } 1856 1857 /** 1858 * [MoveAssignable]: http://en.cppreference.com/w/cpp/concept/MoveAssignable 1859 * 1860 * **Effects**: Destroys the range `[first,last)` and removes it from the devector. 1861 * Invalidates iterators. 1862 * 1863 * **Requires**: `T` shall be [MoveAssignable]. 1864 * 1865 * **Precondition**: `[first,last)` must be in the range of `[begin(), end())`. 1866 * 1867 * **Returns**: Iterator pointing to the element pointed to by `last` prior to any elements 1868 * being erased. If no such element exists, `end()` is returned. 1869 * 1870 * **Exceptions**: Strong exception guarantee if `T` is `NothrowAssignable`, 1871 * Basic exception guarantee otherwise. 1872 * 1873 * **Complexity**: Linear in half the size of `*this` 1874 * plus the distance between `first` and `last`. 1875 */ erase(const_iterator first,const_iterator last)1876 iterator erase(const_iterator first, const_iterator last) 1877 { 1878 iterator nc_first = begin() + (first - begin()); 1879 iterator nc_last = begin() + (last - begin()); 1880 return erase(nc_first, nc_last); 1881 } 1882 1883 /** 1884 * [MoveAssignable]: http://en.cppreference.com/w/cpp/concept/MoveAssignable 1885 * 1886 * **Effects**: Destroys the range `[first,last)` and removes it from the devector. 1887 * Invalidates iterators. 1888 * 1889 * **Requires**: `T` shall be [MoveAssignable]. 1890 * 1891 * **Precondition**: `[first,last)` must be in the range of `[begin(), end())`. 1892 * 1893 * **Returns**: Iterator pointing to the element pointed to by `last` prior to any elements 1894 * being erased. If no such element exists, `end()` is returned. 1895 * 1896 * **Exceptions**: Strong exception guarantee if `T` is `NothrowAssignable`, 1897 * Basic exception guarantee otherwise. 1898 * 1899 * **Complexity**: Linear in half the size of `*this`. 1900 */ erase(iterator first,iterator last)1901 iterator erase(iterator first, iterator last) 1902 { 1903 size_type front_distance = last - begin(); 1904 size_type back_distance = end() - first; 1905 size_type n = boost::container::iterator_distance(first, last); 1906 1907 if (front_distance < back_distance) 1908 { 1909 // move n to the right 1910 boost::container::move_backward(begin(), first, last); 1911 1912 for (iterator i = begin(); i != begin() + n; ++i) 1913 { 1914 allocator_traits_type::destroy(get_allocator_ref(), i); 1915 } 1916 //n is always less than max stored_size_type 1917 m_.set_front_idx(m_.front_idx + n); 1918 1919 BOOST_ASSERT(invariants_ok()); 1920 return last; 1921 } 1922 else { 1923 // move n to the left 1924 boost::container::move(last, end(), first); 1925 1926 for (iterator i = end() - n; i != end(); ++i) 1927 { 1928 allocator_traits_type::destroy(get_allocator_ref(), i); 1929 } 1930 //n is always less than max stored_size_type 1931 m_.set_back_idx(m_.back_idx - n); 1932 1933 BOOST_ASSERT(invariants_ok()); 1934 return first; 1935 } 1936 } 1937 1938 /** 1939 * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable 1940 * 1941 * **Effects**: exchanges the contents of `*this` and `b`. 1942 * 1943 * **Requires**: instances of `T` must be swappable by unqualified call of `swap` 1944 * and `T` must be [MoveInsertable] into `*this`. 1945 * 1946 * **Precondition**: The allocators should allow propagation or should compare equal. 1947 * 1948 * **Exceptions**: Basic exceptions guarantee if not `noexcept`. 1949 * 1950 * **Complexity**: Constant. 1951 */ swap(devector & b)1952 void swap(devector& b) 1953 BOOST_NOEXCEPT_IF( allocator_traits_type::propagate_on_container_swap::value 1954 || allocator_traits_type::is_always_equal::value) 1955 { 1956 BOOST_CONSTEXPR_OR_CONST bool propagate_alloc = allocator_traits_type::propagate_on_container_swap::value; 1957 BOOST_ASSERT(propagate_alloc || get_allocator_ref() == b.get_allocator_ref()); // else it's undefined behavior 1958 1959 swap_big_big(*this, b); 1960 1961 // swap indices 1962 boost::adl_move_swap(m_.front_idx, b.m_.front_idx); 1963 boost::adl_move_swap(m_.back_idx, b.m_.back_idx); 1964 1965 //And now swap the allocator 1966 dtl::swap_alloc(this->get_allocator_ref(), b.get_allocator_ref(), dtl::bool_<propagate_alloc>()); 1967 1968 BOOST_ASSERT( invariants_ok()); 1969 BOOST_ASSERT(b.invariants_ok()); 1970 } 1971 1972 /** 1973 * **Effects**: Destroys all elements in the devector. 1974 * Invalidates all references, pointers and iterators to the 1975 * elements of the devector. 1976 * 1977 * **Postcondition**: `empty() && front_free_capacity() == 0 1978 * && back_free_capacity() == old capacity`. 1979 * 1980 * **Complexity**: Linear in the size of `*this`. 1981 * 1982 * **Remarks**: Does not free memory. 1983 */ clear()1984 void clear() BOOST_NOEXCEPT 1985 { 1986 destroy_elements(begin(), end()); 1987 m_.front_idx = m_.back_idx = 0; 1988 } 1989 1990 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE operator ==(const devector & x,const devector & y)1991 friend bool operator==(const devector& x, const devector& y) 1992 { return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin()); } 1993 1994 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE operator !=(const devector & x,const devector & y)1995 friend bool operator!=(const devector& x, const devector& y) 1996 { return !(x == y); } 1997 1998 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE operator <(const devector & x,const devector & y)1999 friend bool operator< (const devector& x, const devector& y) 2000 { return boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); } 2001 2002 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE operator >(const devector & x,const devector & y)2003 friend bool operator>(const devector& x, const devector& y) 2004 { return y < x; } 2005 2006 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE operator <=(const devector & x,const devector & y)2007 friend bool operator<=(const devector& x, const devector& y) 2008 { return !(y < x); } 2009 2010 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE operator >=(const devector & x,const devector & y)2011 friend bool operator>=(const devector& x, const devector& y) 2012 { return !(x < y); } 2013 swap(devector & x,devector & y)2014 BOOST_CONTAINER_FORCEINLINE friend void swap(devector& x, devector& y) 2015 BOOST_NOEXCEPT_IF( allocator_traits_type::propagate_on_container_swap::value 2016 || allocator_traits_type::is_always_equal::value) 2017 { x.swap(y); } 2018 2019 private: 2020 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 2021 raw_begin()2022 BOOST_CONTAINER_FORCEINLINE T* raw_begin() BOOST_NOEXCEPT 2023 { return boost::movelib::to_raw_pointer(m_.buffer) + m_.front_idx; } 2024 raw_end()2025 BOOST_CONTAINER_FORCEINLINE T* raw_end() BOOST_NOEXCEPT 2026 { return boost::movelib::to_raw_pointer(m_.buffer) + m_.back_idx; } 2027 2028 2029 template <class U> priv_push_front(BOOST_FWD_REF (U)u)2030 BOOST_CONTAINER_FORCEINLINE void priv_push_front(BOOST_FWD_REF(U) u) 2031 { 2032 this->emplace_front(boost::forward<U>(u)); 2033 } 2034 2035 template <class U> priv_push_back(BOOST_FWD_REF (U)u)2036 BOOST_CONTAINER_FORCEINLINE void priv_push_back(BOOST_FWD_REF(U) u) 2037 { 2038 this->emplace_back(boost::forward<U>(u)); 2039 } 2040 2041 template <class U> priv_insert(const_iterator pos,BOOST_FWD_REF (U)u)2042 BOOST_CONTAINER_FORCEINLINE iterator priv_insert(const_iterator pos, BOOST_FWD_REF(U) u) 2043 { 2044 return this->emplace(pos, boost::forward<U>(u)); 2045 } 2046 2047 // allocator_type wrappers 2048 get_allocator_ref()2049 BOOST_CONTAINER_FORCEINLINE allocator_type& get_allocator_ref() BOOST_NOEXCEPT 2050 { 2051 return static_cast<allocator_type&>(m_); 2052 } 2053 get_allocator_ref() const2054 BOOST_CONTAINER_FORCEINLINE const allocator_type& get_allocator_ref() const BOOST_NOEXCEPT 2055 { 2056 return static_cast<const allocator_type&>(m_); 2057 } 2058 allocate(size_type capacity)2059 pointer allocate(size_type capacity) 2060 { 2061 //First detect overflow on smaller stored_size_types 2062 if (capacity > stored_size_type(-1)){ 2063 boost::container::throw_length_error("get_next_capacity, allocator's max size reached"); 2064 } 2065 //(clamp_by_stored_size_type<size_type>)(prefer_in_recvd_out_size, stored_size_type()); 2066 #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS 2067 ++m_.capacity_alloc_count; 2068 #endif // BOOST_CONTAINER_DEVECTOR_ALLOC_STATS 2069 return allocator_traits_type::allocate(get_allocator_ref(), capacity); 2070 } 2071 destroy_elements(pointer begin,pointer end)2072 void destroy_elements(pointer begin, pointer end) 2073 { 2074 for (; begin != end; ++begin) 2075 { 2076 allocator_traits_type::destroy(get_allocator_ref(), begin); 2077 } 2078 } 2079 deallocate_buffer()2080 void deallocate_buffer() 2081 { 2082 if (m_.buffer) 2083 { 2084 allocator_traits_type::deallocate(get_allocator_ref(), m_.buffer, m_.capacity); 2085 } 2086 } 2087 2088 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 2089 template <typename... Args> alloc_construct(pointer dst,Args &&...args)2090 BOOST_CONTAINER_FORCEINLINE void alloc_construct(pointer dst, Args&&... args) 2091 { 2092 allocator_traits_type::construct( 2093 get_allocator_ref(), 2094 dst, 2095 boost::forward<Args>(args)... 2096 ); 2097 } 2098 2099 template <typename... Args> construct_n(pointer buffer,size_type n,Args &&...args)2100 void construct_n(pointer buffer, size_type n, Args&&... args) 2101 { 2102 detail::construction_guard<allocator_type> ctr_guard(buffer, get_allocator_ref()); 2103 guarded_construct_n(buffer, n, ctr_guard, boost::forward<Args>(args)...); 2104 ctr_guard.release(); 2105 } 2106 2107 template <typename... Args> guarded_construct_n(pointer buffer,size_type n,detail::construction_guard<allocator_type> & ctr_guard,Args &&...args)2108 void guarded_construct_n(pointer buffer, size_type n, detail::construction_guard<allocator_type>& ctr_guard, Args&&... args) 2109 { 2110 for (size_type i = 0; i < n; ++i) { 2111 this->alloc_construct(buffer + i, boost::forward<Args>(args)...); 2112 ctr_guard.extend(); 2113 } 2114 } 2115 2116 #else //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 2117 2118 #define BOOST_CONTAINER_DEVECTOR_ALLOC_CONSTRUCT(N) \ 2119 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 2120 BOOST_CONTAINER_FORCEINLINE void alloc_construct(pointer dst BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ 2121 {\ 2122 allocator_traits_type::construct(\ 2123 get_allocator_ref(), dst BOOST_MOVE_I##N BOOST_MOVE_FWD##N );\ 2124 }\ 2125 \ 2126 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 2127 void construct_n(pointer buffer, size_type n BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ 2128 {\ 2129 detail::construction_guard<allocator_type> ctr_guard(buffer, get_allocator_ref());\ 2130 guarded_construct_n(buffer, n, ctr_guard BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ 2131 ctr_guard.release();\ 2132 }\ 2133 \ 2134 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 2135 void guarded_construct_n(pointer buffer, size_type n, detail::construction_guard<allocator_type>& ctr_guard BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ 2136 {\ 2137 for (size_type i = 0; i < n; ++i) {\ 2138 this->alloc_construct(buffer + i BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ 2139 ctr_guard.extend();\ 2140 }\ 2141 } 2142 // BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_DEVECTOR_ALLOC_CONSTRUCT)2143 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_DEVECTOR_ALLOC_CONSTRUCT) 2144 #undef BOOST_CONTAINER_DEVECTOR_ALLOC_CONSTRUCT 2145 2146 #endif //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 2147 2148 BOOST_CONTAINER_FORCEINLINE size_type front_capacity() const 2149 { 2150 return m_.back_idx; 2151 } 2152 back_capacity() const2153 BOOST_CONTAINER_FORCEINLINE size_type back_capacity() const 2154 { 2155 return m_.capacity - m_.front_idx; 2156 } 2157 calculate_new_capacity(size_type requested_capacity)2158 size_type calculate_new_capacity(size_type requested_capacity) 2159 { 2160 size_type max = allocator_traits_type::max_size(this->get_allocator_ref()); 2161 (clamp_by_stored_size_type)(max, stored_size_type()); 2162 const size_type remaining_additional_cap = max - size_type(m_.capacity); 2163 const size_type min_additional_cap = requested_capacity - size_type(m_.capacity); 2164 if ( remaining_additional_cap < min_additional_cap ) 2165 boost::container::throw_length_error("devector: get_next_capacity, max size exceeded"); 2166 2167 return growth_factor_type()( size_type(m_.capacity), min_additional_cap, max); 2168 } 2169 buffer_move_or_copy(pointer dst)2170 void buffer_move_or_copy(pointer dst) 2171 { 2172 detail::construction_guard<allocator_type> guard(dst, get_allocator_ref()); 2173 2174 buffer_move_or_copy(dst, guard); 2175 2176 guard.release(); 2177 } 2178 buffer_move_or_copy(pointer dst,detail::construction_guard<allocator_type> & guard)2179 void buffer_move_or_copy(pointer dst, detail::construction_guard<allocator_type>& guard) 2180 { 2181 opt_move_or_copy(begin(), end(), dst, guard); 2182 2183 destroy_elements(data(), data() + size()); 2184 deallocate_buffer(); 2185 } 2186 opt_move_or_copy(pointer begin,pointer end,pointer dst)2187 void opt_move_or_copy(pointer begin, pointer end, pointer dst) 2188 { 2189 typedef typename dtl::if_c 2190 < boost::move_detail::is_nothrow_copy_constructible<T>::value || boost::is_nothrow_move_constructible<T>::value 2191 , detail::null_construction_guard 2192 , detail::construction_guard<allocator_type> 2193 >::type guard_t; 2194 2195 guard_t guard(dst, get_allocator_ref()); 2196 2197 opt_move_or_copy(begin, end, dst, guard); 2198 2199 guard.release(); 2200 } 2201 2202 template <typename Guard> opt_move_or_copy(pointer begin,pointer end,pointer dst,Guard & guard)2203 void opt_move_or_copy(pointer begin, pointer end, pointer dst, Guard& guard) 2204 { 2205 // if trivial copy and default allocator, memcpy 2206 boost::container::uninitialized_move_alloc(get_allocator_ref(), begin, end, dst); 2207 guard.extend(); 2208 } 2209 2210 template <typename Iterator> opt_copy(Iterator begin,Iterator end,pointer dst)2211 void opt_copy(Iterator begin, Iterator end, pointer dst) 2212 { 2213 typedef typename dtl::if_c 2214 < boost::move_detail::is_nothrow_copy_constructible<T>::value 2215 , detail::null_construction_guard 2216 , detail::construction_guard<allocator_type> 2217 >::type guard_t; 2218 2219 guard_t guard(dst, get_allocator_ref()); 2220 2221 opt_copy(begin, end, dst, guard); 2222 2223 guard.release(); 2224 } 2225 2226 template <typename Iterator, typename Guard> opt_copy(Iterator begin,Iterator end,pointer dst,Guard & guard)2227 void opt_copy(Iterator begin, Iterator end, pointer dst, Guard& guard) 2228 { 2229 while (begin != end) 2230 { 2231 this->alloc_construct(dst++, *begin++); 2232 guard.extend(); 2233 } 2234 } 2235 2236 template <typename Guard> opt_copy(const_pointer begin,const_pointer end,pointer dst,Guard & guard)2237 void opt_copy(const_pointer begin, const_pointer end, pointer dst, Guard& guard) 2238 { 2239 // if trivial copy and default allocator, memcpy 2240 boost::container::uninitialized_copy_alloc(get_allocator_ref(), begin, end, dst); 2241 guard.extend(); 2242 } 2243 2244 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 2245 2246 template <typename... Args> resize_front_impl(size_type sz,Args &&...args)2247 void resize_front_impl(size_type sz , Args&&... args) 2248 { 2249 if (sz > size()) 2250 { 2251 const size_type n = sz - size(); 2252 2253 if (sz <= front_capacity()) 2254 { 2255 construct_n(m_.buffer + m_.front_idx - n, n, boost::forward<Args>(args)...); 2256 m_.set_front_idx(m_.front_idx - n); 2257 } 2258 else 2259 { 2260 resize_front_slow_path(sz, n, boost::forward<Args>(args)...); 2261 } 2262 } 2263 else { 2264 while (this->size() > sz) 2265 { 2266 this->pop_front(); 2267 } 2268 } 2269 } 2270 2271 template <typename... Args> resize_front_slow_path(size_type sz,size_type n,Args &&...args)2272 void resize_front_slow_path(size_type sz, size_type n, Args&&... args) 2273 { 2274 const size_type new_capacity = calculate_new_capacity(sz + back_free_capacity()); 2275 pointer new_buffer = allocate(new_capacity); 2276 allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref()); 2277 2278 const size_type new_old_elem_index = new_capacity - size(); 2279 const size_type new_elem_index = new_old_elem_index - n; 2280 2281 detail::construction_guard<allocator_type> guard(new_buffer + new_elem_index, get_allocator_ref()); 2282 guarded_construct_n(new_buffer + new_elem_index, n, guard, boost::forward<Args>(args)...); 2283 2284 buffer_move_or_copy(new_buffer + new_old_elem_index, guard); 2285 2286 guard.release(); 2287 new_buffer_guard.release(); 2288 2289 m_.buffer = new_buffer; 2290 m_.set_capacity(new_capacity); 2291 m_.set_back_idx(new_old_elem_index + m_.back_idx - m_.front_idx); 2292 m_.set_front_idx(new_elem_index); 2293 } 2294 2295 template <typename... Args> resize_back_impl(size_type sz,Args &&...args)2296 void resize_back_impl(size_type sz, Args&&... args) 2297 { 2298 if (sz > size()) 2299 { 2300 const size_type n = sz - size(); 2301 2302 if (sz <= back_capacity()) 2303 { 2304 construct_n(m_.buffer + m_.back_idx, n, boost::forward<Args>(args)...); 2305 m_.set_back_idx(m_.back_idx + n); 2306 } 2307 else 2308 { 2309 resize_back_slow_path(sz, n, boost::forward<Args>(args)...); 2310 } 2311 } 2312 else 2313 { 2314 while (size() > sz) 2315 { 2316 pop_back(); 2317 } 2318 } 2319 } 2320 2321 template <typename... Args> resize_back_slow_path(size_type sz,size_type n,Args &&...args)2322 void resize_back_slow_path(size_type sz, size_type n, Args&&... args) 2323 { 2324 const size_type new_capacity = calculate_new_capacity(sz + front_free_capacity()); 2325 pointer new_buffer = allocate(new_capacity); 2326 allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref()); 2327 2328 detail::construction_guard<allocator_type> guard(new_buffer + m_.back_idx, get_allocator_ref()); 2329 guarded_construct_n(new_buffer + m_.back_idx, n, guard, boost::forward<Args>(args)...); 2330 2331 buffer_move_or_copy(new_buffer + m_.front_idx); 2332 2333 guard.release(); 2334 new_buffer_guard.release(); 2335 2336 m_.buffer = new_buffer; 2337 m_.set_capacity(new_capacity); 2338 m_.set_back_idx(m_.back_idx + n); 2339 } 2340 2341 template <typename... Args> emplace_slow_path(size_type new_elem_index,Args &&...args)2342 iterator emplace_slow_path(size_type new_elem_index, Args&&... args) 2343 { 2344 pointer position = begin() + new_elem_index; 2345 2346 // prefer moving front to access memory forward if there are less elems to move 2347 bool prefer_move_front = new_elem_index <= size()/2; 2348 2349 if (front_free_capacity() && (!back_free_capacity() || prefer_move_front)) 2350 { 2351 BOOST_ASSERT(size() >= 1); 2352 2353 // move things closer to the front a bit 2354 2355 // avoid invalidating any reference in args later 2356 T tmp(boost::forward<Args>(args)...); 2357 2358 // construct at front - 1 from front (no guard) 2359 this->alloc_construct(begin() - 1, boost::move(*begin())); 2360 2361 // move front half left 2362 boost::move(begin() + 1, position, begin()); 2363 --m_.front_idx; 2364 2365 // move assign new elem before pos 2366 --position; 2367 *position = boost::move(tmp); 2368 2369 return position; 2370 } 2371 else if (back_free_capacity()) { 2372 BOOST_ASSERT(size() >= 1); 2373 2374 // move things closer to the end a bit 2375 2376 // avoid invalidating any reference in args later 2377 T tmp(boost::forward<Args>(args)...); 2378 2379 // construct at back + 1 from back (no guard) 2380 this->alloc_construct(end(), boost::move(back())); 2381 2382 // move back half right 2383 boost::container::move_backward(position, end() - 1, end()); 2384 ++m_.back_idx; 2385 2386 // move assign new elem to pos 2387 *position = boost::move(tmp); 2388 2389 return position; 2390 } 2391 else 2392 { 2393 return emplace_reallocating_slow_path(prefer_move_front, new_elem_index, boost::forward<Args>(args)...); 2394 } 2395 } 2396 2397 template <typename... Args> emplace_reallocating_slow_path(bool make_front_free,size_type new_elem_index,Args &&...args)2398 pointer emplace_reallocating_slow_path(bool make_front_free, size_type new_elem_index, Args&&... args) 2399 { 2400 // reallocate 2401 size_type new_capacity = calculate_new_capacity(capacity() + 1); 2402 pointer new_buffer = allocate(new_capacity); 2403 2404 // guard allocation 2405 allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref()); 2406 2407 size_type new_front_index = (make_front_free) 2408 ? new_capacity - back_free_capacity() - size() - 1 2409 : m_.front_idx; 2410 2411 iterator new_begin = new_buffer + new_front_index; 2412 iterator new_position = new_begin + new_elem_index; 2413 iterator old_position = begin() + new_elem_index; 2414 2415 // construct new element (and guard it) 2416 this->alloc_construct(new_position, boost::forward<Args>(args)...); 2417 2418 detail::construction_guard<allocator_type> second_half_guard(new_position, get_allocator_ref()); 2419 second_half_guard.extend(); 2420 2421 // move front-pos (possibly guarded) 2422 detail::construction_guard<allocator_type> first_half_guard(new_begin, get_allocator_ref()); 2423 opt_move_or_copy(begin(), old_position, new_begin, first_half_guard); 2424 2425 // move pos+1-end (possibly guarded) 2426 opt_move_or_copy(old_position, end(), new_position + 1, second_half_guard); 2427 2428 // cleanup 2429 destroy_elements(begin(), end()); 2430 deallocate_buffer(); 2431 2432 // release alloc and other guards 2433 second_half_guard.release(); 2434 first_half_guard.release(); 2435 new_buffer_guard.release(); 2436 2437 // rebind members 2438 m_.set_capacity(new_capacity); 2439 m_.buffer = new_buffer; 2440 m_.set_back_idx(new_front_index + size() + 1); 2441 m_.set_front_idx(new_front_index); 2442 2443 return new_position; 2444 } 2445 2446 #else //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 2447 2448 #define BOOST_CONTAINER_DEVECTOR_SLOW_PATH(N) \ 2449 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 2450 void resize_front_impl(size_type sz BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ 2451 {\ 2452 if (sz > size())\ 2453 {\ 2454 const size_type n = sz - size();\ 2455 if (sz <= front_capacity()){\ 2456 construct_n(m_.buffer + m_.front_idx - n, n BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ 2457 m_.set_front_idx(m_.front_idx - n);\ 2458 }\ 2459 else\ 2460 {\ 2461 resize_front_slow_path(sz, n BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ 2462 }\ 2463 }\ 2464 else {\ 2465 while (this->size() > sz)\ 2466 {\ 2467 this->pop_front();\ 2468 }\ 2469 }\ 2470 }\ 2471 \ 2472 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 2473 void resize_front_slow_path(size_type sz, size_type n BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ 2474 {\ 2475 const size_type new_capacity = calculate_new_capacity(sz + back_free_capacity());\ 2476 pointer new_buffer = allocate(new_capacity);\ 2477 allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref());\ 2478 \ 2479 const size_type new_old_elem_index = new_capacity - size();\ 2480 const size_type new_elem_index = new_old_elem_index - n;\ 2481 \ 2482 detail::construction_guard<allocator_type> guard(new_buffer + new_elem_index, get_allocator_ref());\ 2483 guarded_construct_n(new_buffer + new_elem_index, n, guard BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ 2484 \ 2485 buffer_move_or_copy(new_buffer + new_old_elem_index, guard);\ 2486 \ 2487 guard.release();\ 2488 new_buffer_guard.release();\ 2489 m_.buffer = new_buffer;\ 2490 m_.set_capacity(new_capacity);\ 2491 m_.set_back_idx(new_old_elem_index + m_.back_idx - m_.front_idx);\ 2492 m_.set_front_idx(new_elem_index);\ 2493 }\ 2494 \ 2495 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 2496 void resize_back_impl(size_type sz BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ 2497 {\ 2498 if (sz > size())\ 2499 {\ 2500 const size_type n = sz - size();\ 2501 \ 2502 if (sz <= back_capacity())\ 2503 {\ 2504 construct_n(m_.buffer + m_.back_idx, n BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ 2505 m_.set_back_idx(m_.back_idx + n);\ 2506 }\ 2507 else\ 2508 {\ 2509 resize_back_slow_path(sz, n BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ 2510 }\ 2511 }\ 2512 else\ 2513 {\ 2514 while (size() > sz)\ 2515 {\ 2516 pop_back();\ 2517 }\ 2518 }\ 2519 }\ 2520 \ 2521 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 2522 void resize_back_slow_path(size_type sz, size_type n BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ 2523 {\ 2524 const size_type new_capacity = calculate_new_capacity(sz + front_free_capacity());\ 2525 pointer new_buffer = allocate(new_capacity);\ 2526 allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref());\ 2527 \ 2528 detail::construction_guard<allocator_type> guard(new_buffer + m_.back_idx, get_allocator_ref());\ 2529 guarded_construct_n(new_buffer + m_.back_idx, n, guard BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ 2530 \ 2531 buffer_move_or_copy(new_buffer + m_.front_idx);\ 2532 \ 2533 guard.release();\ 2534 new_buffer_guard.release();\ 2535 \ 2536 m_.buffer = new_buffer;\ 2537 m_.set_capacity(new_capacity);\ 2538 m_.set_back_idx(m_.back_idx + n);\ 2539 }\ 2540 \ 2541 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 2542 iterator emplace_slow_path(size_type new_elem_index BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ 2543 {\ 2544 pointer position = begin() + new_elem_index;\ 2545 \ 2546 bool prefer_move_front = new_elem_index <= size()/2;\ 2547 \ 2548 if (front_free_capacity() && (!back_free_capacity() || prefer_move_front))\ 2549 {\ 2550 BOOST_ASSERT(size() >= 1);\ 2551 typename dtl::aligned_storage<sizeof(T), dtl::alignment_of<T>::value>::type v;\ 2552 T *vp = reinterpret_cast<T *>(v.data);\ 2553 allocator_traits_type::construct(get_stored_allocator(), vp BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ 2554 T &tmp = *vp;\ 2555 dtl::value_destructor<allocator_type> on_exit(get_stored_allocator(), tmp); (void)on_exit;\ 2556 \ 2557 this->alloc_construct(begin() - 1, boost::move(*begin()));\ 2558 boost::move(begin() + 1, position, begin());\ 2559 --m_.front_idx;\ 2560 --position;\ 2561 *position = boost::move(tmp);\ 2562 return position;\ 2563 }\ 2564 else if (back_free_capacity()) {\ 2565 BOOST_ASSERT(size() >= 1);\ 2566 typename dtl::aligned_storage<sizeof(T), dtl::alignment_of<T>::value>::type v;\ 2567 T *vp = reinterpret_cast<T *>(v.data);\ 2568 allocator_traits_type::construct(get_stored_allocator(), vp BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ 2569 T &tmp = *vp;\ 2570 dtl::value_destructor<allocator_type> on_exit(get_stored_allocator(), tmp); (void)on_exit;\ 2571 this->alloc_construct(end(), boost::move(back()));\ 2572 boost::container::move_backward(position, end() - 1, end());\ 2573 ++m_.back_idx;\ 2574 *position = boost::move(tmp);\ 2575 return position;\ 2576 }\ 2577 else {\ 2578 return emplace_reallocating_slow_path(prefer_move_front, new_elem_index BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ 2579 }\ 2580 }\ 2581 \ 2582 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 2583 pointer emplace_reallocating_slow_path(bool make_front_free, size_type new_elem_index BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ 2584 {\ 2585 size_type new_capacity = calculate_new_capacity(capacity() + 1);\ 2586 pointer new_buffer = allocate(new_capacity);\ 2587 allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref());\ 2588 size_type new_front_index = (make_front_free)\ 2589 ? new_capacity - back_free_capacity() - size() - 1\ 2590 : m_.front_idx;\ 2591 iterator new_begin = new_buffer + new_front_index;\ 2592 iterator new_position = new_begin + new_elem_index;\ 2593 iterator old_position = begin() + new_elem_index;\ 2594 this->alloc_construct(new_position BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ 2595 detail::construction_guard<allocator_type> second_half_guard(new_position, get_allocator_ref());\ 2596 second_half_guard.extend();\ 2597 detail::construction_guard<allocator_type> first_half_guard(new_begin, get_allocator_ref());\ 2598 opt_move_or_copy(begin(), old_position, new_begin, first_half_guard);\ 2599 opt_move_or_copy(old_position, end(), new_position + 1, second_half_guard);\ 2600 destroy_elements(begin(), end());\ 2601 deallocate_buffer();\ 2602 second_half_guard.release();\ 2603 first_half_guard.release();\ 2604 new_buffer_guard.release();\ 2605 m_.set_capacity(new_capacity);\ 2606 m_.buffer = new_buffer;\ 2607 m_.set_back_idx(new_front_index + size() + 1);\ 2608 m_.set_front_idx(new_front_index);\ 2609 return new_position;\ 2610 }\ 2611 // BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_DEVECTOR_SLOW_PATH)2612 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_DEVECTOR_SLOW_PATH) 2613 #undef BOOST_CONTAINER_DEVECTOR_SLOW_PATH 2614 2615 #endif //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 2616 /* 2617 void unsafe_uninitialized_grow_front(size_type n) 2618 { 2619 BOOST_ASSERT(n >= size()); 2620 2621 size_type need = n - size(); 2622 2623 if (need > front_free_capacity()) 2624 { 2625 reallocate_at(n + back_free_capacity(), need); 2626 } 2627 2628 m_.set_front_idx(m_.front_idx - need); 2629 } 2630 2631 void unsafe_uninitialized_shrink_front(size_type n) 2632 { 2633 BOOST_ASSERT(n <= size()); 2634 2635 size_type doesnt_need = size() - n; 2636 m_.set_front_idx(m_.front_idx + doesnt_need); 2637 } 2638 2639 void unsafe_uninitialized_grow_back(size_type n) 2640 { 2641 BOOST_ASSERT(n >= size()); 2642 2643 size_type need = n - size(); 2644 2645 if (need > back_free_capacity()) 2646 { 2647 reallocate_at(n + front_free_capacity(), front_free_capacity()); 2648 } 2649 2650 m_.set_back_idx(m_.back_idx + need); 2651 } 2652 2653 void unsafe_uninitialized_shrink_back(size_type n) 2654 { 2655 BOOST_ASSERT(n <= size()); 2656 2657 size_type doesnt_need = size() - n; 2658 m_.set_back_idx(m_.back_idx - doesnt_need); 2659 } 2660 */ 2661 2662 void reallocate_at(size_type new_capacity, size_type buffer_offset) 2663 { 2664 pointer new_buffer = allocate(new_capacity); 2665 allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref()); 2666 2667 buffer_move_or_copy(new_buffer + buffer_offset); 2668 2669 new_buffer_guard.release(); 2670 2671 m_.buffer = new_buffer; 2672 //Safe cast, allocate() will handle stored_size_type overflow 2673 m_.set_capacity(new_capacity); 2674 m_.set_back_idx(m_.back_idx - m_.front_idx + buffer_offset); 2675 m_.set_front_idx(buffer_offset); 2676 2677 BOOST_ASSERT(invariants_ok()); 2678 } 2679 2680 template <typename ForwardIterator> insert_range(const_iterator position,ForwardIterator first,ForwardIterator last)2681 iterator insert_range(const_iterator position, ForwardIterator first, ForwardIterator last) 2682 { 2683 size_type n = boost::container::iterator_distance(first, last); 2684 2685 if (position == end() && back_free_capacity() >= n) {// fast path 2686 iterator r(this->end()); 2687 boost::container::uninitialized_copy_alloc(get_allocator_ref(), first, last, this->raw_end()); 2688 m_.set_back_idx(m_.back_idx + n); 2689 return r; 2690 } 2691 else if (position == begin() && front_free_capacity() >= n) { // secondary fast path 2692 boost::container::uninitialized_copy_alloc(get_allocator_ref(), first, last, this->raw_begin() - n); 2693 m_.set_front_idx(m_.front_idx - n); 2694 return begin(); 2695 } 2696 else { 2697 return insert_range_slow_path(position, first, last); 2698 } 2699 } 2700 2701 template <typename ForwardIterator> insert_range_slow_path(const_iterator position,ForwardIterator first,ForwardIterator last)2702 iterator insert_range_slow_path(const_iterator position, ForwardIterator first, ForwardIterator last) 2703 { 2704 size_type n = boost::container::iterator_distance(first, last); 2705 size_type index = position - begin(); 2706 2707 if (front_free_capacity() + back_free_capacity() >= n) { 2708 // if we move enough, it can be done without reallocation 2709 2710 iterator middle = begin() + index; 2711 n -= insert_range_slow_path_near_front(middle, first, n); 2712 2713 if (n) { 2714 insert_range_slow_path_near_back(middle, first, n); 2715 } 2716 2717 BOOST_ASSERT(first == last); 2718 return begin() + index; 2719 } 2720 else { 2721 const bool prefer_move_front = 2 * index <= size(); 2722 return insert_range_reallocating_slow_path(prefer_move_front, index, first, n); 2723 } 2724 } 2725 2726 template <typename Iterator> insert_range_slow_path_near_front(iterator position,Iterator & first,size_type n)2727 size_type insert_range_slow_path_near_front(iterator position, Iterator& first, size_type n) 2728 { 2729 size_type n_front = dtl::min_value(front_free_capacity(), n); 2730 iterator new_begin = begin() - n_front; 2731 iterator ctr_pos = new_begin; 2732 detail::construction_guard<allocator_type> ctr_guard(ctr_pos, get_allocator_ref()); 2733 2734 while (ctr_pos != begin()) { 2735 this->alloc_construct(ctr_pos++, *(first++)); 2736 ctr_guard.extend(); 2737 } 2738 2739 boost::movelib::rotate_gcd(new_begin, ctr_pos, position); 2740 m_.set_front_idx(m_.front_idx - n_front); 2741 2742 ctr_guard.release(); 2743 2744 BOOST_ASSERT(invariants_ok()); 2745 2746 return n_front; 2747 } 2748 2749 template <typename Iterator> insert_range_slow_path_near_back(iterator position,Iterator & first,size_type n)2750 size_type insert_range_slow_path_near_back(iterator position, Iterator& first, size_type n) 2751 { 2752 const size_type n_back = dtl::min_value(back_free_capacity(), n); 2753 iterator ctr_pos = end(); 2754 2755 detail::construction_guard<allocator_type> ctr_guard(ctr_pos, get_allocator_ref()); 2756 2757 for (size_type i = 0; i < n_back; ++i) { 2758 this->alloc_construct(ctr_pos++, *first++); 2759 ctr_guard.extend(); 2760 } 2761 2762 boost::movelib::rotate_gcd(position, end(), ctr_pos); 2763 m_.set_back_idx(m_.back_idx + n_back); 2764 2765 ctr_guard.release(); 2766 2767 BOOST_ASSERT(invariants_ok()); 2768 2769 return n_back; 2770 } 2771 2772 template <typename Iterator> insert_range_reallocating_slow_path(bool make_front_free,size_type new_elem_index,Iterator elems,size_type n)2773 iterator insert_range_reallocating_slow_path 2774 (bool make_front_free, size_type new_elem_index, Iterator elems, size_type n) 2775 { 2776 // reallocate 2777 const size_type new_capacity = calculate_new_capacity(capacity() + n); 2778 pointer new_buffer = allocate(new_capacity); 2779 2780 // guard allocation 2781 allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref()); 2782 2783 const size_type new_front_index = (make_front_free) 2784 ? new_capacity - back_free_capacity() - size() - n 2785 : m_.front_idx; 2786 2787 const iterator new_begin = new_buffer + new_front_index; 2788 const iterator new_position = new_begin + new_elem_index; 2789 const iterator old_position = begin() + new_elem_index; 2790 2791 // construct new element (and guard it) 2792 iterator second_half_position = new_position; 2793 detail::construction_guard<allocator_type> second_half_guard(second_half_position, get_allocator_ref()); 2794 2795 for (size_type i = 0; i < n; ++i) { 2796 this->alloc_construct(second_half_position++, *(elems++)); 2797 second_half_guard.extend(); 2798 } 2799 2800 // move front-pos (possibly guarded) 2801 detail::construction_guard<allocator_type> first_half_guard(new_begin, get_allocator_ref()); 2802 opt_move_or_copy(begin(), old_position, new_begin, first_half_guard); 2803 2804 // move pos+1-end (possibly guarded) 2805 opt_move_or_copy(old_position, end(), second_half_position, second_half_guard); 2806 2807 // cleanup 2808 destroy_elements(begin(), end()); 2809 deallocate_buffer(); 2810 2811 // release alloc and other guards 2812 second_half_guard.release(); 2813 first_half_guard.release(); 2814 new_buffer_guard.release(); 2815 2816 // rebind members 2817 m_.set_capacity(new_capacity); 2818 m_.buffer = new_buffer; 2819 m_.set_back_idx(new_front_index + size() + n); 2820 m_.set_front_idx(new_front_index); 2821 2822 return new_position; 2823 } 2824 2825 template <typename Iterator> construct_from_range(Iterator begin,Iterator end)2826 void construct_from_range(Iterator begin, Iterator end) 2827 { 2828 allocation_guard buffer_guard(m_.buffer, m_.capacity, get_allocator_ref()); 2829 opt_copy(begin, end, m_.buffer); 2830 2831 buffer_guard.release(); 2832 } 2833 2834 template <typename ForwardIterator> allocate_and_copy_range(ForwardIterator first,ForwardIterator last)2835 void allocate_and_copy_range(ForwardIterator first, ForwardIterator last) 2836 { 2837 size_type n = boost::container::iterator_distance(first, last); 2838 2839 pointer new_buffer = n ? allocate(n) : pointer(); 2840 allocation_guard new_buffer_guard(new_buffer, n, get_allocator_ref()); 2841 2842 opt_copy(first, last, new_buffer); 2843 2844 destroy_elements(begin(), end()); 2845 deallocate_buffer(); 2846 2847 m_.set_capacity(n); 2848 m_.buffer = new_buffer; 2849 m_.front_idx = 0; 2850 m_.set_back_idx(n); 2851 2852 new_buffer_guard.release(); 2853 } 2854 swap_big_big(devector & a,devector & b)2855 static void swap_big_big(devector& a, devector& b) BOOST_NOEXCEPT 2856 { 2857 boost::adl_move_swap(a.m_.capacity, b.m_.capacity); 2858 boost::adl_move_swap(a.m_.buffer, b.m_.buffer); 2859 } 2860 2861 template <typename ForwardIterator> overwrite_buffer_impl(ForwardIterator first,ForwardIterator last,dtl::true_)2862 void overwrite_buffer_impl(ForwardIterator first, ForwardIterator last, dtl::true_) 2863 { 2864 const size_type n = boost::container::iterator_distance(first, last); 2865 2866 BOOST_ASSERT(capacity() >= n); 2867 boost::container::uninitialized_copy_alloc_n 2868 ( get_allocator_ref(), boost::movelib::iterator_to_raw_pointer(first) 2869 , n, boost::movelib::iterator_to_raw_pointer(m_.buffer)); 2870 m_.front_idx = 0; 2871 m_.set_back_idx(n); 2872 } 2873 2874 template <typename InputIterator> overwrite_buffer_impl(InputIterator first,InputIterator last,dtl::false_)2875 InputIterator overwrite_buffer_impl(InputIterator first, InputIterator last, dtl::false_) 2876 { 2877 pointer pos = m_.buffer; 2878 detail::construction_guard<allocator_type> front_guard(pos, get_allocator_ref()); 2879 2880 while (first != last && pos != begin()) { 2881 this->alloc_construct(pos++, *first++); 2882 front_guard.extend(); 2883 } 2884 2885 while (first != last && pos != end()) { 2886 *pos++ = *first++; 2887 } 2888 2889 detail::construction_guard<allocator_type> back_guard(pos, get_allocator_ref()); 2890 2891 iterator capacity_end = m_.buffer + capacity(); 2892 while (first != last && pos != capacity_end) { 2893 this->alloc_construct(pos++, *first++); 2894 back_guard.extend(); 2895 } 2896 2897 pointer destroy_after = dtl::min_value(dtl::max_value(begin(), pos), end()); 2898 destroy_elements(destroy_after, end()); 2899 2900 front_guard.release(); 2901 back_guard.release(); 2902 2903 m_.front_idx = 0; 2904 m_.set_back_idx(pos - begin()); 2905 return first; 2906 } 2907 2908 template <typename ForwardIterator> overwrite_buffer(ForwardIterator first,ForwardIterator last)2909 BOOST_CONTAINER_FORCEINLINE void overwrite_buffer(ForwardIterator first, ForwardIterator last) 2910 { 2911 this->overwrite_buffer_impl(first, last, 2912 dtl::bool_<dtl::is_trivially_destructible<T>::value>()); 2913 } 2914 invariants_ok()2915 bool invariants_ok() 2916 { 2917 return (!m_.capacity || m_.buffer) 2918 && m_.front_idx <= m_.back_idx 2919 && m_.back_idx <= m_.capacity; 2920 } 2921 2922 struct impl : allocator_type 2923 { implboost::container::devector::impl2924 impl() 2925 : allocator_type(), buffer(), front_idx(), back_idx(), capacity() 2926 #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS 2927 , capacity_alloc_count() 2928 #endif 2929 {} 2930 implboost::container::devector::impl2931 explicit impl(const allocator_type &a) 2932 : allocator_type(a), buffer(), front_idx(), back_idx(), capacity() 2933 #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS 2934 , capacity_alloc_count() 2935 #endif 2936 {} 2937 implboost::container::devector::impl2938 impl(const allocator_type &a, pointer p, size_type f, size_type b, size_type c) 2939 : allocator_type(a), buffer(p) 2940 //static cast sizes, as the allocation function will take care of overflows 2941 , front_idx(static_cast<stored_size_type>(f)) 2942 , back_idx(static_cast<stored_size_type>(b)) 2943 , capacity(static_cast<stored_size_type>(c)) 2944 #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS 2945 , capacity_alloc_count() 2946 #endif 2947 {} 2948 implboost::container::devector::impl2949 impl(BOOST_RV_REF(allocator_type) a, pointer p, size_type f, size_type b, size_type c) 2950 : allocator_type(boost::move(a)), buffer(p) 2951 //static cast sizes, as the allocation function will take care of overflows 2952 , front_idx(static_cast<stored_size_type>(f)) 2953 , back_idx(static_cast<stored_size_type>(b)) 2954 , capacity(static_cast<stored_size_type>(c)) 2955 #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS 2956 , capacity_alloc_count() 2957 #endif 2958 {} 2959 set_back_idxboost::container::devector::impl2960 void set_back_idx(size_type bi) 2961 { back_idx = static_cast<stored_size_type>(bi);} 2962 set_front_idxboost::container::devector::impl2963 void set_front_idx(size_type fi) 2964 { front_idx = static_cast<stored_size_type>(fi);} 2965 set_capacityboost::container::devector::impl2966 void set_capacity(size_type c) 2967 { capacity = static_cast<stored_size_type>(c);} 2968 2969 pointer buffer; 2970 stored_size_type front_idx; 2971 stored_size_type back_idx; 2972 stored_size_type capacity; 2973 #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS 2974 size_type capacity_alloc_count; 2975 #endif 2976 } m_; 2977 2978 2979 #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS 2980 public: reset_alloc_stats()2981 void reset_alloc_stats() 2982 { 2983 m_.capacity_alloc_count = 0; 2984 } 2985 get_alloc_count() const2986 size_type get_alloc_count() const 2987 { 2988 return m_.capacity_alloc_count; 2989 } 2990 2991 #endif // ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS 2992 2993 #endif // ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 2994 }; 2995 2996 }} // namespace boost::container 2997 2998 #include <boost/container/detail/config_end.hpp> 2999 3000 #endif // BOOST_CONTAINER_DEVECTOR_HPP 3001