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>
29 #include <boost/container/detail/advanced_insert_int.hpp>
30 #include <boost/container/detail/algorithm.hpp> //algo_equal(), algo_lexicographical_compare
31 #include <boost/container/detail/alloc_helpers.hpp>
32 #include <boost/container/detail/copy_move_algo.hpp>
33 #include <boost/container/detail/iterator.hpp>
34 #include <boost/container/detail/iterator_to_raw_pointer.hpp>
35 #include <boost/container/detail/iterators.hpp>
36 #include <boost/container/detail/min_max.hpp>
37 #include <boost/container/detail/mpl.hpp>
38 #include <boost/container/detail/to_raw_pointer.hpp>
39 #include <boost/container/detail/type_traits.hpp>
41 #include <boost/move/adl_move_swap.hpp>
42 #include <boost/move/iterator.hpp>
43 #include <boost/move/traits.hpp>
44 #include <boost/move/utility_core.hpp>
46 #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
47 #include <boost/move/detail/fwd_macros.hpp>
49 #include <boost/move/detail/move_helpers.hpp>
51 #include <boost/assert.hpp>
52 #include <boost/core/no_exceptions_support.hpp>
56 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
57 #include <initializer_list>
63 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
64 template <class T, class Allocator>
68 struct deque_value_traits
71 static const bool trivial_dctr = container_detail::is_trivially_destructible<value_type>::value;
72 static const bool trivial_dctr_after_move = ::boost::has_trivial_destructor_after_move<value_type>::value;
75 // Note: this function is simply a kludge to work around several compilers'
76 // bugs in handling constant expressions.
80 static const std::size_t min_size = 512u;
81 static const std::size_t sizeof_t = sizeof(T);
82 static const std::size_t value = sizeof_t < min_size ? (min_size/sizeof_t) : std::size_t(1);
85 namespace container_detail {
88 // For any nonsingular iterator i:
89 // i.node is the address of an element in the map array. The
90 // contents of i.node is a pointer to the beginning of a node.
91 // i.first == //(i.node)
92 // i.last == i.first + node_size
93 // i.cur is a pointer in the range [i.first, i.last). NOTE:
94 // the implication of this is that i.cur is always a dereferenceable
95 // pointer, even if i is a past-the-end iterator.
96 // Start and Finish are always nonsingular iterators. NOTE: this means
97 // that an empty deque must have one node, and that a deque
98 // with N elements, where N is the buffer size, must have two nodes.
99 // For every node other than start.node and finish.node, every element
100 // in the node is an initialized object. If start.node == finish.node,
101 // then [start.cur, finish.cur) are initialized objects, and
102 // the elements outside that range are uninitialized storage. Otherwise,
103 // [start.cur, start.last) and [finish.first, finish.cur) are initialized
104 // objects, and [start.first, start.cur) and [finish.cur, finish.last)
105 // are uninitialized storage.
106 // [map, map + map_size) is a valid, non-empty range.
107 // [start.node, finish.node] is a valid range contained within
108 // [map, map + map_size).
109 // A pointer in the range [map, map + map_size) points to an allocated node
110 // if and only if the pointer is in the range [start.node, finish.node].
111 template<class Pointer, bool IsConst>
115 typedef std::random_access_iterator_tag iterator_category;
116 typedef typename boost::intrusive::pointer_traits<Pointer>::element_type value_type;
117 typedef typename boost::intrusive::pointer_traits<Pointer>::difference_type difference_type;
118 typedef typename if_c
120 , typename boost::intrusive::pointer_traits<Pointer>::template
121 rebind_pointer<const value_type>::type
124 typedef typename if_c
130 static std::size_t s_buffer_size()
131 { return deque_buf_size<value_type>::value; }
133 typedef Pointer val_alloc_ptr;
134 typedef typename boost::intrusive::pointer_traits<Pointer>::
135 template rebind_pointer<Pointer>::type index_pointer;
140 index_pointer m_node;
144 Pointer get_cur() const { return m_cur; }
145 Pointer get_first() const { return m_first; }
146 Pointer get_last() const { return m_last; }
147 index_pointer get_node() const { return m_node; }
149 deque_iterator(val_alloc_ptr x, index_pointer y) BOOST_NOEXCEPT_OR_NOTHROW
150 : m_cur(x), m_first(*y), m_last(*y + s_buffer_size()), m_node(y)
153 deque_iterator() BOOST_NOEXCEPT_OR_NOTHROW
154 : m_cur(), m_first(), m_last(), m_node() //Value initialization to achieve "null iterators" (N3644)
157 deque_iterator(deque_iterator<Pointer, false> const& x) BOOST_NOEXCEPT_OR_NOTHROW
158 : m_cur(x.get_cur()), m_first(x.get_first()), m_last(x.get_last()), m_node(x.get_node())
161 deque_iterator(Pointer cur, Pointer first, Pointer last, index_pointer node) BOOST_NOEXCEPT_OR_NOTHROW
162 : m_cur(cur), m_first(first), m_last(last), m_node(node)
165 deque_iterator<Pointer, false> unconst() const BOOST_NOEXCEPT_OR_NOTHROW
167 return deque_iterator<Pointer, false>(this->get_cur(), this->get_first(), this->get_last(), this->get_node());
170 reference operator*() const BOOST_NOEXCEPT_OR_NOTHROW
171 { return *this->m_cur; }
173 pointer operator->() const BOOST_NOEXCEPT_OR_NOTHROW
174 { return this->m_cur; }
176 difference_type operator-(const deque_iterator& x) const BOOST_NOEXCEPT_OR_NOTHROW
178 if(!this->m_cur && !x.m_cur){
181 return difference_type(this->s_buffer_size()) * (this->m_node - x.m_node - 1) +
182 (this->m_cur - this->m_first) + (x.m_last - x.m_cur);
185 deque_iterator& operator++() BOOST_NOEXCEPT_OR_NOTHROW
188 if (this->m_cur == this->m_last) {
189 this->priv_set_node(this->m_node + 1);
190 this->m_cur = this->m_first;
195 deque_iterator operator++(int) BOOST_NOEXCEPT_OR_NOTHROW
197 deque_iterator tmp(*this);
202 deque_iterator& operator--() BOOST_NOEXCEPT_OR_NOTHROW
204 if (this->m_cur == this->m_first) {
205 this->priv_set_node(this->m_node - 1);
206 this->m_cur = this->m_last;
212 deque_iterator operator--(int) BOOST_NOEXCEPT_OR_NOTHROW
214 deque_iterator tmp(*this);
219 deque_iterator& operator+=(difference_type n) BOOST_NOEXCEPT_OR_NOTHROW
221 difference_type offset = n + (this->m_cur - this->m_first);
222 if (offset >= 0 && offset < difference_type(this->s_buffer_size()))
225 difference_type node_offset =
226 offset > 0 ? offset / difference_type(this->s_buffer_size())
227 : -difference_type((-offset - 1) / this->s_buffer_size()) - 1;
228 this->priv_set_node(this->m_node + node_offset);
229 this->m_cur = this->m_first +
230 (offset - node_offset * difference_type(this->s_buffer_size()));
235 deque_iterator operator+(difference_type n) const BOOST_NOEXCEPT_OR_NOTHROW
236 { deque_iterator tmp(*this); return tmp += n; }
238 deque_iterator& operator-=(difference_type n) BOOST_NOEXCEPT_OR_NOTHROW
239 { return *this += -n; }
241 deque_iterator operator-(difference_type n) const BOOST_NOEXCEPT_OR_NOTHROW
242 { deque_iterator tmp(*this); return tmp -= n; }
244 reference operator[](difference_type n) const BOOST_NOEXCEPT_OR_NOTHROW
245 { return *(*this + n); }
247 friend bool operator==(const deque_iterator& l, const deque_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
248 { return l.m_cur == r.m_cur; }
250 friend bool operator!=(const deque_iterator& l, const deque_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
251 { return l.m_cur != r.m_cur; }
253 friend bool operator<(const deque_iterator& l, const deque_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
254 { return (l.m_node == r.m_node) ? (l.m_cur < r.m_cur) : (l.m_node < r.m_node); }
256 friend bool operator>(const deque_iterator& l, const deque_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
259 friend bool operator<=(const deque_iterator& l, const deque_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
262 friend bool operator>=(const deque_iterator& l, const deque_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
265 void priv_set_node(index_pointer new_node) BOOST_NOEXCEPT_OR_NOTHROW
267 this->m_node = new_node;
268 this->m_first = *new_node;
269 this->m_last = this->m_first + this->s_buffer_size();
272 friend deque_iterator operator+(difference_type n, deque_iterator x) BOOST_NOEXCEPT_OR_NOTHROW
276 } //namespace container_detail {
278 // Deque base class. It has two purposes. First, its constructor
279 // and destructor allocate (but don't initialize) storage. This makes
280 // exception safety easier.
281 template <class Allocator>
284 BOOST_COPYABLE_AND_MOVABLE(deque_base)
286 typedef allocator_traits<Allocator> val_alloc_traits_type;
287 typedef typename val_alloc_traits_type::value_type val_alloc_val;
288 typedef typename val_alloc_traits_type::pointer val_alloc_ptr;
289 typedef typename val_alloc_traits_type::const_pointer val_alloc_cptr;
290 typedef typename val_alloc_traits_type::reference val_alloc_ref;
291 typedef typename val_alloc_traits_type::const_reference val_alloc_cref;
292 typedef typename val_alloc_traits_type::difference_type val_alloc_diff;
293 typedef typename val_alloc_traits_type::size_type val_alloc_size;
294 typedef typename val_alloc_traits_type::template
295 portable_rebind_alloc<val_alloc_ptr>::type ptr_alloc_t;
296 typedef allocator_traits<ptr_alloc_t> ptr_alloc_traits_type;
297 typedef typename ptr_alloc_traits_type::value_type ptr_alloc_val;
298 typedef typename ptr_alloc_traits_type::pointer ptr_alloc_ptr;
299 typedef typename ptr_alloc_traits_type::const_pointer ptr_alloc_cptr;
300 typedef typename ptr_alloc_traits_type::reference ptr_alloc_ref;
301 typedef typename ptr_alloc_traits_type::const_reference ptr_alloc_cref;
302 typedef Allocator allocator_type;
303 typedef allocator_type stored_allocator_type;
304 typedef val_alloc_size size_type;
308 typedef deque_value_traits<val_alloc_val> traits_t;
309 typedef ptr_alloc_t map_allocator_type;
311 static size_type s_buffer_size() BOOST_NOEXCEPT_OR_NOTHROW
312 { return deque_buf_size<val_alloc_val>::value; }
314 val_alloc_ptr priv_allocate_node()
315 { return this->alloc().allocate(s_buffer_size()); }
317 void priv_deallocate_node(val_alloc_ptr p) BOOST_NOEXCEPT_OR_NOTHROW
318 { this->alloc().deallocate(p, s_buffer_size()); }
320 ptr_alloc_ptr priv_allocate_map(size_type n)
321 { return this->ptr_alloc().allocate(n); }
323 void priv_deallocate_map(ptr_alloc_ptr p, size_type n) BOOST_NOEXCEPT_OR_NOTHROW
324 { this->ptr_alloc().deallocate(p, n); }
326 typedef container_detail::deque_iterator<val_alloc_ptr, false> iterator;
327 typedef container_detail::deque_iterator<val_alloc_ptr, true > const_iterator;
329 deque_base(size_type num_elements, const allocator_type& a)
331 { this->priv_initialize_map(num_elements); }
333 explicit deque_base(const allocator_type& a)
341 explicit deque_base(BOOST_RV_REF(deque_base) x)
342 : members_( boost::move(x.ptr_alloc())
343 , boost::move(x.alloc()) )
348 if (this->members_.m_map) {
349 this->priv_destroy_nodes(this->members_.m_start.m_node, this->members_.m_finish.m_node + 1);
350 this->priv_deallocate_map(this->members_.m_map, this->members_.m_map_size);
355 deque_base(const deque_base&);
359 void swap_members(deque_base &x) BOOST_NOEXCEPT_OR_NOTHROW
361 ::boost::adl_move_swap(this->members_.m_start, x.members_.m_start);
362 ::boost::adl_move_swap(this->members_.m_finish, x.members_.m_finish);
363 ::boost::adl_move_swap(this->members_.m_map, x.members_.m_map);
364 ::boost::adl_move_swap(this->members_.m_map_size, x.members_.m_map_size);
367 void priv_initialize_map(size_type num_elements)
370 size_type num_nodes = num_elements / s_buffer_size() + 1;
372 this->members_.m_map_size = container_detail::max_value((size_type) InitialMapSize, num_nodes + 2);
373 this->members_.m_map = this->priv_allocate_map(this->members_.m_map_size);
375 ptr_alloc_ptr nstart = this->members_.m_map + (this->members_.m_map_size - num_nodes) / 2;
376 ptr_alloc_ptr nfinish = nstart + num_nodes;
379 this->priv_create_nodes(nstart, nfinish);
382 this->priv_deallocate_map(this->members_.m_map, this->members_.m_map_size);
383 this->members_.m_map = 0;
384 this->members_.m_map_size = 0;
389 this->members_.m_start.priv_set_node(nstart);
390 this->members_.m_finish.priv_set_node(nfinish - 1);
391 this->members_.m_start.m_cur = this->members_.m_start.m_first;
392 this->members_.m_finish.m_cur = this->members_.m_finish.m_first +
393 num_elements % s_buffer_size();
397 void priv_create_nodes(ptr_alloc_ptr nstart, ptr_alloc_ptr nfinish)
399 ptr_alloc_ptr cur = nstart;
401 for (; cur < nfinish; ++cur)
402 *cur = this->priv_allocate_node();
405 this->priv_destroy_nodes(nstart, cur);
411 void priv_destroy_nodes(ptr_alloc_ptr nstart, ptr_alloc_ptr nfinish) BOOST_NOEXCEPT_OR_NOTHROW
413 for (ptr_alloc_ptr n = nstart; n < nfinish; ++n)
414 this->priv_deallocate_node(*n);
417 void priv_clear_map() BOOST_NOEXCEPT_OR_NOTHROW
419 if (this->members_.m_map) {
420 this->priv_destroy_nodes(this->members_.m_start.m_node, this->members_.m_finish.m_node + 1);
421 this->priv_deallocate_map(this->members_.m_map, this->members_.m_map_size);
422 this->members_.m_map = 0;
423 this->members_.m_map_size = 0;
424 this->members_.m_start = iterator();
425 this->members_.m_finish = this->members_.m_start;
429 enum { InitialMapSize = 8 };
432 struct members_holder
434 , public allocator_type
437 : map_allocator_type(), allocator_type()
438 , m_map(0), m_map_size(0)
439 , m_start(), m_finish(m_start)
442 explicit members_holder(const allocator_type &a)
443 : map_allocator_type(a), allocator_type(a)
444 , m_map(0), m_map_size(0)
445 , m_start(), m_finish(m_start)
448 template<class ValAllocConvertible, class PtrAllocConvertible>
449 members_holder(BOOST_FWD_REF(PtrAllocConvertible) pa, BOOST_FWD_REF(ValAllocConvertible) va)
450 : map_allocator_type(boost::forward<PtrAllocConvertible>(pa))
451 , allocator_type (boost::forward<ValAllocConvertible>(va))
452 , m_map(0), m_map_size(0)
453 , m_start(), m_finish(m_start)
457 val_alloc_size m_map_size;
462 ptr_alloc_t &ptr_alloc() BOOST_NOEXCEPT_OR_NOTHROW
465 const ptr_alloc_t &ptr_alloc() const BOOST_NOEXCEPT_OR_NOTHROW
468 allocator_type &alloc() BOOST_NOEXCEPT_OR_NOTHROW
471 const allocator_type &alloc() const BOOST_NOEXCEPT_OR_NOTHROW
474 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
476 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
477 //! A double-ended queue is a sequence that supports random access to elements, constant time insertion
478 //! and removal of elements at the end of the sequence, and linear time insertion and removal of elements in the middle.
480 //! \tparam T The type of object that is stored in the deque
481 //! \tparam Allocator The allocator used for all internal memory management
482 template <class T, class Allocator = new_allocator<T> >
484 template <class T, class Allocator>
486 class deque : protected deque_base<Allocator>
488 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
490 typedef deque_base<Allocator> Base;
491 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
495 //////////////////////////////////////////////
499 //////////////////////////////////////////////
501 typedef T value_type;
502 typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer;
503 typedef typename ::boost::container::allocator_traits<Allocator>::const_pointer const_pointer;
504 typedef typename ::boost::container::allocator_traits<Allocator>::reference reference;
505 typedef typename ::boost::container::allocator_traits<Allocator>::const_reference const_reference;
506 typedef typename ::boost::container::allocator_traits<Allocator>::size_type size_type;
507 typedef typename ::boost::container::allocator_traits<Allocator>::difference_type difference_type;
508 typedef Allocator allocator_type;
509 typedef BOOST_CONTAINER_IMPDEF(allocator_type) stored_allocator_type;
510 typedef BOOST_CONTAINER_IMPDEF(typename Base::iterator) iterator;
511 typedef BOOST_CONTAINER_IMPDEF(typename Base::const_iterator) const_iterator;
512 typedef BOOST_CONTAINER_IMPDEF(boost::container::reverse_iterator<iterator>) reverse_iterator;
513 typedef BOOST_CONTAINER_IMPDEF(boost::container::reverse_iterator<const_iterator>) const_reverse_iterator;
515 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
517 private: // Internal typedefs
518 BOOST_COPYABLE_AND_MOVABLE(deque)
519 typedef typename Base::ptr_alloc_ptr index_pointer;
520 static size_type s_buffer_size()
521 { return Base::s_buffer_size(); }
522 typedef allocator_traits<Allocator> allocator_traits_type;
524 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
527 //////////////////////////////////////////////
529 // construct/copy/destroy
531 //////////////////////////////////////////////
533 //! <b>Effects</b>: Default constructors a deque.
535 //! <b>Throws</b>: If allocator_type's default constructor throws.
537 //! <b>Complexity</b>: Constant.
538 deque() BOOST_NOEXCEPT_IF(container_detail::is_nothrow_default_constructible<Allocator>::value)
542 //! <b>Effects</b>: Constructs a deque taking the allocator as parameter.
544 //! <b>Throws</b>: Nothing
546 //! <b>Complexity</b>: Constant.
547 explicit deque(const allocator_type& a) BOOST_NOEXCEPT_OR_NOTHROW
551 //! <b>Effects</b>: Constructs a deque
552 //! and inserts n value initialized values.
554 //! <b>Throws</b>: If allocator_type's default constructor
555 //! throws or T's value initialization throws.
557 //! <b>Complexity</b>: Linear to n.
558 explicit deque(size_type n)
559 : Base(n, allocator_type())
561 container_detail::insert_value_initialized_n_proxy<Allocator, iterator> proxy;
562 proxy.uninitialized_copy_n_and_update(this->alloc(), this->begin(), n);
563 //deque_base will deallocate in case of exception...
566 //! <b>Effects</b>: Constructs a deque
567 //! and inserts n default initialized values.
569 //! <b>Throws</b>: If allocator_type's default constructor
570 //! throws or T's default initialization or copy constructor throws.
572 //! <b>Complexity</b>: Linear to n.
574 //! <b>Note</b>: Non-standard extension
575 deque(size_type n, default_init_t)
576 : Base(n, allocator_type())
578 container_detail::insert_default_initialized_n_proxy<Allocator, iterator> proxy;
579 proxy.uninitialized_copy_n_and_update(this->alloc(), this->begin(), n);
580 //deque_base will deallocate in case of exception...
583 //! <b>Effects</b>: Constructs a deque that will use a copy of allocator a
584 //! and inserts n value initialized values.
586 //! <b>Throws</b>: If allocator_type's default constructor
587 //! throws or T's value initialization throws.
589 //! <b>Complexity</b>: Linear to n.
590 explicit deque(size_type n, const allocator_type &a)
593 container_detail::insert_value_initialized_n_proxy<Allocator, iterator> proxy;
594 proxy.uninitialized_copy_n_and_update(this->alloc(), this->begin(), n);
595 //deque_base will deallocate in case of exception...
598 //! <b>Effects</b>: Constructs a deque that will use a copy of allocator a
599 //! and inserts n default initialized values.
601 //! <b>Throws</b>: If allocator_type's default constructor
602 //! throws or T's default initialization or copy constructor throws.
604 //! <b>Complexity</b>: Linear to n.
606 //! <b>Note</b>: Non-standard extension
607 deque(size_type n, default_init_t, const allocator_type &a)
610 container_detail::insert_default_initialized_n_proxy<Allocator, iterator> proxy;
611 proxy.uninitialized_copy_n_and_update(this->alloc(), this->begin(), n);
612 //deque_base will deallocate in case of exception...
615 //! <b>Effects</b>: Constructs a deque that will use a copy of allocator a
616 //! and inserts n copies of value.
618 //! <b>Throws</b>: If allocator_type's default constructor
619 //! throws or T's copy constructor throws.
621 //! <b>Complexity</b>: Linear to n.
622 deque(size_type n, const value_type& value)
623 : Base(n, allocator_type())
624 { this->priv_fill_initialize(value); }
626 //! <b>Effects</b>: Constructs a deque that will use a copy of allocator a
627 //! and inserts n copies of value.
629 //! <b>Throws</b>: If allocator_type's default constructor
630 //! throws or T's copy constructor throws.
632 //! <b>Complexity</b>: Linear to n.
633 deque(size_type n, const value_type& value, const allocator_type& a)
635 { this->priv_fill_initialize(value); }
637 //! <b>Effects</b>: Constructs a deque that will use a copy of allocator a
638 //! and inserts a copy of the range [first, last) in the deque.
640 //! <b>Throws</b>: If allocator_type's default constructor
641 //! throws or T's constructor taking a dereferenced InIt throws.
643 //! <b>Complexity</b>: Linear to the range [first, last).
644 template <class InIt>
645 deque(InIt first, InIt last
646 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
647 , typename container_detail::disable_if_convertible
648 <InIt, size_type>::type * = 0
651 : Base(allocator_type())
653 this->priv_range_initialize(first, last);
656 //! <b>Effects</b>: Constructs a deque that will use a copy of allocator a
657 //! and inserts a copy of the range [first, last) in the deque.
659 //! <b>Throws</b>: If allocator_type's default constructor
660 //! throws or T's constructor taking a dereferenced InIt throws.
662 //! <b>Complexity</b>: Linear to the range [first, last).
663 template <class InIt>
664 deque(InIt first, InIt last, const allocator_type& a
665 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
666 , typename container_detail::disable_if_convertible
667 <InIt, size_type>::type * = 0
672 this->priv_range_initialize(first, last);
675 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
676 //! <b>Effects</b>: Constructs a deque that will use a copy of allocator a
677 //! and inserts a copy of the range [il.begin(), il.end()) in the deque.
679 //! <b>Throws</b>: If allocator_type's default constructor
680 //! throws or T's constructor taking a dereferenced std::initializer_list iterator throws.
682 //! <b>Complexity</b>: Linear to the range [il.begin(), il.end()).
683 deque(std::initializer_list<value_type> il, const allocator_type& a = allocator_type())
686 this->priv_range_initialize(il.begin(), il.end());
690 //! <b>Effects</b>: Copy constructs a deque.
692 //! <b>Postcondition</b>: x == *this.
694 //! <b>Complexity</b>: Linear to the elements x contains.
695 deque(const deque& x)
696 : Base(allocator_traits_type::select_on_container_copy_construction(x.alloc()))
699 this->priv_initialize_map(x.size());
700 boost::container::uninitialized_copy_alloc
701 (this->alloc(), x.begin(), x.end(), this->members_.m_start);
705 //! <b>Effects</b>: Move constructor. Moves x's resources to *this.
707 //! <b>Throws</b>: If allocator_type's copy constructor throws.
709 //! <b>Complexity</b>: Constant.
710 deque(BOOST_RV_REF(deque) x) BOOST_NOEXCEPT_OR_NOTHROW
711 : Base(BOOST_MOVE_BASE(Base, x))
712 { this->swap_members(x); }
714 //! <b>Effects</b>: Copy constructs a vector using the specified allocator.
716 //! <b>Postcondition</b>: x == *this.
718 //! <b>Throws</b>: If allocation
719 //! throws or T's copy constructor throws.
721 //! <b>Complexity</b>: Linear to the elements x contains.
722 deque(const deque& x, const allocator_type &a)
726 this->priv_initialize_map(x.size());
727 boost::container::uninitialized_copy_alloc
728 (this->alloc(), x.begin(), x.end(), this->members_.m_start);
732 //! <b>Effects</b>: Move constructor using the specified allocator.
733 //! Moves x's resources to *this if a == allocator_type().
734 //! Otherwise copies values from x to *this.
736 //! <b>Throws</b>: If allocation or T's copy constructor throws.
738 //! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise.
739 deque(BOOST_RV_REF(deque) x, const allocator_type &a)
743 this->swap_members(x);
747 this->priv_initialize_map(x.size());
748 boost::container::uninitialized_copy_alloc
749 ( this->alloc(), boost::make_move_iterator(x.begin())
750 , boost::make_move_iterator(x.end()), this->members_.m_start);
755 //! <b>Effects</b>: Destroys the deque. All stored values are destroyed
756 //! and used memory is deallocated.
758 //! <b>Throws</b>: Nothing.
760 //! <b>Complexity</b>: Linear to the number of elements.
761 ~deque() BOOST_NOEXCEPT_OR_NOTHROW
763 this->priv_destroy_range(this->members_.m_start, this->members_.m_finish);
766 //! <b>Effects</b>: Makes *this contain the same elements as x.
768 //! <b>Postcondition</b>: this->size() == x.size(). *this contains a copy
769 //! of each of x's elements.
771 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws.
773 //! <b>Complexity</b>: Linear to the number of elements in x.
774 deque& operator= (BOOST_COPY_ASSIGN_REF(deque) x)
777 allocator_type &this_alloc = this->alloc();
778 const allocator_type &x_alloc = x.alloc();
779 container_detail::bool_<allocator_traits_type::
780 propagate_on_container_copy_assignment::value> flag;
781 if(flag && this_alloc != x_alloc){
783 this->shrink_to_fit();
785 container_detail::assign_alloc(this->alloc(), x.alloc(), flag);
786 container_detail::assign_alloc(this->ptr_alloc(), x.ptr_alloc(), flag);
787 this->assign(x.cbegin(), x.cend());
792 //! <b>Effects</b>: Move assignment. All x's values are transferred to *this.
794 //! <b>Throws</b>: If allocator_traits_type::propagate_on_container_move_assignment
795 //! is false and (allocation throws or value_type's move constructor throws)
797 //! <b>Complexity</b>: Constant if allocator_traits_type::
798 //! propagate_on_container_move_assignment is true or
799 //! this->get>allocator() == x.get_allocator(). Linear otherwise.
800 deque& operator= (BOOST_RV_REF(deque) x)
801 BOOST_NOEXCEPT_IF(allocator_traits_type::propagate_on_container_move_assignment::value
802 || allocator_traits_type::is_always_equal::value)
804 BOOST_ASSERT(this != &x);
805 allocator_type &this_alloc = this->alloc();
806 allocator_type &x_alloc = x.alloc();
807 const bool propagate_alloc = allocator_traits_type::
808 propagate_on_container_move_assignment::value;
809 container_detail::bool_<propagate_alloc> flag;
810 const bool allocators_equal = this_alloc == x_alloc; (void)allocators_equal;
811 //Resources can be transferred if both allocators are
812 //going to be equal after this function (either propagated or already equal)
813 if(propagate_alloc || allocators_equal){
814 //Destroy objects but retain memory in case x reuses it in the future
816 //Move allocator if needed
817 container_detail::move_alloc(this_alloc, x_alloc, flag);
818 container_detail::move_alloc(this->ptr_alloc(), x.ptr_alloc(), flag);
820 this->swap_members(x);
822 //Else do a one by one move
824 this->assign( boost::make_move_iterator(x.begin())
825 , boost::make_move_iterator(x.end()));
830 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
831 //! <b>Effects</b>: Makes *this contain the same elements as il.
833 //! <b>Postcondition</b>: this->size() == il.size(). *this contains a copy
834 //! of each of x's elements.
836 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws.
838 //! <b>Complexity</b>: Linear to the number of elements in il.
839 deque& operator=(std::initializer_list<value_type> il)
841 this->assign(il.begin(), il.end());
846 //! <b>Effects</b>: Assigns the n copies of val to *this.
848 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws.
850 //! <b>Complexity</b>: Linear to n.
851 void assign(size_type n, const T& val)
853 typedef constant_iterator<value_type, difference_type> c_it;
854 this->assign(c_it(val, n), c_it());
857 //! <b>Effects</b>: Assigns the the range [first, last) to *this.
859 //! <b>Throws</b>: If memory allocation throws or
860 //! T's constructor from dereferencing InIt throws.
862 //! <b>Complexity</b>: Linear to n.
863 template <class InIt>
864 void assign(InIt first, InIt last
865 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
866 , typename container_detail::disable_if_or
868 , container_detail::is_convertible<InIt, size_type>
869 , container_detail::is_not_input_iterator<InIt>
874 iterator cur = this->begin();
875 for ( ; first != last && cur != end(); ++cur, ++first){
879 this->erase(cur, this->cend());
882 this->insert(this->cend(), first, last);
886 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
887 template <class FwdIt>
888 void assign(FwdIt first, FwdIt last
889 , typename container_detail::disable_if_or
891 , container_detail::is_convertible<FwdIt, size_type>
892 , container_detail::is_input_iterator<FwdIt>
896 const size_type len = boost::container::iterator_distance(first, last);
899 boost::container::iterator_advance(mid, this->size());
900 boost::container::copy(first, mid, begin());
901 this->insert(this->cend(), mid, last);
904 this->erase(boost::container::copy(first, last, this->begin()), cend());
909 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
910 //! <b>Effects</b>: Assigns the the range [il.begin(), il.end()) to *this.
912 //! <b>Throws</b>: If memory allocation throws or
913 //! T's constructor from dereferencing std::initializer_list iterator throws.
915 //! <b>Complexity</b>: Linear to il.size().
916 void assign(std::initializer_list<value_type> il)
917 { this->assign(il.begin(), il.end()); }
920 //! <b>Effects</b>: Returns a copy of the internal allocator.
922 //! <b>Throws</b>: If allocator's copy constructor throws.
924 //! <b>Complexity</b>: Constant.
925 allocator_type get_allocator() const BOOST_NOEXCEPT_OR_NOTHROW
926 { return Base::alloc(); }
928 //! <b>Effects</b>: Returns a reference to the internal allocator.
930 //! <b>Throws</b>: Nothing
932 //! <b>Complexity</b>: Constant.
934 //! <b>Note</b>: Non-standard extension.
935 const stored_allocator_type &get_stored_allocator() const BOOST_NOEXCEPT_OR_NOTHROW
936 { return Base::alloc(); }
938 //////////////////////////////////////////////
942 //////////////////////////////////////////////
944 //! <b>Effects</b>: Returns a reference to the internal allocator.
946 //! <b>Throws</b>: Nothing
948 //! <b>Complexity</b>: Constant.
950 //! <b>Note</b>: Non-standard extension.
951 stored_allocator_type &get_stored_allocator() BOOST_NOEXCEPT_OR_NOTHROW
952 { return Base::alloc(); }
954 //! <b>Effects</b>: Returns an iterator to the first element contained in the deque.
956 //! <b>Throws</b>: Nothing.
958 //! <b>Complexity</b>: Constant.
959 iterator begin() BOOST_NOEXCEPT_OR_NOTHROW
960 { return this->members_.m_start; }
962 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the deque.
964 //! <b>Throws</b>: Nothing.
966 //! <b>Complexity</b>: Constant.
967 const_iterator begin() const BOOST_NOEXCEPT_OR_NOTHROW
968 { return this->members_.m_start; }
970 //! <b>Effects</b>: Returns an iterator to the end of the deque.
972 //! <b>Throws</b>: Nothing.
974 //! <b>Complexity</b>: Constant.
975 iterator end() BOOST_NOEXCEPT_OR_NOTHROW
976 { return this->members_.m_finish; }
978 //! <b>Effects</b>: Returns a const_iterator to the end of the deque.
980 //! <b>Throws</b>: Nothing.
982 //! <b>Complexity</b>: Constant.
983 const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW
984 { return this->members_.m_finish; }
986 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning
987 //! of the reversed deque.
989 //! <b>Throws</b>: Nothing.
991 //! <b>Complexity</b>: Constant.
992 reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW
993 { return reverse_iterator(this->members_.m_finish); }
995 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
996 //! of the reversed deque.
998 //! <b>Throws</b>: Nothing.
1000 //! <b>Complexity</b>: Constant.
1001 const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW
1002 { return const_reverse_iterator(this->members_.m_finish); }
1004 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
1005 //! of the reversed deque.
1007 //! <b>Throws</b>: Nothing.
1009 //! <b>Complexity</b>: Constant.
1010 reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW
1011 { return reverse_iterator(this->members_.m_start); }
1013 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
1014 //! of the reversed deque.
1016 //! <b>Throws</b>: Nothing.
1018 //! <b>Complexity</b>: Constant.
1019 const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW
1020 { return const_reverse_iterator(this->members_.m_start); }
1022 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the deque.
1024 //! <b>Throws</b>: Nothing.
1026 //! <b>Complexity</b>: Constant.
1027 const_iterator cbegin() const BOOST_NOEXCEPT_OR_NOTHROW
1028 { return this->members_.m_start; }
1030 //! <b>Effects</b>: Returns a const_iterator to the end of the deque.
1032 //! <b>Throws</b>: Nothing.
1034 //! <b>Complexity</b>: Constant.
1035 const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW
1036 { return this->members_.m_finish; }
1038 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
1039 //! of the reversed deque.
1041 //! <b>Throws</b>: Nothing.
1043 //! <b>Complexity</b>: Constant.
1044 const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW
1045 { return const_reverse_iterator(this->members_.m_finish); }
1047 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
1048 //! of the reversed deque.
1050 //! <b>Throws</b>: Nothing.
1052 //! <b>Complexity</b>: Constant.
1053 const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW
1054 { return const_reverse_iterator(this->members_.m_start); }
1056 //////////////////////////////////////////////
1060 //////////////////////////////////////////////
1062 //! <b>Effects</b>: Returns true if the deque contains no elements.
1064 //! <b>Throws</b>: Nothing.
1066 //! <b>Complexity</b>: Constant.
1067 bool empty() const BOOST_NOEXCEPT_OR_NOTHROW
1068 { return this->members_.m_finish == this->members_.m_start; }
1070 //! <b>Effects</b>: Returns the number of the elements contained in the deque.
1072 //! <b>Throws</b>: Nothing.
1074 //! <b>Complexity</b>: Constant.
1075 size_type size() const BOOST_NOEXCEPT_OR_NOTHROW
1076 { return this->members_.m_finish - this->members_.m_start; }
1078 //! <b>Effects</b>: Returns the largest possible size of the deque.
1080 //! <b>Throws</b>: Nothing.
1082 //! <b>Complexity</b>: Constant.
1083 size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW
1084 { return allocator_traits_type::max_size(this->alloc()); }
1086 //! <b>Effects</b>: Inserts or erases elements at the end such that
1087 //! the size becomes n. New elements are value initialized.
1089 //! <b>Throws</b>: If memory allocation throws, or T's constructor throws.
1091 //! <b>Complexity</b>: Linear to the difference between size() and new_size.
1092 void resize(size_type new_size)
1094 const size_type len = size();
1096 this->priv_erase_last_n(len - new_size);
1098 const size_type n = new_size - this->size();
1099 container_detail::insert_value_initialized_n_proxy<Allocator, iterator> proxy;
1100 priv_insert_back_aux_impl(n, proxy);
1104 //! <b>Effects</b>: Inserts or erases elements at the end such that
1105 //! the size becomes n. New elements are default initialized.
1107 //! <b>Throws</b>: If memory allocation throws, or T's constructor throws.
1109 //! <b>Complexity</b>: Linear to the difference between size() and new_size.
1111 //! <b>Note</b>: Non-standard extension
1112 void resize(size_type new_size, default_init_t)
1114 const size_type len = size();
1116 this->priv_erase_last_n(len - new_size);
1118 const size_type n = new_size - this->size();
1119 container_detail::insert_default_initialized_n_proxy<Allocator, iterator> proxy;
1120 priv_insert_back_aux_impl(n, proxy);
1124 //! <b>Effects</b>: Inserts or erases elements at the end such that
1125 //! the size becomes n. New elements are copy constructed from x.
1127 //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws.
1129 //! <b>Complexity</b>: Linear to the difference between size() and new_size.
1130 void resize(size_type new_size, const value_type& x)
1132 const size_type len = size();
1134 this->erase(this->members_.m_start + new_size, this->members_.m_finish);
1136 this->insert(this->members_.m_finish, new_size - len, x);
1139 //! <b>Effects</b>: Tries to deallocate the excess of memory created
1140 //! with previous allocations. The size of the deque is unchanged
1142 //! <b>Throws</b>: If memory allocation throws.
1144 //! <b>Complexity</b>: Constant.
1145 void shrink_to_fit()
1147 //This deque implementation already
1148 //deallocates excess nodes when erasing
1149 //so there is nothing to do except for
1152 this->priv_clear_map();
1156 //////////////////////////////////////////////
1160 //////////////////////////////////////////////
1162 //! <b>Requires</b>: !empty()
1164 //! <b>Effects</b>: Returns a reference to the first
1165 //! element of the container.
1167 //! <b>Throws</b>: Nothing.
1169 //! <b>Complexity</b>: Constant.
1170 reference front() BOOST_NOEXCEPT_OR_NOTHROW
1172 BOOST_ASSERT(!this->empty());
1173 return *this->members_.m_start;
1176 //! <b>Requires</b>: !empty()
1178 //! <b>Effects</b>: Returns a const reference to the first element
1179 //! from the beginning of the container.
1181 //! <b>Throws</b>: Nothing.
1183 //! <b>Complexity</b>: Constant.
1184 const_reference front() const BOOST_NOEXCEPT_OR_NOTHROW
1186 BOOST_ASSERT(!this->empty());
1187 return *this->members_.m_start;
1190 //! <b>Requires</b>: !empty()
1192 //! <b>Effects</b>: Returns a reference to the last
1193 //! element of the container.
1195 //! <b>Throws</b>: Nothing.
1197 //! <b>Complexity</b>: Constant.
1198 reference back() BOOST_NOEXCEPT_OR_NOTHROW
1200 BOOST_ASSERT(!this->empty());
1204 //! <b>Requires</b>: !empty()
1206 //! <b>Effects</b>: Returns a const reference to the last
1207 //! element of the container.
1209 //! <b>Throws</b>: Nothing.
1211 //! <b>Complexity</b>: Constant.
1212 const_reference back() const BOOST_NOEXCEPT_OR_NOTHROW
1214 BOOST_ASSERT(!this->empty());
1218 //! <b>Requires</b>: size() > n.
1220 //! <b>Effects</b>: Returns a reference to the nth element
1221 //! from the beginning of the container.
1223 //! <b>Throws</b>: Nothing.
1225 //! <b>Complexity</b>: Constant.
1226 reference operator[](size_type n) BOOST_NOEXCEPT_OR_NOTHROW
1228 BOOST_ASSERT(this->size() > n);
1229 return this->members_.m_start[difference_type(n)];
1232 //! <b>Requires</b>: size() > n.
1234 //! <b>Effects</b>: Returns a const reference to the nth element
1235 //! from the beginning of the container.
1237 //! <b>Throws</b>: Nothing.
1239 //! <b>Complexity</b>: Constant.
1240 const_reference operator[](size_type n) const BOOST_NOEXCEPT_OR_NOTHROW
1242 BOOST_ASSERT(this->size() > n);
1243 return this->members_.m_start[difference_type(n)];
1246 //! <b>Requires</b>: size() >= n.
1248 //! <b>Effects</b>: Returns an iterator to the nth element
1249 //! from the beginning of the container. Returns end()
1252 //! <b>Throws</b>: Nothing.
1254 //! <b>Complexity</b>: Constant.
1256 //! <b>Note</b>: Non-standard extension
1257 iterator nth(size_type n) BOOST_NOEXCEPT_OR_NOTHROW
1259 BOOST_ASSERT(this->size() >= n);
1260 return iterator(this->begin()+n);
1263 //! <b>Requires</b>: size() >= n.
1265 //! <b>Effects</b>: Returns a const_iterator to the nth element
1266 //! from the beginning of the container. Returns end()
1269 //! <b>Throws</b>: Nothing.
1271 //! <b>Complexity</b>: Constant.
1273 //! <b>Note</b>: Non-standard extension
1274 const_iterator nth(size_type n) const BOOST_NOEXCEPT_OR_NOTHROW
1276 BOOST_ASSERT(this->size() >= n);
1277 return const_iterator(this->cbegin()+n);
1280 //! <b>Requires</b>: begin() <= p <= end().
1282 //! <b>Effects</b>: Returns the index of the element pointed by p
1283 //! and size() if p == end().
1285 //! <b>Throws</b>: Nothing.
1287 //! <b>Complexity</b>: Constant.
1289 //! <b>Note</b>: Non-standard extension
1290 size_type index_of(iterator p) BOOST_NOEXCEPT_OR_NOTHROW
1292 //Range checked priv_index_of
1293 return this->priv_index_of(p);
1296 //! <b>Requires</b>: begin() <= p <= end().
1298 //! <b>Effects</b>: Returns the index of the element pointed by p
1299 //! and size() if p == end().
1301 //! <b>Throws</b>: Nothing.
1303 //! <b>Complexity</b>: Constant.
1305 //! <b>Note</b>: Non-standard extension
1306 size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW
1308 //Range checked priv_index_of
1309 return this->priv_index_of(p);
1312 //! <b>Requires</b>: size() > n.
1314 //! <b>Effects</b>: Returns a reference to the nth element
1315 //! from the beginning of the container.
1317 //! <b>Throws</b>: std::range_error if n >= size()
1319 //! <b>Complexity</b>: Constant.
1320 reference at(size_type n)
1322 this->priv_throw_if_out_of_range(n);
1326 //! <b>Requires</b>: size() > n.
1328 //! <b>Effects</b>: Returns a const reference to the nth element
1329 //! from the beginning of the container.
1331 //! <b>Throws</b>: std::range_error if n >= size()
1333 //! <b>Complexity</b>: Constant.
1334 const_reference at(size_type n) const
1336 this->priv_throw_if_out_of_range(n);
1340 //////////////////////////////////////////////
1344 //////////////////////////////////////////////
1346 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1348 //! <b>Effects</b>: Inserts an object of type T constructed with
1349 //! std::forward<Args>(args)... in the beginning of the deque.
1351 //! <b>Returns</b>: A reference to the created object.
1353 //! <b>Throws</b>: If memory allocation throws or the in-place constructor throws.
1355 //! <b>Complexity</b>: Amortized constant time
1356 template <class... Args>
1357 reference emplace_front(BOOST_FWD_REF(Args)... args)
1359 if(this->priv_push_front_simple_available()){
1360 reference r = *this->priv_push_front_simple_pos();
1361 allocator_traits_type::construct
1363 , this->priv_push_front_simple_pos()
1364 , boost::forward<Args>(args)...);
1365 this->priv_push_front_simple_commit();
1369 typedef container_detail::insert_nonmovable_emplace_proxy<Allocator, iterator, Args...> type;
1370 return *this->priv_insert_front_aux_impl(1, type(boost::forward<Args>(args)...));
1374 //! <b>Effects</b>: Inserts an object of type T constructed with
1375 //! std::forward<Args>(args)... in the end of the deque.
1377 //! <b>Returns</b>: A reference to the created object.
1379 //! <b>Throws</b>: If memory allocation throws or the in-place constructor throws.
1381 //! <b>Complexity</b>: Amortized constant time
1382 template <class... Args>
1383 reference emplace_back(BOOST_FWD_REF(Args)... args)
1385 if(this->priv_push_back_simple_available()){
1386 reference r = *this->priv_push_back_simple_pos();
1387 allocator_traits_type::construct
1389 , this->priv_push_back_simple_pos()
1390 , boost::forward<Args>(args)...);
1391 this->priv_push_back_simple_commit();
1395 typedef container_detail::insert_nonmovable_emplace_proxy<Allocator, iterator, Args...> type;
1396 return *this->priv_insert_back_aux_impl(1, type(boost::forward<Args>(args)...));
1400 //! <b>Requires</b>: p must be a valid iterator of *this.
1402 //! <b>Effects</b>: Inserts an object of type T constructed with
1403 //! std::forward<Args>(args)... before p
1405 //! <b>Throws</b>: If memory allocation throws or the in-place constructor throws.
1407 //! <b>Complexity</b>: If p is end(), amortized constant time
1408 //! Linear time otherwise.
1409 template <class... Args>
1410 iterator emplace(const_iterator p, BOOST_FWD_REF(Args)... args)
1412 BOOST_ASSERT(this->priv_in_range_or_end(p));
1413 if(p == this->cbegin()){
1414 this->emplace_front(boost::forward<Args>(args)...);
1415 return this->begin();
1417 else if(p == this->cend()){
1418 this->emplace_back(boost::forward<Args>(args)...);
1419 return (this->end()-1);
1422 typedef container_detail::insert_emplace_proxy<Allocator, iterator, Args...> type;
1423 return this->priv_insert_aux_impl(p, 1, type(boost::forward<Args>(args)...));
1427 #else //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1429 #define BOOST_CONTAINER_DEQUE_EMPLACE_CODE(N) \
1430 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N\
1431 reference emplace_front(BOOST_MOVE_UREF##N)\
1433 if(priv_push_front_simple_available()){\
1434 reference r = *this->priv_push_front_simple_pos();\
1435 allocator_traits_type::construct\
1436 ( this->alloc(), this->priv_push_front_simple_pos() BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
1437 priv_push_front_simple_commit();\
1441 typedef container_detail::insert_nonmovable_emplace_proxy##N\
1442 <Allocator, iterator BOOST_MOVE_I##N BOOST_MOVE_TARG##N> type;\
1443 return *priv_insert_front_aux_impl(1, type(BOOST_MOVE_FWD##N));\
1447 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N\
1448 reference emplace_back(BOOST_MOVE_UREF##N)\
1450 if(priv_push_back_simple_available()){\
1451 reference r = *this->priv_push_back_simple_pos();\
1452 allocator_traits_type::construct\
1453 ( this->alloc(), this->priv_push_back_simple_pos() BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
1454 priv_push_back_simple_commit();\
1458 typedef container_detail::insert_nonmovable_emplace_proxy##N\
1459 <Allocator, iterator BOOST_MOVE_I##N BOOST_MOVE_TARG##N> type;\
1460 return *priv_insert_back_aux_impl(1, type(BOOST_MOVE_FWD##N));\
1464 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N\
1465 iterator emplace(const_iterator p BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
1467 BOOST_ASSERT(this->priv_in_range_or_end(p));\
1468 if(p == this->cbegin()){\
1469 this->emplace_front(BOOST_MOVE_FWD##N);\
1470 return this->begin();\
1472 else if(p == cend()){\
1473 this->emplace_back(BOOST_MOVE_FWD##N);\
1474 return (--this->end());\
1477 typedef container_detail::insert_emplace_proxy_arg##N\
1478 <Allocator, iterator BOOST_MOVE_I##N BOOST_MOVE_TARG##N> type;\
1479 return this->priv_insert_aux_impl(p, 1, type(BOOST_MOVE_FWD##N));\
1483 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_DEQUE_EMPLACE_CODE)
1484 #undef BOOST_CONTAINER_DEQUE_EMPLACE_CODE
1486 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1488 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1489 //! <b>Effects</b>: Inserts a copy of x at the front of the deque.
1491 //! <b>Throws</b>: If memory allocation throws or
1492 //! T's copy constructor throws.
1494 //! <b>Complexity</b>: Amortized constant time.
1495 void push_front(const T &x);
1497 //! <b>Effects</b>: Constructs a new element in the front of the deque
1498 //! and moves the resources of x to this new element.
1500 //! <b>Throws</b>: If memory allocation throws.
1502 //! <b>Complexity</b>: Amortized constant time.
1503 void push_front(T &&x);
1505 BOOST_MOVE_CONVERSION_AWARE_CATCH(push_front, T, void, priv_push_front)
1508 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1509 //! <b>Effects</b>: Inserts a copy of x at the end of the deque.
1511 //! <b>Throws</b>: If memory allocation throws or
1512 //! T's copy constructor throws.
1514 //! <b>Complexity</b>: Amortized constant time.
1515 void push_back(const T &x);
1517 //! <b>Effects</b>: Constructs a new element in the end of the deque
1518 //! and moves the resources of x to this new element.
1520 //! <b>Throws</b>: If memory allocation throws.
1522 //! <b>Complexity</b>: Amortized constant time.
1523 void push_back(T &&x);
1525 BOOST_MOVE_CONVERSION_AWARE_CATCH(push_back, T, void, priv_push_back)
1528 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1530 //! <b>Requires</b>: p must be a valid iterator of *this.
1532 //! <b>Effects</b>: Insert a copy of x before p.
1534 //! <b>Returns</b>: an iterator to the inserted element.
1536 //! <b>Throws</b>: If memory allocation throws or x's copy constructor throws.
1538 //! <b>Complexity</b>: If p is end(), amortized constant time
1539 //! Linear time otherwise.
1540 iterator insert(const_iterator p, const T &x);
1542 //! <b>Requires</b>: p must be a valid iterator of *this.
1544 //! <b>Effects</b>: Insert a new element before p with x's resources.
1546 //! <b>Returns</b>: an iterator to the inserted element.
1548 //! <b>Throws</b>: If memory allocation throws.
1550 //! <b>Complexity</b>: If p is end(), amortized constant time
1551 //! Linear time otherwise.
1552 iterator insert(const_iterator p, T &&x);
1554 BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, T, iterator, priv_insert, const_iterator, const_iterator)
1557 //! <b>Requires</b>: pos must be a valid iterator of *this.
1559 //! <b>Effects</b>: Insert n copies of x before pos.
1561 //! <b>Returns</b>: an iterator to the first inserted element or pos if n is 0.
1563 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws.
1565 //! <b>Complexity</b>: Linear to n.
1566 iterator insert(const_iterator pos, size_type n, const value_type& x)
1568 //Range check of p is done by insert()
1569 typedef constant_iterator<value_type, difference_type> c_it;
1570 return this->insert(pos, c_it(x, n), c_it());
1573 //! <b>Requires</b>: pos must be a valid iterator of *this.
1575 //! <b>Effects</b>: Insert a copy of the [first, last) range before pos.
1577 //! <b>Returns</b>: an iterator to the first inserted element or pos if first == last.
1579 //! <b>Throws</b>: If memory allocation throws, T's constructor from a
1580 //! dereferenced InIt throws or T's copy constructor throws.
1582 //! <b>Complexity</b>: Linear to distance [first, last).
1583 template <class InIt>
1584 iterator insert(const_iterator pos, InIt first, InIt last
1585 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1586 , typename container_detail::disable_if_or
1588 , container_detail::is_convertible<InIt, size_type>
1589 , container_detail::is_not_input_iterator<InIt>
1594 BOOST_ASSERT(this->priv_in_range_or_end(pos));
1596 iterator it(pos.unconst());
1597 for(;first != last; ++first, ++n){
1598 it = this->emplace(it, *first);
1605 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1606 //! <b>Requires</b>: pos must be a valid iterator of *this.
1608 //! <b>Effects</b>: Insert a copy of the [il.begin(), il.end()) range before pos.
1610 //! <b>Returns</b>: an iterator to the first inserted element or pos if il.begin() == il.end().
1612 //! <b>Throws</b>: If memory allocation throws, T's constructor from a
1613 //! dereferenced std::initializer_list throws or T's copy constructor throws.
1615 //! <b>Complexity</b>: Linear to distance [il.begin(), il.end()).
1616 iterator insert(const_iterator pos, std::initializer_list<value_type> il)
1618 //Range check os pos is done in insert()
1619 return insert(pos, il.begin(), il.end());
1623 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1624 template <class FwdIt>
1625 iterator insert(const_iterator p, FwdIt first, FwdIt last
1626 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1627 , typename container_detail::disable_if_or
1629 , container_detail::is_convertible<FwdIt, size_type>
1630 , container_detail::is_input_iterator<FwdIt>
1635 BOOST_ASSERT(this->priv_in_range_or_end(p));
1636 container_detail::insert_range_proxy<Allocator, FwdIt, iterator> proxy(first);
1637 return priv_insert_aux_impl(p, boost::container::iterator_distance(first, last), proxy);
1641 //! <b>Effects</b>: Removes the first element from the deque.
1643 //! <b>Throws</b>: Nothing.
1645 //! <b>Complexity</b>: Constant time.
1646 void pop_front() BOOST_NOEXCEPT_OR_NOTHROW
1648 BOOST_ASSERT(!this->empty());
1649 if (this->members_.m_start.m_cur != this->members_.m_start.m_last - 1) {
1650 allocator_traits_type::destroy
1652 , container_detail::to_raw_pointer(this->members_.m_start.m_cur)
1654 ++this->members_.m_start.m_cur;
1657 this->priv_pop_front_aux();
1660 //! <b>Effects</b>: Removes the last element from the deque.
1662 //! <b>Throws</b>: Nothing.
1664 //! <b>Complexity</b>: Constant time.
1665 void pop_back() BOOST_NOEXCEPT_OR_NOTHROW
1667 BOOST_ASSERT(!this->empty());
1668 if (this->members_.m_finish.m_cur != this->members_.m_finish.m_first) {
1669 --this->members_.m_finish.m_cur;
1670 allocator_traits_type::destroy
1672 , container_detail::to_raw_pointer(this->members_.m_finish.m_cur)
1676 this->priv_pop_back_aux();
1679 //! <b>Effects</b>: Erases the element at p.
1681 //! <b>Throws</b>: Nothing.
1683 //! <b>Complexity</b>: Linear to the elements between pos and the
1684 //! last element (if pos is near the end) or the first element
1685 //! if(pos is near the beginning).
1686 //! Constant if pos is the first or the last element.
1687 iterator erase(const_iterator pos) BOOST_NOEXCEPT_OR_NOTHROW
1689 BOOST_ASSERT(this->priv_in_range(pos));
1690 iterator next = pos.unconst();
1692 size_type index = pos - this->members_.m_start;
1693 if (index < (this->size()/2)) {
1694 boost::container::move_backward(this->begin(), pos.unconst(), next);
1698 boost::container::move(next, this->end(), pos.unconst());
1701 return this->members_.m_start + index;
1704 //! <b>Effects</b>: Erases the elements pointed by [first, last).
1706 //! <b>Throws</b>: Nothing.
1708 //! <b>Complexity</b>: Linear to the distance between first and
1709 //! last plus the elements between pos and the
1710 //! last element (if pos is near the end) or the first element
1711 //! if(pos is near the beginning).
1712 iterator erase(const_iterator first, const_iterator last) BOOST_NOEXCEPT_OR_NOTHROW
1714 BOOST_ASSERT(first == last ||
1715 (first < last && this->priv_in_range(first) && this->priv_in_range_or_end(last)));
1716 if (first == this->members_.m_start && last == this->members_.m_finish) {
1718 return this->members_.m_finish;
1721 const size_type n = static_cast<size_type>(last - first);
1722 const size_type elems_before = static_cast<size_type>(first - this->members_.m_start);
1723 if (elems_before < (this->size() - n) - elems_before) {
1724 boost::container::move_backward(begin(), first.unconst(), last.unconst());
1725 iterator new_start = this->members_.m_start + n;
1726 this->priv_destroy_range(this->members_.m_start, new_start);
1727 this->priv_destroy_nodes(this->members_.m_start.m_node, new_start.m_node);
1728 this->members_.m_start = new_start;
1731 boost::container::move(last.unconst(), end(), first.unconst());
1732 iterator new_finish = this->members_.m_finish - n;
1733 this->priv_destroy_range(new_finish, this->members_.m_finish);
1734 this->priv_destroy_nodes(new_finish.m_node + 1, this->members_.m_finish.m_node + 1);
1735 this->members_.m_finish = new_finish;
1737 return this->members_.m_start + elems_before;
1741 //! <b>Effects</b>: Swaps the contents of *this and x.
1743 //! <b>Throws</b>: Nothing.
1745 //! <b>Complexity</b>: Constant.
1747 BOOST_NOEXCEPT_IF(allocator_traits_type::propagate_on_container_swap::value
1748 || allocator_traits_type::is_always_equal::value)
1750 this->swap_members(x);
1751 container_detail::bool_<allocator_traits_type::propagate_on_container_swap::value> flag;
1752 container_detail::swap_alloc(this->alloc(), x.alloc(), flag);
1753 container_detail::swap_alloc(this->ptr_alloc(), x.ptr_alloc(), flag);
1756 //! <b>Effects</b>: Erases all the elements of the deque.
1758 //! <b>Throws</b>: Nothing.
1760 //! <b>Complexity</b>: Linear to the number of elements in the deque.
1761 void clear() BOOST_NOEXCEPT_OR_NOTHROW
1763 for (index_pointer node = this->members_.m_start.m_node + 1;
1764 node < this->members_.m_finish.m_node;
1766 this->priv_destroy_range(*node, *node + this->s_buffer_size());
1767 this->priv_deallocate_node(*node);
1770 if (this->members_.m_start.m_node != this->members_.m_finish.m_node) {
1771 this->priv_destroy_range(this->members_.m_start.m_cur, this->members_.m_start.m_last);
1772 this->priv_destroy_range(this->members_.m_finish.m_first, this->members_.m_finish.m_cur);
1773 this->priv_deallocate_node(this->members_.m_finish.m_first);
1776 this->priv_destroy_range(this->members_.m_start.m_cur, this->members_.m_finish.m_cur);
1778 this->members_.m_finish = this->members_.m_start;
1781 //! <b>Effects</b>: Returns true if x and y are equal
1783 //! <b>Complexity</b>: Linear to the number of elements in the container.
1784 friend bool operator==(const deque& x, const deque& y)
1785 { return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin()); }
1787 //! <b>Effects</b>: Returns true if x and y are unequal
1789 //! <b>Complexity</b>: Linear to the number of elements in the container.
1790 friend bool operator!=(const deque& x, const deque& y)
1791 { return !(x == y); }
1793 //! <b>Effects</b>: Returns true if x is less than y
1795 //! <b>Complexity</b>: Linear to the number of elements in the container.
1796 friend bool operator<(const deque& x, const deque& y)
1797 { return ::boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); }
1799 //! <b>Effects</b>: Returns true if x is greater than y
1801 //! <b>Complexity</b>: Linear to the number of elements in the container.
1802 friend bool operator>(const deque& x, const deque& y)
1805 //! <b>Effects</b>: Returns true if x is equal or less than y
1807 //! <b>Complexity</b>: Linear to the number of elements in the container.
1808 friend bool operator<=(const deque& x, const deque& y)
1809 { return !(y < x); }
1811 //! <b>Effects</b>: Returns true if x is equal or greater than y
1813 //! <b>Complexity</b>: Linear to the number of elements in the container.
1814 friend bool operator>=(const deque& x, const deque& y)
1815 { return !(x < y); }
1817 //! <b>Effects</b>: x.swap(y)
1819 //! <b>Complexity</b>: Constant.
1820 friend void swap(deque& x, deque& y)
1823 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1826 size_type priv_index_of(const_iterator p) const
1828 BOOST_ASSERT(this->cbegin() <= p);
1829 BOOST_ASSERT(p <= this->cend());
1830 return static_cast<size_type>(p - this->cbegin());
1833 void priv_erase_last_n(size_type n)
1835 if(n == this->size()) {
1839 iterator new_finish = this->members_.m_finish - n;
1840 this->priv_destroy_range(new_finish, this->members_.m_finish);
1841 this->priv_destroy_nodes(new_finish.m_node + 1, this->members_.m_finish.m_node + 1);
1842 this->members_.m_finish = new_finish;
1846 void priv_throw_if_out_of_range(size_type n) const
1848 if (n >= this->size())
1849 throw_out_of_range("deque::at out of range");
1852 bool priv_in_range(const_iterator pos) const
1854 return (this->begin() <= pos) && (pos < this->end());
1857 bool priv_in_range_or_end(const_iterator pos) const
1859 return (this->begin() <= pos) && (pos <= this->end());
1863 iterator priv_insert(const_iterator p, BOOST_FWD_REF(U) x)
1865 BOOST_ASSERT(this->priv_in_range_or_end(p));
1867 this->push_front(::boost::forward<U>(x));
1870 else if (p == cend()){
1871 this->push_back(::boost::forward<U>(x));
1875 return priv_insert_aux_impl
1877 , container_detail::get_insert_value_proxy<iterator, Allocator>(::boost::forward<U>(x)));
1882 void priv_push_front(BOOST_FWD_REF(U) x)
1884 if(this->priv_push_front_simple_available()){
1885 allocator_traits_type::construct
1886 ( this->alloc(), this->priv_push_front_simple_pos(), ::boost::forward<U>(x));
1887 this->priv_push_front_simple_commit();
1890 priv_insert_aux_impl
1891 ( this->cbegin(), (size_type)1
1892 , container_detail::get_insert_value_proxy<iterator, Allocator>(::boost::forward<U>(x)));
1897 void priv_push_back(BOOST_FWD_REF(U) x)
1899 if(this->priv_push_back_simple_available()){
1900 allocator_traits_type::construct
1901 ( this->alloc(), this->priv_push_back_simple_pos(), ::boost::forward<U>(x));
1902 this->priv_push_back_simple_commit();
1905 priv_insert_aux_impl
1906 ( this->cend(), (size_type)1
1907 , container_detail::get_insert_value_proxy<iterator, Allocator>(::boost::forward<U>(x)));
1911 bool priv_push_back_simple_available() const
1913 return this->members_.m_map &&
1914 (this->members_.m_finish.m_cur != (this->members_.m_finish.m_last - 1));
1917 T *priv_push_back_simple_pos() const
1919 return container_detail::to_raw_pointer(this->members_.m_finish.m_cur);
1922 void priv_push_back_simple_commit()
1924 ++this->members_.m_finish.m_cur;
1927 bool priv_push_front_simple_available() const
1929 return this->members_.m_map &&
1930 (this->members_.m_start.m_cur != this->members_.m_start.m_first);
1933 T *priv_push_front_simple_pos() const
1934 { return container_detail::to_raw_pointer(this->members_.m_start.m_cur) - 1; }
1936 void priv_push_front_simple_commit()
1937 { --this->members_.m_start.m_cur; }
1939 void priv_destroy_range(iterator p, iterator p2)
1941 if(!Base::traits_t::trivial_dctr){
1943 allocator_traits_type::destroy(this->alloc(), container_detail::iterator_to_raw_pointer(p));
1948 void priv_destroy_range(pointer p, pointer p2)
1950 if(!Base::traits_t::trivial_dctr){
1952 allocator_traits_type::destroy(this->alloc(), container_detail::iterator_to_raw_pointer(p));
1957 template<class InsertProxy>
1958 iterator priv_insert_aux_impl(const_iterator p, size_type n, InsertProxy proxy)
1960 iterator pos(p.unconst());
1961 const size_type pos_n = p - this->cbegin();
1962 if(!this->members_.m_map){
1963 this->priv_initialize_map(0);
1964 pos = this->begin();
1967 const size_type elemsbefore = static_cast<size_type>(pos - this->members_.m_start);
1968 const size_type length = this->size();
1969 if (elemsbefore < length / 2) {
1970 const iterator new_start = this->priv_reserve_elements_at_front(n);
1971 const iterator old_start = this->members_.m_start;
1973 proxy.uninitialized_copy_n_and_update(this->alloc(), new_start, n);
1974 this->members_.m_start = new_start;
1977 pos = this->members_.m_start + elemsbefore;
1978 if (elemsbefore >= n) {
1979 const iterator start_n = this->members_.m_start + n;
1980 ::boost::container::uninitialized_move_alloc
1981 (this->alloc(), this->members_.m_start, start_n, new_start);
1982 this->members_.m_start = new_start;
1983 boost::container::move(start_n, pos, old_start);
1984 proxy.copy_n_and_update(this->alloc(), pos - n, n);
1987 const size_type mid_count = n - elemsbefore;
1988 const iterator mid_start = old_start - mid_count;
1989 proxy.uninitialized_copy_n_and_update(this->alloc(), mid_start, mid_count);
1990 this->members_.m_start = mid_start;
1991 ::boost::container::uninitialized_move_alloc
1992 (this->alloc(), old_start, pos, new_start);
1993 this->members_.m_start = new_start;
1994 proxy.copy_n_and_update(this->alloc(), old_start, elemsbefore);
1999 const iterator new_finish = this->priv_reserve_elements_at_back(n);
2000 const iterator old_finish = this->members_.m_finish;
2001 const size_type elemsafter = length - elemsbefore;
2003 proxy.uninitialized_copy_n_and_update(this->alloc(), old_finish, n);
2004 this->members_.m_finish = new_finish;
2007 pos = old_finish - elemsafter;
2008 if (elemsafter >= n) {
2009 iterator finish_n = old_finish - difference_type(n);
2010 ::boost::container::uninitialized_move_alloc
2011 (this->alloc(), finish_n, old_finish, old_finish);
2012 this->members_.m_finish = new_finish;
2013 boost::container::move_backward(pos, finish_n, old_finish);
2014 proxy.copy_n_and_update(this->alloc(), pos, n);
2017 const size_type raw_gap = n - elemsafter;
2018 ::boost::container::uninitialized_move_alloc
2019 (this->alloc(), pos, old_finish, old_finish + raw_gap);
2021 proxy.copy_n_and_update(this->alloc(), pos, elemsafter);
2022 proxy.uninitialized_copy_n_and_update(this->alloc(), old_finish, raw_gap);
2025 this->priv_destroy_range(old_finish, old_finish + elemsafter);
2029 this->members_.m_finish = new_finish;
2033 return this->begin() + pos_n;
2036 template <class InsertProxy>
2037 iterator priv_insert_back_aux_impl(size_type n, InsertProxy proxy)
2039 if(!this->members_.m_map){
2040 this->priv_initialize_map(0);
2043 iterator new_finish = this->priv_reserve_elements_at_back(n);
2044 iterator old_finish = this->members_.m_finish;
2045 proxy.uninitialized_copy_n_and_update(this->alloc(), old_finish, n);
2046 this->members_.m_finish = new_finish;
2047 return iterator(this->members_.m_finish - n);
2050 template <class InsertProxy>
2051 iterator priv_insert_front_aux_impl(size_type n, InsertProxy proxy)
2053 if(!this->members_.m_map){
2054 this->priv_initialize_map(0);
2057 iterator new_start = this->priv_reserve_elements_at_front(n);
2058 proxy.uninitialized_copy_n_and_update(this->alloc(), new_start, n);
2059 this->members_.m_start = new_start;
2063 iterator priv_fill_insert(const_iterator pos, size_type n, const value_type& x)
2065 typedef constant_iterator<value_type, difference_type> c_it;
2066 return this->insert(pos, c_it(x, n), c_it());
2069 // Precondition: this->members_.m_start and this->members_.m_finish have already been initialized,
2070 // but none of the deque's elements have yet been constructed.
2071 void priv_fill_initialize(const value_type& value)
2073 index_pointer cur = this->members_.m_start.m_node;
2075 for ( ; cur < this->members_.m_finish.m_node; ++cur){
2076 boost::container::uninitialized_fill_alloc
2077 (this->alloc(), *cur, *cur + this->s_buffer_size(), value);
2079 boost::container::uninitialized_fill_alloc
2080 (this->alloc(), this->members_.m_finish.m_first, this->members_.m_finish.m_cur, value);
2083 this->priv_destroy_range(this->members_.m_start, iterator(*cur, cur));
2089 template <class InIt>
2090 void priv_range_initialize(InIt first, InIt last, typename iterator_enable_if_tag<InIt, std::input_iterator_tag>::type* =0)
2092 this->priv_initialize_map(0);
2094 for ( ; first != last; ++first)
2095 this->emplace_back(*first);
2104 template <class FwdIt>
2105 void priv_range_initialize(FwdIt first, FwdIt last, typename iterator_disable_if_tag<FwdIt, std::input_iterator_tag>::type* =0)
2108 n = boost::container::iterator_distance(first, last);
2109 this->priv_initialize_map(n);
2111 index_pointer cur_node = this->members_.m_start.m_node;
2113 for (; cur_node < this->members_.m_finish.m_node; ++cur_node) {
2115 boost::container::iterator_advance(mid, this->s_buffer_size());
2116 ::boost::container::uninitialized_copy_alloc(this->alloc(), first, mid, *cur_node);
2119 ::boost::container::uninitialized_copy_alloc(this->alloc(), first, last, this->members_.m_finish.m_first);
2122 this->priv_destroy_range(this->members_.m_start, iterator(*cur_node, cur_node));
2128 // Called only if this->members_.m_finish.m_cur == this->members_.m_finish.m_first.
2129 void priv_pop_back_aux() BOOST_NOEXCEPT_OR_NOTHROW
2131 this->priv_deallocate_node(this->members_.m_finish.m_first);
2132 this->members_.m_finish.priv_set_node(this->members_.m_finish.m_node - 1);
2133 this->members_.m_finish.m_cur = this->members_.m_finish.m_last - 1;
2134 allocator_traits_type::destroy
2136 , container_detail::to_raw_pointer(this->members_.m_finish.m_cur)
2140 // Called only if this->members_.m_start.m_cur == this->members_.m_start.m_last - 1. Note that
2141 // if the deque has at least one element (a precondition for this member
2142 // function), and if this->members_.m_start.m_cur == this->members_.m_start.m_last, then the deque
2143 // must have at least two nodes.
2144 void priv_pop_front_aux() BOOST_NOEXCEPT_OR_NOTHROW
2146 allocator_traits_type::destroy
2148 , container_detail::to_raw_pointer(this->members_.m_start.m_cur)
2150 this->priv_deallocate_node(this->members_.m_start.m_first);
2151 this->members_.m_start.priv_set_node(this->members_.m_start.m_node + 1);
2152 this->members_.m_start.m_cur = this->members_.m_start.m_first;
2155 iterator priv_reserve_elements_at_front(size_type n)
2157 size_type vacancies = this->members_.m_start.m_cur - this->members_.m_start.m_first;
2159 size_type new_elems = n-vacancies;
2160 size_type new_nodes = (new_elems + this->s_buffer_size() - 1) /
2161 this->s_buffer_size();
2162 size_type s = (size_type)(this->members_.m_start.m_node - this->members_.m_map);
2164 this->priv_reallocate_map(new_nodes, true);
2168 for (; i <= new_nodes; ++i)
2169 *(this->members_.m_start.m_node - i) = this->priv_allocate_node();
2172 for (size_type j = 1; j < i; ++j)
2173 this->priv_deallocate_node(*(this->members_.m_start.m_node - j));
2178 return this->members_.m_start - difference_type(n);
2181 iterator priv_reserve_elements_at_back(size_type n)
2183 size_type vacancies = (this->members_.m_finish.m_last - this->members_.m_finish.m_cur) - 1;
2185 size_type new_elems = n - vacancies;
2186 size_type new_nodes = (new_elems + this->s_buffer_size() - 1)/s_buffer_size();
2187 size_type s = (size_type)(this->members_.m_map_size - (this->members_.m_finish.m_node - this->members_.m_map));
2188 if (new_nodes + 1 > s){
2189 this->priv_reallocate_map(new_nodes, false);
2193 for (; i <= new_nodes; ++i)
2194 *(this->members_.m_finish.m_node + i) = this->priv_allocate_node();
2197 for (size_type j = 1; j < i; ++j)
2198 this->priv_deallocate_node(*(this->members_.m_finish.m_node + j));
2203 return this->members_.m_finish + difference_type(n);
2206 void priv_reallocate_map(size_type nodes_to_add, bool add_at_front)
2208 size_type old_num_nodes = this->members_.m_finish.m_node - this->members_.m_start.m_node + 1;
2209 size_type new_num_nodes = old_num_nodes + nodes_to_add;
2211 index_pointer new_nstart;
2212 if (this->members_.m_map_size > 2 * new_num_nodes) {
2213 new_nstart = this->members_.m_map + (this->members_.m_map_size - new_num_nodes) / 2
2214 + (add_at_front ? nodes_to_add : 0);
2215 if (new_nstart < this->members_.m_start.m_node)
2216 boost::container::move(this->members_.m_start.m_node, this->members_.m_finish.m_node + 1, new_nstart);
2218 boost::container::move_backward
2219 (this->members_.m_start.m_node, this->members_.m_finish.m_node + 1, new_nstart + old_num_nodes);
2222 size_type new_map_size =
2223 this->members_.m_map_size + container_detail::max_value(this->members_.m_map_size, nodes_to_add) + 2;
2225 index_pointer new_map = this->priv_allocate_map(new_map_size);
2226 new_nstart = new_map + (new_map_size - new_num_nodes) / 2
2227 + (add_at_front ? nodes_to_add : 0);
2228 boost::container::move(this->members_.m_start.m_node, this->members_.m_finish.m_node + 1, new_nstart);
2229 this->priv_deallocate_map(this->members_.m_map, this->members_.m_map_size);
2231 this->members_.m_map = new_map;
2232 this->members_.m_map_size = new_map_size;
2235 this->members_.m_start.priv_set_node(new_nstart);
2236 this->members_.m_finish.priv_set_node(new_nstart + old_num_nodes - 1);
2238 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
2243 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
2247 //!has_trivial_destructor_after_move<> == true_type
2248 //!specialization for optimizations
2249 template <class T, class Allocator>
2250 struct has_trivial_destructor_after_move<boost::container::deque<T, Allocator> >
2252 typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer;
2253 static const bool value = ::boost::has_trivial_destructor_after_move<Allocator>::value &&
2254 ::boost::has_trivial_destructor_after_move<pointer>::value;
2259 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
2261 #include <boost/container/detail/config_end.hpp>
2263 #endif // #ifndef BOOST_CONTAINER_DEQUE_HPP