| ////////////////////////////////////////////////////////////////////////////// |
| // |
| // (C) Copyright Benedek Thaler 2015-2016 |
| // (C) Copyright Ion Gaztanaga 2019-2020. Distributed under the Boost |
| // Software License, Version 1.0. (See accompanying file |
| // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) |
| // |
| // See http://www.boost.org/libs/container for documentation. |
| // |
| ////////////////////////////////////////////////////////////////////////////// |
| |
| #ifndef BOOST_CONTAINER_DEVECTOR_HPP |
| #define BOOST_CONTAINER_DEVECTOR_HPP |
| |
| #include <boost/container/detail/config_begin.hpp> |
| #include <boost/container/detail/workaround.hpp> |
| |
| //#include <algorithm> |
| #include <cstring> // memcpy |
| |
| #include <boost/assert.hpp> |
| #include <boost/aligned_storage.hpp> |
| |
| #include <boost/container/detail/copy_move_algo.hpp> |
| #include <boost/container/new_allocator.hpp> //new_allocator |
| #include <boost/container/allocator_traits.hpp> //allocator_traits |
| #include <boost/container/detail/algorithm.hpp> //equal() |
| #include <boost/container/throw_exception.hpp> |
| #include <boost/container/options.hpp> |
| |
| #include <boost/container/detail/guards_dended.hpp> |
| #include <boost/container/detail/iterator.hpp> |
| #include <boost/container/detail/iterators.hpp> |
| #include <boost/container/detail/destroyers.hpp> |
| #include <boost/container/detail/min_max.hpp> |
| #include <boost/container/detail/next_capacity.hpp> |
| #include <boost/container/detail/alloc_helpers.hpp> |
| |
| // move |
| #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) |
| #include <boost/move/detail/fwd_macros.hpp> |
| #endif |
| #include <boost/move/detail/move_helpers.hpp> |
| #include <boost/move/adl_move_swap.hpp> |
| #include <boost/move/iterator.hpp> |
| #include <boost/move/traits.hpp> |
| #include <boost/move/utility_core.hpp> |
| #include <boost/move/detail/to_raw_pointer.hpp> |
| #include <boost/move/algo/detail/merge.hpp> |
| |
| #include <boost/type_traits/is_nothrow_move_constructible.hpp> |
| |
| //std |
| #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) |
| #include <initializer_list> //for std::initializer_list |
| #endif |
| |
| namespace boost { |
| namespace container { |
| |
| #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) |
| |
| struct growth_factor_60; |
| |
| template<class Options, class AllocatorSizeType> |
| struct get_devector_opt |
| { |
| typedef devector_opt< typename default_if_void<typename Options::growth_factor_type, growth_factor_60>::type |
| , typename default_if_void<typename Options::stored_size_type, AllocatorSizeType>::type |
| > type; |
| }; |
| |
| template<class AllocatorSizeType> |
| struct get_devector_opt<void, AllocatorSizeType> |
| { |
| typedef vector_opt<growth_factor_60, AllocatorSizeType> type; |
| }; |
| |
| #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) |
| |
| struct reserve_only_tag_t {}; |
| //struct unsafe_uninitialized_tag_t {}; |
| |
| /** |
| * A vector-like sequence container providing front and back operations |
| * (e.g: `push_front`/`pop_front`/`push_back`/`pop_back`) with amortized constant complexity |
| * and unsafe methods geared towards additional performance. |
| * |
| * Models the [SequenceContainer], [ReversibleContainer], and [AllocatorAwareContainer] concepts. |
| * |
| * **Requires**: |
| * - `T` shall be [MoveInsertable] into the devector. |
| * - `T` shall be [Erasable] from any `devector<T, allocator_type, GP>`. |
| * - `GrowthFactor`, and `Allocator` must model the concepts with the same names or be void. |
| * |
| * **Definition**: `T` is `NothrowConstructible` if it's either nothrow move constructible or |
| * nothrow copy constructible. |
| * |
| * **Definition**: `T` is `NothrowAssignable` if it's either nothrow move assignable or |
| * nothrow copy assignable. |
| * |
| * **Exceptions**: The exception specifications assume `T` is nothrow [Destructible]. |
| * |
| * Most methods providing the strong exception guarantee assume `T` either has a move |
| * constructor marked noexcept or is [CopyInsertable] into the devector. If it isn't true, |
| * and the move constructor throws, the guarantee is waived and the effects are unspecified. |
| * |
| * In addition to the exceptions specified in the **Throws** clause, the following operations |
| * of `T` can throw when any of the specified concept is required: |
| * - [DefaultInsertable][]: Default constructor |
| * - [MoveInsertable][]: Move constructor |
| * - [CopyInsertable][]: Copy constructor |
| * - [DefaultConstructible][]: Default constructor |
| * - [EmplaceConstructible][]: Constructor selected by the given arguments |
| * - [MoveAssignable][]: Move assignment operator |
| * - [CopyAssignable][]: Copy assignment operator |
| * |
| * Furthermore, not `noexcept` methods throws whatever the allocator throws |
| * if memory allocation fails. Such methods also throw `length_error` if the capacity |
| * exceeds `max_size()`. |
| * |
| * **Remark**: If a method invalidates some iterators, it also invalidates references |
| * and pointers to the elements pointed by the invalidated iterators. |
| * |
| * **Policies**: |
| * |
| * @ref devector_growth_policy models the `GrowthFactor` concept. |
| * |
| * [SequenceContainer]: http://en.cppreference.com/w/cpp/concept/SequenceContainer |
| * [ReversibleContainer]: http://en.cppreference.com/w/cpp/concept/ReversibleContainer |
| * [AllocatorAwareContainer]: http://en.cppreference.com/w/cpp/concept/AllocatorAwareContainer |
| * [DefaultInsertable]: http://en.cppreference.com/w/cpp/concept/DefaultInsertable |
| * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable |
| * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable |
| * [Erasable]: http://en.cppreference.com/w/cpp/concept/Erasable |
| * [DefaultConstructible]: http://en.cppreference.com/w/cpp/concept/DefaultConstructible |
| * [Destructible]: http://en.cppreference.com/w/cpp/concept/Destructible |
| * [EmplaceConstructible]: http://en.cppreference.com/w/cpp/concept/EmplaceConstructible |
| * [MoveAssignable]: http://en.cppreference.com/w/cpp/concept/MoveAssignable |
| * [CopyAssignable]: http://en.cppreference.com/w/cpp/concept/CopyAssignable |
| */ |
| template < typename T, class A BOOST_CONTAINER_DOCONLY(= void), class Options BOOST_CONTAINER_DOCONLY(= void)> |
| class devector |
| { |
| #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED |
| typedef boost::container::allocator_traits |
| <typename real_allocator<T, A>::type> allocator_traits_type; |
| typedef typename allocator_traits_type::size_type alloc_size_type; |
| typedef typename get_devector_opt<Options, alloc_size_type>::type options_type; |
| typedef typename options_type::growth_factor_type growth_factor_type; |
| typedef typename options_type::stored_size_type stored_size_type; |
| |
| #endif // ifndef BOOST_CONTAINER_DOXYGEN_INVOKED |
| |
| public: |
| // Standard Interface Types: |
| typedef T value_type; |
| typedef BOOST_CONTAINER_IMPDEF |
| (typename real_allocator<T BOOST_MOVE_I A>::type) allocator_type; |
| typedef allocator_type stored_allocator_type; |
| typedef typename allocator_traits<allocator_type>::pointer pointer; |
| typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; |
| typedef typename allocator_traits<allocator_type>::reference reference; |
| typedef typename allocator_traits<allocator_type>::const_reference const_reference; |
| typedef typename allocator_traits<allocator_type>::size_type size_type; |
| typedef typename allocator_traits<allocator_type>::difference_type difference_type; |
| typedef pointer iterator; |
| typedef const_pointer const_iterator; |
| typedef BOOST_CONTAINER_IMPDEF |
| (boost::container::reverse_iterator<iterator>) reverse_iterator; |
| typedef BOOST_CONTAINER_IMPDEF |
| (boost::container::reverse_iterator<const_iterator>) const_reverse_iterator; |
| |
| #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED |
| private: |
| BOOST_COPYABLE_AND_MOVABLE(devector) |
| |
| // Guard to deallocate buffer on exception |
| typedef typename detail::allocation_guard<allocator_type> allocation_guard; |
| |
| // Random access pseudo iterator always yielding to the same result |
| typedef constant_iterator<T, difference_type> cvalue_iterator; |
| |
| #endif // ifndef BOOST_CONTAINER_DOXYGEN_INVOKED |
| |
| // Standard Interface |
| public: |
| // construct/copy/destroy |
| |
| /** |
| * **Effects**: Constructs an empty devector. |
| * |
| * **Postcondition**: `empty() && front_free_capacity() == 0 |
| * && back_free_capacity() == 0`. |
| * |
| * **Complexity**: Constant. |
| */ |
| devector() BOOST_NOEXCEPT |
| : m_() |
| {} |
| |
| /** |
| * **Effects**: Constructs an empty devector, using the specified allocator. |
| * |
| * **Postcondition**: `empty() && front_free_capacity() == 0 |
| * && back_free_capacity() == 0`. |
| * |
| * **Complexity**: Constant. |
| */ |
| explicit devector(const allocator_type& allocator) BOOST_NOEXCEPT |
| : m_(allocator) |
| {} |
| |
| /** |
| * **Effects**: Constructs an empty devector, using the specified allocator |
| * and reserves `n` slots as if `reserve(n)` was called. |
| * |
| * **Postcondition**: `empty() && front_free_capacity() == 0 |
| * && back_free_capacity() >= n`. |
| * |
| * **Exceptions**: Strong exception guarantee. |
| * |
| * **Complexity**: Constant. |
| */ |
| devector(size_type n, reserve_only_tag_t, const allocator_type& allocator = allocator_type()) |
| : m_(allocator, this->allocate(n), 0u, 0u, n) |
| {} |
| |
| /** |
| * **Effects**: Constructs an empty devector, using the specified allocator |
| * and reserves `front_cap + back_cap` slots as if `reserve_front(front_cap)` and |
| * `reserve_back(back_cap)` was called. |
| * |
| * **Postcondition**: `empty() && front_free_capacity() == front_cap |
| * && back_free_capacity() >= back_cap`. |
| * |
| * **Exceptions**: Strong exception guarantee. |
| * |
| * **Complexity**: Constant. |
| */ |
| devector(size_type front_cap, size_type back_cap, reserve_only_tag_t, const allocator_type& allocator = allocator_type()) |
| : m_(allocator, this->allocate(front_cap + back_cap), front_cap, front_cap, front_cap + back_cap) |
| {} |
| |
| /** |
| * [DefaultInsertable]: http://en.cppreference.com/w/cpp/concept/DefaultInsertable |
| * |
| * **Effects**: Constructs a devector with `n` default-inserted elements using the specified allocator. |
| * |
| * **Requires**: `T` shall be [DefaultInsertable] into `*this`. |
| * |
| * **Postcondition**: `size() == n && front_free_capacity() == 0`. |
| * |
| * **Exceptions**: Strong exception guarantee. |
| * |
| * **Complexity**: Linear in `n`. |
| */ |
| explicit devector(size_type n, const allocator_type& allocator = allocator_type()) |
| : m_(allocator, n ? allocate(n): pointer(), 0u, n, n) |
| { |
| // Cannot use construct_from_range/constant_iterator and copy_range, |
| // because we are not allowed to default construct T |
| allocation_guard buffer_guard(m_.buffer, m_.capacity, get_allocator_ref()); |
| detail::construction_guard<allocator_type> copy_guard(m_.buffer, get_allocator_ref()); |
| |
| for (size_type i = 0; i < n; ++i) |
| { |
| this->alloc_construct(m_.buffer + i); |
| copy_guard.extend(); |
| } |
| |
| copy_guard.release(); |
| buffer_guard.release(); |
| |
| BOOST_ASSERT(invariants_ok()); |
| } |
| |
| /** |
| * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable |
| * |
| * **Effects**: Constructs a devector with `n` copies of `value`, using the specified allocator. |
| * |
| * **Requires**: `T` shall be [CopyInsertable] into `*this`. |
| * |
| * **Postcondition**: `size() == n && front_free_capacity() == 0`. |
| * |
| * **Exceptions**: Strong exception guarantee. |
| * |
| * **Complexity**: Linear in `n`. |
| */ |
| devector(size_type n, const T& value, const allocator_type& allocator = allocator_type()) |
| : m_(allocator, n ? allocate(n): pointer(), 0u, n, n) |
| { |
| construct_from_range(cvalue_iterator(value, n), cvalue_iterator()); |
| BOOST_ASSERT(invariants_ok()); |
| } |
| |
| /** |
| * **Effects**: Constructs a devector equal to the range `[first,last)`, using the specified allocator. |
| * |
| * **Requires**: `T` shall be [EmplaceConstructible] into `*this` from `*first`. If the specified |
| * iterator does not meet the forward iterator requirements, `T` shall also be [MoveInsertable] |
| * into `*this`. |
| * |
| * **Postcondition**: `size() == boost::container::iterator_distance(first, last) |
| * |
| * **Exceptions**: Strong exception guarantee. |
| * |
| * **Complexity**: Makes only `N` calls to the copy constructor of `T` (where `N` is the distance between `first` |
| * and `last`), at most one allocation and no reallocations if iterators first and last are of forward, |
| * bidirectional, or random access categories. It makes `O(N)` calls to the copy constructor of `T` |
| * and `O(log(N)) reallocations if they are just input iterators. |
| * |
| * **Remarks**: Each iterator in the range `[first,last)` shall be dereferenced exactly once, |
| * unless an exception is thrown. |
| * |
| * [EmplaceConstructible]: http://en.cppreference.com/w/cpp/concept/EmplaceConstructible |
| * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable |
| */ |
| template <class InputIterator> |
| devector(InputIterator first, InputIterator last, const allocator_type& allocator = allocator_type() |
| //Input iterators |
| 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) |
| ) |
| : m_(allocator, pointer(), 0u, 0u, 0u) |
| { |
| while (first != last) { |
| this->emplace_back(*first++); |
| } |
| |
| BOOST_ASSERT(invariants_ok()); |
| } |
| |
| #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED |
| |
| template <class ForwardIterator> |
| devector(ForwardIterator first, ForwardIterator last, const allocator_type& allocator = allocator_type() |
| //Other iterators |
| 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) |
| ) |
| : m_(allocator, pointer(), 0u, 0u, 0u) |
| { |
| const size_type n = boost::container::iterator_distance(first, last); |
| m_.buffer = n ? allocate(n) : pointer(); |
| m_.front_idx = 0u; |
| //this->allocate(n) will take care of overflows |
| m_.set_back_idx(n); |
| m_.set_capacity(n); |
| //construct_from_range releases memory on failure |
| this->construct_from_range(first, last); |
| BOOST_ASSERT(invariants_ok()); |
| } |
| |
| #endif // ifndef BOOST_CONTAINER_DOXYGEN_INVOKED |
| |
| /** |
| * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable |
| * |
| * **Effects**: Copy constructs a devector. |
| * |
| * **Requires**: `T` shall be [CopyInsertable] into `*this`. |
| * |
| * **Postcondition**: `this->size() == x.size() && front_free_capacity() == 0`. |
| * |
| * **Exceptions**: Strong exception guarantee. |
| * |
| * **Complexity**: Linear in the size of `x`. |
| */ |
| devector(const devector& x) |
| : m_( allocator_traits_type::select_on_container_copy_construction(x.get_allocator_ref()) |
| , pointer(), 0u, 0u, 0u) |
| { |
| const size_type n = x.size(); |
| m_.buffer = n ? allocate(n) : pointer(); |
| m_.front_idx = 0u; |
| //this->allocate(n) will take care of overflows |
| m_.set_back_idx(n); |
| m_.set_capacity(n); |
| this->construct_from_range(x.begin(), x.end()); |
| BOOST_ASSERT(invariants_ok()); |
| } |
| |
| /** |
| * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable |
| * |
| * **Effects**: Copy constructs a devector, using the specified allocator. |
| * |
| * **Requires**: `T` shall be [CopyInsertable] into `*this`. |
| * |
| * **Postcondition**: `this->size() == x.size() && front_free_capacity() == 0`. |
| * |
| * **Exceptions**: Strong exception guarantee. |
| * |
| * **Complexity**: Linear in the size of `x`. |
| */ |
| devector(const devector& x, const allocator_type& allocator) |
| : m_(allocator, pointer(), 0u, 0u, 0u) |
| { |
| const size_type n = x.size(); |
| m_.buffer = n ? this->allocate(n) : pointer(); |
| m_.front_idx = 0u; |
| //this->allocate(n) will take care of overflows |
| m_.set_back_idx(n); |
| m_.set_capacity(n); |
| this->construct_from_range(x.begin(), x.end()); |
| BOOST_ASSERT(invariants_ok()); |
| } |
| |
| /** |
| * **Effects**: Moves `rhs`'s resources to `*this`. |
| * |
| * **Throws**: Nothing. |
| * |
| * **Postcondition**: `rhs` is left in an unspecified but valid state. |
| * |
| * **Exceptions**: Strong exception guarantee if not `noexcept`. |
| * |
| * **Complexity**: Constant. |
| */ |
| devector(BOOST_RV_REF(devector) rhs) BOOST_NOEXCEPT_OR_NOTHROW |
| : m_(::boost::move(rhs.get_allocator_ref()), rhs.m_.buffer, rhs.m_.front_idx, rhs.m_.back_idx, rhs.capacity()) |
| { |
| // buffer is already acquired, reset rhs |
| rhs.m_.capacity = 0u; |
| rhs.m_.buffer = pointer(); |
| rhs.m_.front_idx = 0; |
| rhs.m_.back_idx = 0; |
| BOOST_ASSERT( invariants_ok()); |
| BOOST_ASSERT(rhs.invariants_ok()); |
| } |
| |
| /** |
| * **Effects**: Moves `rhs`'s resources to `*this`, using the specified allocator. |
| * |
| * **Throws**: If allocation or T's move constructor throws. |
| * |
| * **Postcondition**: `rhs` is left in an unspecified but valid state. |
| * |
| * **Exceptions**: Strong exception guarantee if not `noexcept`. |
| * |
| * **Complexity**: Linear if allocator != rhs.get_allocator(), otherwise constant. |
| */ |
| devector(BOOST_RV_REF(devector) rhs, const allocator_type& allocator) |
| : m_(allocator, rhs.m_.buffer, rhs.m_.front_idx, rhs.m_.back_idx, rhs.capacity()) |
| { |
| // TODO should move elems-by-elems if the two allocators differ |
| // buffer is already acquired, reset rhs |
| rhs.m_.capacity = 0u; |
| rhs.m_.buffer = pointer(); |
| rhs.m_.front_idx = 0; |
| rhs.m_.back_idx = 0; |
| BOOST_ASSERT( invariants_ok()); |
| BOOST_ASSERT(rhs.invariants_ok()); |
| } |
| |
| #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) |
| /** |
| * **Equivalent to**: `devector(il.begin(), il.end())` or `devector(il.begin(), il.end(), allocator)`. |
| */ |
| devector(const std::initializer_list<T>& il, const allocator_type& allocator = allocator_type()) |
| : m_(allocator, pointer(), 0u, 0u, 0u) |
| { |
| const size_type n = il.size(); |
| m_.buffer = n ? allocate(n) : pointer(); |
| m_.front_idx = 0u; |
| //this->allocate(n) will take care of overflows |
| m_.set_back_idx(n); |
| m_.set_capacity(n); |
| //construct_from_range releases memory on failure |
| this->construct_from_range(il.begin(), il.end()); |
| BOOST_ASSERT(invariants_ok()); |
| } |
| #endif |
| |
| /** |
| * **Effects**: Destroys the devector. All stored values are destroyed and |
| * used memory, if any, deallocated. |
| * |
| * **Complexity**: Linear in the size of `*this`. |
| */ |
| ~devector() BOOST_NOEXCEPT |
| { |
| destroy_elements(m_.buffer + m_.front_idx, m_.buffer + m_.back_idx); |
| deallocate_buffer(); |
| } |
| |
| /** |
| * **Effects**: Copies elements of `x` to `*this`. Previously |
| * held elements get copy assigned to or destroyed. |
| * |
| * **Requires**: `T` shall be [CopyInsertable] into `*this`. |
| * |
| * **Postcondition**: `this->size() == x.size()`, the elements of |
| * `*this` are copies of elements in `x` in the same order. |
| * |
| * **Returns**: `*this`. |
| * |
| * **Exceptions**: Strong exception guarantee if `T` is `NothrowConstructible` |
| * and the allocator is allowed to be propagated |
| * ([propagate_on_container_copy_assignment] is true), |
| * Basic exception guarantee otherwise. |
| * |
| * **Complexity**: Linear in the size of `x` and `*this`. |
| * |
| * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable |
| * [propagate_on_container_copy_assignment]: http://en.cppreference.com/w/cpp/memory/allocator_traits |
| */ |
| |
| BOOST_CONTAINER_FORCEINLINE devector& operator=(BOOST_COPY_ASSIGN_REF(devector) rhs) |
| { |
| const devector &x = rhs; |
| if (this == &x) { return *this; } // skip self |
| |
| BOOST_IF_CONSTEXPR(allocator_traits_type::propagate_on_container_copy_assignment::value) |
| { |
| allocator_type &this_alloc = this->get_allocator_ref(); |
| const allocator_type &other_alloc = x.get_allocator_ref(); |
| if (this_alloc != other_alloc) |
| { |
| // new allocator cannot free existing storage |
| this->clear(); |
| this->deallocate_buffer(); |
| m_.capacity = 0u; |
| m_.buffer = pointer(); |
| } |
| |
| this_alloc = other_alloc; |
| } |
| |
| size_type n = x.size(); |
| if (capacity() >= n) |
| { |
| this->overwrite_buffer(x.begin(), x.end()); |
| } |
| else |
| { |
| this->allocate_and_copy_range(x.begin(), x.end()); |
| } |
| |
| BOOST_ASSERT(invariants_ok()); |
| |
| return *this; |
| } |
| |
| /** |
| * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable |
| * |
| * **Effects**: Moves elements of `x` to `*this`. Previously |
| * held elements get move/copy assigned to or destroyed. |
| * |
| * **Requires**: `T` shall be [MoveInsertable] into `*this`. |
| * |
| * **Postcondition**: `x` is left in an unspecified but valid state. |
| * |
| * **Returns**: `*this`. |
| * |
| * **Exceptions**: Basic exception guarantee if not `noexcept`. |
| * |
| * **Complexity**: Constant if allocator_traits_type:: |
| * propagate_on_container_move_assignment is true or |
| * this->get>allocator() == x.get_allocator(). Linear otherwise. |
| */ |
| devector& operator=(BOOST_RV_REF(devector) x) |
| BOOST_NOEXCEPT_IF(allocator_traits_type::propagate_on_container_move_assignment::value |
| || allocator_traits_type::is_always_equal::value) |
| { |
| BOOST_CONSTEXPR_OR_CONST bool copy_alloc = allocator_traits_type::propagate_on_container_move_assignment::value; |
| |
| BOOST_IF_CONSTEXPR (copy_alloc || get_allocator_ref() == x.get_allocator_ref()) |
| { |
| this->clear(); |
| this->deallocate_buffer(); |
| |
| if (copy_alloc) |
| { |
| this->get_allocator_ref() = boost::move(x.get_allocator_ref()); |
| } |
| |
| m_.capacity = x.m_.capacity; |
| m_.buffer = x.m_.buffer; |
| m_.front_idx = x.m_.front_idx; |
| m_.back_idx = x.m_.back_idx; |
| |
| // leave x in valid state |
| x.m_.capacity = 0u; |
| x.m_.buffer = pointer(); |
| x.m_.back_idx = x.m_.front_idx = 0; |
| } |
| else |
| { |
| // if the allocator shouldn't be copied and they do not compare equal |
| // we can't steal memory. |
| |
| move_iterator<iterator> xbegin = boost::make_move_iterator(x.begin()); |
| move_iterator<iterator> xend = boost::make_move_iterator(x.end()); |
| |
| if (copy_alloc) |
| { |
| get_allocator_ref() = boost::move(x.get_allocator_ref()); |
| } |
| |
| if (capacity() >= x.size()) |
| { |
| overwrite_buffer(xbegin, xend); |
| } |
| else |
| { |
| allocate_and_copy_range(xbegin, xend); |
| } |
| } |
| |
| BOOST_ASSERT(invariants_ok()); |
| |
| return *this; |
| } |
| |
| #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) |
| /** |
| * **Effects**: Copies elements of `il` to `*this`. Previously |
| * held elements get copy assigned to or destroyed. |
| * |
| * **Requires**: `T` shall be [CopyInsertable] into `*this` and [CopyAssignable]. |
| * |
| * **Postcondition**: `this->size() == il.size()`, the elements of |
| * `*this` are copies of elements in `il` in the same order. |
| * |
| * **Exceptions**: Strong exception guarantee if `T` is nothrow copy assignable |
| * from `T` and `NothrowConstructible`, Basic exception guarantee otherwise. |
| * |
| * **Returns**: `*this`. |
| * |
| * **Complexity**: Linear in the size of `il` and `*this`. |
| * |
| * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable |
| * [CopyAssignable]: http://en.cppreference.com/w/cpp/concept/CopyAssignable |
| */ |
| devector& operator=(std::initializer_list<T> il) |
| { |
| assign(il.begin(), il.end()); |
| return *this; |
| } |
| #endif |
| |
| /** |
| * **Effects**: Replaces elements of `*this` with a copy of `[first,last)`. |
| * Previously held elements get copy assigned to or destroyed. |
| * |
| * **Requires**: `T` shall be [EmplaceConstructible] from `*first`. If the specified iterator |
| * does not meet the forward iterator requirements, `T` shall be also [MoveInsertable] into `*this`. |
| * |
| * **Precondition**: `first` and `last` are not iterators into `*this`. |
| * |
| * **Postcondition**: `size() == N`, where `N` is the distance between `first` and `last`. |
| * |
| * **Exceptions**: Strong exception guarantee if `T` is nothrow copy assignable |
| * from `*first` and `NothrowConstructible`, Basic exception guarantee otherwise. |
| * |
| * **Complexity**: Linear in the distance between `first` and `last`. |
| * Makes a single reallocation at most if the iterators `first` and `last` |
| * are of forward, bidirectional, or random access categories. It makes |
| * `O(log(N))` reallocations if they are just input iterators. |
| * |
| * **Remarks**: Each iterator in the range `[first,last)` shall be dereferenced exactly once, |
| * unless an exception is thrown. |
| * |
| * [EmplaceConstructible]: http://en.cppreference.com/w/cpp/concept/EmplaceConstructible |
| * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable |
| */ |
| template <class InputIterator> |
| void assign(InputIterator first, InputIterator last |
| //Input iterators |
| 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) |
| ) |
| { |
| first = overwrite_buffer_impl(first, last, dtl::false_()); |
| while (first != last) |
| { |
| this->emplace_back(*first++); |
| } |
| } |
| |
| #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED |
| |
| template <class ForwardIterator> |
| void assign(ForwardIterator first, ForwardIterator last |
| //Other iterators |
| 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) |
| ) |
| { |
| const size_type n = boost::container::iterator_distance(first, last); |
| |
| if (capacity() >= n) |
| { |
| overwrite_buffer(first, last); |
| } |
| else |
| { |
| allocate_and_copy_range(first, last); |
| } |
| |
| BOOST_ASSERT(invariants_ok()); |
| } |
| |
| #endif // ifndef BOOST_CONTAINER_DOXYGEN_INVOKED |
| |
| /** |
| * **Effects**: Replaces elements of `*this` with `n` copies of `u`. |
| * Previously held elements get copy assigned to or destroyed. |
| * |
| * **Requires**: `T` shall be [CopyInsertable] into `*this` and |
| * [CopyAssignable]. |
| * |
| * **Precondition**: `u` is not a reference into `*this`. |
| * |
| * **Postcondition**: `size() == n` and the elements of |
| * `*this` are copies of `u`. |
| * |
| * **Exceptions**: Strong exception guarantee if `T` is nothrow copy assignable |
| * from `u` and `NothrowConstructible`, Basic exception guarantee otherwise. |
| * |
| * **Complexity**: Linear in `n` and the size of `*this`. |
| * |
| * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable |
| * [CopyAssignable]: http://en.cppreference.com/w/cpp/concept/CopyAssignable |
| */ |
| void assign(size_type n, const T& u) |
| { |
| cvalue_iterator first(u, n); |
| cvalue_iterator last; |
| |
| assign(first, last); |
| } |
| |
| #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) |
| /** **Equivalent to**: `assign(il.begin(), il.end())`. */ |
| void assign(std::initializer_list<T> il) |
| { |
| assign(il.begin(), il.end()); |
| } |
| #endif |
| |
| /** |
| * **Returns**: A copy of the allocator associated with the container. |
| * |
| * **Complexity**: Constant. |
| */ |
| BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE |
| allocator_type get_allocator() const BOOST_NOEXCEPT |
| { |
| return static_cast<const allocator_type&>(m_); |
| } |
| |
| BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE |
| const allocator_type &get_stored_allocator() const BOOST_NOEXCEPT |
| { |
| return static_cast<const allocator_type&>(m_); |
| } |
| |
| BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE |
| allocator_type &get_stored_allocator() BOOST_NOEXCEPT |
| { |
| return static_cast<allocator_type&>(m_); |
| } |
| |
| // iterators |
| |
| /** |
| * **Returns**: A iterator pointing to the first element in the devector, |
| * or the past the end iterator if the devector is empty. |
| * |
| * **Complexity**: Constant. |
| */ |
| BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE |
| iterator begin() BOOST_NOEXCEPT |
| { |
| return m_.buffer + m_.front_idx; |
| } |
| |
| /** |
| * **Returns**: A constant iterator pointing to the first element in the devector, |
| * or the past the end iterator if the devector is empty. |
| * |
| * **Complexity**: Constant. |
| */ |
| BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE |
| const_iterator begin() const BOOST_NOEXCEPT |
| { |
| return m_.buffer + m_.front_idx; |
| } |
| |
| /** |
| * **Returns**: An iterator pointing past the last element of the container. |
| * |
| * **Complexity**: Constant. |
| */ |
| BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE |
| iterator end() BOOST_NOEXCEPT |
| { |
| return m_.buffer + m_.back_idx; |
| } |
| |
| /** |
| * **Returns**: A constant iterator pointing past the last element of the container. |
| * |
| * **Complexity**: Constant. |
| */ |
| BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE |
| const_iterator end() const BOOST_NOEXCEPT |
| { |
| return m_.buffer + m_.back_idx; |
| } |
| |
| /** |
| * **Returns**: A reverse iterator pointing to the first element in the reversed devector, |
| * or the reverse past the end iterator if the devector is empty. |
| * |
| * **Complexity**: Constant. |
| */ |
| BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE |
| reverse_iterator rbegin() BOOST_NOEXCEPT |
| { |
| return reverse_iterator(m_.buffer + m_.back_idx); |
| } |
| |
| /** |
| * **Returns**: A constant reverse iterator |
| * pointing to the first element in the reversed devector, |
| * or the reverse past the end iterator if the devector is empty. |
| * |
| * **Complexity**: Constant. |
| */ |
| BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE |
| const_reverse_iterator rbegin() const BOOST_NOEXCEPT |
| { |
| return const_reverse_iterator(m_.buffer + m_.back_idx); |
| } |
| |
| /** |
| * **Returns**: A reverse iterator pointing past the last element in the |
| * reversed container, or to the beginning of the reversed container if it's empty. |
| * |
| * **Complexity**: Constant. |
| */ |
| BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE |
| reverse_iterator rend() BOOST_NOEXCEPT |
| { |
| return reverse_iterator(m_.buffer + m_.front_idx); |
| } |
| |
| /** |
| * **Returns**: A constant reverse iterator pointing past the last element in the |
| * reversed container, or to the beginning of the reversed container if it's empty. |
| * |
| * **Complexity**: Constant. |
| */ |
| BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE |
| const_reverse_iterator rend() const BOOST_NOEXCEPT |
| { |
| return const_reverse_iterator(m_.buffer + m_.front_idx); |
| } |
| |
| /** |
| * **Returns**: A constant iterator pointing to the first element in the devector, |
| * or the past the end iterator if the devector is empty. |
| * |
| * **Complexity**: Constant. |
| */ |
| BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE |
| const_iterator cbegin() const BOOST_NOEXCEPT |
| { |
| return m_.buffer + m_.front_idx; |
| } |
| |
| /** |
| * **Returns**: A constant iterator pointing past the last element of the container. |
| * |
| * **Complexity**: Constant. |
| */ |
| const_iterator cend() const BOOST_NOEXCEPT |
| { |
| return m_.buffer + m_.back_idx; |
| } |
| |
| /** |
| * **Returns**: A constant reverse iterator |
| * pointing to the first element in the reversed devector, |
| * or the reverse past the end iterator if the devector is empty. |
| * |
| * **Complexity**: Constant. |
| */ |
| BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE |
| const_reverse_iterator crbegin() const BOOST_NOEXCEPT |
| { |
| return const_reverse_iterator(m_.buffer + m_.back_idx); |
| } |
| |
| /** |
| * **Returns**: A constant reverse iterator pointing past the last element in the |
| * reversed container, or to the beginning of the reversed container if it's empty. |
| * |
| * **Complexity**: Constant. |
| */ |
| BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE |
| const_reverse_iterator crend() const BOOST_NOEXCEPT |
| { |
| return const_reverse_iterator(m_.buffer + m_.front_idx); |
| } |
| |
| // capacity |
| |
| /** |
| * **Returns**: True, if `size() == 0`, false otherwise. |
| * |
| * **Complexity**: Constant. |
| */ |
| BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE |
| bool empty() const BOOST_NOEXCEPT |
| { |
| return m_.front_idx == m_.back_idx; |
| } |
| |
| /** |
| * **Returns**: The number of elements the devector contains. |
| * |
| * **Complexity**: Constant. |
| */ |
| BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE |
| size_type size() const BOOST_NOEXCEPT |
| { |
| return m_.back_idx - m_.front_idx; |
| } |
| |
| /** |
| * **Returns**: The maximum number of elements the devector could possibly hold. |
| * |
| * **Complexity**: Constant. |
| */ |
| BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE |
| size_type max_size() const BOOST_NOEXCEPT |
| { |
| size_type alloc_max = allocator_traits_type::max_size(get_allocator_ref()); |
| size_type size_type_max = (size_type)-1; |
| return (alloc_max <= size_type_max) ? size_type(alloc_max) : size_type_max; |
| } |
| |
| /** |
| * **Returns**: The total number of elements that the devector can hold without requiring reallocation. |
| * |
| * **Complexity**: Constant. |
| */ |
| BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE |
| size_type capacity() const BOOST_NOEXCEPT |
| { |
| return m_.capacity; |
| } |
| |
| /** |
| * **Returns**: The total number of elements that can be pushed to the front of the |
| * devector without requiring reallocation. |
| * |
| * **Complexity**: Constant. |
| */ |
| BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE |
| size_type front_free_capacity() const BOOST_NOEXCEPT |
| { |
| return m_.front_idx; |
| } |
| |
| /** |
| * **Returns**: The total number of elements that can be pushed to the back of the |
| * devector without requiring reallocation. |
| * |
| * **Complexity**: Constant. |
| */ |
| BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE |
| size_type back_free_capacity() const BOOST_NOEXCEPT |
| { |
| return m_.capacity - m_.back_idx; |
| } |
| |
| /** **Equivalent to**: `resize_back(sz)` */ |
| void resize(size_type sz) { resize_back(sz); } |
| |
| /** **Equivalent to**: `resize_back(sz, c)` */ |
| void resize(size_type sz, const T& c) { resize_back(sz, c); } |
| |
| /** |
| * **Effects**: If `sz` is greater than the size of `*this`, |
| * additional value-initialized elements are inserted |
| * to the front. Invalidates iterators if reallocation is needed. |
| * If `sz` is smaller than than the size of `*this`, |
| * elements are popped from the front. |
| * |
| * **Requires**: T shall be [MoveInsertable] into *this and [DefaultConstructible]. |
| * |
| * **Postcondition**: `sz == size()`. |
| * |
| * **Exceptions**: Strong exception guarantee. |
| * |
| * **Complexity**: Linear in the size of `*this` and `sz`. |
| * |
| * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable |
| * [DefaultConstructible]: http://en.cppreference.com/w/cpp/concept/DefaultConstructible |
| */ |
| void resize_front(size_type sz) |
| { |
| resize_front_impl(sz); |
| BOOST_ASSERT(invariants_ok()); |
| } |
| |
| /** |
| * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable |
| * |
| * **Effects**: If `sz` is greater than the size of `*this`, |
| * copies of `c` are inserted to the front. |
| * Invalidates iterators if reallocation is needed. |
| * If `sz` is smaller than than the size of `*this`, |
| * elements are popped from the front. |
| * |
| * **Postcondition**: `sz == size()`. |
| * |
| * **Requires**: `T` shall be [CopyInsertable] into `*this`. |
| * |
| * **Exceptions**: Strong exception guarantee. |
| * |
| * **Complexity**: Linear in the size of `*this` and `sz`. |
| */ |
| void resize_front(size_type sz, const T& c) |
| { |
| resize_front_impl(sz, c); |
| BOOST_ASSERT(invariants_ok()); |
| } |
| |
| /** |
| * **Effects**: If `sz` is greater than the size of `*this`, |
| * additional value-initialized elements are inserted |
| * to the back. Invalidates iterators if reallocation is needed. |
| * If `sz` is smaller than than the size of `*this`, |
| * elements are popped from the back. |
| * |
| * **Requires**: T shall be [MoveInsertable] into *this and [DefaultConstructible]. |
| * |
| * **Postcondition**: `sz == size()`. |
| * |
| * **Exceptions**: Strong exception guarantee. |
| * |
| * **Complexity**: Linear in the size of `*this` and `sz`. |
| * |
| * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable |
| * [DefaultConstructible]: http://en.cppreference.com/w/cpp/concept/DefaultConstructible |
| */ |
| void resize_back(size_type sz) |
| { |
| resize_back_impl(sz); |
| BOOST_ASSERT(invariants_ok()); |
| } |
| |
| /** |
| * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable |
| * |
| * **Effects**: If `sz` is greater than the size of `*this`, |
| * copies of `c` are inserted to the back. |
| * If `sz` is smaller than than the size of `*this`, |
| * elements are popped from the back. |
| * |
| * **Postcondition**: `sz == size()`. |
| * |
| * **Requires**: `T` shall be [CopyInsertable] into `*this`. |
| * |
| * **Exceptions**: Strong exception guarantee. |
| * |
| * **Complexity**: Linear in the size of `*this` and `sz`. |
| */ |
| void resize_back(size_type sz, const T& c) |
| { |
| resize_back_impl(sz, c); |
| BOOST_ASSERT(invariants_ok()); |
| } |
| |
| // unsafe uninitialized resize methods |
| |
| /** |
| * **Unsafe method**, use with care. |
| * |
| * **Effects**: Changes the size of the devector without properly |
| * initializing the extra or destroying the superfluous elements. |
| * If `n < size()`, elements are removed from the front without |
| * getting destroyed; if `n > size()`, uninitialized elements are added |
| * before the first element at the front. |
| * Invalidates iterators if reallocation is needed. |
| * |
| * **Postcondition**: `size() == n`. |
| * |
| * **Exceptions**: Strong exception guarantee. |
| * |
| * **Complexity**: Linear in `size()` if `capacity() < n`, constant otherwise. |
| * |
| * **Remarks**: The devector does not keep track of initialization of the elements: |
| * Elements without a trivial destructor must be manually destroyed before shrinking, |
| * elements without a trivial constructor must be initialized after growing. |
| */ |
| /* |
| void unsafe_uninitialized_resize_front(size_type n) |
| { |
| if (n > size()) |
| { |
| unsafe_uninitialized_grow_front(n); |
| } |
| else |
| { |
| unsafe_uninitialized_shrink_front(n); |
| } |
| } |
| */ |
| /** |
| * **Unsafe method**, use with care. |
| * |
| * **Effects**: Changes the size of the devector without properly |
| * initializing the extra or destroying the superfluous elements. |
| * If `n < size()`, elements are removed from the back without |
| * getting destroyed; if `n > size()`, uninitialized elements are added |
| * after the last element at the back. |
| * Invalidates iterators if reallocation is needed. |
| * |
| * **Postcondition**: `size() == n`. |
| * |
| * **Exceptions**: Strong exception guarantee. |
| * |
| * **Complexity**: Linear in `size()` if `capacity() < n`, constant otherwise. |
| * |
| * **Remarks**: The devector does not keep track of initialization of the elements: |
| * Elements without a trivial destructor must be manually destroyed before shrinking, |
| * elements without a trivial constructor must be initialized after growing. |
| */ |
| /* |
| void unsafe_uninitialized_resize_back(size_type n) |
| { |
| if (n > size()) |
| { |
| unsafe_uninitialized_grow_back(n); |
| } |
| else |
| { |
| unsafe_uninitialized_shrink_back(n); |
| } |
| } |
| */ |
| // reserve promise: |
| // after reserve_[front,back](n), n - size() push_[front,back] will not allocate |
| |
| /** **Equivalent to**: `reserve_back(new_capacity)` */ |
| void reserve(size_type new_capacity) { reserve_back(new_capacity); } |
| |
| /** |
| * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable |
| * |
| * **Effects**: Ensures that `n` elements can be pushed to the front |
| * without requiring reallocation, where `n` is `new_capacity - size()`, |
| * if `n` is positive. Otherwise, there are no effects. |
| * Invalidates iterators if reallocation is needed. |
| * |
| * **Requires**: `T` shall be [MoveInsertable] into `*this`. |
| * |
| * **Complexity**: Linear in the size of *this. |
| * |
| * **Exceptions**: Strong exception guarantee. |
| * |
| * **Throws**: `length_error` if `new_capacity > max_size()`. |
| */ |
| void reserve_front(size_type new_capacity) |
| { |
| if (front_capacity() >= new_capacity) { return; } |
| |
| reallocate_at(new_capacity + back_free_capacity(), new_capacity - size()); |
| |
| BOOST_ASSERT(invariants_ok()); |
| } |
| |
| /** |
| * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable |
| * |
| * **Effects**: Ensures that `n` elements can be pushed to the back |
| * without requiring reallocation, where `n` is `new_capacity - size()`, |
| * if `n` is positive. Otherwise, there are no effects. |
| * Invalidates iterators if reallocation is needed. |
| * |
| * **Requires**: `T` shall be [MoveInsertable] into `*this`. |
| * |
| * **Complexity**: Linear in the size of *this. |
| * |
| * **Exceptions**: Strong exception guarantee. |
| * |
| * **Throws**: length_error if `new_capacity > max_size()`. |
| */ |
| void reserve_back(size_type new_capacity) |
| { |
| if (back_capacity() >= new_capacity) { return; } |
| |
| reallocate_at(new_capacity + front_free_capacity(), m_.front_idx); |
| |
| BOOST_ASSERT(invariants_ok()); |
| } |
| |
| |
| /** |
| * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable |
| * |
| * **Effects**: Reduces `capacity()` to `size()`. Invalidates iterators. |
| * |
| * **Requires**: `T` shall be [MoveInsertable] into `*this`. |
| * |
| * **Exceptions**: Strong exception guarantee. |
| * |
| * **Complexity**: Linear in the size of *this. |
| */ |
| void shrink_to_fit() |
| { |
| if(this->front_capacity() || this->back_capacity()) |
| this->reallocate_at(size(), 0); |
| } |
| |
| // element access: |
| |
| /** |
| * **Returns**: A reference to the `n`th element in the devector. |
| * |
| * **Precondition**: `n < size()`. |
| * |
| * **Complexity**: Constant. |
| */ |
| BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE |
| reference operator[](size_type n) BOOST_NOEXCEPT |
| { |
| BOOST_ASSERT(n < size()); |
| return *(begin() + n); |
| } |
| |
| /** |
| * **Returns**: A constant reference to the `n`th element in the devector. |
| * |
| * **Precondition**: `n < size()`. |
| * |
| * **Complexity**: Constant. |
| */ |
| BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE |
| const_reference operator[](size_type n) const BOOST_NOEXCEPT |
| { |
| BOOST_ASSERT(n < size()); |
| |
| return *(begin() + n); |
| } |
| |
| /** |
| * **Returns**: A reference to the `n`th element in the devector. |
| * |
| * **Throws**: `std::out_of_range`, if `n >= size()`. |
| * |
| * **Complexity**: Constant. |
| */ |
| BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE |
| reference at(size_type n) |
| { |
| if (size() <= n) |
| throw_out_of_range("devector::at out of range"); |
| return (*this)[n]; |
| } |
| |
| /** |
| * **Returns**: A constant reference to the `n`th element in the devector. |
| * |
| * **Throws**: `std::out_of_range`, if `n >= size()`. |
| * |
| * **Complexity**: Constant. |
| */ |
| BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE |
| const_reference at(size_type n) const |
| { |
| if (size() <= n) |
| throw_out_of_range("devector::at out of range"); |
| return (*this)[n]; |
| } |
| |
| /** |
| * **Returns**: A reference to the first element in the devector. |
| * |
| * **Precondition**: `!empty()`. |
| * |
| * **Complexity**: Constant. |
| */ |
| BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE |
| reference front() BOOST_NOEXCEPT |
| { |
| BOOST_ASSERT(!empty()); |
| |
| return *(m_.buffer + m_.front_idx); |
| } |
| |
| /** |
| * **Returns**: A constant reference to the first element in the devector. |
| * |
| * **Precondition**: `!empty()`. |
| * |
| * **Complexity**: Constant. |
| */ |
| BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE |
| const_reference front() const BOOST_NOEXCEPT |
| { |
| BOOST_ASSERT(!empty()); |
| |
| return *(m_.buffer + m_.front_idx); |
| } |
| |
| /** |
| * **Returns**: A reference to the last element in the devector. |
| * |
| * **Precondition**: `!empty()`. |
| * |
| * **Complexity**: Constant. |
| */ |
| BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE |
| reference back() BOOST_NOEXCEPT |
| { |
| BOOST_ASSERT(!empty()); |
| |
| return *(m_.buffer + m_.back_idx -1); |
| } |
| |
| /** |
| * **Returns**: A constant reference to the last element in the devector. |
| * |
| * **Precondition**: `!empty()`. |
| * |
| * **Complexity**: Constant. |
| */ |
| BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE |
| const_reference back() const BOOST_NOEXCEPT |
| { |
| BOOST_ASSERT(!empty()); |
| |
| return *(m_.buffer + m_.back_idx -1); |
| } |
| |
| /** |
| * **Returns**: A pointer to the underlying array serving as element storage. |
| * The range `[data(); data() + size())` is always valid. For a non-empty devector, |
| * `data() == &front()`. |
| * |
| * **Complexity**: Constant. |
| */ |
| BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE |
| T* data() BOOST_NOEXCEPT |
| { |
| return boost::movelib::to_raw_pointer(m_.buffer) + m_.front_idx; |
| } |
| |
| /** |
| * **Returns**: A constant pointer to the underlying array serving as element storage. |
| * The range `[data(); data() + size())` is always valid. For a non-empty devector, |
| * `data() == &front()`. |
| * |
| * **Complexity**: Constant. |
| */ |
| BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE |
| const T* data() const BOOST_NOEXCEPT |
| { |
| return boost::movelib::to_raw_pointer(m_.buffer) + m_.front_idx; |
| } |
| |
| // modifiers: |
| |
| /** |
| * **Effects**: Pushes a new element to the front of the devector. |
| * The element is constructed in-place, using the perfect forwarded `args` |
| * as constructor arguments. Invalidates iterators if reallocation is needed. |
| * (`front_free_capacity() == 0`) |
| * |
| * **Requires**: `T` shall be [EmplaceConstructible] from `args` and [MoveInsertable] into `*this`. |
| * |
| * **Exceptions**: Strong exception guarantee. |
| * |
| * **Complexity**: Amortized constant in the size of `*this`. |
| * (Constant, if `front_free_capacity() > 0`) |
| * |
| * [EmplaceConstructible]: http://en.cppreference.com/w/cpp/concept/EmplaceConstructible |
| * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable |
| */ |
| #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) |
| template <class... Args> |
| void emplace_front(Args&&... args) |
| { |
| if (front_free_capacity()) // fast path |
| { |
| this->alloc_construct(m_.buffer + m_.front_idx - 1, boost::forward<Args>(args)...); |
| --m_.front_idx; |
| } |
| else |
| { |
| this->emplace_reallocating_slow_path(true, 0, boost::forward<Args>(args)...); |
| } |
| |
| BOOST_ASSERT(invariants_ok()); |
| } |
| |
| #else //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) |
| |
| #define BOOST_CONTAINER_DEVECTOR_EMPLACE_FRONT(N) \ |
| BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ |
| BOOST_CONTAINER_FORCEINLINE void emplace_front(BOOST_MOVE_UREF##N)\ |
| {\ |
| if (front_free_capacity())\ |
| {\ |
| this->alloc_construct(m_.buffer + m_.front_idx - 1 BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ |
| --m_.front_idx;\ |
| }\ |
| else\ |
| {\ |
| this->emplace_reallocating_slow_path(true, 0 BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ |
| }\ |
| \ |
| BOOST_ASSERT(invariants_ok());\ |
| }\ |
| // |
| BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_DEVECTOR_EMPLACE_FRONT) |
| #undef BOOST_CONTAINER_DEVECTOR_EMPLACE_FRONT |
| |
| #endif |
| |
| #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) |
| /** |
| * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable |
| * |
| * **Effects**: Pushes the copy of `x` to the front of the devector. |
| * Invalidates iterators if reallocation is needed. |
| * (`front_free_capacity() == 0`) |
| * |
| * **Requires**: `T` shall be [CopyInsertable] into `*this`. |
| * |
| * **Exceptions**: Strong exception guarantee. |
| * |
| * **Complexity**: Amortized constant in the size of `*this`. |
| * (Constant, if `front_free_capacity() > 0`) |
| */ |
| void push_front(const T& x); |
| |
| /** |
| * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable |
| * |
| * **Effects**: Move constructs a new element at the front of the devector using `x`. |
| * Invalidates iterators if reallocation is needed. |
| * (`front_free_capacity() == 0`) |
| * |
| * **Requires**: `T` shall be [MoveInsertable] into `*this`. |
| * |
| * **Exceptions**: Strong exception guarantee, not regarding the state of `x`. |
| * |
| * **Complexity**: Amortized constant in the size of `*this`. |
| * (Constant, if `front_free_capacity() > 0`) |
| */ |
| void push_front(T&& x); |
| |
| #else |
| BOOST_MOVE_CONVERSION_AWARE_CATCH(push_front, T, void, priv_push_front) |
| #endif |
| |
| /** |
| * **Effects**: Removes the first element of `*this`. |
| * |
| * **Precondition**: `!empty()`. |
| * |
| * **Postcondition**: `front_free_capacity()` is incremented by 1. |
| * |
| * **Complexity**: Constant. |
| */ |
| void pop_front() BOOST_NOEXCEPT |
| { |
| BOOST_ASSERT(! empty()); |
| allocator_traits_type::destroy(get_allocator_ref(), m_.buffer + m_.front_idx); |
| ++m_.front_idx; |
| BOOST_ASSERT(invariants_ok()); |
| } |
| |
| /** |
| * **Effects**: Pushes a new element to the back of the devector. |
| * The element is constructed in-place, using the perfect forwarded `args` |
| * as constructor arguments. Invalidates iterators if reallocation is needed. |
| * (`back_free_capacity() == 0`) |
| * |
| * **Requires**: `T` shall be [EmplaceConstructible] from `args` and [MoveInsertable] into `*this`, |
| * and [MoveAssignable]. |
| * |
| * **Exceptions**: Strong exception guarantee. |
| * |
| * **Complexity**: Amortized constant in the size of `*this`. |
| * (Constant, if `back_free_capacity() > 0`) |
| * |
| * [EmplaceConstructible]: http://en.cppreference.com/w/cpp/concept/EmplaceConstructible |
| * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable |
| * [MoveAssignable]: http://en.cppreference.com/w/cpp/concept/MoveAssignable |
| */ |
| #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) |
| template <class... Args> |
| BOOST_CONTAINER_FORCEINLINE void emplace_back(Args&&... args) |
| { |
| if (this->back_free_capacity()){ |
| this->alloc_construct(m_.buffer + m_.back_idx, boost::forward<Args>(args)...); |
| ++m_.back_idx; |
| } |
| else { |
| this->emplace_reallocating_slow_path(false, size(), boost::forward<Args>(args)...); |
| } |
| BOOST_ASSERT(invariants_ok()); |
| } |
| |
| #else //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) |
| |
| #define BOOST_CONTAINER_DEVECTOR_EMPLACE_BACK(N) \ |
| BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ |
| BOOST_CONTAINER_FORCEINLINE void emplace_back(BOOST_MOVE_UREF##N)\ |
| {\ |
| if (this->back_free_capacity()){\ |
| this->alloc_construct(m_.buffer + m_.back_idx BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ |
| ++m_.back_idx;\ |
| }\ |
| else {\ |
| this->emplace_reallocating_slow_path(false, size() BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ |
| }\ |
| BOOST_ASSERT(invariants_ok());\ |
| }\ |
| // |
| BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_DEVECTOR_EMPLACE_BACK) |
| #undef BOOST_CONTAINER_DEVECTOR_EMPLACE_BACK |
| |
| #endif //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) |
| |
| |
| #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) |
| /** |
| * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable |
| * |
| * **Effects**: Pushes the copy of `x` to the back of the devector. |
| * Invalidates iterators if reallocation is needed. |
| * (`back_free_capacity() == 0`) |
| * |
| * **Requires**: `T` shall be [CopyInsertable] into `*this`. |
| * |
| * **Exceptions**: Strong exception guarantee. |
| * |
| * **Complexity**: Amortized constant in the size of `*this`. |
| * (Constant, if `back_free_capacity() > 0`) |
| */ |
| void push_back(const T& x); |
| |
| /** |
| * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable |
| * |
| * **Effects**: Move constructs a new element at the back of the devector using `x`. |
| * Invalidates iterators if reallocation is needed. |
| * (`back_free_capacity() == 0`) |
| * |
| * **Requires**: `T` shall be [MoveInsertable] into `*this`. |
| * |
| * **Exceptions**: Strong exception guarantee, not regarding the state of `x`. |
| * |
| * **Complexity**: Amortized constant in the size of `*this`. |
| * (Constant, if `back_free_capacity() > 0`) |
| */ |
| void push_back(T&& x); |
| |
| #else |
| BOOST_MOVE_CONVERSION_AWARE_CATCH(push_back, T, void, priv_push_back) |
| #endif |
| |
| /** |
| * **Effects**: Removes the last element of `*this`. |
| * |
| * **Precondition**: `!empty()`. |
| * |
| * **Postcondition**: `back_free_capacity()` is incremented by 1. |
| * |
| * **Complexity**: Constant. |
| */ |
| void pop_back() BOOST_NOEXCEPT |
| { |
| BOOST_ASSERT(! empty()); |
| --m_.back_idx; |
| allocator_traits_type::destroy(get_allocator_ref(), m_.buffer + m_.back_idx); |
| BOOST_ASSERT(invariants_ok()); |
| } |
| |
| /** |
| * **Effects**: Constructs a new element before the element pointed by `position`. |
| * The element is constructed in-place, using the perfect forwarded `args` |
| * as constructor arguments. Invalidates iterators if reallocation is needed. |
| * |
| * **Requires**: `T` shall be [EmplaceConstructible], and [MoveInsertable] into `*this`, |
| * and [MoveAssignable]. |
| * |
| * **Returns**: Iterator pointing to the newly constructed element. |
| * |
| * **Exceptions**: Strong exception guarantee if `T` is `NothrowConstructible` |
| * and `NothrowAssignable`, Basic exception guarantee otherwise. |
| * |
| * **Complexity**: Linear in the size of `*this`. |
| * |
| * [EmplaceConstructible]: http://en.cppreference.com/w/cpp/concept/EmplaceConstructible |
| * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable |
| * [MoveAssignable]: http://en.cppreference.com/w/cpp/concept/MoveAssignable |
| */ |
| #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) |
| template <class... Args> |
| iterator emplace(const_iterator position, Args&&... args) |
| { |
| BOOST_ASSERT(position >= begin()); |
| BOOST_ASSERT(position <= end()); |
| |
| if (position == end() && back_free_capacity()) // fast path |
| { |
| this->alloc_construct(m_.buffer + m_.back_idx, boost::forward<Args>(args)...); |
| ++m_.back_idx; |
| return end() - 1; |
| } |
| else if (position == begin() && front_free_capacity()) // secondary fast path |
| { |
| this->alloc_construct(m_.buffer + (m_.front_idx - 1), boost::forward<Args>(args)...); |
| --m_.front_idx; |
| return begin(); |
| } |
| else |
| { |
| size_type new_elem_index = position - begin(); |
| return this->emplace_slow_path(new_elem_index, boost::forward<Args>(args)...); |
| } |
| } |
| |
| #else //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) |
| |
| #define BOOST_CONTAINER_DEVECTOR_EMPLACE(N) \ |
| BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ |
| iterator emplace(const_iterator position BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ |
| {\ |
| BOOST_ASSERT(position >= begin());\ |
| BOOST_ASSERT(position <= end());\ |
| \ |
| if (position == end() && back_free_capacity()){\ |
| this->alloc_construct(m_.buffer + m_.back_idx BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ |
| ++m_.back_idx;\ |
| return end() - 1;\ |
| }\ |
| else if (position == begin() && front_free_capacity()){\ |
| this->alloc_construct(m_.buffer + m_.front_idx - 1 BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ |
| --m_.front_idx;\ |
| return begin();\ |
| }\ |
| else{\ |
| size_type new_elem_index = position - begin();\ |
| return this->emplace_slow_path(new_elem_index BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ |
| }\ |
| }\ |
| // |
| BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_DEVECTOR_EMPLACE) |
| #undef BOOST_CONTAINER_DEVECTOR_EMPLACE |
| |
| #endif //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) |
| |
| |
| #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) |
| /** |
| * **Effects**: Copy constructs a new element before the element pointed by `position`, |
| * using `x` as constructor argument. Invalidates iterators if reallocation is needed. |
| * |
| * **Requires**: `T` shall be [CopyInsertable] into `*this` and and [CopyAssignable]. |
| * |
| * **Returns**: Iterator pointing to the newly constructed element. |
| * |
| * **Exceptions**: Strong exception guarantee if `T` is `NothrowConstructible` |
| * and `NothrowAssignable`, Basic exception guarantee otherwise. |
| * |
| * **Complexity**: Linear in the size of `*this`. |
| * |
| * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable |
| * [CopyAssignable]: http://en.cppreference.com/w/cpp/concept/CopyAssignable |
| */ |
| iterator insert(const_iterator position, const T &x); |
| |
| /** |
| * **Effects**: Move constructs a new element before the element pointed by `position`, |
| * using `x` as constructor argument. Invalidates iterators if reallocation is needed. |
| * |
| * **Requires**: `T` shall be [MoveInsertable] into `*this` and and [CopyAssignable]. |
| * |
| * **Returns**: Iterator pointing to the newly constructed element. |
| * |
| * **Exceptions**: Strong exception guarantee if `T` is `NothrowConstructible` |
| * and `NothrowAssignable` (not regarding the state of `x`), |
| * Basic exception guarantee otherwise. |
| * |
| * **Complexity**: Linear in the size of `*this`. |
| * |
| * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable |
| * [CopyAssignable]: http://en.cppreference.com/w/cpp/concept/CopyAssignable |
| */ |
| iterator insert(const_iterator position, T &&x); |
| #else |
| BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, T, iterator, priv_insert, const_iterator, const_iterator) |
| #endif |
| |
| /** |
| * **Effects**: Copy constructs `n` elements before the element pointed by `position`, |
| * using `x` as constructor argument. Invalidates iterators if reallocation is needed. |
| * |
| * **Requires**: `T` shall be [CopyInsertable] into `*this` and and [CopyAssignable]. |
| * |
| * **Returns**: Iterator pointing to the first inserted element, or `position`, if `n` is zero. |
| * |
| * **Exceptions**: Strong exception guarantee if `T` is `NothrowConstructible` |
| * and `NothrowAssignable`, Basic exception guarantee otherwise. |
| * |
| * **Complexity**: Linear in the size of `*this` and `n`. |
| * |
| * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable |
| * [CopyAssignable]: http://en.cppreference.com/w/cpp/concept/CopyAssignable |
| */ |
| iterator insert(const_iterator position, size_type n, const T& x) |
| { |
| cvalue_iterator first(x, n); |
| cvalue_iterator last = first + n; |
| return insert_range(position, first, last); |
| } |
| |
| /** |
| * **Effects**: Copy constructs elements before the element pointed by position |
| * using each element in the rage pointed by `first` and `last` as constructor arguments. |
| * Invalidates iterators if reallocation is needed. |
| * |
| * **Requires**: `T` shall be [EmplaceConstructible] into `*this` from `*first`. If the specified iterator |
| * does not meet the forward iterator requirements, `T` shall also be [MoveInsertable] into `*this` |
| * and [MoveAssignable]. |
| * |
| * **Precondition**: `first` and `last` are not iterators into `*this`. |
| * |
| * **Returns**: Iterator pointing to the first inserted element, or `position`, if `first == last`. |
| * |
| * **Complexity**: Linear in the size of `*this` and `N` (where `N` is the distance between `first` and `last`). |
| * Makes only `N` calls to the constructor of `T` and no reallocations if iterators `first` and `last` |
| * are of forward, bidirectional, or random access categories. It makes 2N calls to the copy constructor of `T` |
| * and allocates memory twice at most if they are just input iterators. |
| * |
| * **Exceptions**: Strong exception guarantee if `T` is `NothrowConstructible` |
| * and `NothrowAssignable`, Basic exception guarantee otherwise. |
| * |
| * **Remarks**: Each iterator in the range `[first,last)` shall be dereferenced exactly once, |
| * unless an exception is thrown. |
| * |
| * [EmplaceConstructible]: http://en.cppreference.com/w/cpp/concept/EmplaceConstructible |
| * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable |
| * [MoveAssignable]: http://en.cppreference.com/w/cpp/concept/MoveAssignable |
| */ |
| template <class InputIterator> |
| iterator insert(const_iterator position, InputIterator first, InputIterator last |
| //Input iterators |
| 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) |
| ) |
| { |
| if (position == end()) |
| { |
| size_type insert_index = size(); |
| |
| for (; first != last; ++first) |
| { |
| this->emplace_back(*first); |
| } |
| |
| return begin() + insert_index; |
| } |
| else |
| { |
| const size_type insert_index = static_cast<size_type>(position - this->cbegin()); |
| const size_type old_size = static_cast<size_type>(this->size()); |
| |
| for (; first != last; ++first) { |
| this->emplace_back(*first); |
| } |
| iterator rit (this->begin() + insert_index); |
| boost::movelib::rotate_gcd(rit, this->begin() + old_size, this->begin() + this->size()); |
| return rit; |
| } |
| } |
| |
| #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED |
| |
| template <class ForwardIterator> |
| iterator insert(const_iterator position, ForwardIterator first, ForwardIterator last |
| //Other iterators |
| 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) |
| ) |
| { |
| return insert_range(position, first, last); |
| } |
| |
| #endif // ifndef BOOST_CONTAINER_DOXYGEN_INVOKED |
| |
| #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) |
| /** **Equivalent to**: `insert(position, il.begin(), il.end())` */ |
| iterator insert(const_iterator position, std::initializer_list<T> il) |
| { |
| return insert_range(position, il.begin(), il.end()); |
| } |
| #endif |
| |
| /** |
| * [MoveAssignable]: http://en.cppreference.com/w/cpp/concept/MoveAssignable |
| * |
| * **Effects**: Destroys the element pointed by `position` and removes it from the devector. |
| * Invalidates iterators. |
| * |
| * **Requires**: `T` shall be [MoveAssignable]. |
| * |
| * **Precondition**: `position` must be in the range of `[begin(), end())`. |
| * |
| * **Returns**: Iterator pointing to the element immediately following the erased element |
| * prior to its erasure. If no such element exists, `end()` is returned. |
| * |
| * **Exceptions**: Strong exception guarantee if `T` is `NothrowAssignable`, |
| * Basic exception guarantee otherwise. |
| * |
| * **Complexity**: Linear in half the size of `*this`. |
| */ |
| iterator erase(const_iterator position) |
| { |
| return erase(position, position + 1); |
| } |
| |
| /** |
| * [MoveAssignable]: http://en.cppreference.com/w/cpp/concept/MoveAssignable |
| * |
| * **Effects**: Destroys the range `[first,last)` and removes it from the devector. |
| * Invalidates iterators. |
| * |
| * **Requires**: `T` shall be [MoveAssignable]. |
| * |
| * **Precondition**: `[first,last)` must be in the range of `[begin(), end())`. |
| * |
| * **Returns**: Iterator pointing to the element pointed to by `last` prior to any elements |
| * being erased. If no such element exists, `end()` is returned. |
| * |
| * **Exceptions**: Strong exception guarantee if `T` is `NothrowAssignable`, |
| * Basic exception guarantee otherwise. |
| * |
| * **Complexity**: Linear in half the size of `*this` |
| * plus the distance between `first` and `last`. |
| */ |
| iterator erase(const_iterator first, const_iterator last) |
| { |
| iterator nc_first = begin() + (first - begin()); |
| iterator nc_last = begin() + (last - begin()); |
| return erase(nc_first, nc_last); |
| } |
| |
| /** |
| * [MoveAssignable]: http://en.cppreference.com/w/cpp/concept/MoveAssignable |
| * |
| * **Effects**: Destroys the range `[first,last)` and removes it from the devector. |
| * Invalidates iterators. |
| * |
| * **Requires**: `T` shall be [MoveAssignable]. |
| * |
| * **Precondition**: `[first,last)` must be in the range of `[begin(), end())`. |
| * |
| * **Returns**: Iterator pointing to the element pointed to by `last` prior to any elements |
| * being erased. If no such element exists, `end()` is returned. |
| * |
| * **Exceptions**: Strong exception guarantee if `T` is `NothrowAssignable`, |
| * Basic exception guarantee otherwise. |
| * |
| * **Complexity**: Linear in half the size of `*this`. |
| */ |
| iterator erase(iterator first, iterator last) |
| { |
| size_type front_distance = last - begin(); |
| size_type back_distance = end() - first; |
| size_type n = boost::container::iterator_distance(first, last); |
| |
| if (front_distance < back_distance) |
| { |
| // move n to the right |
| boost::container::move_backward(begin(), first, last); |
| |
| for (iterator i = begin(); i != begin() + n; ++i) |
| { |
| allocator_traits_type::destroy(get_allocator_ref(), i); |
| } |
| //n is always less than max stored_size_type |
| m_.set_front_idx(m_.front_idx + n); |
| |
| BOOST_ASSERT(invariants_ok()); |
| return last; |
| } |
| else { |
| // move n to the left |
| boost::container::move(last, end(), first); |
| |
| for (iterator i = end() - n; i != end(); ++i) |
| { |
| allocator_traits_type::destroy(get_allocator_ref(), i); |
| } |
| //n is always less than max stored_size_type |
| m_.set_back_idx(m_.back_idx - n); |
| |
| BOOST_ASSERT(invariants_ok()); |
| return first; |
| } |
| } |
| |
| /** |
| * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable |
| * |
| * **Effects**: exchanges the contents of `*this` and `b`. |
| * |
| * **Requires**: instances of `T` must be swappable by unqualified call of `swap` |
| * and `T` must be [MoveInsertable] into `*this`. |
| * |
| * **Precondition**: The allocators should allow propagation or should compare equal. |
| * |
| * **Exceptions**: Basic exceptions guarantee if not `noexcept`. |
| * |
| * **Complexity**: Constant. |
| */ |
| void swap(devector& b) |
| BOOST_NOEXCEPT_IF( allocator_traits_type::propagate_on_container_swap::value |
| || allocator_traits_type::is_always_equal::value) |
| { |
| BOOST_CONSTEXPR_OR_CONST bool propagate_alloc = allocator_traits_type::propagate_on_container_swap::value; |
| BOOST_ASSERT(propagate_alloc || get_allocator_ref() == b.get_allocator_ref()); // else it's undefined behavior |
| |
| swap_big_big(*this, b); |
| |
| // swap indices |
| boost::adl_move_swap(m_.front_idx, b.m_.front_idx); |
| boost::adl_move_swap(m_.back_idx, b.m_.back_idx); |
| |
| //And now swap the allocator |
| dtl::swap_alloc(this->get_allocator_ref(), b.get_allocator_ref(), dtl::bool_<propagate_alloc>()); |
| |
| BOOST_ASSERT( invariants_ok()); |
| BOOST_ASSERT(b.invariants_ok()); |
| } |
| |
| /** |
| * **Effects**: Destroys all elements in the devector. |
| * Invalidates all references, pointers and iterators to the |
| * elements of the devector. |
| * |
| * **Postcondition**: `empty() && front_free_capacity() == 0 |
| * && back_free_capacity() == old capacity`. |
| * |
| * **Complexity**: Linear in the size of `*this`. |
| * |
| * **Remarks**: Does not free memory. |
| */ |
| void clear() BOOST_NOEXCEPT |
| { |
| destroy_elements(begin(), end()); |
| m_.front_idx = m_.back_idx = 0; |
| } |
| |
| BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE |
| friend bool operator==(const devector& x, const devector& y) |
| { return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin()); } |
| |
| BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE |
| friend bool operator!=(const devector& x, const devector& y) |
| { return !(x == y); } |
| |
| BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE |
| friend bool operator< (const devector& x, const devector& y) |
| { return boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); } |
| |
| BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE |
| friend bool operator>(const devector& x, const devector& y) |
| { return y < x; } |
| |
| BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE |
| friend bool operator<=(const devector& x, const devector& y) |
| { return !(y < x); } |
| |
| BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE |
| friend bool operator>=(const devector& x, const devector& y) |
| { return !(x < y); } |
| |
| BOOST_CONTAINER_FORCEINLINE friend void swap(devector& x, devector& y) |
| BOOST_NOEXCEPT_IF( allocator_traits_type::propagate_on_container_swap::value |
| || allocator_traits_type::is_always_equal::value) |
| { x.swap(y); } |
| |
| private: |
| #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED |
| |
| BOOST_CONTAINER_FORCEINLINE T* raw_begin() BOOST_NOEXCEPT |
| { return boost::movelib::to_raw_pointer(m_.buffer) + m_.front_idx; } |
| |
| BOOST_CONTAINER_FORCEINLINE T* raw_end() BOOST_NOEXCEPT |
| { return boost::movelib::to_raw_pointer(m_.buffer) + m_.back_idx; } |
| |
| |
| template <class U> |
| BOOST_CONTAINER_FORCEINLINE void priv_push_front(BOOST_FWD_REF(U) u) |
| { |
| this->emplace_front(boost::forward<U>(u)); |
| } |
| |
| template <class U> |
| BOOST_CONTAINER_FORCEINLINE void priv_push_back(BOOST_FWD_REF(U) u) |
| { |
| this->emplace_back(boost::forward<U>(u)); |
| } |
| |
| template <class U> |
| BOOST_CONTAINER_FORCEINLINE iterator priv_insert(const_iterator pos, BOOST_FWD_REF(U) u) |
| { |
| return this->emplace(pos, boost::forward<U>(u)); |
| } |
| |
| // allocator_type wrappers |
| |
| BOOST_CONTAINER_FORCEINLINE allocator_type& get_allocator_ref() BOOST_NOEXCEPT |
| { |
| return static_cast<allocator_type&>(m_); |
| } |
| |
| BOOST_CONTAINER_FORCEINLINE const allocator_type& get_allocator_ref() const BOOST_NOEXCEPT |
| { |
| return static_cast<const allocator_type&>(m_); |
| } |
| |
| pointer allocate(size_type capacity) |
| { |
| //First detect overflow on smaller stored_size_types |
| if (capacity > stored_size_type(-1)){ |
| boost::container::throw_length_error("get_next_capacity, allocator's max size reached"); |
| } |
| //(clamp_by_stored_size_type<size_type>)(prefer_in_recvd_out_size, stored_size_type()); |
| #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS |
| ++m_.capacity_alloc_count; |
| #endif // BOOST_CONTAINER_DEVECTOR_ALLOC_STATS |
| return allocator_traits_type::allocate(get_allocator_ref(), capacity); |
| } |
| |
| void destroy_elements(pointer begin, pointer end) |
| { |
| for (; begin != end; ++begin) |
| { |
| allocator_traits_type::destroy(get_allocator_ref(), begin); |
| } |
| } |
| |
| void deallocate_buffer() |
| { |
| if (m_.buffer) |
| { |
| allocator_traits_type::deallocate(get_allocator_ref(), m_.buffer, m_.capacity); |
| } |
| } |
| |
| #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) |
| template <typename... Args> |
| BOOST_CONTAINER_FORCEINLINE void alloc_construct(pointer dst, Args&&... args) |
| { |
| allocator_traits_type::construct( |
| get_allocator_ref(), |
| dst, |
| boost::forward<Args>(args)... |
| ); |
| } |
| |
| template <typename... Args> |
| void construct_n(pointer buffer, size_type n, Args&&... args) |
| { |
| detail::construction_guard<allocator_type> ctr_guard(buffer, get_allocator_ref()); |
| guarded_construct_n(buffer, n, ctr_guard, boost::forward<Args>(args)...); |
| ctr_guard.release(); |
| } |
| |
| template <typename... Args> |
| void guarded_construct_n(pointer buffer, size_type n, detail::construction_guard<allocator_type>& ctr_guard, Args&&... args) |
| { |
| for (size_type i = 0; i < n; ++i) { |
| this->alloc_construct(buffer + i, boost::forward<Args>(args)...); |
| ctr_guard.extend(); |
| } |
| } |
| |
| #else //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) |
| |
| #define BOOST_CONTAINER_DEVECTOR_ALLOC_CONSTRUCT(N) \ |
| BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ |
| BOOST_CONTAINER_FORCEINLINE void alloc_construct(pointer dst BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ |
| {\ |
| allocator_traits_type::construct(\ |
| get_allocator_ref(), dst BOOST_MOVE_I##N BOOST_MOVE_FWD##N );\ |
| }\ |
| \ |
| BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ |
| void construct_n(pointer buffer, size_type n BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ |
| {\ |
| detail::construction_guard<allocator_type> ctr_guard(buffer, get_allocator_ref());\ |
| guarded_construct_n(buffer, n, ctr_guard BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ |
| ctr_guard.release();\ |
| }\ |
| \ |
| BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ |
| void guarded_construct_n(pointer buffer, size_type n, detail::construction_guard<allocator_type>& ctr_guard BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ |
| {\ |
| for (size_type i = 0; i < n; ++i) {\ |
| this->alloc_construct(buffer + i BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ |
| ctr_guard.extend();\ |
| }\ |
| } |
| // |
| BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_DEVECTOR_ALLOC_CONSTRUCT) |
| #undef BOOST_CONTAINER_DEVECTOR_ALLOC_CONSTRUCT |
| |
| #endif //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) |
| |
| BOOST_CONTAINER_FORCEINLINE size_type front_capacity() const |
| { |
| return m_.back_idx; |
| } |
| |
| BOOST_CONTAINER_FORCEINLINE size_type back_capacity() const |
| { |
| return m_.capacity - m_.front_idx; |
| } |
| |
| size_type calculate_new_capacity(size_type requested_capacity) |
| { |
| size_type max = allocator_traits_type::max_size(this->get_allocator_ref()); |
| (clamp_by_stored_size_type)(max, stored_size_type()); |
| const size_type remaining_additional_cap = max - size_type(m_.capacity); |
| const size_type min_additional_cap = requested_capacity - size_type(m_.capacity); |
| if ( remaining_additional_cap < min_additional_cap ) |
| boost::container::throw_length_error("devector: get_next_capacity, max size exceeded"); |
| |
| return growth_factor_type()( size_type(m_.capacity), min_additional_cap, max); |
| } |
| |
| void buffer_move_or_copy(pointer dst) |
| { |
| detail::construction_guard<allocator_type> guard(dst, get_allocator_ref()); |
| |
| buffer_move_or_copy(dst, guard); |
| |
| guard.release(); |
| } |
| |
| void buffer_move_or_copy(pointer dst, detail::construction_guard<allocator_type>& guard) |
| { |
| opt_move_or_copy(begin(), end(), dst, guard); |
| |
| destroy_elements(data(), data() + size()); |
| deallocate_buffer(); |
| } |
| |
| void opt_move_or_copy(pointer begin, pointer end, pointer dst) |
| { |
| typedef typename dtl::if_c |
| < boost::move_detail::is_nothrow_copy_constructible<T>::value || boost::is_nothrow_move_constructible<T>::value |
| , detail::null_construction_guard |
| , detail::construction_guard<allocator_type> |
| >::type guard_t; |
| |
| guard_t guard(dst, get_allocator_ref()); |
| |
| opt_move_or_copy(begin, end, dst, guard); |
| |
| guard.release(); |
| } |
| |
| template <typename Guard> |
| void opt_move_or_copy(pointer begin, pointer end, pointer dst, Guard& guard) |
| { |
| // if trivial copy and default allocator, memcpy |
| boost::container::uninitialized_move_alloc(get_allocator_ref(), begin, end, dst); |
| guard.extend(); |
| } |
| |
| template <typename Iterator> |
| void opt_copy(Iterator begin, Iterator end, pointer dst) |
| { |
| typedef typename dtl::if_c |
| < boost::move_detail::is_nothrow_copy_constructible<T>::value |
| , detail::null_construction_guard |
| , detail::construction_guard<allocator_type> |
| >::type guard_t; |
| |
| guard_t guard(dst, get_allocator_ref()); |
| |
| opt_copy(begin, end, dst, guard); |
| |
| guard.release(); |
| } |
| |
| template <typename Iterator, typename Guard> |
| void opt_copy(Iterator begin, Iterator end, pointer dst, Guard& guard) |
| { |
| while (begin != end) |
| { |
| this->alloc_construct(dst++, *begin++); |
| guard.extend(); |
| } |
| } |
| |
| template <typename Guard> |
| void opt_copy(const_pointer begin, const_pointer end, pointer dst, Guard& guard) |
| { |
| // if trivial copy and default allocator, memcpy |
| boost::container::uninitialized_copy_alloc(get_allocator_ref(), begin, end, dst); |
| guard.extend(); |
| } |
| |
| #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) |
| |
| template <typename... Args> |
| void resize_front_impl(size_type sz , Args&&... args) |
| { |
| if (sz > size()) |
| { |
| const size_type n = sz - size(); |
| |
| if (sz <= front_capacity()) |
| { |
| construct_n(m_.buffer + m_.front_idx - n, n, boost::forward<Args>(args)...); |
| m_.set_front_idx(m_.front_idx - n); |
| } |
| else |
| { |
| resize_front_slow_path(sz, n, boost::forward<Args>(args)...); |
| } |
| } |
| else { |
| while (this->size() > sz) |
| { |
| this->pop_front(); |
| } |
| } |
| } |
| |
| template <typename... Args> |
| void resize_front_slow_path(size_type sz, size_type n, Args&&... args) |
| { |
| const size_type new_capacity = calculate_new_capacity(sz + back_free_capacity()); |
| pointer new_buffer = allocate(new_capacity); |
| allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref()); |
| |
| const size_type new_old_elem_index = new_capacity - size(); |
| const size_type new_elem_index = new_old_elem_index - n; |
| |
| detail::construction_guard<allocator_type> guard(new_buffer + new_elem_index, get_allocator_ref()); |
| guarded_construct_n(new_buffer + new_elem_index, n, guard, boost::forward<Args>(args)...); |
| |
| buffer_move_or_copy(new_buffer + new_old_elem_index, guard); |
| |
| guard.release(); |
| new_buffer_guard.release(); |
| |
| m_.buffer = new_buffer; |
| m_.set_capacity(new_capacity); |
| m_.set_back_idx(new_old_elem_index + m_.back_idx - m_.front_idx); |
| m_.set_front_idx(new_elem_index); |
| } |
| |
| template <typename... Args> |
| void resize_back_impl(size_type sz, Args&&... args) |
| { |
| if (sz > size()) |
| { |
| const size_type n = sz - size(); |
| |
| if (sz <= back_capacity()) |
| { |
| construct_n(m_.buffer + m_.back_idx, n, boost::forward<Args>(args)...); |
| m_.set_back_idx(m_.back_idx + n); |
| } |
| else |
| { |
| resize_back_slow_path(sz, n, boost::forward<Args>(args)...); |
| } |
| } |
| else |
| { |
| while (size() > sz) |
| { |
| pop_back(); |
| } |
| } |
| } |
| |
| template <typename... Args> |
| void resize_back_slow_path(size_type sz, size_type n, Args&&... args) |
| { |
| const size_type new_capacity = calculate_new_capacity(sz + front_free_capacity()); |
| pointer new_buffer = allocate(new_capacity); |
| allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref()); |
| |
| detail::construction_guard<allocator_type> guard(new_buffer + m_.back_idx, get_allocator_ref()); |
| guarded_construct_n(new_buffer + m_.back_idx, n, guard, boost::forward<Args>(args)...); |
| |
| buffer_move_or_copy(new_buffer + m_.front_idx); |
| |
| guard.release(); |
| new_buffer_guard.release(); |
| |
| m_.buffer = new_buffer; |
| m_.set_capacity(new_capacity); |
| m_.set_back_idx(m_.back_idx + n); |
| } |
| |
| template <typename... Args> |
| iterator emplace_slow_path(size_type new_elem_index, Args&&... args) |
| { |
| pointer position = begin() + new_elem_index; |
| |
| // prefer moving front to access memory forward if there are less elems to move |
| bool prefer_move_front = new_elem_index <= size()/2; |
| |
| if (front_free_capacity() && (!back_free_capacity() || prefer_move_front)) |
| { |
| BOOST_ASSERT(size() >= 1); |
| |
| // move things closer to the front a bit |
| |
| // avoid invalidating any reference in args later |
| T tmp(boost::forward<Args>(args)...); |
| |
| // construct at front - 1 from front (no guard) |
| this->alloc_construct(begin() - 1, boost::move(*begin())); |
| |
| // move front half left |
| boost::move(begin() + 1, position, begin()); |
| --m_.front_idx; |
| |
| // move assign new elem before pos |
| --position; |
| *position = boost::move(tmp); |
| |
| return position; |
| } |
| else if (back_free_capacity()) { |
| BOOST_ASSERT(size() >= 1); |
| |
| // move things closer to the end a bit |
| |
| // avoid invalidating any reference in args later |
| T tmp(boost::forward<Args>(args)...); |
| |
| // construct at back + 1 from back (no guard) |
| this->alloc_construct(end(), boost::move(back())); |
| |
| // move back half right |
| boost::container::move_backward(position, end() - 1, end()); |
| ++m_.back_idx; |
| |
| // move assign new elem to pos |
| *position = boost::move(tmp); |
| |
| return position; |
| } |
| else |
| { |
| return emplace_reallocating_slow_path(prefer_move_front, new_elem_index, boost::forward<Args>(args)...); |
| } |
| } |
| |
| template <typename... Args> |
| pointer emplace_reallocating_slow_path(bool make_front_free, size_type new_elem_index, Args&&... args) |
| { |
| // reallocate |
| size_type new_capacity = calculate_new_capacity(capacity() + 1); |
| pointer new_buffer = allocate(new_capacity); |
| |
| // guard allocation |
| allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref()); |
| |
| size_type new_front_index = (make_front_free) |
| ? new_capacity - back_free_capacity() - size() - 1 |
| : m_.front_idx; |
| |
| iterator new_begin = new_buffer + new_front_index; |
| iterator new_position = new_begin + new_elem_index; |
| iterator old_position = begin() + new_elem_index; |
| |
| // construct new element (and guard it) |
| this->alloc_construct(new_position, boost::forward<Args>(args)...); |
| |
| detail::construction_guard<allocator_type> second_half_guard(new_position, get_allocator_ref()); |
| second_half_guard.extend(); |
| |
| // move front-pos (possibly guarded) |
| detail::construction_guard<allocator_type> first_half_guard(new_begin, get_allocator_ref()); |
| opt_move_or_copy(begin(), old_position, new_begin, first_half_guard); |
| |
| // move pos+1-end (possibly guarded) |
| opt_move_or_copy(old_position, end(), new_position + 1, second_half_guard); |
| |
| // cleanup |
| destroy_elements(begin(), end()); |
| deallocate_buffer(); |
| |
| // release alloc and other guards |
| second_half_guard.release(); |
| first_half_guard.release(); |
| new_buffer_guard.release(); |
| |
| // rebind members |
| m_.set_capacity(new_capacity); |
| m_.buffer = new_buffer; |
| m_.set_back_idx(new_front_index + size() + 1); |
| m_.set_front_idx(new_front_index); |
| |
| return new_position; |
| } |
| |
| #else //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) |
| |
| #define BOOST_CONTAINER_DEVECTOR_SLOW_PATH(N) \ |
| BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ |
| void resize_front_impl(size_type sz BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ |
| {\ |
| if (sz > size())\ |
| {\ |
| const size_type n = sz - size();\ |
| if (sz <= front_capacity()){\ |
| construct_n(m_.buffer + m_.front_idx - n, n BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ |
| m_.set_front_idx(m_.front_idx - n);\ |
| }\ |
| else\ |
| {\ |
| resize_front_slow_path(sz, n BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ |
| }\ |
| }\ |
| else {\ |
| while (this->size() > sz)\ |
| {\ |
| this->pop_front();\ |
| }\ |
| }\ |
| }\ |
| \ |
| BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ |
| void resize_front_slow_path(size_type sz, size_type n BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ |
| {\ |
| const size_type new_capacity = calculate_new_capacity(sz + back_free_capacity());\ |
| pointer new_buffer = allocate(new_capacity);\ |
| allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref());\ |
| \ |
| const size_type new_old_elem_index = new_capacity - size();\ |
| const size_type new_elem_index = new_old_elem_index - n;\ |
| \ |
| detail::construction_guard<allocator_type> guard(new_buffer + new_elem_index, get_allocator_ref());\ |
| guarded_construct_n(new_buffer + new_elem_index, n, guard BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ |
| \ |
| buffer_move_or_copy(new_buffer + new_old_elem_index, guard);\ |
| \ |
| guard.release();\ |
| new_buffer_guard.release();\ |
| m_.buffer = new_buffer;\ |
| m_.set_capacity(new_capacity);\ |
| m_.set_back_idx(new_old_elem_index + m_.back_idx - m_.front_idx);\ |
| m_.set_front_idx(new_elem_index);\ |
| }\ |
| \ |
| BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ |
| void resize_back_impl(size_type sz BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ |
| {\ |
| if (sz > size())\ |
| {\ |
| const size_type n = sz - size();\ |
| \ |
| if (sz <= back_capacity())\ |
| {\ |
| construct_n(m_.buffer + m_.back_idx, n BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ |
| m_.set_back_idx(m_.back_idx + n);\ |
| }\ |
| else\ |
| {\ |
| resize_back_slow_path(sz, n BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ |
| }\ |
| }\ |
| else\ |
| {\ |
| while (size() > sz)\ |
| {\ |
| pop_back();\ |
| }\ |
| }\ |
| }\ |
| \ |
| BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ |
| void resize_back_slow_path(size_type sz, size_type n BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ |
| {\ |
| const size_type new_capacity = calculate_new_capacity(sz + front_free_capacity());\ |
| pointer new_buffer = allocate(new_capacity);\ |
| allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref());\ |
| \ |
| detail::construction_guard<allocator_type> guard(new_buffer + m_.back_idx, get_allocator_ref());\ |
| guarded_construct_n(new_buffer + m_.back_idx, n, guard BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ |
| \ |
| buffer_move_or_copy(new_buffer + m_.front_idx);\ |
| \ |
| guard.release();\ |
| new_buffer_guard.release();\ |
| \ |
| m_.buffer = new_buffer;\ |
| m_.set_capacity(new_capacity);\ |
| m_.set_back_idx(m_.back_idx + n);\ |
| }\ |
| \ |
| BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ |
| iterator emplace_slow_path(size_type new_elem_index BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ |
| {\ |
| pointer position = begin() + new_elem_index;\ |
| \ |
| bool prefer_move_front = new_elem_index <= size()/2;\ |
| \ |
| if (front_free_capacity() && (!back_free_capacity() || prefer_move_front))\ |
| {\ |
| BOOST_ASSERT(size() >= 1);\ |
| typename dtl::aligned_storage<sizeof(T), dtl::alignment_of<T>::value>::type v;\ |
| T *vp = reinterpret_cast<T *>(v.data);\ |
| allocator_traits_type::construct(get_stored_allocator(), vp BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ |
| T &tmp = *vp;\ |
| dtl::value_destructor<allocator_type> on_exit(get_stored_allocator(), tmp); (void)on_exit;\ |
| \ |
| this->alloc_construct(begin() - 1, boost::move(*begin()));\ |
| boost::move(begin() + 1, position, begin());\ |
| --m_.front_idx;\ |
| --position;\ |
| *position = boost::move(tmp);\ |
| return position;\ |
| }\ |
| else if (back_free_capacity()) {\ |
| BOOST_ASSERT(size() >= 1);\ |
| typename dtl::aligned_storage<sizeof(T), dtl::alignment_of<T>::value>::type v;\ |
| T *vp = reinterpret_cast<T *>(v.data);\ |
| allocator_traits_type::construct(get_stored_allocator(), vp BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ |
| T &tmp = *vp;\ |
| dtl::value_destructor<allocator_type> on_exit(get_stored_allocator(), tmp); (void)on_exit;\ |
| this->alloc_construct(end(), boost::move(back()));\ |
| boost::container::move_backward(position, end() - 1, end());\ |
| ++m_.back_idx;\ |
| *position = boost::move(tmp);\ |
| return position;\ |
| }\ |
| else {\ |
| return emplace_reallocating_slow_path(prefer_move_front, new_elem_index BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ |
| }\ |
| }\ |
| \ |
| BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ |
| pointer emplace_reallocating_slow_path(bool make_front_free, size_type new_elem_index BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ |
| {\ |
| size_type new_capacity = calculate_new_capacity(capacity() + 1);\ |
| pointer new_buffer = allocate(new_capacity);\ |
| allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref());\ |
| size_type new_front_index = (make_front_free)\ |
| ? new_capacity - back_free_capacity() - size() - 1\ |
| : m_.front_idx;\ |
| iterator new_begin = new_buffer + new_front_index;\ |
| iterator new_position = new_begin + new_elem_index;\ |
| iterator old_position = begin() + new_elem_index;\ |
| this->alloc_construct(new_position BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ |
| detail::construction_guard<allocator_type> second_half_guard(new_position, get_allocator_ref());\ |
| second_half_guard.extend();\ |
| detail::construction_guard<allocator_type> first_half_guard(new_begin, get_allocator_ref());\ |
| opt_move_or_copy(begin(), old_position, new_begin, first_half_guard);\ |
| opt_move_or_copy(old_position, end(), new_position + 1, second_half_guard);\ |
| destroy_elements(begin(), end());\ |
| deallocate_buffer();\ |
| second_half_guard.release();\ |
| first_half_guard.release();\ |
| new_buffer_guard.release();\ |
| m_.set_capacity(new_capacity);\ |
| m_.buffer = new_buffer;\ |
| m_.set_back_idx(new_front_index + size() + 1);\ |
| m_.set_front_idx(new_front_index);\ |
| return new_position;\ |
| }\ |
| // |
| BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_DEVECTOR_SLOW_PATH) |
| #undef BOOST_CONTAINER_DEVECTOR_SLOW_PATH |
| |
| #endif //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) |
| /* |
| void unsafe_uninitialized_grow_front(size_type n) |
| { |
| BOOST_ASSERT(n >= size()); |
| |
| size_type need = n - size(); |
| |
| if (need > front_free_capacity()) |
| { |
| reallocate_at(n + back_free_capacity(), need); |
| } |
| |
| m_.set_front_idx(m_.front_idx - need); |
| } |
| |
| void unsafe_uninitialized_shrink_front(size_type n) |
| { |
| BOOST_ASSERT(n <= size()); |
| |
| size_type doesnt_need = size() - n; |
| m_.set_front_idx(m_.front_idx + doesnt_need); |
| } |
| |
| void unsafe_uninitialized_grow_back(size_type n) |
| { |
| BOOST_ASSERT(n >= size()); |
| |
| size_type need = n - size(); |
| |
| if (need > back_free_capacity()) |
| { |
| reallocate_at(n + front_free_capacity(), front_free_capacity()); |
| } |
| |
| m_.set_back_idx(m_.back_idx + need); |
| } |
| |
| void unsafe_uninitialized_shrink_back(size_type n) |
| { |
| BOOST_ASSERT(n <= size()); |
| |
| size_type doesnt_need = size() - n; |
| m_.set_back_idx(m_.back_idx - doesnt_need); |
| } |
| */ |
| |
| void reallocate_at(size_type new_capacity, size_type buffer_offset) |
| { |
| pointer new_buffer = allocate(new_capacity); |
| allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref()); |
| |
| buffer_move_or_copy(new_buffer + buffer_offset); |
| |
| new_buffer_guard.release(); |
| |
| m_.buffer = new_buffer; |
| //Safe cast, allocate() will handle stored_size_type overflow |
| m_.set_capacity(new_capacity); |
| m_.set_back_idx(m_.back_idx - m_.front_idx + buffer_offset); |
| m_.set_front_idx(buffer_offset); |
| |
| BOOST_ASSERT(invariants_ok()); |
| } |
| |
| template <typename ForwardIterator> |
| iterator insert_range(const_iterator position, ForwardIterator first, ForwardIterator last) |
| { |
| size_type n = boost::container::iterator_distance(first, last); |
| |
| if (position == end() && back_free_capacity() >= n) {// fast path |
| iterator r(this->end()); |
| boost::container::uninitialized_copy_alloc(get_allocator_ref(), first, last, this->raw_end()); |
| m_.set_back_idx(m_.back_idx + n); |
| return r; |
| } |
| else if (position == begin() && front_free_capacity() >= n) { // secondary fast path |
| boost::container::uninitialized_copy_alloc(get_allocator_ref(), first, last, this->raw_begin() - n); |
| m_.set_front_idx(m_.front_idx - n); |
| return begin(); |
| } |
| else { |
| return insert_range_slow_path(position, first, last); |
| } |
| } |
| |
| template <typename ForwardIterator> |
| iterator insert_range_slow_path(const_iterator position, ForwardIterator first, ForwardIterator last) |
| { |
| size_type n = boost::container::iterator_distance(first, last); |
| size_type index = position - begin(); |
| |
| if (front_free_capacity() + back_free_capacity() >= n) { |
| // if we move enough, it can be done without reallocation |
| |
| iterator middle = begin() + index; |
| n -= insert_range_slow_path_near_front(middle, first, n); |
| |
| if (n) { |
| insert_range_slow_path_near_back(middle, first, n); |
| } |
| |
| BOOST_ASSERT(first == last); |
| return begin() + index; |
| } |
| else { |
| const bool prefer_move_front = 2 * index <= size(); |
| return insert_range_reallocating_slow_path(prefer_move_front, index, first, n); |
| } |
| } |
| |
| template <typename Iterator> |
| size_type insert_range_slow_path_near_front(iterator position, Iterator& first, size_type n) |
| { |
| size_type n_front = dtl::min_value(front_free_capacity(), n); |
| iterator new_begin = begin() - n_front; |
| iterator ctr_pos = new_begin; |
| detail::construction_guard<allocator_type> ctr_guard(ctr_pos, get_allocator_ref()); |
| |
| while (ctr_pos != begin()) { |
| this->alloc_construct(ctr_pos++, *(first++)); |
| ctr_guard.extend(); |
| } |
| |
| boost::movelib::rotate_gcd(new_begin, ctr_pos, position); |
| m_.set_front_idx(m_.front_idx - n_front); |
| |
| ctr_guard.release(); |
| |
| BOOST_ASSERT(invariants_ok()); |
| |
| return n_front; |
| } |
| |
| template <typename Iterator> |
| size_type insert_range_slow_path_near_back(iterator position, Iterator& first, size_type n) |
| { |
| const size_type n_back = dtl::min_value(back_free_capacity(), n); |
| iterator ctr_pos = end(); |
| |
| detail::construction_guard<allocator_type> ctr_guard(ctr_pos, get_allocator_ref()); |
| |
| for (size_type i = 0; i < n_back; ++i) { |
| this->alloc_construct(ctr_pos++, *first++); |
| ctr_guard.extend(); |
| } |
| |
| boost::movelib::rotate_gcd(position, end(), ctr_pos); |
| m_.set_back_idx(m_.back_idx + n_back); |
| |
| ctr_guard.release(); |
| |
| BOOST_ASSERT(invariants_ok()); |
| |
| return n_back; |
| } |
| |
| template <typename Iterator> |
| iterator insert_range_reallocating_slow_path |
| (bool make_front_free, size_type new_elem_index, Iterator elems, size_type n) |
| { |
| // reallocate |
| const size_type new_capacity = calculate_new_capacity(capacity() + n); |
| pointer new_buffer = allocate(new_capacity); |
| |
| // guard allocation |
| allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref()); |
| |
| const size_type new_front_index = (make_front_free) |
| ? new_capacity - back_free_capacity() - size() - n |
| : m_.front_idx; |
| |
| const iterator new_begin = new_buffer + new_front_index; |
| const iterator new_position = new_begin + new_elem_index; |
| const iterator old_position = begin() + new_elem_index; |
| |
| // construct new element (and guard it) |
| iterator second_half_position = new_position; |
| detail::construction_guard<allocator_type> second_half_guard(second_half_position, get_allocator_ref()); |
| |
| for (size_type i = 0; i < n; ++i) { |
| this->alloc_construct(second_half_position++, *(elems++)); |
| second_half_guard.extend(); |
| } |
| |
| // move front-pos (possibly guarded) |
| detail::construction_guard<allocator_type> first_half_guard(new_begin, get_allocator_ref()); |
| opt_move_or_copy(begin(), old_position, new_begin, first_half_guard); |
| |
| // move pos+1-end (possibly guarded) |
| opt_move_or_copy(old_position, end(), second_half_position, second_half_guard); |
| |
| // cleanup |
| destroy_elements(begin(), end()); |
| deallocate_buffer(); |
| |
| // release alloc and other guards |
| second_half_guard.release(); |
| first_half_guard.release(); |
| new_buffer_guard.release(); |
| |
| // rebind members |
| m_.set_capacity(new_capacity); |
| m_.buffer = new_buffer; |
| m_.set_back_idx(new_front_index + size() + n); |
| m_.set_front_idx(new_front_index); |
| |
| return new_position; |
| } |
| |
| template <typename Iterator> |
| void construct_from_range(Iterator begin, Iterator end) |
| { |
| allocation_guard buffer_guard(m_.buffer, m_.capacity, get_allocator_ref()); |
| opt_copy(begin, end, m_.buffer); |
| |
| buffer_guard.release(); |
| } |
| |
| template <typename ForwardIterator> |
| void allocate_and_copy_range(ForwardIterator first, ForwardIterator last) |
| { |
| size_type n = boost::container::iterator_distance(first, last); |
| |
| pointer new_buffer = n ? allocate(n) : pointer(); |
| allocation_guard new_buffer_guard(new_buffer, n, get_allocator_ref()); |
| |
| opt_copy(first, last, new_buffer); |
| |
| destroy_elements(begin(), end()); |
| deallocate_buffer(); |
| |
| m_.set_capacity(n); |
| m_.buffer = new_buffer; |
| m_.front_idx = 0; |
| m_.set_back_idx(n); |
| |
| new_buffer_guard.release(); |
| } |
| |
| static void swap_big_big(devector& a, devector& b) BOOST_NOEXCEPT |
| { |
| boost::adl_move_swap(a.m_.capacity, b.m_.capacity); |
| boost::adl_move_swap(a.m_.buffer, b.m_.buffer); |
| } |
| |
| template <typename ForwardIterator> |
| void overwrite_buffer_impl(ForwardIterator first, ForwardIterator last, dtl::true_) |
| { |
| const size_type n = boost::container::iterator_distance(first, last); |
| |
| BOOST_ASSERT(capacity() >= n); |
| boost::container::uninitialized_copy_alloc_n |
| ( get_allocator_ref(), boost::movelib::iterator_to_raw_pointer(first) |
| , n, boost::movelib::iterator_to_raw_pointer(m_.buffer)); |
| m_.front_idx = 0; |
| m_.set_back_idx(n); |
| } |
| |
| template <typename InputIterator> |
| InputIterator overwrite_buffer_impl(InputIterator first, InputIterator last, dtl::false_) |
| { |
| pointer pos = m_.buffer; |
| detail::construction_guard<allocator_type> front_guard(pos, get_allocator_ref()); |
| |
| while (first != last && pos != begin()) { |
| this->alloc_construct(pos++, *first++); |
| front_guard.extend(); |
| } |
| |
| while (first != last && pos != end()) { |
| *pos++ = *first++; |
| } |
| |
| detail::construction_guard<allocator_type> back_guard(pos, get_allocator_ref()); |
| |
| iterator capacity_end = m_.buffer + capacity(); |
| while (first != last && pos != capacity_end) { |
| this->alloc_construct(pos++, *first++); |
| back_guard.extend(); |
| } |
| |
| pointer destroy_after = dtl::min_value(dtl::max_value(begin(), pos), end()); |
| destroy_elements(destroy_after, end()); |
| |
| front_guard.release(); |
| back_guard.release(); |
| |
| m_.front_idx = 0; |
| m_.set_back_idx(pos - begin()); |
| return first; |
| } |
| |
| template <typename ForwardIterator> |
| BOOST_CONTAINER_FORCEINLINE void overwrite_buffer(ForwardIterator first, ForwardIterator last) |
| { |
| this->overwrite_buffer_impl(first, last, |
| dtl::bool_<dtl::is_trivially_destructible<T>::value>()); |
| } |
| |
| bool invariants_ok() |
| { |
| return (!m_.capacity || m_.buffer) |
| && m_.front_idx <= m_.back_idx |
| && m_.back_idx <= m_.capacity; |
| } |
| |
| struct impl : allocator_type |
| { |
| impl() |
| : allocator_type(), buffer(), front_idx(), back_idx(), capacity() |
| #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS |
| , capacity_alloc_count() |
| #endif |
| {} |
| |
| explicit impl(const allocator_type &a) |
| : allocator_type(a), buffer(), front_idx(), back_idx(), capacity() |
| #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS |
| , capacity_alloc_count() |
| #endif |
| {} |
| |
| impl(const allocator_type &a, pointer p, size_type f, size_type b, size_type c) |
| : allocator_type(a), buffer(p) |
| //static cast sizes, as the allocation function will take care of overflows |
| , front_idx(static_cast<stored_size_type>(f)) |
| , back_idx(static_cast<stored_size_type>(b)) |
| , capacity(static_cast<stored_size_type>(c)) |
| #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS |
| , capacity_alloc_count() |
| #endif |
| {} |
| |
| impl(BOOST_RV_REF(allocator_type) a, pointer p, size_type f, size_type b, size_type c) |
| : allocator_type(boost::move(a)), buffer(p) |
| //static cast sizes, as the allocation function will take care of overflows |
| , front_idx(static_cast<stored_size_type>(f)) |
| , back_idx(static_cast<stored_size_type>(b)) |
| , capacity(static_cast<stored_size_type>(c)) |
| #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS |
| , capacity_alloc_count() |
| #endif |
| {} |
| |
| void set_back_idx(size_type bi) |
| { back_idx = static_cast<stored_size_type>(bi);} |
| |
| void set_front_idx(size_type fi) |
| { front_idx = static_cast<stored_size_type>(fi);} |
| |
| void set_capacity(size_type c) |
| { capacity = static_cast<stored_size_type>(c);} |
| |
| pointer buffer; |
| stored_size_type front_idx; |
| stored_size_type back_idx; |
| stored_size_type capacity; |
| #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS |
| size_type capacity_alloc_count; |
| #endif |
| } m_; |
| |
| |
| #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS |
| public: |
| void reset_alloc_stats() |
| { |
| m_.capacity_alloc_count = 0; |
| } |
| |
| size_type get_alloc_count() const |
| { |
| return m_.capacity_alloc_count; |
| } |
| |
| #endif // ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS |
| |
| #endif // ifndef BOOST_CONTAINER_DOXYGEN_INVOKED |
| }; |
| |
| }} // namespace boost::container |
| |
| #include <boost/container/detail/config_end.hpp> |
| |
| #endif // BOOST_CONTAINER_DEVECTOR_HPP |