the game where you go into mines and start crafting! but for consoles (forked directly from smartcmd's github)
1//////////////////////////////////////////////////////////////////////////////
2//
3// (C) Copyright Ion Gaztanaga 2005-2012. 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)
6//
7// See http://www.boost.org/libs/container for documentation.
8//
9//////////////////////////////////////////////////////////////////////////////
10// Copyright (c) 1996,1997
11// Silicon Graphics Computer Systems, Inc.
12//
13// Permission to use, copy, modify, distribute and sell this software
14// and its documentation for any purpose is hereby granted without fee,
15// provided that the above copyright notice appear in all copies and
16// that both that copyright notice and this permission notice appear
17// in supporting documentation. Silicon Graphics makes no
18// representations about the suitability of this software for any
19// purpose. It is provided "as is" without express or implied warranty.
20//
21//
22// Copyright (c) 1994
23// Hewlett-Packard Company
24//
25// Permission to use, copy, modify, distribute and sell this software
26// and its documentation for any purpose is hereby granted without fee,
27// provided that the above copyright notice appear in all copies and
28// that both that copyright notice and this permission notice appear
29// in supporting documentation. Hewlett-Packard Company makes no
30// representations about the suitability of this software for any
31// purpose. It is provided "as is" without express or implied warranty.
32
33#ifndef BOOST_CONTAINER_DEQUE_HPP
34#define BOOST_CONTAINER_DEQUE_HPP
35
36#if (defined _MSC_VER) && (_MSC_VER >= 1200)
37# pragma once
38#endif
39
40#include <boost/container/detail/config_begin.hpp>
41#include <boost/container/detail/workaround.hpp>
42
43#include <boost/container/detail/utilities.hpp>
44#include <boost/container/detail/iterators.hpp>
45#include <boost/container/detail/algorithms.hpp>
46#include <boost/container/detail/mpl.hpp>
47#include <boost/container/allocator_traits.hpp>
48#include <boost/container/container_fwd.hpp>
49#include <cstddef>
50#include <iterator>
51#include <boost/assert.hpp>
52#include <memory>
53#include <algorithm>
54#include <stdexcept>
55#include <boost/detail/no_exceptions_support.hpp>
56#include <boost/type_traits/has_trivial_destructor.hpp>
57#include <boost/type_traits/has_trivial_copy.hpp>
58#include <boost/type_traits/has_trivial_assign.hpp>
59#include <boost/type_traits/has_nothrow_copy.hpp>
60#include <boost/type_traits/has_nothrow_assign.hpp>
61#include <boost/move/utility.hpp>
62#include <boost/move/iterator.hpp>
63#include <boost/move/detail/move_helpers.hpp>
64#include <boost/container/detail/advanced_insert_int.hpp>
65#include <boost/detail/no_exceptions_support.hpp>
66
67namespace boost {
68namespace container {
69
70/// @cond
71#ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
72template <class T, class Allocator = std::allocator<T> >
73#else
74template <class T, class Allocator>
75#endif
76class deque;
77
78template <class T, class Allocator>
79struct deque_value_traits
80{
81 typedef T value_type;
82 typedef Allocator allocator_type;
83 static const bool trivial_dctr = boost::has_trivial_destructor<value_type>::value;
84 static const bool trivial_dctr_after_move = ::boost::has_trivial_destructor_after_move<value_type>::value;
85 static const bool trivial_copy = has_trivial_copy<value_type>::value;
86 static const bool nothrow_copy = has_nothrow_copy<value_type>::value;
87 static const bool trivial_assign = has_trivial_assign<value_type>::value;
88 //static const bool nothrow_assign = has_nothrow_assign<value_type>::value;
89 static const bool nothrow_assign = false;
90};
91
92// Note: this function is simply a kludge to work around several compilers'
93// bugs in handling constant expressions.
94inline std::size_t deque_buf_size(std::size_t size)
95 { return size < 512 ? std::size_t(512 / size) : std::size_t(1); }
96
97// Deque base class. It has two purposes. First, its constructor
98// and destructor allocate (but don't initialize) storage. This makes
99// exception safety easier.
100template <class T, class Allocator>
101class deque_base
102{
103 BOOST_COPYABLE_AND_MOVABLE(deque_base)
104 public:
105 typedef allocator_traits<Allocator> val_alloc_traits_type;
106 typedef typename val_alloc_traits_type::value_type val_alloc_val;
107 typedef typename val_alloc_traits_type::pointer val_alloc_ptr;
108 typedef typename val_alloc_traits_type::const_pointer val_alloc_cptr;
109 typedef typename val_alloc_traits_type::reference val_alloc_ref;
110 typedef typename val_alloc_traits_type::const_reference val_alloc_cref;
111 typedef typename val_alloc_traits_type::difference_type val_alloc_diff;
112 typedef typename val_alloc_traits_type::size_type val_alloc_size;
113 typedef typename val_alloc_traits_type::template
114 portable_rebind_alloc<val_alloc_ptr>::type ptr_alloc_t;
115 typedef allocator_traits<ptr_alloc_t> ptr_alloc_traits_type;
116 typedef typename ptr_alloc_traits_type::value_type ptr_alloc_val;
117 typedef typename ptr_alloc_traits_type::pointer ptr_alloc_ptr;
118 typedef typename ptr_alloc_traits_type::const_pointer ptr_alloc_cptr;
119 typedef typename ptr_alloc_traits_type::reference ptr_alloc_ref;
120 typedef typename ptr_alloc_traits_type::const_reference ptr_alloc_cref;
121 typedef Allocator allocator_type;
122 typedef allocator_type stored_allocator_type;
123 typedef val_alloc_size size_type;
124
125 protected:
126
127 typedef deque_value_traits<T, Allocator> traits_t;
128 typedef ptr_alloc_t map_allocator_type;
129
130 static size_type s_buffer_size() { return deque_buf_size(sizeof(T)); }
131
132 val_alloc_ptr priv_allocate_node()
133 { return this->alloc().allocate(s_buffer_size()); }
134
135 void priv_deallocate_node(val_alloc_ptr p)
136 { this->alloc().deallocate(p, s_buffer_size()); }
137
138 ptr_alloc_ptr priv_allocate_map(size_type n)
139 { return this->ptr_alloc().allocate(n); }
140
141 void priv_deallocate_map(ptr_alloc_ptr p, size_type n)
142 { this->ptr_alloc().deallocate(p, n); }
143
144 public:
145 // Class invariants:
146 // For any nonsingular iterator i:
147 // i.node is the address of an element in the map array. The
148 // contents of i.node is a pointer to the beginning of a node.
149 // i.first == //(i.node)
150 // i.last == i.first + node_size
151 // i.cur is a pointer in the range [i.first, i.last). NOTE:
152 // the implication of this is that i.cur is always a dereferenceable
153 // pointer, even if i is a past-the-end iterator.
154 // Start and Finish are always nonsingular iterators. NOTE: this means
155 // that an empty deque must have one node, and that a deque
156 // with N elements, where N is the buffer size, must have two nodes.
157 // For every node other than start.node and finish.node, every element
158 // in the node is an initialized object. If start.node == finish.node,
159 // then [start.cur, finish.cur) are initialized objects, and
160 // the elements outside that range are uninitialized storage. Otherwise,
161 // [start.cur, start.last) and [finish.first, finish.cur) are initialized
162 // objects, and [start.first, start.cur) and [finish.cur, finish.last)
163 // are uninitialized storage.
164 // [map, map + map_size) is a valid, non-empty range.
165 // [start.node, finish.node] is a valid range contained within
166 // [map, map + map_size).
167 // Allocator pointer in the range [map, map + map_size) points to an allocated node
168 // if and only if the pointer is in the range [start.node, finish.node].
169 class const_iterator
170 : public std::iterator<std::random_access_iterator_tag,
171 val_alloc_val, val_alloc_diff,
172 val_alloc_cptr, val_alloc_cref>
173 {
174 public:
175 static size_type s_buffer_size() { return deque_base<T, Allocator>::s_buffer_size(); }
176
177 typedef std::random_access_iterator_tag iterator_category;
178 typedef val_alloc_val value_type;
179 typedef val_alloc_cptr pointer;
180 typedef val_alloc_cref reference;
181 typedef val_alloc_diff difference_type;
182
183 typedef ptr_alloc_ptr index_pointer;
184 typedef const_iterator self_t;
185
186 friend class deque<T, Allocator>;
187 friend class deque_base<T, Allocator>;
188
189 protected:
190 val_alloc_ptr m_cur;
191 val_alloc_ptr m_first;
192 val_alloc_ptr m_last;
193 index_pointer m_node;
194
195 public:
196 const_iterator(val_alloc_ptr x, index_pointer y)
197 : m_cur(x), m_first(*y),
198 m_last(*y + s_buffer_size()), m_node(y) {}
199
200 const_iterator() : m_cur(0), m_first(0), m_last(0), m_node(0) {}
201
202 const_iterator(const const_iterator& x)
203 : m_cur(x.m_cur), m_first(x.m_first),
204 m_last(x.m_last), m_node(x.m_node) {}
205
206 reference operator*() const
207 { return *this->m_cur; }
208
209 pointer operator->() const
210 { return this->m_cur; }
211
212 difference_type operator-(const self_t& x) const
213 {
214 if(!this->m_cur && !x.m_cur){
215 return 0;
216 }
217 return difference_type(this->s_buffer_size()) * (this->m_node - x.m_node - 1) +
218 (this->m_cur - this->m_first) + (x.m_last - x.m_cur);
219 }
220
221 self_t& operator++()
222 {
223 ++this->m_cur;
224 if (this->m_cur == this->m_last) {
225 this->priv_set_node(this->m_node + 1);
226 this->m_cur = this->m_first;
227 }
228 return *this;
229 }
230
231 self_t operator++(int)
232 {
233 self_t tmp = *this;
234 ++*this;
235 return tmp;
236 }
237
238 self_t& operator--()
239 {
240 if (this->m_cur == this->m_first) {
241 this->priv_set_node(this->m_node - 1);
242 this->m_cur = this->m_last;
243 }
244 --this->m_cur;
245 return *this;
246 }
247
248 self_t operator--(int)
249 {
250 self_t tmp = *this;
251 --*this;
252 return tmp;
253 }
254
255 self_t& operator+=(difference_type n)
256 {
257 difference_type offset = n + (this->m_cur - this->m_first);
258 if (offset >= 0 && offset < difference_type(this->s_buffer_size()))
259 this->m_cur += n;
260 else {
261 difference_type node_offset =
262 offset > 0 ? offset / difference_type(this->s_buffer_size())
263 : -difference_type((-offset - 1) / this->s_buffer_size()) - 1;
264 this->priv_set_node(this->m_node + node_offset);
265 this->m_cur = this->m_first +
266 (offset - node_offset * difference_type(this->s_buffer_size()));
267 }
268 return *this;
269 }
270
271 self_t operator+(difference_type n) const
272 { self_t tmp = *this; return tmp += n; }
273
274 self_t& operator-=(difference_type n)
275 { return *this += -n; }
276
277 self_t operator-(difference_type n) const
278 { self_t tmp = *this; return tmp -= n; }
279
280 reference operator[](difference_type n) const
281 { return *(*this + n); }
282
283 bool operator==(const self_t& x) const
284 { return this->m_cur == x.m_cur; }
285
286 bool operator!=(const self_t& x) const
287 { return !(*this == x); }
288
289 bool operator<(const self_t& x) const
290 {
291 return (this->m_node == x.m_node) ?
292 (this->m_cur < x.m_cur) : (this->m_node < x.m_node);
293 }
294
295 bool operator>(const self_t& x) const
296 { return x < *this; }
297
298 bool operator<=(const self_t& x) const
299 { return !(x < *this); }
300
301 bool operator>=(const self_t& x) const
302 { return !(*this < x); }
303
304 void priv_set_node(index_pointer new_node)
305 {
306 this->m_node = new_node;
307 this->m_first = *new_node;
308 this->m_last = this->m_first + this->s_buffer_size();
309 }
310
311 friend const_iterator operator+(difference_type n, const const_iterator& x)
312 { return x + n; }
313 };
314
315 //Deque iterator
316 class iterator : public const_iterator
317 {
318 public:
319 typedef std::random_access_iterator_tag iterator_category;
320 typedef val_alloc_val value_type;
321 typedef val_alloc_ptr pointer;
322 typedef val_alloc_ref reference;
323 typedef val_alloc_diff difference_type;
324 typedef ptr_alloc_ptr index_pointer;
325 typedef const_iterator self_t;
326
327 friend class deque<T, Allocator>;
328 friend class deque_base<T, Allocator>;
329
330 private:
331 explicit iterator(const const_iterator& x) : const_iterator(x){}
332
333 public:
334 //Constructors
335 iterator(val_alloc_ptr x, index_pointer y) : const_iterator(x, y){}
336 iterator() : const_iterator(){}
337 //iterator(const const_iterator &cit) : const_iterator(cit){}
338 iterator(const iterator& x) : const_iterator(x){}
339
340 //Pointer like operators
341 reference operator*() const { return *this->m_cur; }
342 pointer operator->() const { return this->m_cur; }
343
344 reference operator[](difference_type n) const { return *(*this + n); }
345
346 //Increment / Decrement
347 iterator& operator++()
348 { this->const_iterator::operator++(); return *this; }
349
350 iterator operator++(int)
351 { iterator tmp = *this; ++*this; return tmp; }
352
353 iterator& operator--()
354 { this->const_iterator::operator--(); return *this; }
355
356 iterator operator--(int)
357 { iterator tmp = *this; --*this; return tmp; }
358
359 // Arithmetic
360 iterator& operator+=(difference_type off)
361 { this->const_iterator::operator+=(off); return *this; }
362
363 iterator operator+(difference_type off) const
364 { return iterator(this->const_iterator::operator+(off)); }
365
366 friend iterator operator+(difference_type off, const iterator& right)
367 { return iterator(off+static_cast<const const_iterator &>(right)); }
368
369 iterator& operator-=(difference_type off)
370 { this->const_iterator::operator-=(off); return *this; }
371
372 iterator operator-(difference_type off) const
373 { return iterator(this->const_iterator::operator-(off)); }
374
375 difference_type operator-(const const_iterator& right) const
376 { return static_cast<const const_iterator&>(*this) - right; }
377 };
378
379 deque_base(size_type num_elements, const allocator_type& a)
380 : members_(a)
381 { this->priv_initialize_map(num_elements); }
382
383 explicit deque_base(const allocator_type& a)
384 : members_(a)
385 {}
386
387 deque_base()
388 : members_()
389 {}
390
391 explicit deque_base(BOOST_RV_REF(deque_base) x)
392 : members_( boost::move(x.ptr_alloc())
393 , boost::move(x.alloc()) )
394 {}
395
396 ~deque_base()
397 {
398 if (this->members_.m_map) {
399 this->priv_destroy_nodes(this->members_.m_start.m_node, this->members_.m_finish.m_node + 1);
400 this->priv_deallocate_map(this->members_.m_map, this->members_.m_map_size);
401 }
402 }
403
404 private:
405 deque_base(const deque_base&);
406
407 protected:
408
409 void swap_members(deque_base &x)
410 {
411 std::swap(this->members_.m_start, x.members_.m_start);
412 std::swap(this->members_.m_finish, x.members_.m_finish);
413 std::swap(this->members_.m_map, x.members_.m_map);
414 std::swap(this->members_.m_map_size, x.members_.m_map_size);
415 }
416
417 void priv_initialize_map(size_type num_elements)
418 {
419// if(num_elements){
420 size_type num_nodes = num_elements / s_buffer_size() + 1;
421
422 this->members_.m_map_size = container_detail::max_value((size_type) InitialMapSize, num_nodes + 2);
423 this->members_.m_map = this->priv_allocate_map(this->members_.m_map_size);
424
425 ptr_alloc_ptr nstart = this->members_.m_map + (this->members_.m_map_size - num_nodes) / 2;
426 ptr_alloc_ptr nfinish = nstart + num_nodes;
427
428 BOOST_TRY {
429 this->priv_create_nodes(nstart, nfinish);
430 }
431 BOOST_CATCH(...){
432 this->priv_deallocate_map(this->members_.m_map, this->members_.m_map_size);
433 this->members_.m_map = 0;
434 this->members_.m_map_size = 0;
435 BOOST_RETHROW
436 }
437 BOOST_CATCH_END
438
439 this->members_.m_start.priv_set_node(nstart);
440 this->members_.m_finish.priv_set_node(nfinish - 1);
441 this->members_.m_start.m_cur = this->members_.m_start.m_first;
442 this->members_.m_finish.m_cur = this->members_.m_finish.m_first +
443 num_elements % s_buffer_size();
444// }
445 }
446
447 void priv_create_nodes(ptr_alloc_ptr nstart, ptr_alloc_ptr nfinish)
448 {
449 ptr_alloc_ptr cur;
450 BOOST_TRY {
451 for (cur = nstart; cur < nfinish; ++cur)
452 *cur = this->priv_allocate_node();
453 }
454 BOOST_CATCH(...){
455 this->priv_destroy_nodes(nstart, cur);
456 BOOST_RETHROW
457 }
458 BOOST_CATCH_END
459 }
460
461 void priv_destroy_nodes(ptr_alloc_ptr nstart, ptr_alloc_ptr nfinish)
462 {
463 for (ptr_alloc_ptr n = nstart; n < nfinish; ++n)
464 this->priv_deallocate_node(*n);
465 }
466
467 void priv_clear_map()
468 {
469 if (this->members_.m_map) {
470 this->priv_destroy_nodes(this->members_.m_start.m_node, this->members_.m_finish.m_node + 1);
471 this->priv_deallocate_map(this->members_.m_map, this->members_.m_map_size);
472 this->members_.m_map = 0;
473 this->members_.m_map_size = 0;
474 this->members_.m_start = iterator();
475 this->members_.m_finish = this->members_.m_start;
476 }
477 }
478
479 enum { InitialMapSize = 8 };
480
481 protected:
482 struct members_holder
483 : public ptr_alloc_t
484 , public allocator_type
485 {
486 members_holder()
487 : map_allocator_type(), allocator_type()
488 , m_map(0), m_map_size(0)
489 , m_start(), m_finish(m_start)
490 {}
491
492 explicit members_holder(const allocator_type &a)
493 : map_allocator_type(a), allocator_type(a)
494 , m_map(0), m_map_size(0)
495 , m_start(), m_finish(m_start)
496 {}
497
498 template<class ValAllocConvertible, class PtrAllocConvertible>
499 members_holder(BOOST_FWD_REF(PtrAllocConvertible) pa, BOOST_FWD_REF(ValAllocConvertible) va)
500 : map_allocator_type(boost::forward<PtrAllocConvertible>(pa))
501 , allocator_type (boost::forward<ValAllocConvertible>(va))
502 , m_map(0), m_map_size(0)
503 , m_start(), m_finish(m_start)
504 {}
505
506 ptr_alloc_ptr m_map;
507 val_alloc_size m_map_size;
508 iterator m_start;
509 iterator m_finish;
510 } members_;
511
512 ptr_alloc_t &ptr_alloc()
513 { return members_; }
514
515 const ptr_alloc_t &ptr_alloc() const
516 { return members_; }
517
518 allocator_type &alloc()
519 { return members_; }
520
521 const allocator_type &alloc() const
522 { return members_; }
523};
524/// @endcond
525
526//! Deque class
527//!
528#ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
529template <class T, class Allocator = std::allocator<T> >
530#else
531template <class T, class Allocator>
532#endif
533class deque : protected deque_base<T, Allocator>
534{
535 /// @cond
536 private:
537 typedef deque_base<T, Allocator> Base;
538 /// @endcond
539
540 public:
541
542 //////////////////////////////////////////////
543 //
544 // types
545 //
546 //////////////////////////////////////////////
547
548 typedef T value_type;
549 typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer;
550 typedef typename ::boost::container::allocator_traits<Allocator>::const_pointer const_pointer;
551 typedef typename ::boost::container::allocator_traits<Allocator>::reference reference;
552 typedef typename ::boost::container::allocator_traits<Allocator>::const_reference const_reference;
553 typedef typename ::boost::container::allocator_traits<Allocator>::size_type size_type;
554 typedef typename ::boost::container::allocator_traits<Allocator>::difference_type difference_type;
555 typedef Allocator allocator_type;
556 typedef BOOST_CONTAINER_IMPDEF(allocator_type) stored_allocator_type;
557 typedef BOOST_CONTAINER_IMPDEF(typename Base::iterator) iterator;
558 typedef BOOST_CONTAINER_IMPDEF(typename Base::const_iterator) const_iterator;
559 typedef BOOST_CONTAINER_IMPDEF(std::reverse_iterator<iterator>) reverse_iterator;
560 typedef BOOST_CONTAINER_IMPDEF(std::reverse_iterator<const_iterator>) const_reverse_iterator;
561
562 /// @cond
563
564 private: // Internal typedefs
565 BOOST_COPYABLE_AND_MOVABLE(deque)
566 typedef typename Base::ptr_alloc_ptr index_pointer;
567 static size_type s_buffer_size()
568 { return Base::s_buffer_size(); }
569 typedef allocator_traits<Allocator> allocator_traits_type;
570
571 /// @endcond
572
573 public:
574 //////////////////////////////////////////////
575 //
576 // construct/copy/destroy
577 //
578 //////////////////////////////////////////////
579
580 //! <b>Effects</b>: Default constructors a deque.
581 //!
582 //! <b>Throws</b>: If allocator_type's default constructor throws.
583 //!
584 //! <b>Complexity</b>: Constant.
585 deque()
586 : Base()
587 {}
588
589 //! <b>Effects</b>: Constructs a deque taking the allocator as parameter.
590 //!
591 //! <b>Throws</b>: Nothing
592 //!
593 //! <b>Complexity</b>: Constant.
594 explicit deque(const allocator_type& a) BOOST_CONTAINER_NOEXCEPT
595 : Base(a)
596 {}
597
598 //! <b>Effects</b>: Constructs a deque that will use a copy of allocator a
599 //! and inserts n default contructed values.
600 //!
601 //! <b>Throws</b>: If allocator_type's default constructor or copy constructor
602 //! throws or T's default or copy constructor throws.
603 //!
604 //! <b>Complexity</b>: Linear to n.
605 explicit deque(size_type n)
606 : Base(n, allocator_type())
607 {
608 container_detail::insert_default_constructed_n_proxy<Allocator, iterator> proxy(this->alloc());
609 proxy.uninitialized_copy_n_and_update(this->begin(), n);
610 //deque_base will deallocate in case of exception...
611 }
612
613 //! <b>Effects</b>: Constructs a deque that will use a copy of allocator a
614 //! and inserts n copies of value.
615 //!
616 //! <b>Throws</b>: If allocator_type's default constructor or copy constructor
617 //! throws or T's default or copy constructor throws.
618 //!
619 //! <b>Complexity</b>: Linear to n.
620 deque(size_type n, const value_type& value,
621 const allocator_type& a = allocator_type())
622 : Base(n, a)
623 { this->priv_fill_initialize(value); }
624
625 //! <b>Effects</b>: Constructs a deque that will use a copy of allocator a
626 //! and inserts a copy of the range [first, last) in the deque.
627 //!
628 //! <b>Throws</b>: If allocator_type's default constructor or copy constructor
629 //! throws or T's constructor taking an dereferenced InIt throws.
630 //!
631 //! <b>Complexity</b>: Linear to the range [first, last).
632 template <class InIt>
633 deque(InIt first, InIt last, const allocator_type& a = allocator_type()
634 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
635 , typename container_detail::enable_if_c
636 < !container_detail::is_convertible<InIt, size_type>::value
637 >::type * = 0
638 #endif
639 )
640 : Base(a)
641 {
642 typedef typename std::iterator_traits<InIt>::iterator_category ItCat;
643 this->priv_range_initialize(first, last, ItCat());
644 }
645
646 //! <b>Effects</b>: Copy constructs a deque.
647 //!
648 //! <b>Postcondition</b>: x == *this.
649 //!
650 //! <b>Complexity</b>: Linear to the elements x contains.
651 deque(const deque& x)
652 : Base(allocator_traits_type::select_on_container_copy_construction(x.alloc()))
653 {
654 if(x.size()){
655 this->priv_initialize_map(x.size());
656 boost::container::uninitialized_copy_alloc
657 (this->alloc(), x.begin(), x.end(), this->members_.m_start);
658 }
659 }
660
661 //! <b>Effects</b>: Move constructor. Moves mx's resources to *this.
662 //!
663 //! <b>Throws</b>: If allocator_type's copy constructor throws.
664 //!
665 //! <b>Complexity</b>: Constant.
666 deque(BOOST_RV_REF(deque) x)
667 : Base(boost::move(static_cast<Base&>(x)))
668 { this->swap_members(x); }
669
670 //! <b>Effects</b>: Copy constructs a vector using the specified allocator.
671 //!
672 //! <b>Postcondition</b>: x == *this.
673 //!
674 //! <b>Throws</b>: If allocation
675 //! throws or T's copy constructor throws.
676 //!
677 //! <b>Complexity</b>: Linear to the elements x contains.
678 deque(const deque& x, const allocator_type &a)
679 : Base(a)
680 {
681 if(x.size()){
682 this->priv_initialize_map(x.size());
683 boost::container::uninitialized_copy_alloc
684 (this->alloc(), x.begin(), x.end(), this->members_.m_start);
685 }
686 }
687
688 //! <b>Effects</b>: Move constructor using the specified allocator.
689 //! Moves mx's resources to *this if a == allocator_type().
690 //! Otherwise copies values from x to *this.
691 //!
692 //! <b>Throws</b>: If allocation or T's copy constructor throws.
693 //!
694 //! <b>Complexity</b>: Constant if a == mx.get_allocator(), linear otherwise.
695 deque(BOOST_RV_REF(deque) mx, const allocator_type &a)
696 : Base(a)
697 {
698 if(mx.alloc() == a){
699 this->swap_members(mx);
700 }
701 else{
702 if(mx.size()){
703 this->priv_initialize_map(mx.size());
704 boost::container::uninitialized_copy_alloc
705 (this->alloc(), mx.begin(), mx.end(), this->members_.m_start);
706 }
707 }
708 }
709
710 //! <b>Effects</b>: Destroys the deque. All stored values are destroyed
711 //! and used memory is deallocated.
712 //!
713 //! <b>Throws</b>: Nothing.
714 //!
715 //! <b>Complexity</b>: Linear to the number of elements.
716 ~deque() BOOST_CONTAINER_NOEXCEPT
717 {
718 this->priv_destroy_range(this->members_.m_start, this->members_.m_finish);
719 }
720
721 //! <b>Effects</b>: Makes *this contain the same elements as x.
722 //!
723 //! <b>Postcondition</b>: this->size() == x.size(). *this contains a copy
724 //! of each of x's elements.
725 //!
726 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws.
727 //!
728 //! <b>Complexity</b>: Linear to the number of elements in x.
729 deque& operator= (BOOST_COPY_ASSIGN_REF(deque) x)
730 {
731 if (&x != this){
732 allocator_type &this_alloc = this->alloc();
733 const allocator_type &x_alloc = x.alloc();
734 container_detail::bool_<allocator_traits_type::
735 propagate_on_container_copy_assignment::value> flag;
736 if(flag && this_alloc != x_alloc){
737 this->clear();
738 this->shrink_to_fit();
739 }
740 container_detail::assign_alloc(this->alloc(), x.alloc(), flag);
741 container_detail::assign_alloc(this->ptr_alloc(), x.ptr_alloc(), flag);
742 this->assign(x.cbegin(), x.cend());
743 }
744 return *this;
745 }
746
747 //! <b>Effects</b>: Move assignment. All mx's values are transferred to *this.
748 //!
749 //! <b>Postcondition</b>: x.empty(). *this contains a the elements x had
750 //! before the function.
751 //!
752 //! <b>Throws</b>: If allocator_type's copy constructor throws.
753 //!
754 //! <b>Complexity</b>: Linear.
755 deque& operator= (BOOST_RV_REF(deque) x)
756 {
757 if (&x != this){
758 allocator_type &this_alloc = this->alloc();
759 allocator_type &x_alloc = x.alloc();
760 //If allocators are equal we can just swap pointers
761 if(this_alloc == x_alloc){
762 //Destroy objects but retain memory in case x reuses it in the future
763 this->clear();
764 this->swap_members(x);
765 //Move allocator if needed
766 container_detail::bool_<allocator_traits_type::
767 propagate_on_container_move_assignment::value> flag;
768 container_detail::move_alloc(this_alloc, x_alloc, flag);
769 container_detail::move_alloc(this->ptr_alloc(), x.ptr_alloc(), flag);
770 }
771 //If unequal allocators, then do a one by one move
772 else{
773 typedef typename std::iterator_traits<iterator>::iterator_category ItCat;
774 this->assign( boost::make_move_iterator(x.begin())
775 , boost::make_move_iterator(x.end()));
776 }
777 }
778 return *this;
779 }
780
781 //! <b>Effects</b>: Assigns the n copies of val to *this.
782 //!
783 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws.
784 //!
785 //! <b>Complexity</b>: Linear to n.
786 void assign(size_type n, const T& val)
787 {
788 typedef constant_iterator<value_type, difference_type> c_it;
789 this->assign(c_it(val, n), c_it());
790 }
791
792 //! <b>Effects</b>: Assigns the the range [first, last) to *this.
793 //!
794 //! <b>Throws</b>: If memory allocation throws or
795 //! T's constructor from dereferencing InIt throws.
796 //!
797 //! <b>Complexity</b>: Linear to n.
798 template <class InIt>
799 void assign(InIt first, InIt last
800 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
801 , typename container_detail::enable_if_c
802 < !container_detail::is_convertible<InIt, size_type>::value
803 && container_detail::is_input_iterator<InIt>::value
804 >::type * = 0
805 #endif
806 )
807 {
808 iterator cur = this->begin();
809 for ( ; first != last && cur != end(); ++cur, ++first){
810 *cur = *first;
811 }
812 if (first == last){
813 this->erase(cur, this->cend());
814 }
815 else{
816 this->insert(this->cend(), first, last);
817 }
818 }
819
820 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
821 template <class FwdIt>
822 void assign(FwdIt first, FwdIt last
823 , typename container_detail::enable_if_c
824 < !container_detail::is_convertible<FwdIt, size_type>::value
825 && !container_detail::is_input_iterator<FwdIt>::value
826 >::type * = 0
827 )
828 {
829 const size_type len = std::distance(first, last);
830 if (len > size()) {
831 FwdIt mid = first;
832 std::advance(mid, this->size());
833 boost::copy_or_move(first, mid, begin());
834 this->insert(this->cend(), mid, last);
835 }
836 else{
837 this->erase(boost::copy_or_move(first, last, this->begin()), cend());
838 }
839 }
840 #endif
841
842 //! <b>Effects</b>: Returns a copy of the internal allocator.
843 //!
844 //! <b>Throws</b>: If allocator's copy constructor throws.
845 //!
846 //! <b>Complexity</b>: Constant.
847 allocator_type get_allocator() const BOOST_CONTAINER_NOEXCEPT
848 { return Base::alloc(); }
849
850 //! <b>Effects</b>: Returns a reference to the internal allocator.
851 //!
852 //! <b>Throws</b>: Nothing
853 //!
854 //! <b>Complexity</b>: Constant.
855 //!
856 //! <b>Note</b>: Non-standard extension.
857 const stored_allocator_type &get_stored_allocator() const BOOST_CONTAINER_NOEXCEPT
858 { return Base::alloc(); }
859
860 //////////////////////////////////////////////
861 //
862 // iterators
863 //
864 //////////////////////////////////////////////
865
866 //! <b>Effects</b>: Returns a reference to the internal allocator.
867 //!
868 //! <b>Throws</b>: Nothing
869 //!
870 //! <b>Complexity</b>: Constant.
871 //!
872 //! <b>Note</b>: Non-standard extension.
873 stored_allocator_type &get_stored_allocator() BOOST_CONTAINER_NOEXCEPT
874 { return Base::alloc(); }
875
876 //! <b>Effects</b>: Returns an iterator to the first element contained in the deque.
877 //!
878 //! <b>Throws</b>: Nothing.
879 //!
880 //! <b>Complexity</b>: Constant.
881 iterator begin() BOOST_CONTAINER_NOEXCEPT
882 { return this->members_.m_start; }
883
884 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the deque.
885 //!
886 //! <b>Throws</b>: Nothing.
887 //!
888 //! <b>Complexity</b>: Constant.
889 const_iterator begin() const BOOST_CONTAINER_NOEXCEPT
890 { return this->members_.m_start; }
891
892 //! <b>Effects</b>: Returns an iterator to the end of the deque.
893 //!
894 //! <b>Throws</b>: Nothing.
895 //!
896 //! <b>Complexity</b>: Constant.
897 iterator end() BOOST_CONTAINER_NOEXCEPT
898 { return this->members_.m_finish; }
899
900 //! <b>Effects</b>: Returns a const_iterator to the end of the deque.
901 //!
902 //! <b>Throws</b>: Nothing.
903 //!
904 //! <b>Complexity</b>: Constant.
905 const_iterator end() const BOOST_CONTAINER_NOEXCEPT
906 { return this->members_.m_finish; }
907
908 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning
909 //! of the reversed deque.
910 //!
911 //! <b>Throws</b>: Nothing.
912 //!
913 //! <b>Complexity</b>: Constant.
914 reverse_iterator rbegin() BOOST_CONTAINER_NOEXCEPT
915 { return reverse_iterator(this->members_.m_finish); }
916
917 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
918 //! of the reversed deque.
919 //!
920 //! <b>Throws</b>: Nothing.
921 //!
922 //! <b>Complexity</b>: Constant.
923 const_reverse_iterator rbegin() const BOOST_CONTAINER_NOEXCEPT
924 { return const_reverse_iterator(this->members_.m_finish); }
925
926 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
927 //! of the reversed deque.
928 //!
929 //! <b>Throws</b>: Nothing.
930 //!
931 //! <b>Complexity</b>: Constant.
932 reverse_iterator rend() BOOST_CONTAINER_NOEXCEPT
933 { return reverse_iterator(this->members_.m_start); }
934
935 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
936 //! of the reversed deque.
937 //!
938 //! <b>Throws</b>: Nothing.
939 //!
940 //! <b>Complexity</b>: Constant.
941 const_reverse_iterator rend() const BOOST_CONTAINER_NOEXCEPT
942 { return const_reverse_iterator(this->members_.m_start); }
943
944 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the deque.
945 //!
946 //! <b>Throws</b>: Nothing.
947 //!
948 //! <b>Complexity</b>: Constant.
949 const_iterator cbegin() const BOOST_CONTAINER_NOEXCEPT
950 { return this->members_.m_start; }
951
952 //! <b>Effects</b>: Returns a const_iterator to the end of the deque.
953 //!
954 //! <b>Throws</b>: Nothing.
955 //!
956 //! <b>Complexity</b>: Constant.
957 const_iterator cend() const BOOST_CONTAINER_NOEXCEPT
958 { return this->members_.m_finish; }
959
960 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
961 //! of the reversed deque.
962 //!
963 //! <b>Throws</b>: Nothing.
964 //!
965 //! <b>Complexity</b>: Constant.
966 const_reverse_iterator crbegin() const BOOST_CONTAINER_NOEXCEPT
967 { return const_reverse_iterator(this->members_.m_finish); }
968
969 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
970 //! of the reversed deque.
971 //!
972 //! <b>Throws</b>: Nothing.
973 //!
974 //! <b>Complexity</b>: Constant.
975 const_reverse_iterator crend() const BOOST_CONTAINER_NOEXCEPT
976 { return const_reverse_iterator(this->members_.m_start); }
977
978 //////////////////////////////////////////////
979 //
980 // capacity
981 //
982 //////////////////////////////////////////////
983
984 //! <b>Effects</b>: Returns true if the deque contains no elements.
985 //!
986 //! <b>Throws</b>: Nothing.
987 //!
988 //! <b>Complexity</b>: Constant.
989 bool empty() const BOOST_CONTAINER_NOEXCEPT
990 { return this->members_.m_finish == this->members_.m_start; }
991
992 //! <b>Effects</b>: Returns the number of the elements contained in the deque.
993 //!
994 //! <b>Throws</b>: Nothing.
995 //!
996 //! <b>Complexity</b>: Constant.
997 size_type size() const BOOST_CONTAINER_NOEXCEPT
998 { return this->members_.m_finish - this->members_.m_start; }
999
1000 //! <b>Effects</b>: Returns the largest possible size of the deque.
1001 //!
1002 //! <b>Throws</b>: Nothing.
1003 //!
1004 //! <b>Complexity</b>: Constant.
1005 size_type max_size() const BOOST_CONTAINER_NOEXCEPT
1006 { return allocator_traits_type::max_size(this->alloc()); }
1007
1008 //! <b>Effects</b>: Inserts or erases elements at the end such that
1009 //! the size becomes n. New elements are default constructed.
1010 //!
1011 //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws.
1012 //!
1013 //! <b>Complexity</b>: Linear to the difference between size() and new_size.
1014 void resize(size_type new_size)
1015 {
1016 const size_type len = size();
1017 if (new_size < len)
1018 this->priv_erase_last_n(len - new_size);
1019 else{
1020 const size_type n = new_size - this->size();
1021 container_detail::insert_default_constructed_n_proxy<Allocator, iterator> proxy(this->alloc());
1022 priv_insert_back_aux_impl(n, proxy);
1023 }
1024 }
1025
1026 //! <b>Effects</b>: Inserts or erases elements at the end such that
1027 //! the size becomes n. New elements are copy constructed from x.
1028 //!
1029 //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws.
1030 //!
1031 //! <b>Complexity</b>: Linear to the difference between size() and new_size.
1032 void resize(size_type new_size, const value_type& x)
1033 {
1034 const size_type len = size();
1035 if (new_size < len)
1036 this->erase(this->members_.m_start + new_size, this->members_.m_finish);
1037 else
1038 this->insert(this->members_.m_finish, new_size - len, x);
1039 }
1040
1041 //! <b>Effects</b>: Tries to deallocate the excess of memory created
1042 //! with previous allocations. The size of the deque is unchanged
1043 //!
1044 //! <b>Throws</b>: If memory allocation throws.
1045 //!
1046 //! <b>Complexity</b>: Constant.
1047 void shrink_to_fit()
1048 {
1049 //This deque implementation already
1050 //deallocates excess nodes when erasing
1051 //so there is nothing to do except for
1052 //empty deque
1053 if(this->empty()){
1054 this->priv_clear_map();
1055 }
1056 }
1057
1058 //////////////////////////////////////////////
1059 //
1060 // element access
1061 //
1062 //////////////////////////////////////////////
1063
1064 //! <b>Requires</b>: !empty()
1065 //!
1066 //! <b>Effects</b>: Returns a reference to the first
1067 //! element of the container.
1068 //!
1069 //! <b>Throws</b>: Nothing.
1070 //!
1071 //! <b>Complexity</b>: Constant.
1072 reference front() BOOST_CONTAINER_NOEXCEPT
1073 { return *this->members_.m_start; }
1074
1075 //! <b>Requires</b>: !empty()
1076 //!
1077 //! <b>Effects</b>: Returns a const reference to the first element
1078 //! from the beginning of the container.
1079 //!
1080 //! <b>Throws</b>: Nothing.
1081 //!
1082 //! <b>Complexity</b>: Constant.
1083 const_reference front() const BOOST_CONTAINER_NOEXCEPT
1084 { return *this->members_.m_start; }
1085
1086 //! <b>Requires</b>: !empty()
1087 //!
1088 //! <b>Effects</b>: Returns a reference to the last
1089 //! element of the container.
1090 //!
1091 //! <b>Throws</b>: Nothing.
1092 //!
1093 //! <b>Complexity</b>: Constant.
1094 reference back() BOOST_CONTAINER_NOEXCEPT
1095 { return *(end()-1); }
1096
1097 //! <b>Requires</b>: !empty()
1098 //!
1099 //! <b>Effects</b>: Returns a const reference to the last
1100 //! element of the container.
1101 //!
1102 //! <b>Throws</b>: Nothing.
1103 //!
1104 //! <b>Complexity</b>: Constant.
1105 const_reference back() const BOOST_CONTAINER_NOEXCEPT
1106 { return *(cend()-1); }
1107
1108 //! <b>Requires</b>: size() > n.
1109 //!
1110 //! <b>Effects</b>: Returns a reference to the nth element
1111 //! from the beginning of the container.
1112 //!
1113 //! <b>Throws</b>: Nothing.
1114 //!
1115 //! <b>Complexity</b>: Constant.
1116 reference operator[](size_type n) BOOST_CONTAINER_NOEXCEPT
1117 { return this->members_.m_start[difference_type(n)]; }
1118
1119 //! <b>Requires</b>: size() > n.
1120 //!
1121 //! <b>Effects</b>: Returns a const reference to the nth element
1122 //! from the beginning of the container.
1123 //!
1124 //! <b>Throws</b>: Nothing.
1125 //!
1126 //! <b>Complexity</b>: Constant.
1127 const_reference operator[](size_type n) const BOOST_CONTAINER_NOEXCEPT
1128 { return this->members_.m_start[difference_type(n)]; }
1129
1130 //! <b>Requires</b>: size() > n.
1131 //!
1132 //! <b>Effects</b>: Returns a reference to the nth element
1133 //! from the beginning of the container.
1134 //!
1135 //! <b>Throws</b>: std::range_error if n >= size()
1136 //!
1137 //! <b>Complexity</b>: Constant.
1138 reference at(size_type n)
1139 { this->priv_range_check(n); return (*this)[n]; }
1140
1141 //! <b>Requires</b>: size() > n.
1142 //!
1143 //! <b>Effects</b>: Returns a const reference to the nth element
1144 //! from the beginning of the container.
1145 //!
1146 //! <b>Throws</b>: std::range_error if n >= size()
1147 //!
1148 //! <b>Complexity</b>: Constant.
1149 const_reference at(size_type n) const
1150 { this->priv_range_check(n); return (*this)[n]; }
1151
1152 //////////////////////////////////////////////
1153 //
1154 // modifiers
1155 //
1156 //////////////////////////////////////////////
1157
1158 #if defined(BOOST_CONTAINER_PERFECT_FORWARDING) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1159
1160 //! <b>Effects</b>: Inserts an object of type T constructed with
1161 //! std::forward<Args>(args)... in the beginning of the deque.
1162 //!
1163 //! <b>Throws</b>: If memory allocation throws or the in-place constructor throws.
1164 //!
1165 //! <b>Complexity</b>: Amortized constant time
1166 template <class... Args>
1167 void emplace_front(Args&&... args)
1168 {
1169 if(this->priv_push_front_simple_available()){
1170 allocator_traits_type::construct
1171 ( this->alloc()
1172 , this->priv_push_front_simple_pos()
1173 , boost::forward<Args>(args)...);
1174 this->priv_push_front_simple_commit();
1175 }
1176 else{
1177 typedef container_detail::insert_non_movable_emplace_proxy<Allocator, iterator, Args...> type;
1178 this->priv_insert_front_aux_impl(1, type(this->alloc(), boost::forward<Args>(args)...));
1179 }
1180 }
1181
1182 //! <b>Effects</b>: Inserts an object of type T constructed with
1183 //! std::forward<Args>(args)... in the end of the deque.
1184 //!
1185 //! <b>Throws</b>: If memory allocation throws or the in-place constructor throws.
1186 //!
1187 //! <b>Complexity</b>: Amortized constant time
1188 template <class... Args>
1189 void emplace_back(Args&&... args)
1190 {
1191 if(this->priv_push_back_simple_available()){
1192 allocator_traits_type::construct
1193 ( this->alloc()
1194 , this->priv_push_back_simple_pos()
1195 , boost::forward<Args>(args)...);
1196 this->priv_push_back_simple_commit();
1197 }
1198 else{
1199 typedef container_detail::insert_non_movable_emplace_proxy<Allocator, iterator, Args...> type;
1200 this->priv_insert_back_aux_impl(1, type(this->alloc(), boost::forward<Args>(args)...));
1201 }
1202 }
1203
1204 //! <b>Requires</b>: position must be a valid iterator of *this.
1205 //!
1206 //! <b>Effects</b>: Inserts an object of type T constructed with
1207 //! std::forward<Args>(args)... before position
1208 //!
1209 //! <b>Throws</b>: If memory allocation throws or the in-place constructor throws.
1210 //!
1211 //! <b>Complexity</b>: If position is end(), amortized constant time
1212 //! Linear time otherwise.
1213 template <class... Args>
1214 iterator emplace(const_iterator p, Args&&... args)
1215 {
1216 if(p == this->cbegin()){
1217 this->emplace_front(boost::forward<Args>(args)...);
1218 return this->begin();
1219 }
1220 else if(p == this->cend()){
1221 this->emplace_back(boost::forward<Args>(args)...);
1222 return (this->end()-1);
1223 }
1224 else{
1225 typedef container_detail::insert_emplace_proxy<Allocator, iterator, Args...> type;
1226 return this->priv_insert_aux_impl(p, 1, type(this->alloc(), boost::forward<Args>(args)...));
1227 }
1228 }
1229
1230 #else //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
1231
1232 //advanced_insert_int.hpp includes all necessary preprocessor machinery...
1233 #define BOOST_PP_LOCAL_MACRO(n) \
1234 BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, > ) \
1235 void emplace_front(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
1236 { \
1237 if(priv_push_front_simple_available()){ \
1238 allocator_traits_type::construct \
1239 ( this->alloc() \
1240 , this->priv_push_front_simple_pos() \
1241 BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)); \
1242 priv_push_front_simple_commit(); \
1243 } \
1244 else{ \
1245 container_detail::BOOST_PP_CAT(insert_non_movable_emplace_proxy_arg, n) \
1246 <Allocator, iterator BOOST_PP_ENUM_TRAILING_PARAMS(n, P)> proxy \
1247 (this->alloc() BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)); \
1248 priv_insert_front_aux_impl(1, proxy); \
1249 } \
1250 } \
1251 \
1252 BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
1253 void emplace_back(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
1254 { \
1255 if(priv_push_back_simple_available()){ \
1256 allocator_traits_type::construct \
1257 ( this->alloc() \
1258 , this->priv_push_back_simple_pos() \
1259 BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)); \
1260 priv_push_back_simple_commit(); \
1261 } \
1262 else{ \
1263 container_detail::BOOST_PP_CAT(insert_non_movable_emplace_proxy_arg, n) \
1264 <Allocator, iterator BOOST_PP_ENUM_TRAILING_PARAMS(n, P)> proxy \
1265 (this->alloc() BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)); \
1266 priv_insert_back_aux_impl(1, proxy); \
1267 } \
1268 } \
1269 \
1270 BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
1271 iterator emplace(const_iterator p \
1272 BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
1273 { \
1274 if(p == this->cbegin()){ \
1275 this->emplace_front(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)); \
1276 return this->begin(); \
1277 } \
1278 else if(p == cend()){ \
1279 this->emplace_back(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)); \
1280 return (this->end()-1); \
1281 } \
1282 else{ \
1283 container_detail::BOOST_PP_CAT(insert_emplace_proxy_arg, n) \
1284 <Allocator, iterator BOOST_PP_ENUM_TRAILING_PARAMS(n, P)> proxy \
1285 (this->alloc() BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)); \
1286 return this->priv_insert_aux_impl(p, 1, proxy); \
1287 } \
1288 } \
1289 //!
1290 #define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS)
1291 #include BOOST_PP_LOCAL_ITERATE()
1292
1293 #endif //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
1294
1295 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1296 //! <b>Effects</b>: Inserts a copy of x at the front of the deque.
1297 //!
1298 //! <b>Throws</b>: If memory allocation throws or
1299 //! T's copy constructor throws.
1300 //!
1301 //! <b>Complexity</b>: Amortized constant time.
1302 void push_front(const T &x);
1303
1304 //! <b>Effects</b>: Constructs a new element in the front of the deque
1305 //! and moves the resources of mx to this new element.
1306 //!
1307 //! <b>Throws</b>: If memory allocation throws.
1308 //!
1309 //! <b>Complexity</b>: Amortized constant time.
1310 void push_front(T &&x);
1311 #else
1312 BOOST_MOVE_CONVERSION_AWARE_CATCH(push_front, T, void, priv_push_front)
1313 #endif
1314
1315 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1316 //! <b>Effects</b>: Inserts a copy of x at the end of the deque.
1317 //!
1318 //! <b>Throws</b>: If memory allocation throws or
1319 //! T's copy constructor throws.
1320 //!
1321 //! <b>Complexity</b>: Amortized constant time.
1322 void push_back(const T &x);
1323
1324 //! <b>Effects</b>: Constructs a new element in the end of the deque
1325 //! and moves the resources of mx to this new element.
1326 //!
1327 //! <b>Throws</b>: If memory allocation throws.
1328 //!
1329 //! <b>Complexity</b>: Amortized constant time.
1330 void push_back(T &&x);
1331 #else
1332 BOOST_MOVE_CONVERSION_AWARE_CATCH(push_back, T, void, priv_push_back)
1333 #endif
1334
1335 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1336
1337 //! <b>Requires</b>: position must be a valid iterator of *this.
1338 //!
1339 //! <b>Effects</b>: Insert a copy of x before position.
1340 //!
1341 //! <b>Returns</b>: an iterator to the inserted element.
1342 //!
1343 //! <b>Throws</b>: If memory allocation throws or x's copy constructor throws.
1344 //!
1345 //! <b>Complexity</b>: If position is end(), amortized constant time
1346 //! Linear time otherwise.
1347 iterator insert(const_iterator position, const T &x);
1348
1349 //! <b>Requires</b>: position must be a valid iterator of *this.
1350 //!
1351 //! <b>Effects</b>: Insert a new element before position with mx's resources.
1352 //!
1353 //! <b>Returns</b>: an iterator to the inserted element.
1354 //!
1355 //! <b>Throws</b>: If memory allocation throws.
1356 //!
1357 //! <b>Complexity</b>: If position is end(), amortized constant time
1358 //! Linear time otherwise.
1359 iterator insert(const_iterator position, T &&x);
1360 #else
1361 BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, T, iterator, priv_insert, const_iterator)
1362 #endif
1363
1364 //! <b>Requires</b>: pos must be a valid iterator of *this.
1365 //!
1366 //! <b>Effects</b>: Insert n copies of x before pos.
1367 //!
1368 //! <b>Returns</b>: an iterator to the first inserted element or pos if n is 0.
1369 //!
1370 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws.
1371 //!
1372 //! <b>Complexity</b>: Linear to n.
1373 iterator insert(const_iterator pos, size_type n, const value_type& x)
1374 {
1375 typedef constant_iterator<value_type, difference_type> c_it;
1376 return this->insert(pos, c_it(x, n), c_it());
1377 }
1378
1379 //! <b>Requires</b>: pos must be a valid iterator of *this.
1380 //!
1381 //! <b>Effects</b>: Insert a copy of the [first, last) range before pos.
1382 //!
1383 //! <b>Returns</b>: an iterator to the first inserted element or pos if first == last.
1384 //!
1385 //! <b>Throws</b>: If memory allocation throws, T's constructor from a
1386 //! dereferenced InIt throws or T's copy constructor throws.
1387 //!
1388 //! <b>Complexity</b>: Linear to std::distance [first, last).
1389 template <class InIt>
1390 iterator insert(const_iterator pos, InIt first, InIt last
1391 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1392 , typename container_detail::enable_if_c
1393 < !container_detail::is_convertible<InIt, size_type>::value
1394 && container_detail::is_input_iterator<InIt>::value
1395 >::type * = 0
1396 #endif
1397 )
1398 {
1399 size_type n = 0;
1400 iterator it(pos);
1401 for(;first != last; ++first, ++n){
1402 it = this->emplace(it, *first);
1403 ++it;
1404 }
1405 it -= n;
1406 return it;
1407 }
1408
1409 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1410 template <class FwdIt>
1411 iterator insert(const_iterator p, FwdIt first, FwdIt last
1412 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1413 , typename container_detail::enable_if_c
1414 < !container_detail::is_convertible<FwdIt, size_type>::value
1415 && !container_detail::is_input_iterator<FwdIt>::value
1416 >::type * = 0
1417 #endif
1418 )
1419 {
1420 container_detail::insert_range_proxy<Allocator, FwdIt, iterator> proxy(this->alloc(), first);
1421 return priv_insert_aux_impl(p, (size_type)std::distance(first, last), proxy);
1422 }
1423 #endif
1424
1425 //! <b>Effects</b>: Removes the first element from the deque.
1426 //!
1427 //! <b>Throws</b>: Nothing.
1428 //!
1429 //! <b>Complexity</b>: Constant time.
1430 void pop_front() BOOST_CONTAINER_NOEXCEPT
1431 {
1432 if (this->members_.m_start.m_cur != this->members_.m_start.m_last - 1) {
1433 allocator_traits_type::destroy
1434 ( this->alloc()
1435 , container_detail::to_raw_pointer(this->members_.m_start.m_cur)
1436 );
1437 ++this->members_.m_start.m_cur;
1438 }
1439 else
1440 this->priv_pop_front_aux();
1441 }
1442
1443 //! <b>Effects</b>: Removes the last element from the deque.
1444 //!
1445 //! <b>Throws</b>: Nothing.
1446 //!
1447 //! <b>Complexity</b>: Constant time.
1448 void pop_back() BOOST_CONTAINER_NOEXCEPT
1449 {
1450 if (this->members_.m_finish.m_cur != this->members_.m_finish.m_first) {
1451 --this->members_.m_finish.m_cur;
1452 allocator_traits_type::destroy
1453 ( this->alloc()
1454 , container_detail::to_raw_pointer(this->members_.m_finish.m_cur)
1455 );
1456 }
1457 else
1458 this->priv_pop_back_aux();
1459 }
1460
1461 //! <b>Effects</b>: Erases the element at position pos.
1462 //!
1463 //! <b>Throws</b>: Nothing.
1464 //!
1465 //! <b>Complexity</b>: Linear to the elements between pos and the
1466 //! last element (if pos is near the end) or the first element
1467 //! if(pos is near the beginning).
1468 //! Constant if pos is the first or the last element.
1469 iterator erase(const_iterator pos) BOOST_CONTAINER_NOEXCEPT
1470 {
1471 const_iterator next = pos;
1472 ++next;
1473 size_type index = pos - this->members_.m_start;
1474 if (index < (this->size()/2)) {
1475 boost::move_backward(begin(), iterator(pos), iterator(next));
1476 pop_front();
1477 }
1478 else {
1479 boost::move(iterator(next), end(), iterator(pos));
1480 pop_back();
1481 }
1482 return this->members_.m_start + index;
1483 }
1484
1485 //! <b>Effects</b>: Erases the elements pointed by [first, last).
1486 //!
1487 //! <b>Throws</b>: Nothing.
1488 //!
1489 //! <b>Complexity</b>: Linear to the distance between first and
1490 //! last plus the elements between pos and the
1491 //! last element (if pos is near the end) or the first element
1492 //! if(pos is near the beginning).
1493 iterator erase(const_iterator first, const_iterator last) BOOST_CONTAINER_NOEXCEPT
1494 {
1495 if (first == this->members_.m_start && last == this->members_.m_finish) {
1496 this->clear();
1497 return this->members_.m_finish;
1498 }
1499 else {
1500 const size_type n = static_cast<size_type>(last - first);
1501 const size_type elems_before = static_cast<size_type>(first - this->members_.m_start);
1502 if (elems_before < (this->size() - n) - elems_before) {
1503 boost::move_backward(begin(), iterator(first), iterator(last));
1504 iterator new_start = this->members_.m_start + n;
1505 if(!Base::traits_t::trivial_dctr_after_move)
1506 this->priv_destroy_range(this->members_.m_start, new_start);
1507 this->priv_destroy_nodes(this->members_.m_start.m_node, new_start.m_node);
1508 this->members_.m_start = new_start;
1509 }
1510 else {
1511 boost::move(iterator(last), end(), iterator(first));
1512 iterator new_finish = this->members_.m_finish - n;
1513 if(!Base::traits_t::trivial_dctr_after_move)
1514 this->priv_destroy_range(new_finish, this->members_.m_finish);
1515 this->priv_destroy_nodes(new_finish.m_node + 1, this->members_.m_finish.m_node + 1);
1516 this->members_.m_finish = new_finish;
1517 }
1518 return this->members_.m_start + elems_before;
1519 }
1520 }
1521
1522 //! <b>Effects</b>: Swaps the contents of *this and x.
1523 //!
1524 //! <b>Throws</b>: Nothing.
1525 //!
1526 //! <b>Complexity</b>: Constant.
1527 void swap(deque &x)
1528 {
1529 this->swap_members(x);
1530 container_detail::bool_<allocator_traits_type::propagate_on_container_swap::value> flag;
1531 container_detail::swap_alloc(this->alloc(), x.alloc(), flag);
1532 container_detail::swap_alloc(this->ptr_alloc(), x.ptr_alloc(), flag);
1533 }
1534
1535 //! <b>Effects</b>: Erases all the elements of the deque.
1536 //!
1537 //! <b>Throws</b>: Nothing.
1538 //!
1539 //! <b>Complexity</b>: Linear to the number of elements in the deque.
1540 void clear() BOOST_CONTAINER_NOEXCEPT
1541 {
1542 for (index_pointer node = this->members_.m_start.m_node + 1;
1543 node < this->members_.m_finish.m_node;
1544 ++node) {
1545 this->priv_destroy_range(*node, *node + this->s_buffer_size());
1546 this->priv_deallocate_node(*node);
1547 }
1548
1549 if (this->members_.m_start.m_node != this->members_.m_finish.m_node) {
1550 this->priv_destroy_range(this->members_.m_start.m_cur, this->members_.m_start.m_last);
1551 this->priv_destroy_range(this->members_.m_finish.m_first, this->members_.m_finish.m_cur);
1552 this->priv_deallocate_node(this->members_.m_finish.m_first);
1553 }
1554 else
1555 this->priv_destroy_range(this->members_.m_start.m_cur, this->members_.m_finish.m_cur);
1556
1557 this->members_.m_finish = this->members_.m_start;
1558 }
1559
1560 /// @cond
1561 private:
1562
1563 void priv_erase_last_n(size_type n)
1564 {
1565 if(n == this->size()) {
1566 this->clear();
1567 }
1568 else {
1569 iterator new_finish = this->members_.m_finish - n;
1570 if(!Base::traits_t::trivial_dctr_after_move)
1571 this->priv_destroy_range(new_finish, this->members_.m_finish);
1572 this->priv_destroy_nodes(new_finish.m_node + 1, this->members_.m_finish.m_node + 1);
1573 this->members_.m_finish = new_finish;
1574 }
1575 }
1576
1577 void priv_range_check(size_type n) const
1578 { if (n >= this->size()) BOOST_RETHROW std::out_of_range("deque"); }
1579
1580 template <class U>
1581 iterator priv_insert(const_iterator position, BOOST_FWD_REF(U) x)
1582 {
1583 if (position == cbegin()){
1584 this->push_front(::boost::forward<U>(x));
1585 return begin();
1586 }
1587 else if (position == cend()){
1588 this->push_back(::boost::forward<U>(x));
1589 return --end();
1590 }
1591 else {
1592 return priv_insert_aux_impl
1593 (position, (size_type)1, container_detail::get_insert_value_proxy<iterator>(this->alloc(), ::boost::forward<U>(x)));
1594 }
1595 }
1596
1597 template <class U>
1598 void priv_push_front(BOOST_FWD_REF(U) x)
1599 {
1600 if(this->priv_push_front_simple_available()){
1601 allocator_traits_type::construct
1602 ( this->alloc(), this->priv_push_front_simple_pos(), ::boost::forward<U>(x));
1603 this->priv_push_front_simple_commit();
1604 }
1605 else{
1606 priv_insert_aux_impl
1607 (this->cbegin(), (size_type)1, container_detail::get_insert_value_proxy<iterator>(this->alloc(), ::boost::forward<U>(x)));
1608 }
1609 }
1610
1611 template <class U>
1612 void priv_push_back(BOOST_FWD_REF(U) x)
1613 {
1614 if(this->priv_push_back_simple_available()){
1615 allocator_traits_type::construct
1616 ( this->alloc(), this->priv_push_back_simple_pos(), ::boost::forward<U>(x));
1617 this->priv_push_back_simple_commit();
1618 }
1619 else{
1620 priv_insert_aux_impl
1621 (this->cend(), (size_type)1, container_detail::get_insert_value_proxy<iterator>(this->alloc(), ::boost::forward<U>(x)));
1622 container_detail::insert_copy_proxy<Allocator, iterator> proxy(this->alloc(), x);
1623 }
1624 }
1625
1626 bool priv_push_back_simple_available() const
1627 {
1628 return this->members_.m_map &&
1629 (this->members_.m_finish.m_cur != (this->members_.m_finish.m_last - 1));
1630 }
1631
1632 T *priv_push_back_simple_pos() const
1633 {
1634 return container_detail::to_raw_pointer(this->members_.m_finish.m_cur);
1635 }
1636
1637 void priv_push_back_simple_commit()
1638 {
1639 ++this->members_.m_finish.m_cur;
1640 }
1641
1642 bool priv_push_front_simple_available() const
1643 {
1644 return this->members_.m_map &&
1645 (this->members_.m_start.m_cur != this->members_.m_start.m_first);
1646 }
1647
1648 T *priv_push_front_simple_pos() const
1649 { return container_detail::to_raw_pointer(this->members_.m_start.m_cur) - 1; }
1650
1651 void priv_push_front_simple_commit()
1652 { --this->members_.m_start.m_cur; }
1653
1654 void priv_destroy_range(iterator p, iterator p2)
1655 {
1656 for(;p != p2; ++p){
1657 allocator_traits_type::destroy
1658 ( this->alloc()
1659 , container_detail::to_raw_pointer(&*p)
1660 );
1661 }
1662 }
1663
1664 void priv_destroy_range(pointer p, pointer p2)
1665 {
1666 for(;p != p2; ++p){
1667 allocator_traits_type::destroy
1668 ( this->alloc()
1669 , container_detail::to_raw_pointer(&*p)
1670 );
1671 }
1672 }
1673
1674 template<class InsertProxy>
1675 iterator priv_insert_aux_impl(const_iterator p, size_type n, InsertProxy interf)
1676 {
1677 iterator pos(p);
1678 const size_type pos_n = p - this->cbegin();
1679 if(!this->members_.m_map){
1680 this->priv_initialize_map(0);
1681 pos = this->begin();
1682 }
1683
1684 const size_type elemsbefore = static_cast<size_type>(pos - this->members_.m_start);
1685 const size_type length = this->size();
1686 if (elemsbefore < length / 2) {
1687 const iterator new_start = this->priv_reserve_elements_at_front(n);
1688 const iterator old_start = this->members_.m_start;
1689 if(!elemsbefore){
1690 interf.uninitialized_copy_n_and_update(new_start, n);
1691 this->members_.m_start = new_start;
1692 }
1693 else{
1694 pos = this->members_.m_start + elemsbefore;
1695 if (elemsbefore >= n) {
1696 const iterator start_n = this->members_.m_start + n;
1697 ::boost::container::uninitialized_move_alloc
1698 (this->alloc(), this->members_.m_start, start_n, new_start);
1699 this->members_.m_start = new_start;
1700 boost::move(start_n, pos, old_start);
1701 interf.copy_n_and_update(pos - n, n);
1702 }
1703 else {
1704 const size_type mid_count = n - elemsbefore;
1705 const iterator mid_start = old_start - mid_count;
1706 interf.uninitialized_copy_n_and_update(mid_start, mid_count);
1707 this->members_.m_start = mid_start;
1708 ::boost::container::uninitialized_move_alloc
1709 (this->alloc(), old_start, pos, new_start);
1710 this->members_.m_start = new_start;
1711 interf.copy_n_and_update(old_start, elemsbefore);
1712 }
1713 }
1714 }
1715 else {
1716 const iterator new_finish = this->priv_reserve_elements_at_back(n);
1717 const iterator old_finish = this->members_.m_finish;
1718 const size_type elemsafter = length - elemsbefore;
1719 if(!elemsafter){
1720 interf.uninitialized_copy_n_and_update(old_finish, n);
1721 this->members_.m_finish = new_finish;
1722 }
1723 else{
1724 pos = this->members_.m_finish - elemsafter;
1725 if (elemsafter >= n) {
1726 iterator finish_n = this->members_.m_finish - difference_type(n);
1727 ::boost::container::uninitialized_move_alloc
1728 (this->alloc(), finish_n, this->members_.m_finish, this->members_.m_finish);
1729 this->members_.m_finish = new_finish;
1730 boost::move_backward(pos, finish_n, old_finish);
1731 interf.copy_n_and_update(pos, n);
1732 }
1733 else {
1734 const size_type raw_gap = n - elemsafter;
1735 ::boost::container::uninitialized_move_alloc
1736 (this->alloc(), pos, old_finish, this->members_.m_finish + raw_gap);
1737 BOOST_TRY{
1738 interf.uninitialized_copy_n_and_update(old_finish, raw_gap);
1739 }
1740 BOOST_CATCH(...){
1741 this->priv_destroy_range(this->members_.m_finish, this->members_.m_finish + (old_finish - pos));
1742 BOOST_RETHROW
1743 }
1744 BOOST_CATCH_END
1745 this->members_.m_finish = new_finish;
1746 interf.copy_n_and_update(pos, elemsafter);
1747 /*
1748 interf.uninitialized_copy_some_and_update(old_finish, elemsafter, false);
1749 this->members_.m_finish += n-elemsafter;
1750 ::boost::container::uninitialized_move_alloc
1751 (this->alloc(), pos, old_finish, this->members_.m_finish);
1752 this->members_.m_finish = new_finish;
1753 interf.copy_remaining_to(pos);
1754 */
1755 }
1756 }
1757 }
1758 return this->begin() + pos_n;
1759 }
1760
1761 template <class InsertProxy>
1762 iterator priv_insert_back_aux_impl(size_type n, InsertProxy interf)
1763 {
1764 if(!this->members_.m_map){
1765 this->priv_initialize_map(0);
1766 }
1767
1768 iterator new_finish = this->priv_reserve_elements_at_back(n);
1769 iterator old_finish = this->members_.m_finish;
1770 interf.uninitialized_copy_n_and_update(old_finish, n);
1771 this->members_.m_finish = new_finish;
1772 return iterator(this->members_.m_finish - n);
1773 }
1774
1775 template <class InsertProxy>
1776 iterator priv_insert_front_aux_impl(size_type n, InsertProxy interf)
1777 {
1778 if(!this->members_.m_map){
1779 this->priv_initialize_map(0);
1780 }
1781
1782 iterator new_start = this->priv_reserve_elements_at_front(n);
1783 interf.uninitialized_copy_n_and_update(new_start, n);
1784 this->members_.m_start = new_start;
1785 return new_start;
1786 }
1787
1788 iterator priv_fill_insert(const_iterator pos, size_type n, const value_type& x)
1789 {
1790 typedef constant_iterator<value_type, difference_type> c_it;
1791 return this->insert(pos, c_it(x, n), c_it());
1792 }
1793
1794 // Precondition: this->members_.m_start and this->members_.m_finish have already been initialized,
1795 // but none of the deque's elements have yet been constructed.
1796 void priv_fill_initialize(const value_type& value)
1797 {
1798 index_pointer cur;
1799 BOOST_TRY {
1800 for (cur = this->members_.m_start.m_node; cur < this->members_.m_finish.m_node; ++cur){
1801 boost::container::uninitialized_fill_alloc
1802 (this->alloc(), *cur, *cur + this->s_buffer_size(), value);
1803 }
1804 boost::container::uninitialized_fill_alloc
1805 (this->alloc(), this->members_.m_finish.m_first, this->members_.m_finish.m_cur, value);
1806 }
1807 BOOST_CATCH(...){
1808 this->priv_destroy_range(this->members_.m_start, iterator(*cur, cur));
1809 BOOST_RETHROW
1810 }
1811 BOOST_CATCH_END
1812 }
1813
1814 template <class InIt>
1815 void priv_range_initialize(InIt first, InIt last, std::input_iterator_tag)
1816 {
1817 this->priv_initialize_map(0);
1818 BOOST_TRY {
1819 for ( ; first != last; ++first)
1820 this->emplace_back(*first);
1821 }
1822 BOOST_CATCH(...){
1823 this->clear();
1824 BOOST_RETHROW
1825 }
1826 BOOST_CATCH_END
1827 }
1828
1829 template <class FwdIt>
1830 void priv_range_initialize(FwdIt first, FwdIt last, std::forward_iterator_tag)
1831 {
1832 size_type n = 0;
1833 n = std::distance(first, last);
1834 this->priv_initialize_map(n);
1835
1836 index_pointer cur_node;
1837 BOOST_TRY {
1838 for (cur_node = this->members_.m_start.m_node;
1839 cur_node < this->members_.m_finish.m_node;
1840 ++cur_node) {
1841 FwdIt mid = first;
1842 std::advance(mid, this->s_buffer_size());
1843 ::boost::container::uninitialized_copy_or_move_alloc
1844 (this->alloc(), first, mid, *cur_node);
1845 first = mid;
1846 }
1847 ::boost::container::uninitialized_copy_or_move_alloc
1848 (this->alloc(), first, last, this->members_.m_finish.m_first);
1849 }
1850 BOOST_CATCH(...){
1851 this->priv_destroy_range(this->members_.m_start, iterator(*cur_node, cur_node));
1852 BOOST_RETHROW
1853 }
1854 BOOST_CATCH_END
1855 }
1856
1857 // Called only if this->members_.m_finish.m_cur == this->members_.m_finish.m_first.
1858 void priv_pop_back_aux()
1859 {
1860 this->priv_deallocate_node(this->members_.m_finish.m_first);
1861 this->members_.m_finish.priv_set_node(this->members_.m_finish.m_node - 1);
1862 this->members_.m_finish.m_cur = this->members_.m_finish.m_last - 1;
1863 allocator_traits_type::destroy
1864 ( this->alloc()
1865 , container_detail::to_raw_pointer(this->members_.m_finish.m_cur)
1866 );
1867 }
1868
1869 // Called only if this->members_.m_start.m_cur == this->members_.m_start.m_last - 1. Note that
1870 // if the deque has at least one element (a precondition for this member
1871 // function), and if this->members_.m_start.m_cur == this->members_.m_start.m_last, then the deque
1872 // must have at least two nodes.
1873 void priv_pop_front_aux()
1874 {
1875 allocator_traits_type::destroy
1876 ( this->alloc()
1877 , container_detail::to_raw_pointer(this->members_.m_start.m_cur)
1878 );
1879 this->priv_deallocate_node(this->members_.m_start.m_first);
1880 this->members_.m_start.priv_set_node(this->members_.m_start.m_node + 1);
1881 this->members_.m_start.m_cur = this->members_.m_start.m_first;
1882 }
1883
1884 iterator priv_reserve_elements_at_front(size_type n)
1885 {
1886 size_type vacancies = this->members_.m_start.m_cur - this->members_.m_start.m_first;
1887 if (n > vacancies){
1888 size_type new_elems = n-vacancies;
1889 size_type new_nodes = (new_elems + this->s_buffer_size() - 1) /
1890 this->s_buffer_size();
1891 size_type s = (size_type)(this->members_.m_start.m_node - this->members_.m_map);
1892 if (new_nodes > s){
1893 this->priv_reallocate_map(new_nodes, true);
1894 }
1895 size_type i = 1;
1896 BOOST_TRY {
1897 for (; i <= new_nodes; ++i)
1898 *(this->members_.m_start.m_node - i) = this->priv_allocate_node();
1899 }
1900 BOOST_CATCH(...) {
1901 for (size_type j = 1; j < i; ++j)
1902 this->priv_deallocate_node(*(this->members_.m_start.m_node - j));
1903 BOOST_RETHROW
1904 }
1905 BOOST_CATCH_END
1906 }
1907 return this->members_.m_start - difference_type(n);
1908 }
1909
1910 iterator priv_reserve_elements_at_back(size_type n)
1911 {
1912 size_type vacancies = (this->members_.m_finish.m_last - this->members_.m_finish.m_cur) - 1;
1913 if (n > vacancies){
1914 size_type new_elems = n - vacancies;
1915 size_type new_nodes = (new_elems + this->s_buffer_size() - 1)/s_buffer_size();
1916 size_type s = (size_type)(this->members_.m_map_size - (this->members_.m_finish.m_node - this->members_.m_map));
1917 if (new_nodes + 1 > s){
1918 this->priv_reallocate_map(new_nodes, false);
1919 }
1920 size_type i;
1921 BOOST_TRY {
1922 for (i = 1; i <= new_nodes; ++i)
1923 *(this->members_.m_finish.m_node + i) = this->priv_allocate_node();
1924 }
1925 BOOST_CATCH(...) {
1926 for (size_type j = 1; j < i; ++j)
1927 this->priv_deallocate_node(*(this->members_.m_finish.m_node + j));
1928 BOOST_RETHROW
1929 }
1930 BOOST_CATCH_END
1931 }
1932 return this->members_.m_finish + difference_type(n);
1933 }
1934
1935 void priv_reallocate_map(size_type nodes_to_add, bool add_at_front)
1936 {
1937 size_type old_num_nodes = this->members_.m_finish.m_node - this->members_.m_start.m_node + 1;
1938 size_type new_num_nodes = old_num_nodes + nodes_to_add;
1939
1940 index_pointer new_nstart;
1941 if (this->members_.m_map_size > 2 * new_num_nodes) {
1942 new_nstart = this->members_.m_map + (this->members_.m_map_size - new_num_nodes) / 2
1943 + (add_at_front ? nodes_to_add : 0);
1944 if (new_nstart < this->members_.m_start.m_node)
1945 boost::move(this->members_.m_start.m_node, this->members_.m_finish.m_node + 1, new_nstart);
1946 else
1947 boost::move_backward
1948 (this->members_.m_start.m_node, this->members_.m_finish.m_node + 1, new_nstart + old_num_nodes);
1949 }
1950 else {
1951 size_type new_map_size =
1952 this->members_.m_map_size + container_detail::max_value(this->members_.m_map_size, nodes_to_add) + 2;
1953
1954 index_pointer new_map = this->priv_allocate_map(new_map_size);
1955 new_nstart = new_map + (new_map_size - new_num_nodes) / 2
1956 + (add_at_front ? nodes_to_add : 0);
1957 boost::move(this->members_.m_start.m_node, this->members_.m_finish.m_node + 1, new_nstart);
1958 this->priv_deallocate_map(this->members_.m_map, this->members_.m_map_size);
1959
1960 this->members_.m_map = new_map;
1961 this->members_.m_map_size = new_map_size;
1962 }
1963
1964 this->members_.m_start.priv_set_node(new_nstart);
1965 this->members_.m_finish.priv_set_node(new_nstart + old_num_nodes - 1);
1966 }
1967 /// @endcond
1968};
1969
1970// Nonmember functions.
1971template <class T, class Allocator>
1972inline bool operator==(const deque<T, Allocator>& x, const deque<T, Allocator>& y)
1973{
1974 return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
1975}
1976
1977template <class T, class Allocator>
1978inline bool operator<(const deque<T, Allocator>& x, const deque<T, Allocator>& y)
1979{
1980 return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
1981}
1982
1983template <class T, class Allocator>
1984inline bool operator!=(const deque<T, Allocator>& x, const deque<T, Allocator>& y)
1985 { return !(x == y); }
1986
1987template <class T, class Allocator>
1988inline bool operator>(const deque<T, Allocator>& x, const deque<T, Allocator>& y)
1989 { return y < x; }
1990
1991template <class T, class Allocator>
1992inline bool operator>=(const deque<T, Allocator>& x, const deque<T, Allocator>& y)
1993 { return !(x < y); }
1994
1995template <class T, class Allocator>
1996inline bool operator<=(const deque<T, Allocator>& x, const deque<T, Allocator>& y)
1997 { return !(y < x); }
1998
1999template <class T, class Allocator>
2000inline void swap(deque<T, Allocator>& x, deque<T, Allocator>& y)
2001{ x.swap(y); }
2002
2003}}
2004
2005/// @cond
2006
2007namespace boost {
2008
2009//!has_trivial_destructor_after_move<> == true_type
2010//!specialization for optimizations
2011template <class T, class Allocator>
2012struct has_trivial_destructor_after_move<boost::container::deque<T, Allocator> >
2013 : public ::boost::has_trivial_destructor_after_move<Allocator>
2014{};
2015
2016}
2017
2018/// @endcond
2019
2020#include <boost/container/detail/config_end.hpp>
2021
2022#endif // #ifndef BOOST_CONTAINER_DEQUE_HPP