1 //////////////////////////////////////////////////////////////////////////////
3 // (C) Copyright Ion Gaztanaga 2005-2015. Distributed under the Boost
4 // Software License, Version 1.0. (See accompanying file
5 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
7 // See http://www.boost.org/libs/container for documentation.
9 //////////////////////////////////////////////////////////////////////////////
10 #ifndef BOOST_CONTAINER_DEQUE_HPP
11 #define BOOST_CONTAINER_DEQUE_HPP
13 #ifndef BOOST_CONFIG_HPP
14 # include <boost/config.hpp>
17 #if defined(BOOST_HAS_PRAGMA_ONCE)
21 #include <boost/container/detail/config_begin.hpp>
22 #include <boost/container/detail/workaround.hpp>
24 #include <boost/container/allocator_traits.hpp>
25 #include <boost/container/container_fwd.hpp>
26 #include <boost/container/new_allocator.hpp> //new_allocator
27 #include <boost/container/throw_exception.hpp>
28 #include <boost/container/options.hpp>
30 #include <boost/container/detail/advanced_insert_int.hpp>
31 #include <boost/container/detail/algorithm.hpp> //algo_equal(), algo_lexicographical_compare
32 #include <boost/container/detail/alloc_helpers.hpp>
33 #include <boost/container/detail/copy_move_algo.hpp>
34 #include <boost/container/detail/iterator.hpp>
35 #include <boost/move/detail/iterator_to_raw_pointer.hpp>
36 #include <boost/container/detail/iterators.hpp>
37 #include <boost/container/detail/min_max.hpp>
38 #include <boost/container/detail/mpl.hpp>
39 #include <boost/move/detail/to_raw_pointer.hpp>
40 #include <boost/container/detail/type_traits.hpp>
42 #include <boost/move/adl_move_swap.hpp>
43 #include <boost/move/iterator.hpp>
44 #include <boost/move/traits.hpp>
45 #include <boost/move/utility_core.hpp>
47 #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
48 #include <boost/move/detail/fwd_macros.hpp>
50 #include <boost/move/detail/move_helpers.hpp>
52 #include <boost/assert.hpp>
53 #include <boost/core/no_exceptions_support.hpp>
57 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
58 #include <initializer_list>
64 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
65 template <class T, class Allocator, class Options>
69 struct deque_value_traits
72 static const bool trivial_dctr = dtl::is_trivially_destructible<value_type>::value;
73 static const bool trivial_dctr_after_move = ::boost::has_trivial_destructor_after_move<value_type>::value;
76 template<class T, std::size_t BlockBytes, std::size_t BlockSize>
77 struct deque_block_size
79 BOOST_STATIC_ASSERT_MSG(!(BlockBytes && BlockSize), "BlockBytes and BlockSize can't be specified at the same time");
80 static const std::size_t block_bytes = BlockBytes ? BlockBytes : 512u;
81 static const std::size_t value = BlockSize ? BlockSize : (sizeof(T) < block_bytes ? (block_bytes/sizeof(T)) : std::size_t(1));
87 // For any nonsingular iterator i:
88 // i.node is the address of an element in the map array. The
89 // contents of i.node is a pointer to the beginning of a node.
90 // i.first == //(i.node)
91 // i.last == i.first + node_size
92 // i.cur is a pointer in the range [i.first, i.last). NOTE:
93 // the implication of this is that i.cur is always a dereferenceable
94 // pointer, even if i is a past-the-end iterator.
95 // Start and Finish are always nonsingular iterators. NOTE: this means
96 // that an empty deque must have one node, and that a deque
97 // with N elements, where N is the buffer size, must have two nodes.
98 // For every node other than start.node and finish.node, every element
99 // in the node is an initialized object. If start.node == finish.node,
100 // then [start.cur, finish.cur) are initialized objects, and
101 // the elements outside that range are uninitialized storage. Otherwise,
102 // [start.cur, start.last) and [finish.first, finish.cur) are initialized
103 // objects, and [start.first, start.cur) and [finish.cur, finish.last)
104 // are uninitialized storage.
105 // [map, map + map_size) is a valid, non-empty range.
106 // [start.node, finish.node] is a valid range contained within
107 // [map, map + map_size).
108 // A pointer in the range [map, map + map_size) points to an allocated node
109 // if and only if the pointer is in the range [start.node, finish.node].
110 template<class Pointer, bool IsConst>
114 typedef std::random_access_iterator_tag iterator_category;
115 typedef typename boost::intrusive::pointer_traits<Pointer>::element_type value_type;
116 typedef typename boost::intrusive::pointer_traits<Pointer>::difference_type difference_type;
117 typedef typename if_c
119 , typename boost::intrusive::pointer_traits<Pointer>::template
120 rebind_pointer<const value_type>::type
123 typedef typename if_c
130 typedef typename dtl::if_c< IsConst
131 , deque_iterator<Pointer, false>
132 , nat>::type nonconst_iterator;
134 typedef Pointer val_alloc_ptr;
135 typedef typename boost::intrusive::pointer_traits<Pointer>::
136 template rebind_pointer<Pointer>::type index_pointer;
141 index_pointer m_node;
145 BOOST_CONTAINER_FORCEINLINE Pointer get_cur() const { return m_cur; }
146 BOOST_CONTAINER_FORCEINLINE Pointer get_first() const { return m_first; }
147 BOOST_CONTAINER_FORCEINLINE Pointer get_last() const { return m_last; }
148 BOOST_CONTAINER_FORCEINLINE index_pointer get_node() const { return m_node; }
150 BOOST_CONTAINER_FORCEINLINE deque_iterator(val_alloc_ptr x, index_pointer y, difference_type block_size) BOOST_NOEXCEPT_OR_NOTHROW
151 : m_cur(x), m_first(*y), m_last(*y + block_size), m_node(y)
154 BOOST_CONTAINER_FORCEINLINE deque_iterator() BOOST_NOEXCEPT_OR_NOTHROW
155 : m_cur(), m_first(), m_last(), m_node() //Value initialization to achieve "null iterators" (N3644)
158 BOOST_CONTAINER_FORCEINLINE deque_iterator(const deque_iterator& x) BOOST_NOEXCEPT_OR_NOTHROW
159 : m_cur(x.get_cur()), m_first(x.get_first()), m_last(x.get_last()), m_node(x.get_node())
162 BOOST_CONTAINER_FORCEINLINE deque_iterator(const nonconst_iterator& x) BOOST_NOEXCEPT_OR_NOTHROW
163 : m_cur(x.get_cur()), m_first(x.get_first()), m_last(x.get_last()), m_node(x.get_node())
166 BOOST_CONTAINER_FORCEINLINE deque_iterator(Pointer cur, Pointer first, Pointer last, index_pointer node) BOOST_NOEXCEPT_OR_NOTHROW
167 : m_cur(cur), m_first(first), m_last(last), m_node(node)
170 BOOST_CONTAINER_FORCEINLINE deque_iterator& operator=(const deque_iterator& x) BOOST_NOEXCEPT_OR_NOTHROW
171 { m_cur = x.get_cur(); m_first = x.get_first(); m_last = x.get_last(); m_node = x.get_node(); return *this; }
173 BOOST_CONTAINER_FORCEINLINE deque_iterator<Pointer, false> unconst() const BOOST_NOEXCEPT_OR_NOTHROW
175 return deque_iterator<Pointer, false>(this->get_cur(), this->get_first(), this->get_last(), this->get_node());
178 BOOST_CONTAINER_FORCEINLINE reference operator*() const BOOST_NOEXCEPT_OR_NOTHROW
179 { return *this->m_cur; }
181 BOOST_CONTAINER_FORCEINLINE pointer operator->() const BOOST_NOEXCEPT_OR_NOTHROW
182 { return this->m_cur; }
184 difference_type operator-(const deque_iterator& x) const BOOST_NOEXCEPT_OR_NOTHROW
186 if(!this->m_cur && !x.m_cur){
189 const difference_type block_size = this->m_last - this->m_first;
190 BOOST_ASSERT(block_size);
191 return block_size * (this->m_node - x.m_node - 1) +
192 (this->m_cur - this->m_first) + (x.m_last - x.m_cur);
195 deque_iterator& operator++() BOOST_NOEXCEPT_OR_NOTHROW
197 BOOST_ASSERT(!!m_cur);
199 if (this->m_cur == this->m_last) {
200 const difference_type block_size = m_last - m_first;
201 BOOST_ASSERT(block_size);
202 this->priv_set_node(this->m_node + 1, block_size);
203 this->m_cur = this->m_first;
208 BOOST_CONTAINER_FORCEINLINE deque_iterator operator++(int) BOOST_NOEXCEPT_OR_NOTHROW
210 deque_iterator tmp(*this);
215 deque_iterator& operator--() BOOST_NOEXCEPT_OR_NOTHROW
217 BOOST_ASSERT(!!m_cur);
218 if (this->m_cur == this->m_first) {
219 const difference_type block_size = m_last - m_first;
220 BOOST_ASSERT(block_size);
221 this->priv_set_node(this->m_node - 1, block_size);
222 this->m_cur = this->m_last;
228 BOOST_CONTAINER_FORCEINLINE deque_iterator operator--(int) BOOST_NOEXCEPT_OR_NOTHROW
230 deque_iterator tmp(*this);
235 deque_iterator& operator+=(difference_type n) BOOST_NOEXCEPT_OR_NOTHROW
239 BOOST_ASSERT(!!m_cur);
240 difference_type offset = n + (this->m_cur - this->m_first);
241 const difference_type block_size = this->m_last - this->m_first;
242 BOOST_ASSERT(block_size);
243 if (offset >= 0 && offset < block_size)
246 difference_type node_offset =
247 offset > 0 ? (offset / block_size)
248 : (-difference_type((-offset - 1) / block_size) - 1);
249 this->priv_set_node(this->m_node + node_offset, block_size);
250 this->m_cur = this->m_first +
251 (offset - node_offset * block_size);
256 BOOST_CONTAINER_FORCEINLINE deque_iterator operator+(difference_type n) const BOOST_NOEXCEPT_OR_NOTHROW
257 { deque_iterator tmp(*this); return tmp += n; }
259 BOOST_CONTAINER_FORCEINLINE deque_iterator& operator-=(difference_type n) BOOST_NOEXCEPT_OR_NOTHROW
260 { return *this += -n; }
262 BOOST_CONTAINER_FORCEINLINE deque_iterator operator-(difference_type n) const BOOST_NOEXCEPT_OR_NOTHROW
263 { deque_iterator tmp(*this); return tmp -= n; }
265 BOOST_CONTAINER_FORCEINLINE reference operator[](difference_type n) const BOOST_NOEXCEPT_OR_NOTHROW
266 { return *(*this + n); }
268 BOOST_CONTAINER_FORCEINLINE friend bool operator==(const deque_iterator& l, const deque_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
269 { return l.m_cur == r.m_cur; }
271 BOOST_CONTAINER_FORCEINLINE friend bool operator!=(const deque_iterator& l, const deque_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
272 { return l.m_cur != r.m_cur; }
274 BOOST_CONTAINER_FORCEINLINE friend bool operator<(const deque_iterator& l, const deque_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
275 { return (l.m_node == r.m_node) ? (l.m_cur < r.m_cur) : (l.m_node < r.m_node); }
277 BOOST_CONTAINER_FORCEINLINE friend bool operator>(const deque_iterator& l, const deque_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
280 BOOST_CONTAINER_FORCEINLINE friend bool operator<=(const deque_iterator& l, const deque_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
283 BOOST_CONTAINER_FORCEINLINE friend bool operator>=(const deque_iterator& l, const deque_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
286 BOOST_CONTAINER_FORCEINLINE void priv_set_node(index_pointer new_node, difference_type block_size) BOOST_NOEXCEPT_OR_NOTHROW
288 this->m_node = new_node;
289 this->m_first = *new_node;
290 this->m_last = this->m_first + block_size;
293 BOOST_CONTAINER_FORCEINLINE friend deque_iterator operator+(difference_type n, deque_iterator x) BOOST_NOEXCEPT_OR_NOTHROW
299 template<class Options>
302 typedef Options type;
306 struct get_deque_opt<void>
308 typedef deque_null_opt type;
311 // Deque base class. It has two purposes. First, its constructor
312 // and destructor allocate (but don't initialize) storage. This makes
313 // exception safety easier.
314 template <class Allocator, class Options>
317 BOOST_COPYABLE_AND_MOVABLE(deque_base)
319 typedef allocator_traits<Allocator> val_alloc_traits_type;
320 typedef typename val_alloc_traits_type::value_type val_alloc_val;
321 typedef typename val_alloc_traits_type::pointer val_alloc_ptr;
322 typedef typename val_alloc_traits_type::const_pointer val_alloc_cptr;
323 typedef typename val_alloc_traits_type::reference val_alloc_ref;
324 typedef typename val_alloc_traits_type::const_reference val_alloc_cref;
325 typedef typename val_alloc_traits_type::difference_type val_alloc_diff;
326 typedef typename val_alloc_traits_type::size_type val_alloc_size;
327 typedef typename val_alloc_traits_type::template
328 portable_rebind_alloc<val_alloc_ptr>::type ptr_alloc_t;
329 typedef allocator_traits<ptr_alloc_t> ptr_alloc_traits_type;
330 typedef typename ptr_alloc_traits_type::value_type ptr_alloc_val;
331 typedef typename ptr_alloc_traits_type::pointer ptr_alloc_ptr;
332 typedef typename ptr_alloc_traits_type::const_pointer ptr_alloc_cptr;
333 typedef typename ptr_alloc_traits_type::reference ptr_alloc_ref;
334 typedef typename ptr_alloc_traits_type::const_reference ptr_alloc_cref;
335 typedef Allocator allocator_type;
336 typedef allocator_type stored_allocator_type;
337 typedef val_alloc_size size_type;
340 typedef typename get_deque_opt<Options>::type options_type;
343 typedef dtl::deque_iterator<val_alloc_ptr, false> iterator;
344 typedef dtl::deque_iterator<val_alloc_ptr, true > const_iterator;
346 BOOST_CONSTEXPR BOOST_CONTAINER_FORCEINLINE static size_type get_block_size() BOOST_NOEXCEPT_OR_NOTHROW
347 { return deque_block_size<val_alloc_val, options_type::block_bytes, options_type::block_size>::value; }
349 typedef deque_value_traits<val_alloc_val> traits_t;
350 typedef ptr_alloc_t map_allocator_type;
352 BOOST_CONTAINER_FORCEINLINE val_alloc_ptr priv_allocate_node()
353 { return this->alloc().allocate(get_block_size()); }
355 BOOST_CONTAINER_FORCEINLINE void priv_deallocate_node(val_alloc_ptr p) BOOST_NOEXCEPT_OR_NOTHROW
356 { this->alloc().deallocate(p, get_block_size()); }
358 BOOST_CONTAINER_FORCEINLINE ptr_alloc_ptr priv_allocate_map(size_type n)
359 { return this->ptr_alloc().allocate(n); }
361 BOOST_CONTAINER_FORCEINLINE void priv_deallocate_map(ptr_alloc_ptr p, size_type n) BOOST_NOEXCEPT_OR_NOTHROW
362 { this->ptr_alloc().deallocate(p, n); }
364 BOOST_CONTAINER_FORCEINLINE deque_base(size_type num_elements, const allocator_type& a)
366 { this->priv_initialize_map(num_elements); }
368 BOOST_CONTAINER_FORCEINLINE explicit deque_base(const allocator_type& a)
372 BOOST_CONTAINER_FORCEINLINE deque_base()
376 BOOST_CONTAINER_FORCEINLINE explicit deque_base(BOOST_RV_REF(deque_base) x)
377 : members_( boost::move(x.ptr_alloc())
378 , boost::move(x.alloc()) )
383 if (this->members_.m_map) {
384 this->priv_destroy_nodes(this->members_.m_start.m_node, this->members_.m_finish.m_node + 1);
385 this->priv_deallocate_map(this->members_.m_map, this->members_.m_map_size);
390 deque_base(const deque_base&);
394 void swap_members(deque_base &x) BOOST_NOEXCEPT_OR_NOTHROW
396 ::boost::adl_move_swap(this->members_.m_start, x.members_.m_start);
397 ::boost::adl_move_swap(this->members_.m_finish, x.members_.m_finish);
398 ::boost::adl_move_swap(this->members_.m_map, x.members_.m_map);
399 ::boost::adl_move_swap(this->members_.m_map_size, x.members_.m_map_size);
402 void priv_initialize_map(size_type num_elements)
405 size_type num_nodes = num_elements / get_block_size() + 1;
407 this->members_.m_map_size = dtl::max_value((size_type) InitialMapSize, num_nodes + 2);
408 this->members_.m_map = this->priv_allocate_map(this->members_.m_map_size);
410 ptr_alloc_ptr nstart = this->members_.m_map + (this->members_.m_map_size - num_nodes) / 2;
411 ptr_alloc_ptr nfinish = nstart + num_nodes;
414 this->priv_create_nodes(nstart, nfinish);
417 this->priv_deallocate_map(this->members_.m_map, this->members_.m_map_size);
418 this->members_.m_map = 0;
419 this->members_.m_map_size = 0;
424 this->members_.m_start.priv_set_node(nstart, get_block_size());
425 this->members_.m_finish.priv_set_node(nfinish - 1, get_block_size());
426 this->members_.m_start.m_cur = this->members_.m_start.m_first;
427 this->members_.m_finish.m_cur = this->members_.m_finish.m_first +
428 num_elements % get_block_size();
432 void priv_create_nodes(ptr_alloc_ptr nstart, ptr_alloc_ptr nfinish)
434 ptr_alloc_ptr cur = nstart;
436 for (; cur < nfinish; ++cur)
437 *cur = this->priv_allocate_node();
440 this->priv_destroy_nodes(nstart, cur);
446 void priv_destroy_nodes(ptr_alloc_ptr nstart, ptr_alloc_ptr nfinish) BOOST_NOEXCEPT_OR_NOTHROW
448 for (ptr_alloc_ptr n = nstart; n < nfinish; ++n)
449 this->priv_deallocate_node(*n);
452 void priv_clear_map() BOOST_NOEXCEPT_OR_NOTHROW
454 if (this->members_.m_map) {
455 this->priv_destroy_nodes(this->members_.m_start.m_node, this->members_.m_finish.m_node + 1);
456 this->priv_deallocate_map(this->members_.m_map, this->members_.m_map_size);
457 this->members_.m_map = 0;
458 this->members_.m_map_size = 0;
459 this->members_.m_start = iterator();
460 this->members_.m_finish = this->members_.m_start;
464 enum { InitialMapSize = 8 };
467 struct members_holder
469 , public allocator_type
472 : map_allocator_type(), allocator_type()
473 , m_map(0), m_map_size(0)
474 , m_start(), m_finish(m_start)
477 explicit members_holder(const allocator_type &a)
478 : map_allocator_type(a), allocator_type(a)
479 , m_map(0), m_map_size(0)
480 , m_start(), m_finish(m_start)
483 template<class ValAllocConvertible, class PtrAllocConvertible>
484 members_holder(BOOST_FWD_REF(PtrAllocConvertible) pa, BOOST_FWD_REF(ValAllocConvertible) va)
485 : map_allocator_type(boost::forward<PtrAllocConvertible>(pa))
486 , allocator_type (boost::forward<ValAllocConvertible>(va))
487 , m_map(0), m_map_size(0)
488 , m_start(), m_finish(m_start)
492 val_alloc_size m_map_size;
497 BOOST_CONTAINER_FORCEINLINE ptr_alloc_t &ptr_alloc() BOOST_NOEXCEPT_OR_NOTHROW
500 BOOST_CONTAINER_FORCEINLINE const ptr_alloc_t &ptr_alloc() const BOOST_NOEXCEPT_OR_NOTHROW
503 BOOST_CONTAINER_FORCEINLINE allocator_type &alloc() BOOST_NOEXCEPT_OR_NOTHROW
506 BOOST_CONTAINER_FORCEINLINE const allocator_type &alloc() const BOOST_NOEXCEPT_OR_NOTHROW
509 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
511 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
512 //! A double-ended queue is a sequence that supports random access to elements, constant time insertion
513 //! and removal of elements at the end of the sequence, and linear time insertion and removal of elements in the middle.
515 //! \tparam T The type of object that is stored in the deque
516 //! \tparam A The allocator used for all internal memory management, use void
517 //! for the default allocator
518 //! \tparam Options A type produced from \c boost::container::deque_options.
519 template <class T, class Allocator = void, class Options = void>
521 template <class T, class Allocator, class Options>
523 class deque : protected deque_base<typename real_allocator<T, Allocator>::type, Options>
525 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
527 typedef deque_base<typename real_allocator<T, Allocator>::type, Options> Base;
528 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
529 typedef typename real_allocator<T, Allocator>::type ValAllocator;
533 //////////////////////////////////////////////
537 //////////////////////////////////////////////
539 typedef T value_type;
540 typedef ValAllocator allocator_type;
541 typedef typename ::boost::container::allocator_traits<ValAllocator>::pointer pointer;
542 typedef typename ::boost::container::allocator_traits<ValAllocator>::const_pointer const_pointer;
543 typedef typename ::boost::container::allocator_traits<ValAllocator>::reference reference;
544 typedef typename ::boost::container::allocator_traits<ValAllocator>::const_reference const_reference;
545 typedef typename ::boost::container::allocator_traits<ValAllocator>::size_type size_type;
546 typedef typename ::boost::container::allocator_traits<ValAllocator>::difference_type difference_type;
547 typedef BOOST_CONTAINER_IMPDEF(allocator_type) stored_allocator_type;
548 typedef BOOST_CONTAINER_IMPDEF(typename Base::iterator) iterator;
549 typedef BOOST_CONTAINER_IMPDEF(typename Base::const_iterator) const_iterator;
550 typedef BOOST_CONTAINER_IMPDEF(boost::container::reverse_iterator<iterator>) reverse_iterator;
551 typedef BOOST_CONTAINER_IMPDEF(boost::container::reverse_iterator<const_iterator>) const_reverse_iterator;
553 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
555 private: // Internal typedefs
556 BOOST_COPYABLE_AND_MOVABLE(deque)
557 typedef typename Base::ptr_alloc_ptr index_pointer;
558 typedef allocator_traits<ValAllocator> allocator_traits_type;
560 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
564 BOOST_CONSTEXPR BOOST_CONTAINER_FORCEINLINE static size_type get_block_size() BOOST_NOEXCEPT_OR_NOTHROW
565 { return Base::get_block_size(); }
567 //////////////////////////////////////////////
569 // construct/copy/destroy
571 //////////////////////////////////////////////
573 //! <b>Effects</b>: Default constructors a deque.
575 //! <b>Throws</b>: If allocator_type's default constructor throws.
577 //! <b>Complexity</b>: Constant.
578 BOOST_CONTAINER_FORCEINLINE deque() BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<ValAllocator>::value)
582 //! <b>Effects</b>: Constructs a deque taking the allocator as parameter.
584 //! <b>Throws</b>: Nothing
586 //! <b>Complexity</b>: Constant.
587 BOOST_CONTAINER_FORCEINLINE explicit deque(const allocator_type& a) BOOST_NOEXCEPT_OR_NOTHROW
591 //! <b>Effects</b>: Constructs a deque
592 //! and inserts n value initialized values.
594 //! <b>Throws</b>: If allocator_type's default constructor
595 //! throws or T's value initialization throws.
597 //! <b>Complexity</b>: Linear to n.
598 BOOST_CONTAINER_FORCEINLINE explicit deque(size_type n)
599 : Base(n, allocator_type())
601 dtl::insert_value_initialized_n_proxy<ValAllocator, iterator> proxy;
602 proxy.uninitialized_copy_n_and_update(this->alloc(), this->begin(), n);
603 //deque_base will deallocate in case of exception...
606 //! <b>Effects</b>: Constructs a deque
607 //! and inserts n default initialized values.
609 //! <b>Throws</b>: If allocator_type's default constructor
610 //! throws or T's default initialization or copy constructor throws.
612 //! <b>Complexity</b>: Linear to n.
614 //! <b>Note</b>: Non-standard extension
615 BOOST_CONTAINER_FORCEINLINE deque(size_type n, default_init_t)
616 : Base(n, allocator_type())
618 dtl::insert_default_initialized_n_proxy<ValAllocator, iterator> proxy;
619 proxy.uninitialized_copy_n_and_update(this->alloc(), this->begin(), n);
620 //deque_base will deallocate in case of exception...
623 //! <b>Effects</b>: Constructs a deque that will use a copy of allocator a
624 //! and inserts n value initialized values.
626 //! <b>Throws</b>: If allocator_type's default constructor
627 //! throws or T's value initialization throws.
629 //! <b>Complexity</b>: Linear to n.
630 BOOST_CONTAINER_FORCEINLINE explicit deque(size_type n, const allocator_type &a)
633 dtl::insert_value_initialized_n_proxy<ValAllocator, iterator> proxy;
634 proxy.uninitialized_copy_n_and_update(this->alloc(), this->begin(), n);
635 //deque_base will deallocate in case of exception...
638 //! <b>Effects</b>: Constructs a deque that will use a copy of allocator a
639 //! and inserts n default initialized values.
641 //! <b>Throws</b>: If allocator_type's default constructor
642 //! throws or T's default initialization or copy constructor throws.
644 //! <b>Complexity</b>: Linear to n.
646 //! <b>Note</b>: Non-standard extension
647 BOOST_CONTAINER_FORCEINLINE deque(size_type n, default_init_t, const allocator_type &a)
650 dtl::insert_default_initialized_n_proxy<ValAllocator, iterator> proxy;
651 proxy.uninitialized_copy_n_and_update(this->alloc(), this->begin(), n);
652 //deque_base will deallocate in case of exception...
655 //! <b>Effects</b>: Constructs a deque that will use a copy of allocator a
656 //! and inserts n copies of value.
658 //! <b>Throws</b>: If allocator_type's default constructor
659 //! throws or T's copy constructor throws.
661 //! <b>Complexity</b>: Linear to n.
662 BOOST_CONTAINER_FORCEINLINE deque(size_type n, const value_type& value)
663 : Base(n, allocator_type())
664 { this->priv_fill_initialize(value); }
666 //! <b>Effects</b>: Constructs a deque that will use a copy of allocator a
667 //! and inserts n copies of value.
669 //! <b>Throws</b>: If allocator_type's default constructor
670 //! throws or T's copy constructor throws.
672 //! <b>Complexity</b>: Linear to n.
673 BOOST_CONTAINER_FORCEINLINE deque(size_type n, const value_type& value, const allocator_type& a)
675 { this->priv_fill_initialize(value); }
677 //! <b>Effects</b>: Constructs a deque that will use a copy of allocator a
678 //! and inserts a copy of the range [first, last) in the deque.
680 //! <b>Throws</b>: If allocator_type's default constructor
681 //! throws or T's constructor taking a dereferenced InIt throws.
683 //! <b>Complexity</b>: Linear to the range [first, last).
684 template <class InIt>
685 BOOST_CONTAINER_FORCEINLINE deque(InIt first, InIt last
686 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
687 , typename dtl::disable_if_convertible
688 <InIt, size_type>::type * = 0
691 : Base(allocator_type())
693 this->priv_range_initialize(first, last);
696 //! <b>Effects</b>: Constructs a deque that will use a copy of allocator a
697 //! and inserts a copy of the range [first, last) in the deque.
699 //! <b>Throws</b>: If allocator_type's default constructor
700 //! throws or T's constructor taking a dereferenced InIt throws.
702 //! <b>Complexity</b>: Linear to the range [first, last).
703 template <class InIt>
704 BOOST_CONTAINER_FORCEINLINE deque(InIt first, InIt last, const allocator_type& a
705 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
706 , typename dtl::disable_if_convertible
707 <InIt, size_type>::type * = 0
712 this->priv_range_initialize(first, last);
715 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
716 //! <b>Effects</b>: Constructs a deque that will use a copy of allocator a
717 //! and inserts a copy of the range [il.begin(), il.end()) in the deque.
719 //! <b>Throws</b>: If allocator_type's default constructor
720 //! throws or T's constructor taking a dereferenced std::initializer_list iterator throws.
722 //! <b>Complexity</b>: Linear to the range [il.begin(), il.end()).
723 BOOST_CONTAINER_FORCEINLINE deque(std::initializer_list<value_type> il, const allocator_type& a = allocator_type())
726 this->priv_range_initialize(il.begin(), il.end());
730 //! <b>Effects</b>: Copy constructs a deque.
732 //! <b>Postcondition</b>: x == *this.
734 //! <b>Complexity</b>: Linear to the elements x contains.
735 BOOST_CONTAINER_FORCEINLINE deque(const deque& x)
736 : Base(allocator_traits_type::select_on_container_copy_construction(x.alloc()))
739 this->priv_initialize_map(x.size());
740 boost::container::uninitialized_copy_alloc
741 (this->alloc(), x.begin(), x.end(), this->members_.m_start);
745 //! <b>Effects</b>: Move constructor. Moves x's resources to *this.
747 //! <b>Throws</b>: If allocator_type's copy constructor throws.
749 //! <b>Complexity</b>: Constant.
750 BOOST_CONTAINER_FORCEINLINE deque(BOOST_RV_REF(deque) x) BOOST_NOEXCEPT_OR_NOTHROW
751 : Base(BOOST_MOVE_BASE(Base, x))
752 { this->swap_members(x); }
754 //! <b>Effects</b>: Copy constructs a vector using the specified allocator.
756 //! <b>Postcondition</b>: x == *this.
758 //! <b>Throws</b>: If allocation
759 //! throws or T's copy constructor throws.
761 //! <b>Complexity</b>: Linear to the elements x contains.
762 deque(const deque& x, const allocator_type &a)
766 this->priv_initialize_map(x.size());
767 boost::container::uninitialized_copy_alloc
768 (this->alloc(), x.begin(), x.end(), this->members_.m_start);
772 //! <b>Effects</b>: Move constructor using the specified allocator.
773 //! Moves x's resources to *this if a == allocator_type().
774 //! Otherwise copies values from x to *this.
776 //! <b>Throws</b>: If allocation or T's copy constructor throws.
778 //! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise.
779 deque(BOOST_RV_REF(deque) x, const allocator_type &a)
783 this->swap_members(x);
787 this->priv_initialize_map(x.size());
788 boost::container::uninitialized_copy_alloc
789 ( this->alloc(), boost::make_move_iterator(x.begin())
790 , boost::make_move_iterator(x.end()), this->members_.m_start);
795 //! <b>Effects</b>: Destroys the deque. All stored values are destroyed
796 //! and used memory is deallocated.
798 //! <b>Throws</b>: Nothing.
800 //! <b>Complexity</b>: Linear to the number of elements.
801 BOOST_CONTAINER_FORCEINLINE ~deque() BOOST_NOEXCEPT_OR_NOTHROW
803 this->priv_destroy_range(this->members_.m_start, this->members_.m_finish);
806 //! <b>Effects</b>: Makes *this contain the same elements as x.
808 //! <b>Postcondition</b>: this->size() == x.size(). *this contains a copy
809 //! of each of x's elements.
811 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws.
813 //! <b>Complexity</b>: Linear to the number of elements in x.
814 deque& operator= (BOOST_COPY_ASSIGN_REF(deque) x)
816 if (BOOST_LIKELY(&x != this)){
817 allocator_type &this_alloc = this->alloc();
818 const allocator_type &x_alloc = x.alloc();
819 dtl::bool_<allocator_traits_type::
820 propagate_on_container_copy_assignment::value> flag;
821 if(flag && this_alloc != x_alloc){
823 this->shrink_to_fit();
825 dtl::assign_alloc(this->alloc(), x.alloc(), flag);
826 dtl::assign_alloc(this->ptr_alloc(), x.ptr_alloc(), flag);
827 this->assign(x.cbegin(), x.cend());
832 //! <b>Effects</b>: Move assignment. All x's values are transferred to *this.
834 //! <b>Throws</b>: If allocator_traits_type::propagate_on_container_move_assignment
835 //! is false and (allocation throws or value_type's move constructor throws)
837 //! <b>Complexity</b>: Constant if allocator_traits_type::
838 //! propagate_on_container_move_assignment is true or
839 //! this->get>allocator() == x.get_allocator(). Linear otherwise.
840 deque& operator= (BOOST_RV_REF(deque) x)
841 BOOST_NOEXCEPT_IF(allocator_traits_type::propagate_on_container_move_assignment::value
842 || allocator_traits_type::is_always_equal::value)
844 if (BOOST_LIKELY(this != &x)) {
845 allocator_type &this_alloc = this->alloc();
846 allocator_type &x_alloc = x.alloc();
847 const bool propagate_alloc = allocator_traits_type::
848 propagate_on_container_move_assignment::value;
849 dtl::bool_<propagate_alloc> flag;
850 const bool allocators_equal = this_alloc == x_alloc; (void)allocators_equal;
851 //Resources can be transferred if both allocators are
852 //going to be equal after this function (either propagated or already equal)
853 if(propagate_alloc || allocators_equal){
854 //Destroy objects but retain memory in case x reuses it in the future
856 //Move allocator if needed
857 dtl::move_alloc(this_alloc, x_alloc, flag);
858 dtl::move_alloc(this->ptr_alloc(), x.ptr_alloc(), flag);
860 this->swap_members(x);
862 //Else do a one by one move
864 this->assign( boost::make_move_iterator(x.begin())
865 , boost::make_move_iterator(x.end()));
871 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
872 //! <b>Effects</b>: Makes *this contain the same elements as il.
874 //! <b>Postcondition</b>: this->size() == il.size(). *this contains a copy
875 //! of each of x's elements.
877 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws.
879 //! <b>Complexity</b>: Linear to the number of elements in il.
880 BOOST_CONTAINER_FORCEINLINE deque& operator=(std::initializer_list<value_type> il)
882 this->assign(il.begin(), il.end());
887 //! <b>Effects</b>: Assigns the n copies of val to *this.
889 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws.
891 //! <b>Complexity</b>: Linear to n.
892 BOOST_CONTAINER_FORCEINLINE void assign(size_type n, const T& val)
894 typedef constant_iterator<value_type, difference_type> c_it;
895 this->assign(c_it(val, n), c_it());
898 //! <b>Effects</b>: Assigns the the range [first, last) to *this.
900 //! <b>Throws</b>: If memory allocation throws or
901 //! T's constructor from dereferencing InIt throws.
903 //! <b>Complexity</b>: Linear to n.
904 template <class InIt>
905 void assign(InIt first, InIt last
906 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
907 , typename dtl::disable_if_or
909 , dtl::is_convertible<InIt, size_type>
910 , dtl::is_not_input_iterator<InIt>
915 iterator cur = this->begin();
916 for ( ; first != last && cur != end(); ++cur, ++first){
920 this->erase(cur, this->cend());
923 this->insert(this->cend(), first, last);
927 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
928 template <class FwdIt>
929 void assign(FwdIt first, FwdIt last
930 , typename dtl::disable_if_or
932 , dtl::is_convertible<FwdIt, size_type>
933 , dtl::is_input_iterator<FwdIt>
937 const size_type len = boost::container::iterator_distance(first, last);
940 boost::container::iterator_advance(mid, this->size());
941 boost::container::copy(first, mid, begin());
942 this->insert(this->cend(), mid, last);
945 this->erase(boost::container::copy(first, last, this->begin()), cend());
950 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
951 //! <b>Effects</b>: Assigns the the range [il.begin(), il.end()) to *this.
953 //! <b>Throws</b>: If memory allocation throws or
954 //! T's constructor from dereferencing std::initializer_list iterator throws.
956 //! <b>Complexity</b>: Linear to il.size().
957 BOOST_CONTAINER_FORCEINLINE void assign(std::initializer_list<value_type> il)
958 { this->assign(il.begin(), il.end()); }
961 //! <b>Effects</b>: Returns a copy of the internal allocator.
963 //! <b>Throws</b>: If allocator's copy constructor throws.
965 //! <b>Complexity</b>: Constant.
966 BOOST_CONTAINER_FORCEINLINE allocator_type get_allocator() const BOOST_NOEXCEPT_OR_NOTHROW
967 { return Base::alloc(); }
969 //! <b>Effects</b>: Returns a reference to the internal allocator.
971 //! <b>Throws</b>: Nothing
973 //! <b>Complexity</b>: Constant.
975 //! <b>Note</b>: Non-standard extension.
976 BOOST_CONTAINER_FORCEINLINE const stored_allocator_type &get_stored_allocator() const BOOST_NOEXCEPT_OR_NOTHROW
977 { return Base::alloc(); }
979 //////////////////////////////////////////////
983 //////////////////////////////////////////////
985 //! <b>Effects</b>: Returns a reference to the internal allocator.
987 //! <b>Throws</b>: Nothing
989 //! <b>Complexity</b>: Constant.
991 //! <b>Note</b>: Non-standard extension.
992 BOOST_CONTAINER_FORCEINLINE stored_allocator_type &get_stored_allocator() BOOST_NOEXCEPT_OR_NOTHROW
993 { return Base::alloc(); }
995 //! <b>Effects</b>: Returns an iterator to the first element contained in the deque.
997 //! <b>Throws</b>: Nothing.
999 //! <b>Complexity</b>: Constant.
1000 BOOST_CONTAINER_FORCEINLINE iterator begin() BOOST_NOEXCEPT_OR_NOTHROW
1001 { return this->members_.m_start; }
1003 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the deque.
1005 //! <b>Throws</b>: Nothing.
1007 //! <b>Complexity</b>: Constant.
1008 BOOST_CONTAINER_FORCEINLINE const_iterator begin() const BOOST_NOEXCEPT_OR_NOTHROW
1009 { return this->members_.m_start; }
1011 //! <b>Effects</b>: Returns an iterator to the end of the deque.
1013 //! <b>Throws</b>: Nothing.
1015 //! <b>Complexity</b>: Constant.
1016 BOOST_CONTAINER_FORCEINLINE iterator end() BOOST_NOEXCEPT_OR_NOTHROW
1017 { return this->members_.m_finish; }
1019 //! <b>Effects</b>: Returns a const_iterator to the end of the deque.
1021 //! <b>Throws</b>: Nothing.
1023 //! <b>Complexity</b>: Constant.
1024 BOOST_CONTAINER_FORCEINLINE const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW
1025 { return this->members_.m_finish; }
1027 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning
1028 //! of the reversed deque.
1030 //! <b>Throws</b>: Nothing.
1032 //! <b>Complexity</b>: Constant.
1033 BOOST_CONTAINER_FORCEINLINE reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW
1034 { return reverse_iterator(this->members_.m_finish); }
1036 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
1037 //! of the reversed deque.
1039 //! <b>Throws</b>: Nothing.
1041 //! <b>Complexity</b>: Constant.
1042 BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW
1043 { return const_reverse_iterator(this->members_.m_finish); }
1045 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
1046 //! of the reversed deque.
1048 //! <b>Throws</b>: Nothing.
1050 //! <b>Complexity</b>: Constant.
1051 BOOST_CONTAINER_FORCEINLINE reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW
1052 { return reverse_iterator(this->members_.m_start); }
1054 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
1055 //! of the reversed deque.
1057 //! <b>Throws</b>: Nothing.
1059 //! <b>Complexity</b>: Constant.
1060 BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW
1061 { return const_reverse_iterator(this->members_.m_start); }
1063 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the deque.
1065 //! <b>Throws</b>: Nothing.
1067 //! <b>Complexity</b>: Constant.
1068 BOOST_CONTAINER_FORCEINLINE const_iterator cbegin() const BOOST_NOEXCEPT_OR_NOTHROW
1069 { return this->members_.m_start; }
1071 //! <b>Effects</b>: Returns a const_iterator to the end of the deque.
1073 //! <b>Throws</b>: Nothing.
1075 //! <b>Complexity</b>: Constant.
1076 BOOST_CONTAINER_FORCEINLINE const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW
1077 { return this->members_.m_finish; }
1079 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
1080 //! of the reversed deque.
1082 //! <b>Throws</b>: Nothing.
1084 //! <b>Complexity</b>: Constant.
1085 BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW
1086 { return const_reverse_iterator(this->members_.m_finish); }
1088 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
1089 //! of the reversed deque.
1091 //! <b>Throws</b>: Nothing.
1093 //! <b>Complexity</b>: Constant.
1094 BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW
1095 { return const_reverse_iterator(this->members_.m_start); }
1097 //////////////////////////////////////////////
1101 //////////////////////////////////////////////
1103 //! <b>Effects</b>: Returns true if the deque contains no elements.
1105 //! <b>Throws</b>: Nothing.
1107 //! <b>Complexity</b>: Constant.
1108 BOOST_CONTAINER_FORCEINLINE bool empty() const BOOST_NOEXCEPT_OR_NOTHROW
1109 { return this->members_.m_finish == this->members_.m_start; }
1111 //! <b>Effects</b>: Returns the number of the elements contained in the deque.
1113 //! <b>Throws</b>: Nothing.
1115 //! <b>Complexity</b>: Constant.
1116 BOOST_CONTAINER_FORCEINLINE size_type size() const BOOST_NOEXCEPT_OR_NOTHROW
1117 { return this->members_.m_finish - this->members_.m_start; }
1119 //! <b>Effects</b>: Returns the largest possible size of the deque.
1121 //! <b>Throws</b>: Nothing.
1123 //! <b>Complexity</b>: Constant.
1124 BOOST_CONTAINER_FORCEINLINE size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW
1125 { return allocator_traits_type::max_size(this->alloc()); }
1127 //! <b>Effects</b>: Inserts or erases elements at the end such that
1128 //! the size becomes n. New elements are value initialized.
1130 //! <b>Throws</b>: If memory allocation throws, or T's constructor throws.
1132 //! <b>Complexity</b>: Linear to the difference between size() and new_size.
1133 void resize(size_type new_size)
1135 const size_type len = size();
1137 this->priv_erase_last_n(len - new_size);
1139 const size_type n = new_size - this->size();
1140 dtl::insert_value_initialized_n_proxy<ValAllocator, iterator> proxy;
1141 priv_insert_back_aux_impl(n, proxy);
1145 //! <b>Effects</b>: Inserts or erases elements at the end such that
1146 //! the size becomes n. New elements are default initialized.
1148 //! <b>Throws</b>: If memory allocation throws, or T's constructor throws.
1150 //! <b>Complexity</b>: Linear to the difference between size() and new_size.
1152 //! <b>Note</b>: Non-standard extension
1153 void resize(size_type new_size, default_init_t)
1155 const size_type len = size();
1157 this->priv_erase_last_n(len - new_size);
1159 const size_type n = new_size - this->size();
1160 dtl::insert_default_initialized_n_proxy<ValAllocator, iterator> proxy;
1161 priv_insert_back_aux_impl(n, proxy);
1165 //! <b>Effects</b>: Inserts or erases elements at the end such that
1166 //! the size becomes n. New elements are copy constructed from x.
1168 //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws.
1170 //! <b>Complexity</b>: Linear to the difference between size() and new_size.
1171 void resize(size_type new_size, const value_type& x)
1173 const size_type len = size();
1175 this->erase(this->members_.m_start + new_size, this->members_.m_finish);
1177 this->insert(this->members_.m_finish, new_size - len, x);
1180 //! <b>Effects</b>: Tries to deallocate the excess of memory created
1181 //! with previous allocations. The size of the deque is unchanged
1183 //! <b>Throws</b>: If memory allocation throws.
1185 //! <b>Complexity</b>: Constant.
1186 void shrink_to_fit()
1188 //This deque implementation already
1189 //deallocates excess nodes when erasing
1190 //so there is nothing to do except for
1193 this->priv_clear_map();
1197 //////////////////////////////////////////////
1201 //////////////////////////////////////////////
1203 //! <b>Requires</b>: !empty()
1205 //! <b>Effects</b>: Returns a reference to the first
1206 //! element of the container.
1208 //! <b>Throws</b>: Nothing.
1210 //! <b>Complexity</b>: Constant.
1211 BOOST_CONTAINER_FORCEINLINE reference front() BOOST_NOEXCEPT_OR_NOTHROW
1213 BOOST_ASSERT(!this->empty());
1214 return *this->members_.m_start;
1217 //! <b>Requires</b>: !empty()
1219 //! <b>Effects</b>: Returns a const reference to the first element
1220 //! from the beginning of the container.
1222 //! <b>Throws</b>: Nothing.
1224 //! <b>Complexity</b>: Constant.
1225 BOOST_CONTAINER_FORCEINLINE const_reference front() const BOOST_NOEXCEPT_OR_NOTHROW
1227 BOOST_ASSERT(!this->empty());
1228 return *this->members_.m_start;
1231 //! <b>Requires</b>: !empty()
1233 //! <b>Effects</b>: Returns a reference to the last
1234 //! element of the container.
1236 //! <b>Throws</b>: Nothing.
1238 //! <b>Complexity</b>: Constant.
1239 BOOST_CONTAINER_FORCEINLINE reference back() BOOST_NOEXCEPT_OR_NOTHROW
1241 BOOST_ASSERT(!this->empty());
1245 //! <b>Requires</b>: !empty()
1247 //! <b>Effects</b>: Returns a const reference to the last
1248 //! element of the container.
1250 //! <b>Throws</b>: Nothing.
1252 //! <b>Complexity</b>: Constant.
1253 BOOST_CONTAINER_FORCEINLINE const_reference back() const BOOST_NOEXCEPT_OR_NOTHROW
1255 BOOST_ASSERT(!this->empty());
1259 //! <b>Requires</b>: size() > n.
1261 //! <b>Effects</b>: Returns a reference to the nth element
1262 //! from the beginning of the container.
1264 //! <b>Throws</b>: Nothing.
1266 //! <b>Complexity</b>: Constant.
1267 BOOST_CONTAINER_FORCEINLINE reference operator[](size_type n) BOOST_NOEXCEPT_OR_NOTHROW
1269 BOOST_ASSERT(this->size() > n);
1270 return this->members_.m_start[difference_type(n)];
1273 //! <b>Requires</b>: size() > n.
1275 //! <b>Effects</b>: Returns a const reference to the nth element
1276 //! from the beginning of the container.
1278 //! <b>Throws</b>: Nothing.
1280 //! <b>Complexity</b>: Constant.
1281 BOOST_CONTAINER_FORCEINLINE const_reference operator[](size_type n) const BOOST_NOEXCEPT_OR_NOTHROW
1283 BOOST_ASSERT(this->size() > n);
1284 return this->members_.m_start[difference_type(n)];
1287 //! <b>Requires</b>: size() >= n.
1289 //! <b>Effects</b>: Returns an iterator to the nth element
1290 //! from the beginning of the container. Returns end()
1293 //! <b>Throws</b>: Nothing.
1295 //! <b>Complexity</b>: Constant.
1297 //! <b>Note</b>: Non-standard extension
1298 BOOST_CONTAINER_FORCEINLINE iterator nth(size_type n) BOOST_NOEXCEPT_OR_NOTHROW
1300 BOOST_ASSERT(this->size() >= n);
1301 return iterator(this->begin()+n);
1304 //! <b>Requires</b>: size() >= n.
1306 //! <b>Effects</b>: Returns a const_iterator to the nth element
1307 //! from the beginning of the container. Returns end()
1310 //! <b>Throws</b>: Nothing.
1312 //! <b>Complexity</b>: Constant.
1314 //! <b>Note</b>: Non-standard extension
1315 BOOST_CONTAINER_FORCEINLINE const_iterator nth(size_type n) const BOOST_NOEXCEPT_OR_NOTHROW
1317 BOOST_ASSERT(this->size() >= n);
1318 return const_iterator(this->cbegin()+n);
1321 //! <b>Requires</b>: begin() <= p <= end().
1323 //! <b>Effects</b>: Returns the index of the element pointed by p
1324 //! and size() if p == end().
1326 //! <b>Throws</b>: Nothing.
1328 //! <b>Complexity</b>: Constant.
1330 //! <b>Note</b>: Non-standard extension
1331 BOOST_CONTAINER_FORCEINLINE size_type index_of(iterator p) BOOST_NOEXCEPT_OR_NOTHROW
1333 //Range checked priv_index_of
1334 return this->priv_index_of(p);
1337 //! <b>Requires</b>: begin() <= p <= end().
1339 //! <b>Effects</b>: Returns the index of the element pointed by p
1340 //! and size() if p == end().
1342 //! <b>Throws</b>: Nothing.
1344 //! <b>Complexity</b>: Constant.
1346 //! <b>Note</b>: Non-standard extension
1347 BOOST_CONTAINER_FORCEINLINE size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW
1349 //Range checked priv_index_of
1350 return this->priv_index_of(p);
1353 //! <b>Requires</b>: size() > n.
1355 //! <b>Effects</b>: Returns a reference to the nth element
1356 //! from the beginning of the container.
1358 //! <b>Throws</b>: std::range_error if n >= size()
1360 //! <b>Complexity</b>: Constant.
1361 BOOST_CONTAINER_FORCEINLINE reference at(size_type n)
1363 this->priv_throw_if_out_of_range(n);
1367 //! <b>Requires</b>: size() > n.
1369 //! <b>Effects</b>: Returns a const reference to the nth element
1370 //! from the beginning of the container.
1372 //! <b>Throws</b>: std::range_error if n >= size()
1374 //! <b>Complexity</b>: Constant.
1375 BOOST_CONTAINER_FORCEINLINE const_reference at(size_type n) const
1377 this->priv_throw_if_out_of_range(n);
1381 //////////////////////////////////////////////
1385 //////////////////////////////////////////////
1387 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1389 //! <b>Effects</b>: Inserts an object of type T constructed with
1390 //! std::forward<Args>(args)... in the beginning of the deque.
1392 //! <b>Returns</b>: A reference to the created object.
1394 //! <b>Throws</b>: If memory allocation throws or the in-place constructor throws.
1396 //! <b>Complexity</b>: Amortized constant time
1397 template <class... Args>
1398 reference emplace_front(BOOST_FWD_REF(Args)... args)
1400 if(this->priv_push_front_simple_available()){
1401 reference r = *this->priv_push_front_simple_pos();
1402 allocator_traits_type::construct
1404 , this->priv_push_front_simple_pos()
1405 , boost::forward<Args>(args)...);
1406 this->priv_push_front_simple_commit();
1410 typedef dtl::insert_nonmovable_emplace_proxy<ValAllocator, iterator, Args...> type;
1411 return *this->priv_insert_front_aux_impl(1, type(boost::forward<Args>(args)...));
1415 //! <b>Effects</b>: Inserts an object of type T constructed with
1416 //! std::forward<Args>(args)... in the end of the deque.
1418 //! <b>Returns</b>: A reference to the created object.
1420 //! <b>Throws</b>: If memory allocation throws or the in-place constructor throws.
1422 //! <b>Complexity</b>: Amortized constant time
1423 template <class... Args>
1424 reference emplace_back(BOOST_FWD_REF(Args)... args)
1426 if(this->priv_push_back_simple_available()){
1427 reference r = *this->priv_push_back_simple_pos();
1428 allocator_traits_type::construct
1430 , this->priv_push_back_simple_pos()
1431 , boost::forward<Args>(args)...);
1432 this->priv_push_back_simple_commit();
1436 typedef dtl::insert_nonmovable_emplace_proxy<ValAllocator, iterator, Args...> type;
1437 return *this->priv_insert_back_aux_impl(1, type(boost::forward<Args>(args)...));
1441 //! <b>Requires</b>: p must be a valid iterator of *this.
1443 //! <b>Effects</b>: Inserts an object of type T constructed with
1444 //! std::forward<Args>(args)... before p
1446 //! <b>Throws</b>: If memory allocation throws or the in-place constructor throws.
1448 //! <b>Complexity</b>: If p is end(), amortized constant time
1449 //! Linear time otherwise.
1450 template <class... Args>
1451 iterator emplace(const_iterator p, BOOST_FWD_REF(Args)... args)
1453 BOOST_ASSERT(this->priv_in_range_or_end(p));
1454 if(p == this->cbegin()){
1455 this->emplace_front(boost::forward<Args>(args)...);
1456 return this->begin();
1458 else if(p == this->cend()){
1459 this->emplace_back(boost::forward<Args>(args)...);
1460 return (this->end()-1);
1463 typedef dtl::insert_emplace_proxy<ValAllocator, iterator, Args...> type;
1464 return this->priv_insert_aux_impl(p, 1, type(boost::forward<Args>(args)...));
1468 #else //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1470 #define BOOST_CONTAINER_DEQUE_EMPLACE_CODE(N) \
1471 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N\
1472 reference emplace_front(BOOST_MOVE_UREF##N)\
1474 if(priv_push_front_simple_available()){\
1475 reference r = *this->priv_push_front_simple_pos();\
1476 allocator_traits_type::construct\
1477 ( this->alloc(), this->priv_push_front_simple_pos() BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
1478 priv_push_front_simple_commit();\
1482 typedef dtl::insert_nonmovable_emplace_proxy##N\
1483 <ValAllocator, iterator BOOST_MOVE_I##N BOOST_MOVE_TARG##N> type;\
1484 return *priv_insert_front_aux_impl(1, type(BOOST_MOVE_FWD##N));\
1488 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N\
1489 reference emplace_back(BOOST_MOVE_UREF##N)\
1491 if(priv_push_back_simple_available()){\
1492 reference r = *this->priv_push_back_simple_pos();\
1493 allocator_traits_type::construct\
1494 ( this->alloc(), this->priv_push_back_simple_pos() BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
1495 priv_push_back_simple_commit();\
1499 typedef dtl::insert_nonmovable_emplace_proxy##N\
1500 <ValAllocator, iterator BOOST_MOVE_I##N BOOST_MOVE_TARG##N> type;\
1501 return *priv_insert_back_aux_impl(1, type(BOOST_MOVE_FWD##N));\
1505 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N\
1506 iterator emplace(const_iterator p BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
1508 BOOST_ASSERT(this->priv_in_range_or_end(p));\
1509 if(p == this->cbegin()){\
1510 this->emplace_front(BOOST_MOVE_FWD##N);\
1511 return this->begin();\
1513 else if(p == cend()){\
1514 this->emplace_back(BOOST_MOVE_FWD##N);\
1515 return (--this->end());\
1518 typedef dtl::insert_emplace_proxy_arg##N\
1519 <ValAllocator, iterator BOOST_MOVE_I##N BOOST_MOVE_TARG##N> type;\
1520 return this->priv_insert_aux_impl(p, 1, type(BOOST_MOVE_FWD##N));\
1524 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_DEQUE_EMPLACE_CODE)
1525 #undef BOOST_CONTAINER_DEQUE_EMPLACE_CODE
1527 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1529 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1530 //! <b>Effects</b>: Inserts a copy of x at the front of the deque.
1532 //! <b>Throws</b>: If memory allocation throws or
1533 //! T's copy constructor throws.
1535 //! <b>Complexity</b>: Amortized constant time.
1536 void push_front(const T &x);
1538 //! <b>Effects</b>: Constructs a new element in the front of the deque
1539 //! and moves the resources of x to this new element.
1541 //! <b>Throws</b>: If memory allocation throws.
1543 //! <b>Complexity</b>: Amortized constant time.
1544 void push_front(T &&x);
1546 BOOST_MOVE_CONVERSION_AWARE_CATCH(push_front, T, void, priv_push_front)
1549 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1550 //! <b>Effects</b>: Inserts a copy of x at the end of the deque.
1552 //! <b>Throws</b>: If memory allocation throws or
1553 //! T's copy constructor throws.
1555 //! <b>Complexity</b>: Amortized constant time.
1556 void push_back(const T &x);
1558 //! <b>Effects</b>: Constructs a new element in the end of the deque
1559 //! and moves the resources of x to this new element.
1561 //! <b>Throws</b>: If memory allocation throws.
1563 //! <b>Complexity</b>: Amortized constant time.
1564 void push_back(T &&x);
1566 BOOST_MOVE_CONVERSION_AWARE_CATCH(push_back, T, void, priv_push_back)
1569 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1571 //! <b>Requires</b>: p must be a valid iterator of *this.
1573 //! <b>Effects</b>: Insert a copy of x before p.
1575 //! <b>Returns</b>: an iterator to the inserted element.
1577 //! <b>Throws</b>: If memory allocation throws or x's copy constructor throws.
1579 //! <b>Complexity</b>: If p is end(), amortized constant time
1580 //! Linear time otherwise.
1581 iterator insert(const_iterator p, const T &x);
1583 //! <b>Requires</b>: p must be a valid iterator of *this.
1585 //! <b>Effects</b>: Insert a new element before p with x's resources.
1587 //! <b>Returns</b>: an iterator to the inserted element.
1589 //! <b>Throws</b>: If memory allocation throws.
1591 //! <b>Complexity</b>: If p is end(), amortized constant time
1592 //! Linear time otherwise.
1593 iterator insert(const_iterator p, T &&x);
1595 BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, T, iterator, priv_insert, const_iterator, const_iterator)
1598 //! <b>Requires</b>: pos must be a valid iterator of *this.
1600 //! <b>Effects</b>: Insert n copies of x before pos.
1602 //! <b>Returns</b>: an iterator to the first inserted element or pos if n is 0.
1604 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws.
1606 //! <b>Complexity</b>: Linear to n.
1607 BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator pos, size_type n, const value_type& x)
1609 //Range check of p is done by insert()
1610 typedef constant_iterator<value_type, difference_type> c_it;
1611 return this->insert(pos, c_it(x, n), c_it());
1614 //! <b>Requires</b>: pos must be a valid iterator of *this.
1616 //! <b>Effects</b>: Insert a copy of the [first, last) range before pos.
1618 //! <b>Returns</b>: an iterator to the first inserted element or pos if first == last.
1620 //! <b>Throws</b>: If memory allocation throws, T's constructor from a
1621 //! dereferenced InIt throws or T's copy constructor throws.
1623 //! <b>Complexity</b>: Linear to distance [first, last).
1624 template <class InIt>
1625 iterator insert(const_iterator pos, InIt first, InIt last
1626 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1627 , typename dtl::disable_if_or
1629 , dtl::is_convertible<InIt, size_type>
1630 , dtl::is_not_input_iterator<InIt>
1635 BOOST_ASSERT(this->priv_in_range_or_end(pos));
1637 iterator it(pos.unconst());
1638 for(;first != last; ++first, ++n){
1639 it = this->emplace(it, *first);
1646 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1647 //! <b>Requires</b>: pos must be a valid iterator of *this.
1649 //! <b>Effects</b>: Insert a copy of the [il.begin(), il.end()) range before pos.
1651 //! <b>Returns</b>: an iterator to the first inserted element or pos if il.begin() == il.end().
1653 //! <b>Throws</b>: If memory allocation throws, T's constructor from a
1654 //! dereferenced std::initializer_list throws or T's copy constructor throws.
1656 //! <b>Complexity</b>: Linear to distance [il.begin(), il.end()).
1657 BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator pos, std::initializer_list<value_type> il)
1659 //Range check os pos is done in insert()
1660 return insert(pos, il.begin(), il.end());
1664 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1665 template <class FwdIt>
1666 BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, FwdIt first, FwdIt last
1667 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1668 , typename dtl::disable_if_or
1670 , dtl::is_convertible<FwdIt, size_type>
1671 , dtl::is_input_iterator<FwdIt>
1676 BOOST_ASSERT(this->priv_in_range_or_end(p));
1677 dtl::insert_range_proxy<ValAllocator, FwdIt, iterator> proxy(first);
1678 return priv_insert_aux_impl(p, boost::container::iterator_distance(first, last), proxy);
1682 //! <b>Effects</b>: Removes the first element from the deque.
1684 //! <b>Throws</b>: Nothing.
1686 //! <b>Complexity</b>: Constant time.
1687 void pop_front() BOOST_NOEXCEPT_OR_NOTHROW
1689 BOOST_ASSERT(!this->empty());
1690 if (this->members_.m_start.m_cur != this->members_.m_start.m_last - 1) {
1691 allocator_traits_type::destroy
1693 , boost::movelib::to_raw_pointer(this->members_.m_start.m_cur)
1695 ++this->members_.m_start.m_cur;
1698 this->priv_pop_front_aux();
1701 //! <b>Effects</b>: Removes the last element from the deque.
1703 //! <b>Throws</b>: Nothing.
1705 //! <b>Complexity</b>: Constant time.
1706 void pop_back() BOOST_NOEXCEPT_OR_NOTHROW
1708 BOOST_ASSERT(!this->empty());
1709 if (this->members_.m_finish.m_cur != this->members_.m_finish.m_first) {
1710 --this->members_.m_finish.m_cur;
1711 allocator_traits_type::destroy
1713 , boost::movelib::to_raw_pointer(this->members_.m_finish.m_cur)
1717 this->priv_pop_back_aux();
1720 //! <b>Effects</b>: Erases the element at p.
1722 //! <b>Throws</b>: Nothing.
1724 //! <b>Complexity</b>: Linear to the elements between pos and the
1725 //! last element (if pos is near the end) or the first element
1726 //! if(pos is near the beginning).
1727 //! Constant if pos is the first or the last element.
1728 iterator erase(const_iterator pos) BOOST_NOEXCEPT_OR_NOTHROW
1730 BOOST_ASSERT(this->priv_in_range(pos));
1731 iterator next = pos.unconst();
1733 size_type index = pos - this->members_.m_start;
1734 if (index < (this->size()/2)) {
1735 boost::container::move_backward(this->begin(), pos.unconst(), next);
1739 boost::container::move(next, this->end(), pos.unconst());
1742 return this->members_.m_start + index;
1745 //! <b>Effects</b>: Erases the elements pointed by [first, last).
1747 //! <b>Throws</b>: Nothing.
1749 //! <b>Complexity</b>: Linear to the distance between first and
1750 //! last plus the elements between pos and the
1751 //! last element (if pos is near the end) or the first element
1752 //! if(pos is near the beginning).
1753 iterator erase(const_iterator first, const_iterator last) BOOST_NOEXCEPT_OR_NOTHROW
1755 BOOST_ASSERT(first == last ||
1756 (first < last && this->priv_in_range(first) && this->priv_in_range_or_end(last)));
1757 if (first == this->members_.m_start && last == this->members_.m_finish) {
1759 return this->members_.m_finish;
1762 const size_type n = static_cast<size_type>(last - first);
1763 const size_type elems_before = static_cast<size_type>(first - this->members_.m_start);
1764 if (elems_before < (this->size() - n) - elems_before) {
1765 boost::container::move_backward(begin(), first.unconst(), last.unconst());
1766 iterator new_start = this->members_.m_start + n;
1767 this->priv_destroy_range(this->members_.m_start, new_start);
1768 this->priv_destroy_nodes(this->members_.m_start.m_node, new_start.m_node);
1769 this->members_.m_start = new_start;
1772 boost::container::move(last.unconst(), end(), first.unconst());
1773 iterator new_finish = this->members_.m_finish - n;
1774 this->priv_destroy_range(new_finish, this->members_.m_finish);
1775 this->priv_destroy_nodes(new_finish.m_node + 1, this->members_.m_finish.m_node + 1);
1776 this->members_.m_finish = new_finish;
1778 return this->members_.m_start + elems_before;
1782 //! <b>Effects</b>: Swaps the contents of *this and x.
1784 //! <b>Throws</b>: Nothing.
1786 //! <b>Complexity</b>: Constant.
1787 BOOST_CONTAINER_FORCEINLINE void swap(deque &x)
1788 BOOST_NOEXCEPT_IF(allocator_traits_type::propagate_on_container_swap::value
1789 || allocator_traits_type::is_always_equal::value)
1791 this->swap_members(x);
1792 dtl::bool_<allocator_traits_type::propagate_on_container_swap::value> flag;
1793 dtl::swap_alloc(this->alloc(), x.alloc(), flag);
1794 dtl::swap_alloc(this->ptr_alloc(), x.ptr_alloc(), flag);
1797 //! <b>Effects</b>: Erases all the elements of the deque.
1799 //! <b>Throws</b>: Nothing.
1801 //! <b>Complexity</b>: Linear to the number of elements in the deque.
1802 void clear() BOOST_NOEXCEPT_OR_NOTHROW
1804 for (index_pointer node = this->members_.m_start.m_node + 1;
1805 node < this->members_.m_finish.m_node;
1807 this->priv_destroy_range(*node, *node + get_block_size());
1808 this->priv_deallocate_node(*node);
1811 if (this->members_.m_start.m_node != this->members_.m_finish.m_node) {
1812 this->priv_destroy_range(this->members_.m_start.m_cur, this->members_.m_start.m_last);
1813 this->priv_destroy_range(this->members_.m_finish.m_first, this->members_.m_finish.m_cur);
1814 this->priv_deallocate_node(this->members_.m_finish.m_first);
1817 this->priv_destroy_range(this->members_.m_start.m_cur, this->members_.m_finish.m_cur);
1819 this->members_.m_finish = this->members_.m_start;
1822 //! <b>Effects</b>: Returns true if x and y are equal
1824 //! <b>Complexity</b>: Linear to the number of elements in the container.
1825 BOOST_CONTAINER_FORCEINLINE friend bool operator==(const deque& x, const deque& y)
1826 { return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin()); }
1828 //! <b>Effects</b>: Returns true if x and y are unequal
1830 //! <b>Complexity</b>: Linear to the number of elements in the container.
1831 BOOST_CONTAINER_FORCEINLINE friend bool operator!=(const deque& x, const deque& y)
1832 { return !(x == y); }
1834 //! <b>Effects</b>: Returns true if x is less than y
1836 //! <b>Complexity</b>: Linear to the number of elements in the container.
1837 BOOST_CONTAINER_FORCEINLINE friend bool operator<(const deque& x, const deque& y)
1838 { return ::boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); }
1840 //! <b>Effects</b>: Returns true if x is greater than y
1842 //! <b>Complexity</b>: Linear to the number of elements in the container.
1843 BOOST_CONTAINER_FORCEINLINE friend bool operator>(const deque& x, const deque& y)
1846 //! <b>Effects</b>: Returns true if x is equal or less than y
1848 //! <b>Complexity</b>: Linear to the number of elements in the container.
1849 BOOST_CONTAINER_FORCEINLINE friend bool operator<=(const deque& x, const deque& y)
1850 { return !(y < x); }
1852 //! <b>Effects</b>: Returns true if x is equal or greater than y
1854 //! <b>Complexity</b>: Linear to the number of elements in the container.
1855 BOOST_CONTAINER_FORCEINLINE friend bool operator>=(const deque& x, const deque& y)
1856 { return !(x < y); }
1858 //! <b>Effects</b>: x.swap(y)
1860 //! <b>Complexity</b>: Constant.
1861 BOOST_CONTAINER_FORCEINLINE friend void swap(deque& x, deque& y)
1864 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1867 BOOST_CONTAINER_FORCEINLINE size_type priv_index_of(const_iterator p) const
1869 BOOST_ASSERT(this->cbegin() <= p);
1870 BOOST_ASSERT(p <= this->cend());
1871 return static_cast<size_type>(p - this->cbegin());
1874 void priv_erase_last_n(size_type n)
1876 if(n == this->size()) {
1880 iterator new_finish = this->members_.m_finish - n;
1881 this->priv_destroy_range(new_finish, this->members_.m_finish);
1882 this->priv_destroy_nodes(new_finish.m_node + 1, this->members_.m_finish.m_node + 1);
1883 this->members_.m_finish = new_finish;
1887 void priv_throw_if_out_of_range(size_type n) const
1889 if (n >= this->size())
1890 throw_out_of_range("deque::at out of range");
1893 BOOST_CONTAINER_FORCEINLINE bool priv_in_range(const_iterator pos) const
1895 return (this->begin() <= pos) && (pos < this->end());
1898 BOOST_CONTAINER_FORCEINLINE bool priv_in_range_or_end(const_iterator pos) const
1900 return (this->begin() <= pos) && (pos <= this->end());
1904 iterator priv_insert(const_iterator p, BOOST_FWD_REF(U) x)
1906 BOOST_ASSERT(this->priv_in_range_or_end(p));
1908 this->push_front(::boost::forward<U>(x));
1911 else if (p == cend()){
1912 this->push_back(::boost::forward<U>(x));
1916 return priv_insert_aux_impl
1918 , dtl::get_insert_value_proxy<iterator, ValAllocator>(::boost::forward<U>(x)));
1923 void priv_push_front(BOOST_FWD_REF(U) x)
1925 if(this->priv_push_front_simple_available()){
1926 allocator_traits_type::construct
1927 ( this->alloc(), this->priv_push_front_simple_pos(), ::boost::forward<U>(x));
1928 this->priv_push_front_simple_commit();
1931 priv_insert_aux_impl
1932 ( this->cbegin(), (size_type)1
1933 , dtl::get_insert_value_proxy<iterator, ValAllocator>(::boost::forward<U>(x)));
1938 void priv_push_back(BOOST_FWD_REF(U) x)
1940 if(this->priv_push_back_simple_available()){
1941 allocator_traits_type::construct
1942 ( this->alloc(), this->priv_push_back_simple_pos(), ::boost::forward<U>(x));
1943 this->priv_push_back_simple_commit();
1946 priv_insert_aux_impl
1947 ( this->cend(), (size_type)1
1948 , dtl::get_insert_value_proxy<iterator, ValAllocator>(::boost::forward<U>(x)));
1952 BOOST_CONTAINER_FORCEINLINE bool priv_push_back_simple_available() const
1954 return this->members_.m_map &&
1955 (this->members_.m_finish.m_cur != (this->members_.m_finish.m_last - 1));
1958 BOOST_CONTAINER_FORCEINLINE T *priv_push_back_simple_pos() const
1960 return boost::movelib::to_raw_pointer(this->members_.m_finish.m_cur);
1963 BOOST_CONTAINER_FORCEINLINE void priv_push_back_simple_commit()
1965 ++this->members_.m_finish.m_cur;
1968 BOOST_CONTAINER_FORCEINLINE bool priv_push_front_simple_available() const
1970 return this->members_.m_map &&
1971 (this->members_.m_start.m_cur != this->members_.m_start.m_first);
1974 BOOST_CONTAINER_FORCEINLINE T *priv_push_front_simple_pos() const
1975 { return boost::movelib::to_raw_pointer(this->members_.m_start.m_cur) - 1; }
1977 BOOST_CONTAINER_FORCEINLINE void priv_push_front_simple_commit()
1978 { --this->members_.m_start.m_cur; }
1980 void priv_destroy_range(iterator p, iterator p2)
1982 if(!Base::traits_t::trivial_dctr){
1984 allocator_traits_type::destroy(this->alloc(), boost::movelib::iterator_to_raw_pointer(p));
1989 void priv_destroy_range(pointer p, pointer p2)
1991 if(!Base::traits_t::trivial_dctr){
1993 allocator_traits_type::destroy(this->alloc(), boost::movelib::iterator_to_raw_pointer(p));
1998 template<class InsertProxy>
1999 iterator priv_insert_aux_impl(const_iterator p, size_type n, InsertProxy proxy)
2001 iterator pos(p.unconst());
2002 const size_type pos_n = p - this->cbegin();
2003 if(!this->members_.m_map){
2004 this->priv_initialize_map(0);
2005 pos = this->begin();
2008 const size_type elemsbefore = static_cast<size_type>(pos - this->members_.m_start);
2009 const size_type length = this->size();
2010 if (elemsbefore < length / 2) {
2011 const iterator new_start = this->priv_reserve_elements_at_front(n);
2012 const iterator old_start = this->members_.m_start;
2014 proxy.uninitialized_copy_n_and_update(this->alloc(), new_start, n);
2015 this->members_.m_start = new_start;
2018 pos = this->members_.m_start + elemsbefore;
2019 if (elemsbefore >= n) {
2020 const iterator start_n = this->members_.m_start + n;
2021 ::boost::container::uninitialized_move_alloc
2022 (this->alloc(), this->members_.m_start, start_n, new_start);
2023 this->members_.m_start = new_start;
2024 boost::container::move(start_n, pos, old_start);
2025 proxy.copy_n_and_update(this->alloc(), pos - n, n);
2028 const size_type mid_count = n - elemsbefore;
2029 const iterator mid_start = old_start - mid_count;
2030 proxy.uninitialized_copy_n_and_update(this->alloc(), mid_start, mid_count);
2031 this->members_.m_start = mid_start;
2032 ::boost::container::uninitialized_move_alloc
2033 (this->alloc(), old_start, pos, new_start);
2034 this->members_.m_start = new_start;
2035 proxy.copy_n_and_update(this->alloc(), old_start, elemsbefore);
2040 const iterator new_finish = this->priv_reserve_elements_at_back(n);
2041 const iterator old_finish = this->members_.m_finish;
2042 const size_type elemsafter = length - elemsbefore;
2044 proxy.uninitialized_copy_n_and_update(this->alloc(), old_finish, n);
2045 this->members_.m_finish = new_finish;
2048 pos = old_finish - elemsafter;
2049 if (elemsafter >= n) {
2050 iterator finish_n = old_finish - difference_type(n);
2051 ::boost::container::uninitialized_move_alloc
2052 (this->alloc(), finish_n, old_finish, old_finish);
2053 this->members_.m_finish = new_finish;
2054 boost::container::move_backward(pos, finish_n, old_finish);
2055 proxy.copy_n_and_update(this->alloc(), pos, n);
2058 const size_type raw_gap = n - elemsafter;
2059 ::boost::container::uninitialized_move_alloc
2060 (this->alloc(), pos, old_finish, old_finish + raw_gap);
2062 proxy.copy_n_and_update(this->alloc(), pos, elemsafter);
2063 proxy.uninitialized_copy_n_and_update(this->alloc(), old_finish, raw_gap);
2066 this->priv_destroy_range(old_finish, old_finish + elemsafter);
2070 this->members_.m_finish = new_finish;
2074 return this->begin() + pos_n;
2077 template <class InsertProxy>
2078 iterator priv_insert_back_aux_impl(size_type n, InsertProxy proxy)
2080 if(!this->members_.m_map){
2081 this->priv_initialize_map(0);
2084 iterator new_finish = this->priv_reserve_elements_at_back(n);
2085 iterator old_finish = this->members_.m_finish;
2086 proxy.uninitialized_copy_n_and_update(this->alloc(), old_finish, n);
2087 this->members_.m_finish = new_finish;
2088 return iterator(this->members_.m_finish - n);
2091 template <class InsertProxy>
2092 iterator priv_insert_front_aux_impl(size_type n, InsertProxy proxy)
2094 if(!this->members_.m_map){
2095 this->priv_initialize_map(0);
2098 iterator new_start = this->priv_reserve_elements_at_front(n);
2099 proxy.uninitialized_copy_n_and_update(this->alloc(), new_start, n);
2100 this->members_.m_start = new_start;
2104 BOOST_CONTAINER_FORCEINLINE iterator priv_fill_insert(const_iterator pos, size_type n, const value_type& x)
2106 typedef constant_iterator<value_type, difference_type> c_it;
2107 return this->insert(pos, c_it(x, n), c_it());
2110 // Precondition: this->members_.m_start and this->members_.m_finish have already been initialized,
2111 // but none of the deque's elements have yet been constructed.
2112 void priv_fill_initialize(const value_type& value)
2114 index_pointer cur = this->members_.m_start.m_node;
2116 for ( ; cur < this->members_.m_finish.m_node; ++cur){
2117 boost::container::uninitialized_fill_alloc
2118 (this->alloc(), *cur, *cur + get_block_size(), value);
2120 boost::container::uninitialized_fill_alloc
2121 (this->alloc(), this->members_.m_finish.m_first, this->members_.m_finish.m_cur, value);
2124 this->priv_destroy_range(this->members_.m_start, iterator(*cur, cur, get_block_size()));
2130 template <class InIt>
2131 void priv_range_initialize(InIt first, InIt last, typename iterator_enable_if_tag<InIt, std::input_iterator_tag>::type* =0)
2133 this->priv_initialize_map(0);
2135 for ( ; first != last; ++first)
2136 this->emplace_back(*first);
2145 template <class FwdIt>
2146 void priv_range_initialize(FwdIt first, FwdIt last, typename iterator_disable_if_tag<FwdIt, std::input_iterator_tag>::type* =0)
2149 n = boost::container::iterator_distance(first, last);
2150 this->priv_initialize_map(n);
2152 index_pointer cur_node = this->members_.m_start.m_node;
2154 for (; cur_node < this->members_.m_finish.m_node; ++cur_node) {
2156 boost::container::iterator_advance(mid, get_block_size());
2157 ::boost::container::uninitialized_copy_alloc(this->alloc(), first, mid, *cur_node);
2160 ::boost::container::uninitialized_copy_alloc(this->alloc(), first, last, this->members_.m_finish.m_first);
2163 this->priv_destroy_range(this->members_.m_start, iterator(*cur_node, cur_node, get_block_size()));
2169 // Called only if this->members_.m_finish.m_cur == this->members_.m_finish.m_first.
2170 void priv_pop_back_aux() BOOST_NOEXCEPT_OR_NOTHROW
2172 this->priv_deallocate_node(this->members_.m_finish.m_first);
2173 this->members_.m_finish.priv_set_node(this->members_.m_finish.m_node - 1, get_block_size());
2174 this->members_.m_finish.m_cur = this->members_.m_finish.m_last - 1;
2175 allocator_traits_type::destroy
2177 , boost::movelib::to_raw_pointer(this->members_.m_finish.m_cur)
2181 // Called only if this->members_.m_start.m_cur == this->members_.m_start.m_last - 1. Note that
2182 // if the deque has at least one element (a precondition for this member
2183 // function), and if this->members_.m_start.m_cur == this->members_.m_start.m_last, then the deque
2184 // must have at least two nodes.
2185 void priv_pop_front_aux() BOOST_NOEXCEPT_OR_NOTHROW
2187 allocator_traits_type::destroy
2189 , boost::movelib::to_raw_pointer(this->members_.m_start.m_cur)
2191 this->priv_deallocate_node(this->members_.m_start.m_first);
2192 this->members_.m_start.priv_set_node(this->members_.m_start.m_node + 1, get_block_size());
2193 this->members_.m_start.m_cur = this->members_.m_start.m_first;
2196 iterator priv_reserve_elements_at_front(size_type n)
2198 size_type vacancies = this->members_.m_start.m_cur - this->members_.m_start.m_first;
2200 size_type new_elems = n-vacancies;
2201 size_type new_nodes = (new_elems + get_block_size() - 1) /
2203 size_type s = (size_type)(this->members_.m_start.m_node - this->members_.m_map);
2205 this->priv_reallocate_map(new_nodes, true);
2209 for (; i <= new_nodes; ++i)
2210 *(this->members_.m_start.m_node - i) = this->priv_allocate_node();
2213 for (size_type j = 1; j < i; ++j)
2214 this->priv_deallocate_node(*(this->members_.m_start.m_node - j));
2219 return this->members_.m_start - difference_type(n);
2222 iterator priv_reserve_elements_at_back(size_type n)
2224 size_type vacancies = (this->members_.m_finish.m_last - this->members_.m_finish.m_cur) - 1;
2226 size_type new_elems = n - vacancies;
2227 size_type new_nodes = (new_elems + get_block_size() - 1)/get_block_size();
2228 size_type s = (size_type)(this->members_.m_map_size - (this->members_.m_finish.m_node - this->members_.m_map));
2229 if (new_nodes + 1 > s){
2230 this->priv_reallocate_map(new_nodes, false);
2234 for (; i <= new_nodes; ++i)
2235 *(this->members_.m_finish.m_node + i) = this->priv_allocate_node();
2238 for (size_type j = 1; j < i; ++j)
2239 this->priv_deallocate_node(*(this->members_.m_finish.m_node + j));
2244 return this->members_.m_finish + difference_type(n);
2247 void priv_reallocate_map(size_type nodes_to_add, bool add_at_front)
2249 size_type old_num_nodes = this->members_.m_finish.m_node - this->members_.m_start.m_node + 1;
2250 size_type new_num_nodes = old_num_nodes + nodes_to_add;
2252 index_pointer new_nstart;
2253 if (this->members_.m_map_size > 2 * new_num_nodes) {
2254 new_nstart = this->members_.m_map + (this->members_.m_map_size - new_num_nodes) / 2
2255 + (add_at_front ? nodes_to_add : 0);
2256 if (new_nstart < this->members_.m_start.m_node)
2257 boost::container::move(this->members_.m_start.m_node, this->members_.m_finish.m_node + 1, new_nstart);
2259 boost::container::move_backward
2260 (this->members_.m_start.m_node, this->members_.m_finish.m_node + 1, new_nstart + old_num_nodes);
2263 size_type new_map_size =
2264 this->members_.m_map_size + dtl::max_value(this->members_.m_map_size, nodes_to_add) + 2;
2266 index_pointer new_map = this->priv_allocate_map(new_map_size);
2267 new_nstart = new_map + (new_map_size - new_num_nodes) / 2
2268 + (add_at_front ? nodes_to_add : 0);
2269 boost::container::move(this->members_.m_start.m_node, this->members_.m_finish.m_node + 1, new_nstart);
2270 this->priv_deallocate_map(this->members_.m_map, this->members_.m_map_size);
2272 this->members_.m_map = new_map;
2273 this->members_.m_map_size = new_map_size;
2276 this->members_.m_start.priv_set_node(new_nstart, get_block_size());
2277 this->members_.m_finish.priv_set_node(new_nstart + old_num_nodes - 1, get_block_size());
2279 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
2282 #ifndef BOOST_CONTAINER_NO_CXX17_CTAD
2283 template <typename InputIterator>
2284 deque(InputIterator, InputIterator) -> deque<typename iterator_traits<InputIterator>::value_type>;
2285 template <typename InputIterator, typename Allocator>
2286 deque(InputIterator, InputIterator, Allocator const&) -> deque<typename iterator_traits<InputIterator>::value_type, Allocator>;
2291 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
2295 //!has_trivial_destructor_after_move<> == true_type
2296 //!specialization for optimizations
2297 template <class T, class Allocator, class Options>
2298 struct has_trivial_destructor_after_move<boost::container::deque<T, Allocator, Options> >
2300 typedef typename boost::container::deque<T, Allocator, Options>::allocator_type allocator_type;
2301 typedef typename ::boost::container::allocator_traits<allocator_type>::pointer pointer;
2302 static const bool value = ::boost::has_trivial_destructor_after_move<allocator_type>::value &&
2303 ::boost::has_trivial_destructor_after_move<pointer>::value;
2308 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
2310 #include <boost/container/detail/config_end.hpp>
2312 #endif // #ifndef BOOST_CONTAINER_DEQUE_HPP