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
237 BOOST_ASSERT(!!m_cur);
238 difference_type offset = n + (this->m_cur - this->m_first);
239 const difference_type block_size = this->m_last - this->m_first;
240 BOOST_ASSERT(block_size);
241 if (offset >= 0 && offset < block_size)
244 difference_type node_offset =
245 offset > 0 ? (offset / block_size)
246 : (-difference_type((-offset - 1) / block_size) - 1);
247 this->priv_set_node(this->m_node + node_offset, block_size);
248 this->m_cur = this->m_first +
249 (offset - node_offset * block_size);
254 BOOST_CONTAINER_FORCEINLINE deque_iterator operator+(difference_type n) const BOOST_NOEXCEPT_OR_NOTHROW
255 { deque_iterator tmp(*this); return tmp += n; }
257 BOOST_CONTAINER_FORCEINLINE deque_iterator& operator-=(difference_type n) BOOST_NOEXCEPT_OR_NOTHROW
258 { return *this += -n; }
260 BOOST_CONTAINER_FORCEINLINE deque_iterator operator-(difference_type n) const BOOST_NOEXCEPT_OR_NOTHROW
261 { deque_iterator tmp(*this); return tmp -= n; }
263 BOOST_CONTAINER_FORCEINLINE reference operator[](difference_type n) const BOOST_NOEXCEPT_OR_NOTHROW
264 { return *(*this + n); }
266 BOOST_CONTAINER_FORCEINLINE friend bool operator==(const deque_iterator& l, const deque_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
267 { return l.m_cur == r.m_cur; }
269 BOOST_CONTAINER_FORCEINLINE friend bool operator!=(const deque_iterator& l, const deque_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
270 { return l.m_cur != r.m_cur; }
272 BOOST_CONTAINER_FORCEINLINE friend bool operator<(const deque_iterator& l, const deque_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
273 { return (l.m_node == r.m_node) ? (l.m_cur < r.m_cur) : (l.m_node < r.m_node); }
275 BOOST_CONTAINER_FORCEINLINE friend bool operator>(const deque_iterator& l, const deque_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
278 BOOST_CONTAINER_FORCEINLINE friend bool operator<=(const deque_iterator& l, const deque_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
281 BOOST_CONTAINER_FORCEINLINE friend bool operator>=(const deque_iterator& l, const deque_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
284 BOOST_CONTAINER_FORCEINLINE void priv_set_node(index_pointer new_node, difference_type block_size) BOOST_NOEXCEPT_OR_NOTHROW
286 this->m_node = new_node;
287 this->m_first = *new_node;
288 this->m_last = this->m_first + block_size;
291 BOOST_CONTAINER_FORCEINLINE friend deque_iterator operator+(difference_type n, deque_iterator x) BOOST_NOEXCEPT_OR_NOTHROW
297 template<class Options>
300 typedef Options type;
304 struct get_deque_opt<void>
306 typedef deque_null_opt type;
309 // Deque base class. It has two purposes. First, its constructor
310 // and destructor allocate (but don't initialize) storage. This makes
311 // exception safety easier.
312 template <class Allocator, class Options>
315 BOOST_COPYABLE_AND_MOVABLE(deque_base)
317 typedef allocator_traits<Allocator> val_alloc_traits_type;
318 typedef typename val_alloc_traits_type::value_type val_alloc_val;
319 typedef typename val_alloc_traits_type::pointer val_alloc_ptr;
320 typedef typename val_alloc_traits_type::const_pointer val_alloc_cptr;
321 typedef typename val_alloc_traits_type::reference val_alloc_ref;
322 typedef typename val_alloc_traits_type::const_reference val_alloc_cref;
323 typedef typename val_alloc_traits_type::difference_type val_alloc_diff;
324 typedef typename val_alloc_traits_type::size_type val_alloc_size;
325 typedef typename val_alloc_traits_type::template
326 portable_rebind_alloc<val_alloc_ptr>::type ptr_alloc_t;
327 typedef allocator_traits<ptr_alloc_t> ptr_alloc_traits_type;
328 typedef typename ptr_alloc_traits_type::value_type ptr_alloc_val;
329 typedef typename ptr_alloc_traits_type::pointer ptr_alloc_ptr;
330 typedef typename ptr_alloc_traits_type::const_pointer ptr_alloc_cptr;
331 typedef typename ptr_alloc_traits_type::reference ptr_alloc_ref;
332 typedef typename ptr_alloc_traits_type::const_reference ptr_alloc_cref;
333 typedef Allocator allocator_type;
334 typedef allocator_type stored_allocator_type;
335 typedef val_alloc_size size_type;
338 typedef typename get_deque_opt<Options>::type options_type;
341 typedef dtl::deque_iterator<val_alloc_ptr, false> iterator;
342 typedef dtl::deque_iterator<val_alloc_ptr, true > const_iterator;
344 BOOST_CONSTEXPR BOOST_CONTAINER_FORCEINLINE static size_type get_block_size() BOOST_NOEXCEPT_OR_NOTHROW
345 { return deque_block_size<val_alloc_val, options_type::block_bytes, options_type::block_size>::value; }
347 typedef deque_value_traits<val_alloc_val> traits_t;
348 typedef ptr_alloc_t map_allocator_type;
350 BOOST_CONTAINER_FORCEINLINE val_alloc_ptr priv_allocate_node()
351 { return this->alloc().allocate(get_block_size()); }
353 BOOST_CONTAINER_FORCEINLINE void priv_deallocate_node(val_alloc_ptr p) BOOST_NOEXCEPT_OR_NOTHROW
354 { this->alloc().deallocate(p, get_block_size()); }
356 BOOST_CONTAINER_FORCEINLINE ptr_alloc_ptr priv_allocate_map(size_type n)
357 { return this->ptr_alloc().allocate(n); }
359 BOOST_CONTAINER_FORCEINLINE void priv_deallocate_map(ptr_alloc_ptr p, size_type n) BOOST_NOEXCEPT_OR_NOTHROW
360 { this->ptr_alloc().deallocate(p, n); }
362 BOOST_CONTAINER_FORCEINLINE deque_base(size_type num_elements, const allocator_type& a)
364 { this->priv_initialize_map(num_elements); }
366 BOOST_CONTAINER_FORCEINLINE explicit deque_base(const allocator_type& a)
370 BOOST_CONTAINER_FORCEINLINE deque_base()
374 BOOST_CONTAINER_FORCEINLINE explicit deque_base(BOOST_RV_REF(deque_base) x)
375 : members_( boost::move(x.ptr_alloc())
376 , boost::move(x.alloc()) )
381 if (this->members_.m_map) {
382 this->priv_destroy_nodes(this->members_.m_start.m_node, this->members_.m_finish.m_node + 1);
383 this->priv_deallocate_map(this->members_.m_map, this->members_.m_map_size);
388 deque_base(const deque_base&);
392 void swap_members(deque_base &x) BOOST_NOEXCEPT_OR_NOTHROW
394 ::boost::adl_move_swap(this->members_.m_start, x.members_.m_start);
395 ::boost::adl_move_swap(this->members_.m_finish, x.members_.m_finish);
396 ::boost::adl_move_swap(this->members_.m_map, x.members_.m_map);
397 ::boost::adl_move_swap(this->members_.m_map_size, x.members_.m_map_size);
400 void priv_initialize_map(size_type num_elements)
403 size_type num_nodes = num_elements / get_block_size() + 1;
405 this->members_.m_map_size = dtl::max_value((size_type) InitialMapSize, num_nodes + 2);
406 this->members_.m_map = this->priv_allocate_map(this->members_.m_map_size);
408 ptr_alloc_ptr nstart = this->members_.m_map + (this->members_.m_map_size - num_nodes) / 2;
409 ptr_alloc_ptr nfinish = nstart + num_nodes;
412 this->priv_create_nodes(nstart, nfinish);
415 this->priv_deallocate_map(this->members_.m_map, this->members_.m_map_size);
416 this->members_.m_map = 0;
417 this->members_.m_map_size = 0;
422 this->members_.m_start.priv_set_node(nstart, get_block_size());
423 this->members_.m_finish.priv_set_node(nfinish - 1, get_block_size());
424 this->members_.m_start.m_cur = this->members_.m_start.m_first;
425 this->members_.m_finish.m_cur = this->members_.m_finish.m_first +
426 num_elements % get_block_size();
430 void priv_create_nodes(ptr_alloc_ptr nstart, ptr_alloc_ptr nfinish)
432 ptr_alloc_ptr cur = nstart;
434 for (; cur < nfinish; ++cur)
435 *cur = this->priv_allocate_node();
438 this->priv_destroy_nodes(nstart, cur);
444 void priv_destroy_nodes(ptr_alloc_ptr nstart, ptr_alloc_ptr nfinish) BOOST_NOEXCEPT_OR_NOTHROW
446 for (ptr_alloc_ptr n = nstart; n < nfinish; ++n)
447 this->priv_deallocate_node(*n);
450 void priv_clear_map() BOOST_NOEXCEPT_OR_NOTHROW
452 if (this->members_.m_map) {
453 this->priv_destroy_nodes(this->members_.m_start.m_node, this->members_.m_finish.m_node + 1);
454 this->priv_deallocate_map(this->members_.m_map, this->members_.m_map_size);
455 this->members_.m_map = 0;
456 this->members_.m_map_size = 0;
457 this->members_.m_start = iterator();
458 this->members_.m_finish = this->members_.m_start;
462 enum { InitialMapSize = 8 };
465 struct members_holder
467 , public allocator_type
470 : map_allocator_type(), allocator_type()
471 , m_map(0), m_map_size(0)
472 , m_start(), m_finish(m_start)
475 explicit members_holder(const allocator_type &a)
476 : map_allocator_type(a), allocator_type(a)
477 , m_map(0), m_map_size(0)
478 , m_start(), m_finish(m_start)
481 template<class ValAllocConvertible, class PtrAllocConvertible>
482 members_holder(BOOST_FWD_REF(PtrAllocConvertible) pa, BOOST_FWD_REF(ValAllocConvertible) va)
483 : map_allocator_type(boost::forward<PtrAllocConvertible>(pa))
484 , allocator_type (boost::forward<ValAllocConvertible>(va))
485 , m_map(0), m_map_size(0)
486 , m_start(), m_finish(m_start)
490 val_alloc_size m_map_size;
495 BOOST_CONTAINER_FORCEINLINE ptr_alloc_t &ptr_alloc() BOOST_NOEXCEPT_OR_NOTHROW
498 BOOST_CONTAINER_FORCEINLINE const ptr_alloc_t &ptr_alloc() const BOOST_NOEXCEPT_OR_NOTHROW
501 BOOST_CONTAINER_FORCEINLINE allocator_type &alloc() BOOST_NOEXCEPT_OR_NOTHROW
504 BOOST_CONTAINER_FORCEINLINE const allocator_type &alloc() const BOOST_NOEXCEPT_OR_NOTHROW
507 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
509 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
510 //! A double-ended queue is a sequence that supports random access to elements, constant time insertion
511 //! and removal of elements at the end of the sequence, and linear time insertion and removal of elements in the middle.
513 //! \tparam T The type of object that is stored in the deque
514 //! \tparam A The allocator used for all internal memory management, use void
515 //! for the default allocator
516 //! \tparam Options A type produced from \c boost::container::deque_options.
517 template <class T, class Allocator = void, class Options = void>
519 template <class T, class Allocator, class Options>
521 class deque : protected deque_base<typename real_allocator<T, Allocator>::type, Options>
523 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
525 typedef deque_base<typename real_allocator<T, Allocator>::type, Options> Base;
526 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
527 typedef typename real_allocator<T, Allocator>::type ValAllocator;
531 //////////////////////////////////////////////
535 //////////////////////////////////////////////
537 typedef T value_type;
538 typedef ValAllocator allocator_type;
539 typedef typename ::boost::container::allocator_traits<ValAllocator>::pointer pointer;
540 typedef typename ::boost::container::allocator_traits<ValAllocator>::const_pointer const_pointer;
541 typedef typename ::boost::container::allocator_traits<ValAllocator>::reference reference;
542 typedef typename ::boost::container::allocator_traits<ValAllocator>::const_reference const_reference;
543 typedef typename ::boost::container::allocator_traits<ValAllocator>::size_type size_type;
544 typedef typename ::boost::container::allocator_traits<ValAllocator>::difference_type difference_type;
545 typedef BOOST_CONTAINER_IMPDEF(allocator_type) stored_allocator_type;
546 typedef BOOST_CONTAINER_IMPDEF(typename Base::iterator) iterator;
547 typedef BOOST_CONTAINER_IMPDEF(typename Base::const_iterator) const_iterator;
548 typedef BOOST_CONTAINER_IMPDEF(boost::container::reverse_iterator<iterator>) reverse_iterator;
549 typedef BOOST_CONTAINER_IMPDEF(boost::container::reverse_iterator<const_iterator>) const_reverse_iterator;
551 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
553 private: // Internal typedefs
554 BOOST_COPYABLE_AND_MOVABLE(deque)
555 typedef typename Base::ptr_alloc_ptr index_pointer;
556 typedef allocator_traits<ValAllocator> allocator_traits_type;
558 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
562 BOOST_CONSTEXPR BOOST_CONTAINER_FORCEINLINE static size_type get_block_size() BOOST_NOEXCEPT_OR_NOTHROW
563 { return Base::get_block_size(); }
565 //////////////////////////////////////////////
567 // construct/copy/destroy
569 //////////////////////////////////////////////
571 //! <b>Effects</b>: Default constructors a deque.
573 //! <b>Throws</b>: If allocator_type's default constructor throws.
575 //! <b>Complexity</b>: Constant.
576 BOOST_CONTAINER_FORCEINLINE deque() BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<ValAllocator>::value)
580 //! <b>Effects</b>: Constructs a deque taking the allocator as parameter.
582 //! <b>Throws</b>: Nothing
584 //! <b>Complexity</b>: Constant.
585 BOOST_CONTAINER_FORCEINLINE explicit deque(const allocator_type& a) BOOST_NOEXCEPT_OR_NOTHROW
589 //! <b>Effects</b>: Constructs a deque
590 //! and inserts n value initialized values.
592 //! <b>Throws</b>: If allocator_type's default constructor
593 //! throws or T's value initialization throws.
595 //! <b>Complexity</b>: Linear to n.
596 BOOST_CONTAINER_FORCEINLINE explicit deque(size_type n)
597 : Base(n, allocator_type())
599 dtl::insert_value_initialized_n_proxy<ValAllocator, iterator> proxy;
600 proxy.uninitialized_copy_n_and_update(this->alloc(), this->begin(), n);
601 //deque_base will deallocate in case of exception...
604 //! <b>Effects</b>: Constructs a deque
605 //! and inserts n default initialized values.
607 //! <b>Throws</b>: If allocator_type's default constructor
608 //! throws or T's default initialization or copy constructor throws.
610 //! <b>Complexity</b>: Linear to n.
612 //! <b>Note</b>: Non-standard extension
613 BOOST_CONTAINER_FORCEINLINE deque(size_type n, default_init_t)
614 : Base(n, allocator_type())
616 dtl::insert_default_initialized_n_proxy<ValAllocator, iterator> proxy;
617 proxy.uninitialized_copy_n_and_update(this->alloc(), this->begin(), n);
618 //deque_base will deallocate in case of exception...
621 //! <b>Effects</b>: Constructs a deque that will use a copy of allocator a
622 //! and inserts n value initialized values.
624 //! <b>Throws</b>: If allocator_type's default constructor
625 //! throws or T's value initialization throws.
627 //! <b>Complexity</b>: Linear to n.
628 BOOST_CONTAINER_FORCEINLINE explicit deque(size_type n, const allocator_type &a)
631 dtl::insert_value_initialized_n_proxy<ValAllocator, iterator> proxy;
632 proxy.uninitialized_copy_n_and_update(this->alloc(), this->begin(), n);
633 //deque_base will deallocate in case of exception...
636 //! <b>Effects</b>: Constructs a deque that will use a copy of allocator a
637 //! and inserts n default initialized values.
639 //! <b>Throws</b>: If allocator_type's default constructor
640 //! throws or T's default initialization or copy constructor throws.
642 //! <b>Complexity</b>: Linear to n.
644 //! <b>Note</b>: Non-standard extension
645 BOOST_CONTAINER_FORCEINLINE deque(size_type n, default_init_t, const allocator_type &a)
648 dtl::insert_default_initialized_n_proxy<ValAllocator, iterator> proxy;
649 proxy.uninitialized_copy_n_and_update(this->alloc(), this->begin(), n);
650 //deque_base will deallocate in case of exception...
653 //! <b>Effects</b>: Constructs a deque that will use a copy of allocator a
654 //! and inserts n copies of value.
656 //! <b>Throws</b>: If allocator_type's default constructor
657 //! throws or T's copy constructor throws.
659 //! <b>Complexity</b>: Linear to n.
660 BOOST_CONTAINER_FORCEINLINE deque(size_type n, const value_type& value)
661 : Base(n, allocator_type())
662 { this->priv_fill_initialize(value); }
664 //! <b>Effects</b>: Constructs a deque that will use a copy of allocator a
665 //! and inserts n copies of value.
667 //! <b>Throws</b>: If allocator_type's default constructor
668 //! throws or T's copy constructor throws.
670 //! <b>Complexity</b>: Linear to n.
671 BOOST_CONTAINER_FORCEINLINE deque(size_type n, const value_type& value, const allocator_type& a)
673 { this->priv_fill_initialize(value); }
675 //! <b>Effects</b>: Constructs a deque that will use a copy of allocator a
676 //! and inserts a copy of the range [first, last) in the deque.
678 //! <b>Throws</b>: If allocator_type's default constructor
679 //! throws or T's constructor taking a dereferenced InIt throws.
681 //! <b>Complexity</b>: Linear to the range [first, last).
682 template <class InIt>
683 BOOST_CONTAINER_FORCEINLINE deque(InIt first, InIt last
684 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
685 , typename dtl::disable_if_convertible
686 <InIt, size_type>::type * = 0
689 : Base(allocator_type())
691 this->priv_range_initialize(first, last);
694 //! <b>Effects</b>: Constructs a deque that will use a copy of allocator a
695 //! and inserts a copy of the range [first, last) in the deque.
697 //! <b>Throws</b>: If allocator_type's default constructor
698 //! throws or T's constructor taking a dereferenced InIt throws.
700 //! <b>Complexity</b>: Linear to the range [first, last).
701 template <class InIt>
702 BOOST_CONTAINER_FORCEINLINE deque(InIt first, InIt last, const allocator_type& a
703 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
704 , typename dtl::disable_if_convertible
705 <InIt, size_type>::type * = 0
710 this->priv_range_initialize(first, last);
713 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
714 //! <b>Effects</b>: Constructs a deque that will use a copy of allocator a
715 //! and inserts a copy of the range [il.begin(), il.end()) in the deque.
717 //! <b>Throws</b>: If allocator_type's default constructor
718 //! throws or T's constructor taking a dereferenced std::initializer_list iterator throws.
720 //! <b>Complexity</b>: Linear to the range [il.begin(), il.end()).
721 BOOST_CONTAINER_FORCEINLINE deque(std::initializer_list<value_type> il, const allocator_type& a = allocator_type())
724 this->priv_range_initialize(il.begin(), il.end());
728 //! <b>Effects</b>: Copy constructs a deque.
730 //! <b>Postcondition</b>: x == *this.
732 //! <b>Complexity</b>: Linear to the elements x contains.
733 BOOST_CONTAINER_FORCEINLINE deque(const deque& x)
734 : Base(allocator_traits_type::select_on_container_copy_construction(x.alloc()))
737 this->priv_initialize_map(x.size());
738 boost::container::uninitialized_copy_alloc
739 (this->alloc(), x.begin(), x.end(), this->members_.m_start);
743 //! <b>Effects</b>: Move constructor. Moves x's resources to *this.
745 //! <b>Throws</b>: If allocator_type's copy constructor throws.
747 //! <b>Complexity</b>: Constant.
748 BOOST_CONTAINER_FORCEINLINE deque(BOOST_RV_REF(deque) x) BOOST_NOEXCEPT_OR_NOTHROW
749 : Base(BOOST_MOVE_BASE(Base, x))
750 { this->swap_members(x); }
752 //! <b>Effects</b>: Copy constructs a vector using the specified allocator.
754 //! <b>Postcondition</b>: x == *this.
756 //! <b>Throws</b>: If allocation
757 //! throws or T's copy constructor throws.
759 //! <b>Complexity</b>: Linear to the elements x contains.
760 deque(const deque& x, const allocator_type &a)
764 this->priv_initialize_map(x.size());
765 boost::container::uninitialized_copy_alloc
766 (this->alloc(), x.begin(), x.end(), this->members_.m_start);
770 //! <b>Effects</b>: Move constructor using the specified allocator.
771 //! Moves x's resources to *this if a == allocator_type().
772 //! Otherwise copies values from x to *this.
774 //! <b>Throws</b>: If allocation or T's copy constructor throws.
776 //! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise.
777 deque(BOOST_RV_REF(deque) x, const allocator_type &a)
781 this->swap_members(x);
785 this->priv_initialize_map(x.size());
786 boost::container::uninitialized_copy_alloc
787 ( this->alloc(), boost::make_move_iterator(x.begin())
788 , boost::make_move_iterator(x.end()), this->members_.m_start);
793 //! <b>Effects</b>: Destroys the deque. All stored values are destroyed
794 //! and used memory is deallocated.
796 //! <b>Throws</b>: Nothing.
798 //! <b>Complexity</b>: Linear to the number of elements.
799 BOOST_CONTAINER_FORCEINLINE ~deque() BOOST_NOEXCEPT_OR_NOTHROW
801 this->priv_destroy_range(this->members_.m_start, this->members_.m_finish);
804 //! <b>Effects</b>: Makes *this contain the same elements as x.
806 //! <b>Postcondition</b>: this->size() == x.size(). *this contains a copy
807 //! of each of x's elements.
809 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws.
811 //! <b>Complexity</b>: Linear to the number of elements in x.
812 deque& operator= (BOOST_COPY_ASSIGN_REF(deque) x)
814 if (BOOST_LIKELY(&x != this)){
815 allocator_type &this_alloc = this->alloc();
816 const allocator_type &x_alloc = x.alloc();
817 dtl::bool_<allocator_traits_type::
818 propagate_on_container_copy_assignment::value> flag;
819 if(flag && this_alloc != x_alloc){
821 this->shrink_to_fit();
823 dtl::assign_alloc(this->alloc(), x.alloc(), flag);
824 dtl::assign_alloc(this->ptr_alloc(), x.ptr_alloc(), flag);
825 this->assign(x.cbegin(), x.cend());
830 //! <b>Effects</b>: Move assignment. All x's values are transferred to *this.
832 //! <b>Throws</b>: If allocator_traits_type::propagate_on_container_move_assignment
833 //! is false and (allocation throws or value_type's move constructor throws)
835 //! <b>Complexity</b>: Constant if allocator_traits_type::
836 //! propagate_on_container_move_assignment is true or
837 //! this->get>allocator() == x.get_allocator(). Linear otherwise.
838 deque& operator= (BOOST_RV_REF(deque) x)
839 BOOST_NOEXCEPT_IF(allocator_traits_type::propagate_on_container_move_assignment::value
840 || allocator_traits_type::is_always_equal::value)
842 if (BOOST_LIKELY(this != &x)) {
843 allocator_type &this_alloc = this->alloc();
844 allocator_type &x_alloc = x.alloc();
845 const bool propagate_alloc = allocator_traits_type::
846 propagate_on_container_move_assignment::value;
847 dtl::bool_<propagate_alloc> flag;
848 const bool allocators_equal = this_alloc == x_alloc; (void)allocators_equal;
849 //Resources can be transferred if both allocators are
850 //going to be equal after this function (either propagated or already equal)
851 if(propagate_alloc || allocators_equal){
852 //Destroy objects but retain memory in case x reuses it in the future
854 //Move allocator if needed
855 dtl::move_alloc(this_alloc, x_alloc, flag);
856 dtl::move_alloc(this->ptr_alloc(), x.ptr_alloc(), flag);
858 this->swap_members(x);
860 //Else do a one by one move
862 this->assign( boost::make_move_iterator(x.begin())
863 , boost::make_move_iterator(x.end()));
869 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
870 //! <b>Effects</b>: Makes *this contain the same elements as il.
872 //! <b>Postcondition</b>: this->size() == il.size(). *this contains a copy
873 //! of each of x's elements.
875 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws.
877 //! <b>Complexity</b>: Linear to the number of elements in il.
878 BOOST_CONTAINER_FORCEINLINE deque& operator=(std::initializer_list<value_type> il)
880 this->assign(il.begin(), il.end());
885 //! <b>Effects</b>: Assigns the n copies of val to *this.
887 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws.
889 //! <b>Complexity</b>: Linear to n.
890 BOOST_CONTAINER_FORCEINLINE void assign(size_type n, const T& val)
892 typedef constant_iterator<value_type, difference_type> c_it;
893 this->assign(c_it(val, n), c_it());
896 //! <b>Effects</b>: Assigns the the range [first, last) to *this.
898 //! <b>Throws</b>: If memory allocation throws or
899 //! T's constructor from dereferencing InIt throws.
901 //! <b>Complexity</b>: Linear to n.
902 template <class InIt>
903 void assign(InIt first, InIt last
904 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
905 , typename dtl::disable_if_or
907 , dtl::is_convertible<InIt, size_type>
908 , dtl::is_not_input_iterator<InIt>
913 iterator cur = this->begin();
914 for ( ; first != last && cur != end(); ++cur, ++first){
918 this->erase(cur, this->cend());
921 this->insert(this->cend(), first, last);
925 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
926 template <class FwdIt>
927 void assign(FwdIt first, FwdIt last
928 , typename dtl::disable_if_or
930 , dtl::is_convertible<FwdIt, size_type>
931 , dtl::is_input_iterator<FwdIt>
935 const size_type len = boost::container::iterator_distance(first, last);
938 boost::container::iterator_advance(mid, this->size());
939 boost::container::copy(first, mid, begin());
940 this->insert(this->cend(), mid, last);
943 this->erase(boost::container::copy(first, last, this->begin()), cend());
948 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
949 //! <b>Effects</b>: Assigns the the range [il.begin(), il.end()) to *this.
951 //! <b>Throws</b>: If memory allocation throws or
952 //! T's constructor from dereferencing std::initializer_list iterator throws.
954 //! <b>Complexity</b>: Linear to il.size().
955 BOOST_CONTAINER_FORCEINLINE void assign(std::initializer_list<value_type> il)
956 { this->assign(il.begin(), il.end()); }
959 //! <b>Effects</b>: Returns a copy of the internal allocator.
961 //! <b>Throws</b>: If allocator's copy constructor throws.
963 //! <b>Complexity</b>: Constant.
964 BOOST_CONTAINER_FORCEINLINE allocator_type get_allocator() const BOOST_NOEXCEPT_OR_NOTHROW
965 { return Base::alloc(); }
967 //! <b>Effects</b>: Returns a reference to the internal allocator.
969 //! <b>Throws</b>: Nothing
971 //! <b>Complexity</b>: Constant.
973 //! <b>Note</b>: Non-standard extension.
974 BOOST_CONTAINER_FORCEINLINE const stored_allocator_type &get_stored_allocator() const BOOST_NOEXCEPT_OR_NOTHROW
975 { return Base::alloc(); }
977 //////////////////////////////////////////////
981 //////////////////////////////////////////////
983 //! <b>Effects</b>: Returns a reference to the internal allocator.
985 //! <b>Throws</b>: Nothing
987 //! <b>Complexity</b>: Constant.
989 //! <b>Note</b>: Non-standard extension.
990 BOOST_CONTAINER_FORCEINLINE stored_allocator_type &get_stored_allocator() BOOST_NOEXCEPT_OR_NOTHROW
991 { return Base::alloc(); }
993 //! <b>Effects</b>: Returns an iterator to the first element contained in the deque.
995 //! <b>Throws</b>: Nothing.
997 //! <b>Complexity</b>: Constant.
998 BOOST_CONTAINER_FORCEINLINE iterator begin() BOOST_NOEXCEPT_OR_NOTHROW
999 { return this->members_.m_start; }
1001 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the deque.
1003 //! <b>Throws</b>: Nothing.
1005 //! <b>Complexity</b>: Constant.
1006 BOOST_CONTAINER_FORCEINLINE const_iterator begin() const BOOST_NOEXCEPT_OR_NOTHROW
1007 { return this->members_.m_start; }
1009 //! <b>Effects</b>: Returns an iterator to the end of the deque.
1011 //! <b>Throws</b>: Nothing.
1013 //! <b>Complexity</b>: Constant.
1014 BOOST_CONTAINER_FORCEINLINE iterator end() BOOST_NOEXCEPT_OR_NOTHROW
1015 { return this->members_.m_finish; }
1017 //! <b>Effects</b>: Returns a const_iterator to the end of the deque.
1019 //! <b>Throws</b>: Nothing.
1021 //! <b>Complexity</b>: Constant.
1022 BOOST_CONTAINER_FORCEINLINE const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW
1023 { return this->members_.m_finish; }
1025 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning
1026 //! of the reversed deque.
1028 //! <b>Throws</b>: Nothing.
1030 //! <b>Complexity</b>: Constant.
1031 BOOST_CONTAINER_FORCEINLINE reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW
1032 { return reverse_iterator(this->members_.m_finish); }
1034 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
1035 //! of the reversed deque.
1037 //! <b>Throws</b>: Nothing.
1039 //! <b>Complexity</b>: Constant.
1040 BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW
1041 { return const_reverse_iterator(this->members_.m_finish); }
1043 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
1044 //! of the reversed deque.
1046 //! <b>Throws</b>: Nothing.
1048 //! <b>Complexity</b>: Constant.
1049 BOOST_CONTAINER_FORCEINLINE reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW
1050 { return reverse_iterator(this->members_.m_start); }
1052 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
1053 //! of the reversed deque.
1055 //! <b>Throws</b>: Nothing.
1057 //! <b>Complexity</b>: Constant.
1058 BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW
1059 { return const_reverse_iterator(this->members_.m_start); }
1061 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the deque.
1063 //! <b>Throws</b>: Nothing.
1065 //! <b>Complexity</b>: Constant.
1066 BOOST_CONTAINER_FORCEINLINE const_iterator cbegin() const BOOST_NOEXCEPT_OR_NOTHROW
1067 { return this->members_.m_start; }
1069 //! <b>Effects</b>: Returns a const_iterator to the end of the deque.
1071 //! <b>Throws</b>: Nothing.
1073 //! <b>Complexity</b>: Constant.
1074 BOOST_CONTAINER_FORCEINLINE const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW
1075 { return this->members_.m_finish; }
1077 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
1078 //! of the reversed deque.
1080 //! <b>Throws</b>: Nothing.
1082 //! <b>Complexity</b>: Constant.
1083 BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW
1084 { return const_reverse_iterator(this->members_.m_finish); }
1086 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
1087 //! of the reversed deque.
1089 //! <b>Throws</b>: Nothing.
1091 //! <b>Complexity</b>: Constant.
1092 BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW
1093 { return const_reverse_iterator(this->members_.m_start); }
1095 //////////////////////////////////////////////
1099 //////////////////////////////////////////////
1101 //! <b>Effects</b>: Returns true if the deque contains no elements.
1103 //! <b>Throws</b>: Nothing.
1105 //! <b>Complexity</b>: Constant.
1106 BOOST_CONTAINER_FORCEINLINE bool empty() const BOOST_NOEXCEPT_OR_NOTHROW
1107 { return this->members_.m_finish == this->members_.m_start; }
1109 //! <b>Effects</b>: Returns the number of the elements contained in the deque.
1111 //! <b>Throws</b>: Nothing.
1113 //! <b>Complexity</b>: Constant.
1114 BOOST_CONTAINER_FORCEINLINE size_type size() const BOOST_NOEXCEPT_OR_NOTHROW
1115 { return this->members_.m_finish - this->members_.m_start; }
1117 //! <b>Effects</b>: Returns the largest possible size of the deque.
1119 //! <b>Throws</b>: Nothing.
1121 //! <b>Complexity</b>: Constant.
1122 BOOST_CONTAINER_FORCEINLINE size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW
1123 { return allocator_traits_type::max_size(this->alloc()); }
1125 //! <b>Effects</b>: Inserts or erases elements at the end such that
1126 //! the size becomes n. New elements are value initialized.
1128 //! <b>Throws</b>: If memory allocation throws, or T's constructor throws.
1130 //! <b>Complexity</b>: Linear to the difference between size() and new_size.
1131 void resize(size_type new_size)
1133 const size_type len = size();
1135 this->priv_erase_last_n(len - new_size);
1137 const size_type n = new_size - this->size();
1138 dtl::insert_value_initialized_n_proxy<ValAllocator, iterator> proxy;
1139 priv_insert_back_aux_impl(n, proxy);
1143 //! <b>Effects</b>: Inserts or erases elements at the end such that
1144 //! the size becomes n. New elements are default initialized.
1146 //! <b>Throws</b>: If memory allocation throws, or T's constructor throws.
1148 //! <b>Complexity</b>: Linear to the difference between size() and new_size.
1150 //! <b>Note</b>: Non-standard extension
1151 void resize(size_type new_size, default_init_t)
1153 const size_type len = size();
1155 this->priv_erase_last_n(len - new_size);
1157 const size_type n = new_size - this->size();
1158 dtl::insert_default_initialized_n_proxy<ValAllocator, iterator> proxy;
1159 priv_insert_back_aux_impl(n, proxy);
1163 //! <b>Effects</b>: Inserts or erases elements at the end such that
1164 //! the size becomes n. New elements are copy constructed from x.
1166 //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws.
1168 //! <b>Complexity</b>: Linear to the difference between size() and new_size.
1169 void resize(size_type new_size, const value_type& x)
1171 const size_type len = size();
1173 this->erase(this->members_.m_start + new_size, this->members_.m_finish);
1175 this->insert(this->members_.m_finish, new_size - len, x);
1178 //! <b>Effects</b>: Tries to deallocate the excess of memory created
1179 //! with previous allocations. The size of the deque is unchanged
1181 //! <b>Throws</b>: If memory allocation throws.
1183 //! <b>Complexity</b>: Constant.
1184 void shrink_to_fit()
1186 //This deque implementation already
1187 //deallocates excess nodes when erasing
1188 //so there is nothing to do except for
1191 this->priv_clear_map();
1195 //////////////////////////////////////////////
1199 //////////////////////////////////////////////
1201 //! <b>Requires</b>: !empty()
1203 //! <b>Effects</b>: Returns a reference to the first
1204 //! element of the container.
1206 //! <b>Throws</b>: Nothing.
1208 //! <b>Complexity</b>: Constant.
1209 BOOST_CONTAINER_FORCEINLINE reference front() BOOST_NOEXCEPT_OR_NOTHROW
1211 BOOST_ASSERT(!this->empty());
1212 return *this->members_.m_start;
1215 //! <b>Requires</b>: !empty()
1217 //! <b>Effects</b>: Returns a const reference to the first element
1218 //! from the beginning of the container.
1220 //! <b>Throws</b>: Nothing.
1222 //! <b>Complexity</b>: Constant.
1223 BOOST_CONTAINER_FORCEINLINE const_reference front() const BOOST_NOEXCEPT_OR_NOTHROW
1225 BOOST_ASSERT(!this->empty());
1226 return *this->members_.m_start;
1229 //! <b>Requires</b>: !empty()
1231 //! <b>Effects</b>: Returns a reference to the last
1232 //! element of the container.
1234 //! <b>Throws</b>: Nothing.
1236 //! <b>Complexity</b>: Constant.
1237 BOOST_CONTAINER_FORCEINLINE reference back() BOOST_NOEXCEPT_OR_NOTHROW
1239 BOOST_ASSERT(!this->empty());
1243 //! <b>Requires</b>: !empty()
1245 //! <b>Effects</b>: Returns a const reference to the last
1246 //! element of the container.
1248 //! <b>Throws</b>: Nothing.
1250 //! <b>Complexity</b>: Constant.
1251 BOOST_CONTAINER_FORCEINLINE const_reference back() const BOOST_NOEXCEPT_OR_NOTHROW
1253 BOOST_ASSERT(!this->empty());
1257 //! <b>Requires</b>: size() > n.
1259 //! <b>Effects</b>: Returns a reference to the nth element
1260 //! from the beginning of the container.
1262 //! <b>Throws</b>: Nothing.
1264 //! <b>Complexity</b>: Constant.
1265 BOOST_CONTAINER_FORCEINLINE reference operator[](size_type n) BOOST_NOEXCEPT_OR_NOTHROW
1267 BOOST_ASSERT(this->size() > n);
1268 return this->members_.m_start[difference_type(n)];
1271 //! <b>Requires</b>: size() > n.
1273 //! <b>Effects</b>: Returns a const reference to the nth element
1274 //! from the beginning of the container.
1276 //! <b>Throws</b>: Nothing.
1278 //! <b>Complexity</b>: Constant.
1279 BOOST_CONTAINER_FORCEINLINE const_reference operator[](size_type n) const BOOST_NOEXCEPT_OR_NOTHROW
1281 BOOST_ASSERT(this->size() > n);
1282 return this->members_.m_start[difference_type(n)];
1285 //! <b>Requires</b>: size() >= n.
1287 //! <b>Effects</b>: Returns an iterator to the nth element
1288 //! from the beginning of the container. Returns end()
1291 //! <b>Throws</b>: Nothing.
1293 //! <b>Complexity</b>: Constant.
1295 //! <b>Note</b>: Non-standard extension
1296 BOOST_CONTAINER_FORCEINLINE iterator nth(size_type n) BOOST_NOEXCEPT_OR_NOTHROW
1298 BOOST_ASSERT(this->size() >= n);
1299 return iterator(this->begin()+n);
1302 //! <b>Requires</b>: size() >= n.
1304 //! <b>Effects</b>: Returns a const_iterator to the nth element
1305 //! from the beginning of the container. Returns end()
1308 //! <b>Throws</b>: Nothing.
1310 //! <b>Complexity</b>: Constant.
1312 //! <b>Note</b>: Non-standard extension
1313 BOOST_CONTAINER_FORCEINLINE const_iterator nth(size_type n) const BOOST_NOEXCEPT_OR_NOTHROW
1315 BOOST_ASSERT(this->size() >= n);
1316 return const_iterator(this->cbegin()+n);
1319 //! <b>Requires</b>: begin() <= p <= end().
1321 //! <b>Effects</b>: Returns the index of the element pointed by p
1322 //! and size() if p == end().
1324 //! <b>Throws</b>: Nothing.
1326 //! <b>Complexity</b>: Constant.
1328 //! <b>Note</b>: Non-standard extension
1329 BOOST_CONTAINER_FORCEINLINE size_type index_of(iterator p) BOOST_NOEXCEPT_OR_NOTHROW
1331 //Range checked priv_index_of
1332 return this->priv_index_of(p);
1335 //! <b>Requires</b>: begin() <= p <= end().
1337 //! <b>Effects</b>: Returns the index of the element pointed by p
1338 //! and size() if p == end().
1340 //! <b>Throws</b>: Nothing.
1342 //! <b>Complexity</b>: Constant.
1344 //! <b>Note</b>: Non-standard extension
1345 BOOST_CONTAINER_FORCEINLINE size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW
1347 //Range checked priv_index_of
1348 return this->priv_index_of(p);
1351 //! <b>Requires</b>: size() > n.
1353 //! <b>Effects</b>: Returns a reference to the nth element
1354 //! from the beginning of the container.
1356 //! <b>Throws</b>: std::range_error if n >= size()
1358 //! <b>Complexity</b>: Constant.
1359 BOOST_CONTAINER_FORCEINLINE reference at(size_type n)
1361 this->priv_throw_if_out_of_range(n);
1365 //! <b>Requires</b>: size() > n.
1367 //! <b>Effects</b>: Returns a const reference to the nth element
1368 //! from the beginning of the container.
1370 //! <b>Throws</b>: std::range_error if n >= size()
1372 //! <b>Complexity</b>: Constant.
1373 BOOST_CONTAINER_FORCEINLINE const_reference at(size_type n) const
1375 this->priv_throw_if_out_of_range(n);
1379 //////////////////////////////////////////////
1383 //////////////////////////////////////////////
1385 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1387 //! <b>Effects</b>: Inserts an object of type T constructed with
1388 //! std::forward<Args>(args)... in the beginning of the deque.
1390 //! <b>Returns</b>: A reference to the created object.
1392 //! <b>Throws</b>: If memory allocation throws or the in-place constructor throws.
1394 //! <b>Complexity</b>: Amortized constant time
1395 template <class... Args>
1396 reference emplace_front(BOOST_FWD_REF(Args)... args)
1398 if(this->priv_push_front_simple_available()){
1399 reference r = *this->priv_push_front_simple_pos();
1400 allocator_traits_type::construct
1402 , this->priv_push_front_simple_pos()
1403 , boost::forward<Args>(args)...);
1404 this->priv_push_front_simple_commit();
1408 typedef dtl::insert_nonmovable_emplace_proxy<ValAllocator, iterator, Args...> type;
1409 return *this->priv_insert_front_aux_impl(1, type(boost::forward<Args>(args)...));
1413 //! <b>Effects</b>: Inserts an object of type T constructed with
1414 //! std::forward<Args>(args)... in the end of the deque.
1416 //! <b>Returns</b>: A reference to the created object.
1418 //! <b>Throws</b>: If memory allocation throws or the in-place constructor throws.
1420 //! <b>Complexity</b>: Amortized constant time
1421 template <class... Args>
1422 reference emplace_back(BOOST_FWD_REF(Args)... args)
1424 if(this->priv_push_back_simple_available()){
1425 reference r = *this->priv_push_back_simple_pos();
1426 allocator_traits_type::construct
1428 , this->priv_push_back_simple_pos()
1429 , boost::forward<Args>(args)...);
1430 this->priv_push_back_simple_commit();
1434 typedef dtl::insert_nonmovable_emplace_proxy<ValAllocator, iterator, Args...> type;
1435 return *this->priv_insert_back_aux_impl(1, type(boost::forward<Args>(args)...));
1439 //! <b>Requires</b>: p must be a valid iterator of *this.
1441 //! <b>Effects</b>: Inserts an object of type T constructed with
1442 //! std::forward<Args>(args)... before p
1444 //! <b>Throws</b>: If memory allocation throws or the in-place constructor throws.
1446 //! <b>Complexity</b>: If p is end(), amortized constant time
1447 //! Linear time otherwise.
1448 template <class... Args>
1449 iterator emplace(const_iterator p, BOOST_FWD_REF(Args)... args)
1451 BOOST_ASSERT(this->priv_in_range_or_end(p));
1452 if(p == this->cbegin()){
1453 this->emplace_front(boost::forward<Args>(args)...);
1454 return this->begin();
1456 else if(p == this->cend()){
1457 this->emplace_back(boost::forward<Args>(args)...);
1458 return (this->end()-1);
1461 typedef dtl::insert_emplace_proxy<ValAllocator, iterator, Args...> type;
1462 return this->priv_insert_aux_impl(p, 1, type(boost::forward<Args>(args)...));
1466 #else //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1468 #define BOOST_CONTAINER_DEQUE_EMPLACE_CODE(N) \
1469 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N\
1470 reference emplace_front(BOOST_MOVE_UREF##N)\
1472 if(priv_push_front_simple_available()){\
1473 reference r = *this->priv_push_front_simple_pos();\
1474 allocator_traits_type::construct\
1475 ( this->alloc(), this->priv_push_front_simple_pos() BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
1476 priv_push_front_simple_commit();\
1480 typedef dtl::insert_nonmovable_emplace_proxy##N\
1481 <ValAllocator, iterator BOOST_MOVE_I##N BOOST_MOVE_TARG##N> type;\
1482 return *priv_insert_front_aux_impl(1, type(BOOST_MOVE_FWD##N));\
1486 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N\
1487 reference emplace_back(BOOST_MOVE_UREF##N)\
1489 if(priv_push_back_simple_available()){\
1490 reference r = *this->priv_push_back_simple_pos();\
1491 allocator_traits_type::construct\
1492 ( this->alloc(), this->priv_push_back_simple_pos() BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
1493 priv_push_back_simple_commit();\
1497 typedef dtl::insert_nonmovable_emplace_proxy##N\
1498 <ValAllocator, iterator BOOST_MOVE_I##N BOOST_MOVE_TARG##N> type;\
1499 return *priv_insert_back_aux_impl(1, type(BOOST_MOVE_FWD##N));\
1503 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N\
1504 iterator emplace(const_iterator p BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
1506 BOOST_ASSERT(this->priv_in_range_or_end(p));\
1507 if(p == this->cbegin()){\
1508 this->emplace_front(BOOST_MOVE_FWD##N);\
1509 return this->begin();\
1511 else if(p == cend()){\
1512 this->emplace_back(BOOST_MOVE_FWD##N);\
1513 return (--this->end());\
1516 typedef dtl::insert_emplace_proxy_arg##N\
1517 <ValAllocator, iterator BOOST_MOVE_I##N BOOST_MOVE_TARG##N> type;\
1518 return this->priv_insert_aux_impl(p, 1, type(BOOST_MOVE_FWD##N));\
1522 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_DEQUE_EMPLACE_CODE)
1523 #undef BOOST_CONTAINER_DEQUE_EMPLACE_CODE
1525 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1527 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1528 //! <b>Effects</b>: Inserts a copy of x at the front of the deque.
1530 //! <b>Throws</b>: If memory allocation throws or
1531 //! T's copy constructor throws.
1533 //! <b>Complexity</b>: Amortized constant time.
1534 void push_front(const T &x);
1536 //! <b>Effects</b>: Constructs a new element in the front of the deque
1537 //! and moves the resources of x to this new element.
1539 //! <b>Throws</b>: If memory allocation throws.
1541 //! <b>Complexity</b>: Amortized constant time.
1542 void push_front(T &&x);
1544 BOOST_MOVE_CONVERSION_AWARE_CATCH(push_front, T, void, priv_push_front)
1547 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1548 //! <b>Effects</b>: Inserts a copy of x at the end of the deque.
1550 //! <b>Throws</b>: If memory allocation throws or
1551 //! T's copy constructor throws.
1553 //! <b>Complexity</b>: Amortized constant time.
1554 void push_back(const T &x);
1556 //! <b>Effects</b>: Constructs a new element in the end of the deque
1557 //! and moves the resources of x to this new element.
1559 //! <b>Throws</b>: If memory allocation throws.
1561 //! <b>Complexity</b>: Amortized constant time.
1562 void push_back(T &&x);
1564 BOOST_MOVE_CONVERSION_AWARE_CATCH(push_back, T, void, priv_push_back)
1567 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1569 //! <b>Requires</b>: p must be a valid iterator of *this.
1571 //! <b>Effects</b>: Insert a copy of x before p.
1573 //! <b>Returns</b>: an iterator to the inserted element.
1575 //! <b>Throws</b>: If memory allocation throws or x's copy constructor throws.
1577 //! <b>Complexity</b>: If p is end(), amortized constant time
1578 //! Linear time otherwise.
1579 iterator insert(const_iterator p, const T &x);
1581 //! <b>Requires</b>: p must be a valid iterator of *this.
1583 //! <b>Effects</b>: Insert a new element before p with x's resources.
1585 //! <b>Returns</b>: an iterator to the inserted element.
1587 //! <b>Throws</b>: If memory allocation throws.
1589 //! <b>Complexity</b>: If p is end(), amortized constant time
1590 //! Linear time otherwise.
1591 iterator insert(const_iterator p, T &&x);
1593 BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, T, iterator, priv_insert, const_iterator, const_iterator)
1596 //! <b>Requires</b>: pos must be a valid iterator of *this.
1598 //! <b>Effects</b>: Insert n copies of x before pos.
1600 //! <b>Returns</b>: an iterator to the first inserted element or pos if n is 0.
1602 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws.
1604 //! <b>Complexity</b>: Linear to n.
1605 BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator pos, size_type n, const value_type& x)
1607 //Range check of p is done by insert()
1608 typedef constant_iterator<value_type, difference_type> c_it;
1609 return this->insert(pos, c_it(x, n), c_it());
1612 //! <b>Requires</b>: pos must be a valid iterator of *this.
1614 //! <b>Effects</b>: Insert a copy of the [first, last) range before pos.
1616 //! <b>Returns</b>: an iterator to the first inserted element or pos if first == last.
1618 //! <b>Throws</b>: If memory allocation throws, T's constructor from a
1619 //! dereferenced InIt throws or T's copy constructor throws.
1621 //! <b>Complexity</b>: Linear to distance [first, last).
1622 template <class InIt>
1623 iterator insert(const_iterator pos, InIt first, InIt last
1624 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1625 , typename dtl::disable_if_or
1627 , dtl::is_convertible<InIt, size_type>
1628 , dtl::is_not_input_iterator<InIt>
1633 BOOST_ASSERT(this->priv_in_range_or_end(pos));
1635 iterator it(pos.unconst());
1636 for(;first != last; ++first, ++n){
1637 it = this->emplace(it, *first);
1644 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1645 //! <b>Requires</b>: pos must be a valid iterator of *this.
1647 //! <b>Effects</b>: Insert a copy of the [il.begin(), il.end()) range before pos.
1649 //! <b>Returns</b>: an iterator to the first inserted element or pos if il.begin() == il.end().
1651 //! <b>Throws</b>: If memory allocation throws, T's constructor from a
1652 //! dereferenced std::initializer_list throws or T's copy constructor throws.
1654 //! <b>Complexity</b>: Linear to distance [il.begin(), il.end()).
1655 BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator pos, std::initializer_list<value_type> il)
1657 //Range check os pos is done in insert()
1658 return insert(pos, il.begin(), il.end());
1662 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1663 template <class FwdIt>
1664 BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, FwdIt first, FwdIt last
1665 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1666 , typename dtl::disable_if_or
1668 , dtl::is_convertible<FwdIt, size_type>
1669 , dtl::is_input_iterator<FwdIt>
1674 BOOST_ASSERT(this->priv_in_range_or_end(p));
1675 dtl::insert_range_proxy<ValAllocator, FwdIt, iterator> proxy(first);
1676 return priv_insert_aux_impl(p, boost::container::iterator_distance(first, last), proxy);
1680 //! <b>Effects</b>: Removes the first element from the deque.
1682 //! <b>Throws</b>: Nothing.
1684 //! <b>Complexity</b>: Constant time.
1685 void pop_front() BOOST_NOEXCEPT_OR_NOTHROW
1687 BOOST_ASSERT(!this->empty());
1688 if (this->members_.m_start.m_cur != this->members_.m_start.m_last - 1) {
1689 allocator_traits_type::destroy
1691 , boost::movelib::to_raw_pointer(this->members_.m_start.m_cur)
1693 ++this->members_.m_start.m_cur;
1696 this->priv_pop_front_aux();
1699 //! <b>Effects</b>: Removes the last element from the deque.
1701 //! <b>Throws</b>: Nothing.
1703 //! <b>Complexity</b>: Constant time.
1704 void pop_back() BOOST_NOEXCEPT_OR_NOTHROW
1706 BOOST_ASSERT(!this->empty());
1707 if (this->members_.m_finish.m_cur != this->members_.m_finish.m_first) {
1708 --this->members_.m_finish.m_cur;
1709 allocator_traits_type::destroy
1711 , boost::movelib::to_raw_pointer(this->members_.m_finish.m_cur)
1715 this->priv_pop_back_aux();
1718 //! <b>Effects</b>: Erases the element at p.
1720 //! <b>Throws</b>: Nothing.
1722 //! <b>Complexity</b>: Linear to the elements between pos and the
1723 //! last element (if pos is near the end) or the first element
1724 //! if(pos is near the beginning).
1725 //! Constant if pos is the first or the last element.
1726 iterator erase(const_iterator pos) BOOST_NOEXCEPT_OR_NOTHROW
1728 BOOST_ASSERT(this->priv_in_range(pos));
1729 iterator next = pos.unconst();
1731 size_type index = pos - this->members_.m_start;
1732 if (index < (this->size()/2)) {
1733 boost::container::move_backward(this->begin(), pos.unconst(), next);
1737 boost::container::move(next, this->end(), pos.unconst());
1740 return this->members_.m_start + index;
1743 //! <b>Effects</b>: Erases the elements pointed by [first, last).
1745 //! <b>Throws</b>: Nothing.
1747 //! <b>Complexity</b>: Linear to the distance between first and
1748 //! last plus the elements between pos and the
1749 //! last element (if pos is near the end) or the first element
1750 //! if(pos is near the beginning).
1751 iterator erase(const_iterator first, const_iterator last) BOOST_NOEXCEPT_OR_NOTHROW
1753 BOOST_ASSERT(first == last ||
1754 (first < last && this->priv_in_range(first) && this->priv_in_range_or_end(last)));
1755 if (first == this->members_.m_start && last == this->members_.m_finish) {
1757 return this->members_.m_finish;
1760 const size_type n = static_cast<size_type>(last - first);
1761 const size_type elems_before = static_cast<size_type>(first - this->members_.m_start);
1762 if (elems_before < (this->size() - n) - elems_before) {
1763 boost::container::move_backward(begin(), first.unconst(), last.unconst());
1764 iterator new_start = this->members_.m_start + n;
1765 this->priv_destroy_range(this->members_.m_start, new_start);
1766 this->priv_destroy_nodes(this->members_.m_start.m_node, new_start.m_node);
1767 this->members_.m_start = new_start;
1770 boost::container::move(last.unconst(), end(), first.unconst());
1771 iterator new_finish = this->members_.m_finish - n;
1772 this->priv_destroy_range(new_finish, this->members_.m_finish);
1773 this->priv_destroy_nodes(new_finish.m_node + 1, this->members_.m_finish.m_node + 1);
1774 this->members_.m_finish = new_finish;
1776 return this->members_.m_start + elems_before;
1780 //! <b>Effects</b>: Swaps the contents of *this and x.
1782 //! <b>Throws</b>: Nothing.
1784 //! <b>Complexity</b>: Constant.
1785 BOOST_CONTAINER_FORCEINLINE void swap(deque &x)
1786 BOOST_NOEXCEPT_IF(allocator_traits_type::propagate_on_container_swap::value
1787 || allocator_traits_type::is_always_equal::value)
1789 this->swap_members(x);
1790 dtl::bool_<allocator_traits_type::propagate_on_container_swap::value> flag;
1791 dtl::swap_alloc(this->alloc(), x.alloc(), flag);
1792 dtl::swap_alloc(this->ptr_alloc(), x.ptr_alloc(), flag);
1795 //! <b>Effects</b>: Erases all the elements of the deque.
1797 //! <b>Throws</b>: Nothing.
1799 //! <b>Complexity</b>: Linear to the number of elements in the deque.
1800 void clear() BOOST_NOEXCEPT_OR_NOTHROW
1802 for (index_pointer node = this->members_.m_start.m_node + 1;
1803 node < this->members_.m_finish.m_node;
1805 this->priv_destroy_range(*node, *node + get_block_size());
1806 this->priv_deallocate_node(*node);
1809 if (this->members_.m_start.m_node != this->members_.m_finish.m_node) {
1810 this->priv_destroy_range(this->members_.m_start.m_cur, this->members_.m_start.m_last);
1811 this->priv_destroy_range(this->members_.m_finish.m_first, this->members_.m_finish.m_cur);
1812 this->priv_deallocate_node(this->members_.m_finish.m_first);
1815 this->priv_destroy_range(this->members_.m_start.m_cur, this->members_.m_finish.m_cur);
1817 this->members_.m_finish = this->members_.m_start;
1820 //! <b>Effects</b>: Returns true if x and y are equal
1822 //! <b>Complexity</b>: Linear to the number of elements in the container.
1823 BOOST_CONTAINER_FORCEINLINE friend bool operator==(const deque& x, const deque& y)
1824 { return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin()); }
1826 //! <b>Effects</b>: Returns true if x and y are unequal
1828 //! <b>Complexity</b>: Linear to the number of elements in the container.
1829 BOOST_CONTAINER_FORCEINLINE friend bool operator!=(const deque& x, const deque& y)
1830 { return !(x == y); }
1832 //! <b>Effects</b>: Returns true if x is less than y
1834 //! <b>Complexity</b>: Linear to the number of elements in the container.
1835 BOOST_CONTAINER_FORCEINLINE friend bool operator<(const deque& x, const deque& y)
1836 { return ::boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); }
1838 //! <b>Effects</b>: Returns true if x is greater than y
1840 //! <b>Complexity</b>: Linear to the number of elements in the container.
1841 BOOST_CONTAINER_FORCEINLINE friend bool operator>(const deque& x, const deque& y)
1844 //! <b>Effects</b>: Returns true if x is equal or less than y
1846 //! <b>Complexity</b>: Linear to the number of elements in the container.
1847 BOOST_CONTAINER_FORCEINLINE friend bool operator<=(const deque& x, const deque& y)
1848 { return !(y < x); }
1850 //! <b>Effects</b>: Returns true if x is equal or greater than y
1852 //! <b>Complexity</b>: Linear to the number of elements in the container.
1853 BOOST_CONTAINER_FORCEINLINE friend bool operator>=(const deque& x, const deque& y)
1854 { return !(x < y); }
1856 //! <b>Effects</b>: x.swap(y)
1858 //! <b>Complexity</b>: Constant.
1859 BOOST_CONTAINER_FORCEINLINE friend void swap(deque& x, deque& y)
1862 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1865 BOOST_CONTAINER_FORCEINLINE size_type priv_index_of(const_iterator p) const
1867 BOOST_ASSERT(this->cbegin() <= p);
1868 BOOST_ASSERT(p <= this->cend());
1869 return static_cast<size_type>(p - this->cbegin());
1872 void priv_erase_last_n(size_type n)
1874 if(n == this->size()) {
1878 iterator new_finish = this->members_.m_finish - n;
1879 this->priv_destroy_range(new_finish, this->members_.m_finish);
1880 this->priv_destroy_nodes(new_finish.m_node + 1, this->members_.m_finish.m_node + 1);
1881 this->members_.m_finish = new_finish;
1885 void priv_throw_if_out_of_range(size_type n) const
1887 if (n >= this->size())
1888 throw_out_of_range("deque::at out of range");
1891 BOOST_CONTAINER_FORCEINLINE bool priv_in_range(const_iterator pos) const
1893 return (this->begin() <= pos) && (pos < this->end());
1896 BOOST_CONTAINER_FORCEINLINE bool priv_in_range_or_end(const_iterator pos) const
1898 return (this->begin() <= pos) && (pos <= this->end());
1902 iterator priv_insert(const_iterator p, BOOST_FWD_REF(U) x)
1904 BOOST_ASSERT(this->priv_in_range_or_end(p));
1906 this->push_front(::boost::forward<U>(x));
1909 else if (p == cend()){
1910 this->push_back(::boost::forward<U>(x));
1914 return priv_insert_aux_impl
1916 , dtl::get_insert_value_proxy<iterator, ValAllocator>(::boost::forward<U>(x)));
1921 void priv_push_front(BOOST_FWD_REF(U) x)
1923 if(this->priv_push_front_simple_available()){
1924 allocator_traits_type::construct
1925 ( this->alloc(), this->priv_push_front_simple_pos(), ::boost::forward<U>(x));
1926 this->priv_push_front_simple_commit();
1929 priv_insert_aux_impl
1930 ( this->cbegin(), (size_type)1
1931 , dtl::get_insert_value_proxy<iterator, ValAllocator>(::boost::forward<U>(x)));
1936 void priv_push_back(BOOST_FWD_REF(U) x)
1938 if(this->priv_push_back_simple_available()){
1939 allocator_traits_type::construct
1940 ( this->alloc(), this->priv_push_back_simple_pos(), ::boost::forward<U>(x));
1941 this->priv_push_back_simple_commit();
1944 priv_insert_aux_impl
1945 ( this->cend(), (size_type)1
1946 , dtl::get_insert_value_proxy<iterator, ValAllocator>(::boost::forward<U>(x)));
1950 BOOST_CONTAINER_FORCEINLINE bool priv_push_back_simple_available() const
1952 return this->members_.m_map &&
1953 (this->members_.m_finish.m_cur != (this->members_.m_finish.m_last - 1));
1956 BOOST_CONTAINER_FORCEINLINE T *priv_push_back_simple_pos() const
1958 return boost::movelib::to_raw_pointer(this->members_.m_finish.m_cur);
1961 BOOST_CONTAINER_FORCEINLINE void priv_push_back_simple_commit()
1963 ++this->members_.m_finish.m_cur;
1966 BOOST_CONTAINER_FORCEINLINE bool priv_push_front_simple_available() const
1968 return this->members_.m_map &&
1969 (this->members_.m_start.m_cur != this->members_.m_start.m_first);
1972 BOOST_CONTAINER_FORCEINLINE T *priv_push_front_simple_pos() const
1973 { return boost::movelib::to_raw_pointer(this->members_.m_start.m_cur) - 1; }
1975 BOOST_CONTAINER_FORCEINLINE void priv_push_front_simple_commit()
1976 { --this->members_.m_start.m_cur; }
1978 void priv_destroy_range(iterator p, iterator p2)
1980 if(!Base::traits_t::trivial_dctr){
1982 allocator_traits_type::destroy(this->alloc(), boost::movelib::iterator_to_raw_pointer(p));
1987 void priv_destroy_range(pointer p, pointer p2)
1989 if(!Base::traits_t::trivial_dctr){
1991 allocator_traits_type::destroy(this->alloc(), boost::movelib::iterator_to_raw_pointer(p));
1996 template<class InsertProxy>
1997 iterator priv_insert_aux_impl(const_iterator p, size_type n, InsertProxy proxy)
1999 iterator pos(p.unconst());
2000 const size_type pos_n = p - this->cbegin();
2001 if(!this->members_.m_map){
2002 this->priv_initialize_map(0);
2003 pos = this->begin();
2006 const size_type elemsbefore = static_cast<size_type>(pos - this->members_.m_start);
2007 const size_type length = this->size();
2008 if (elemsbefore < length / 2) {
2009 const iterator new_start = this->priv_reserve_elements_at_front(n);
2010 const iterator old_start = this->members_.m_start;
2012 proxy.uninitialized_copy_n_and_update(this->alloc(), new_start, n);
2013 this->members_.m_start = new_start;
2016 pos = this->members_.m_start + elemsbefore;
2017 if (elemsbefore >= n) {
2018 const iterator start_n = this->members_.m_start + n;
2019 ::boost::container::uninitialized_move_alloc
2020 (this->alloc(), this->members_.m_start, start_n, new_start);
2021 this->members_.m_start = new_start;
2022 boost::container::move(start_n, pos, old_start);
2023 proxy.copy_n_and_update(this->alloc(), pos - n, n);
2026 const size_type mid_count = n - elemsbefore;
2027 const iterator mid_start = old_start - mid_count;
2028 proxy.uninitialized_copy_n_and_update(this->alloc(), mid_start, mid_count);
2029 this->members_.m_start = mid_start;
2030 ::boost::container::uninitialized_move_alloc
2031 (this->alloc(), old_start, pos, new_start);
2032 this->members_.m_start = new_start;
2033 proxy.copy_n_and_update(this->alloc(), old_start, elemsbefore);
2038 const iterator new_finish = this->priv_reserve_elements_at_back(n);
2039 const iterator old_finish = this->members_.m_finish;
2040 const size_type elemsafter = length - elemsbefore;
2042 proxy.uninitialized_copy_n_and_update(this->alloc(), old_finish, n);
2043 this->members_.m_finish = new_finish;
2046 pos = old_finish - elemsafter;
2047 if (elemsafter >= n) {
2048 iterator finish_n = old_finish - difference_type(n);
2049 ::boost::container::uninitialized_move_alloc
2050 (this->alloc(), finish_n, old_finish, old_finish);
2051 this->members_.m_finish = new_finish;
2052 boost::container::move_backward(pos, finish_n, old_finish);
2053 proxy.copy_n_and_update(this->alloc(), pos, n);
2056 const size_type raw_gap = n - elemsafter;
2057 ::boost::container::uninitialized_move_alloc
2058 (this->alloc(), pos, old_finish, old_finish + raw_gap);
2060 proxy.copy_n_and_update(this->alloc(), pos, elemsafter);
2061 proxy.uninitialized_copy_n_and_update(this->alloc(), old_finish, raw_gap);
2064 this->priv_destroy_range(old_finish, old_finish + elemsafter);
2068 this->members_.m_finish = new_finish;
2072 return this->begin() + pos_n;
2075 template <class InsertProxy>
2076 iterator priv_insert_back_aux_impl(size_type n, InsertProxy proxy)
2078 if(!this->members_.m_map){
2079 this->priv_initialize_map(0);
2082 iterator new_finish = this->priv_reserve_elements_at_back(n);
2083 iterator old_finish = this->members_.m_finish;
2084 proxy.uninitialized_copy_n_and_update(this->alloc(), old_finish, n);
2085 this->members_.m_finish = new_finish;
2086 return iterator(this->members_.m_finish - n);
2089 template <class InsertProxy>
2090 iterator priv_insert_front_aux_impl(size_type n, InsertProxy proxy)
2092 if(!this->members_.m_map){
2093 this->priv_initialize_map(0);
2096 iterator new_start = this->priv_reserve_elements_at_front(n);
2097 proxy.uninitialized_copy_n_and_update(this->alloc(), new_start, n);
2098 this->members_.m_start = new_start;
2102 BOOST_CONTAINER_FORCEINLINE iterator priv_fill_insert(const_iterator pos, size_type n, const value_type& x)
2104 typedef constant_iterator<value_type, difference_type> c_it;
2105 return this->insert(pos, c_it(x, n), c_it());
2108 // Precondition: this->members_.m_start and this->members_.m_finish have already been initialized,
2109 // but none of the deque's elements have yet been constructed.
2110 void priv_fill_initialize(const value_type& value)
2112 index_pointer cur = this->members_.m_start.m_node;
2114 for ( ; cur < this->members_.m_finish.m_node; ++cur){
2115 boost::container::uninitialized_fill_alloc
2116 (this->alloc(), *cur, *cur + get_block_size(), value);
2118 boost::container::uninitialized_fill_alloc
2119 (this->alloc(), this->members_.m_finish.m_first, this->members_.m_finish.m_cur, value);
2122 this->priv_destroy_range(this->members_.m_start, iterator(*cur, cur, get_block_size()));
2128 template <class InIt>
2129 void priv_range_initialize(InIt first, InIt last, typename iterator_enable_if_tag<InIt, std::input_iterator_tag>::type* =0)
2131 this->priv_initialize_map(0);
2133 for ( ; first != last; ++first)
2134 this->emplace_back(*first);
2143 template <class FwdIt>
2144 void priv_range_initialize(FwdIt first, FwdIt last, typename iterator_disable_if_tag<FwdIt, std::input_iterator_tag>::type* =0)
2147 n = boost::container::iterator_distance(first, last);
2148 this->priv_initialize_map(n);
2150 index_pointer cur_node = this->members_.m_start.m_node;
2152 for (; cur_node < this->members_.m_finish.m_node; ++cur_node) {
2154 boost::container::iterator_advance(mid, get_block_size());
2155 ::boost::container::uninitialized_copy_alloc(this->alloc(), first, mid, *cur_node);
2158 ::boost::container::uninitialized_copy_alloc(this->alloc(), first, last, this->members_.m_finish.m_first);
2161 this->priv_destroy_range(this->members_.m_start, iterator(*cur_node, cur_node, get_block_size()));
2167 // Called only if this->members_.m_finish.m_cur == this->members_.m_finish.m_first.
2168 void priv_pop_back_aux() BOOST_NOEXCEPT_OR_NOTHROW
2170 this->priv_deallocate_node(this->members_.m_finish.m_first);
2171 this->members_.m_finish.priv_set_node(this->members_.m_finish.m_node - 1, get_block_size());
2172 this->members_.m_finish.m_cur = this->members_.m_finish.m_last - 1;
2173 allocator_traits_type::destroy
2175 , boost::movelib::to_raw_pointer(this->members_.m_finish.m_cur)
2179 // Called only if this->members_.m_start.m_cur == this->members_.m_start.m_last - 1. Note that
2180 // if the deque has at least one element (a precondition for this member
2181 // function), and if this->members_.m_start.m_cur == this->members_.m_start.m_last, then the deque
2182 // must have at least two nodes.
2183 void priv_pop_front_aux() BOOST_NOEXCEPT_OR_NOTHROW
2185 allocator_traits_type::destroy
2187 , boost::movelib::to_raw_pointer(this->members_.m_start.m_cur)
2189 this->priv_deallocate_node(this->members_.m_start.m_first);
2190 this->members_.m_start.priv_set_node(this->members_.m_start.m_node + 1, get_block_size());
2191 this->members_.m_start.m_cur = this->members_.m_start.m_first;
2194 iterator priv_reserve_elements_at_front(size_type n)
2196 size_type vacancies = this->members_.m_start.m_cur - this->members_.m_start.m_first;
2198 size_type new_elems = n-vacancies;
2199 size_type new_nodes = (new_elems + get_block_size() - 1) /
2201 size_type s = (size_type)(this->members_.m_start.m_node - this->members_.m_map);
2203 this->priv_reallocate_map(new_nodes, true);
2207 for (; i <= new_nodes; ++i)
2208 *(this->members_.m_start.m_node - i) = this->priv_allocate_node();
2211 for (size_type j = 1; j < i; ++j)
2212 this->priv_deallocate_node(*(this->members_.m_start.m_node - j));
2217 return this->members_.m_start - difference_type(n);
2220 iterator priv_reserve_elements_at_back(size_type n)
2222 size_type vacancies = (this->members_.m_finish.m_last - this->members_.m_finish.m_cur) - 1;
2224 size_type new_elems = n - vacancies;
2225 size_type new_nodes = (new_elems + get_block_size() - 1)/get_block_size();
2226 size_type s = (size_type)(this->members_.m_map_size - (this->members_.m_finish.m_node - this->members_.m_map));
2227 if (new_nodes + 1 > s){
2228 this->priv_reallocate_map(new_nodes, false);
2232 for (; i <= new_nodes; ++i)
2233 *(this->members_.m_finish.m_node + i) = this->priv_allocate_node();
2236 for (size_type j = 1; j < i; ++j)
2237 this->priv_deallocate_node(*(this->members_.m_finish.m_node + j));
2242 return this->members_.m_finish + difference_type(n);
2245 void priv_reallocate_map(size_type nodes_to_add, bool add_at_front)
2247 size_type old_num_nodes = this->members_.m_finish.m_node - this->members_.m_start.m_node + 1;
2248 size_type new_num_nodes = old_num_nodes + nodes_to_add;
2250 index_pointer new_nstart;
2251 if (this->members_.m_map_size > 2 * new_num_nodes) {
2252 new_nstart = this->members_.m_map + (this->members_.m_map_size - new_num_nodes) / 2
2253 + (add_at_front ? nodes_to_add : 0);
2254 if (new_nstart < this->members_.m_start.m_node)
2255 boost::container::move(this->members_.m_start.m_node, this->members_.m_finish.m_node + 1, new_nstart);
2257 boost::container::move_backward
2258 (this->members_.m_start.m_node, this->members_.m_finish.m_node + 1, new_nstart + old_num_nodes);
2261 size_type new_map_size =
2262 this->members_.m_map_size + dtl::max_value(this->members_.m_map_size, nodes_to_add) + 2;
2264 index_pointer new_map = this->priv_allocate_map(new_map_size);
2265 new_nstart = new_map + (new_map_size - new_num_nodes) / 2
2266 + (add_at_front ? nodes_to_add : 0);
2267 boost::container::move(this->members_.m_start.m_node, this->members_.m_finish.m_node + 1, new_nstart);
2268 this->priv_deallocate_map(this->members_.m_map, this->members_.m_map_size);
2270 this->members_.m_map = new_map;
2271 this->members_.m_map_size = new_map_size;
2274 this->members_.m_start.priv_set_node(new_nstart, get_block_size());
2275 this->members_.m_finish.priv_set_node(new_nstart + old_num_nodes - 1, get_block_size());
2277 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
2280 #ifndef BOOST_CONTAINER_NO_CXX17_CTAD
2281 template <typename InputIterator>
2282 deque(InputIterator, InputIterator) -> deque<typename iterator_traits<InputIterator>::value_type>;
2283 template <typename InputIterator, typename Allocator>
2284 deque(InputIterator, InputIterator, Allocator const&) -> deque<typename iterator_traits<InputIterator>::value_type, Allocator>;
2289 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
2293 //!has_trivial_destructor_after_move<> == true_type
2294 //!specialization for optimizations
2295 template <class T, class Allocator, class Options>
2296 struct has_trivial_destructor_after_move<boost::container::deque<T, Allocator, Options> >
2298 typedef typename boost::container::deque<T, Allocator, Options>::allocator_type allocator_type;
2299 typedef typename ::boost::container::allocator_traits<allocator_type>::pointer pointer;
2300 static const bool value = ::boost::has_trivial_destructor_after_move<allocator_type>::value &&
2301 ::boost::has_trivial_destructor_after_move<pointer>::value;
2306 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
2308 #include <boost/container/detail/config_end.hpp>
2310 #endif // #ifndef BOOST_CONTAINER_DEQUE_HPP