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