1 ////////////////////////////////////////////////////////////////////////////// 2 // 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) 6 // 7 // See http://www.boost.org/libs/container for documentation. 8 // 9 ////////////////////////////////////////////////////////////////////////////// 10 #ifndef BOOST_CONTAINER_DEQUE_HPP 11 #define BOOST_CONTAINER_DEQUE_HPP 12 13 #ifndef BOOST_CONFIG_HPP 14 # include <boost/config.hpp> 15 #endif 16 17 #if defined(BOOST_HAS_PRAGMA_ONCE) 18 # pragma once 19 #endif 20 21 #include <boost/container/detail/config_begin.hpp> 22 #include <boost/container/detail/workaround.hpp> 23 // container 24 #include <boost/container/allocator_traits.hpp> 25 #include <boost/container/container_fwd.hpp> 26 #include <boost/container/new_allocator.hpp> //new_allocator 27 #include <boost/container/throw_exception.hpp> 28 // container/detail 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/move/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/move/detail/to_raw_pointer.hpp> 39 #include <boost/container/detail/type_traits.hpp> 40 // move 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> 45 // move/detail 46 #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 47 #include <boost/move/detail/fwd_macros.hpp> 48 #endif 49 #include <boost/move/detail/move_helpers.hpp> 50 // other 51 #include <boost/assert.hpp> 52 #include <boost/core/no_exceptions_support.hpp> 53 // std 54 #include <cstddef> 55 56 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 57 #include <initializer_list> 58 #endif 59 60 namespace boost { 61 namespace container { 62 63 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 64 template <class T, class Allocator> 65 class deque; 66 67 template <class T> 68 struct deque_value_traits 69 { 70 typedef T value_type; 71 static const bool trivial_dctr = dtl::is_trivially_destructible<value_type>::value; 72 static const bool trivial_dctr_after_move = ::boost::has_trivial_destructor_after_move<value_type>::value; 73 }; 74 75 // Note: this function is simply a kludge to work around several compilers' 76 // bugs in handling constant expressions. 77 template<class T> 78 struct deque_buf_size 79 { 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); 83 }; 84 85 namespace dtl { 86 87 // Class invariants: 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> 112 class deque_iterator 113 { 114 public: 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 119 < IsConst 120 , typename boost::intrusive::pointer_traits<Pointer>::template 121 rebind_pointer<const value_type>::type 122 , Pointer 123 >::type pointer; 124 typedef typename if_c 125 < IsConst 126 , const value_type& 127 , value_type& 128 >::type reference; 129 130 class nat; 131 typedef typename dtl::if_c< IsConst 132 , deque_iterator<Pointer, false> 133 , nat>::type nonconst_iterator; 134 s_buffer_size()135 BOOST_CONTAINER_FORCEINLINE static std::size_t s_buffer_size() 136 { return deque_buf_size<value_type>::value; } 137 138 typedef Pointer val_alloc_ptr; 139 typedef typename boost::intrusive::pointer_traits<Pointer>:: 140 template rebind_pointer<Pointer>::type index_pointer; 141 142 Pointer m_cur; 143 Pointer m_first; 144 Pointer m_last; 145 index_pointer m_node; 146 147 public: 148 get_cur() const149 BOOST_CONTAINER_FORCEINLINE Pointer get_cur() const { return m_cur; } get_first() const150 BOOST_CONTAINER_FORCEINLINE Pointer get_first() const { return m_first; } get_last() const151 BOOST_CONTAINER_FORCEINLINE Pointer get_last() const { return m_last; } get_node() const152 BOOST_CONTAINER_FORCEINLINE index_pointer get_node() const { return m_node; } 153 deque_iterator(val_alloc_ptr x,index_pointer y)154 BOOST_CONTAINER_FORCEINLINE deque_iterator(val_alloc_ptr x, index_pointer y) BOOST_NOEXCEPT_OR_NOTHROW 155 : m_cur(x), m_first(*y), m_last(*y + s_buffer_size()), m_node(y) 156 {} 157 deque_iterator()158 BOOST_CONTAINER_FORCEINLINE deque_iterator() BOOST_NOEXCEPT_OR_NOTHROW 159 : m_cur(), m_first(), m_last(), m_node() //Value initialization to achieve "null iterators" (N3644) 160 {} 161 deque_iterator(const deque_iterator & x)162 BOOST_CONTAINER_FORCEINLINE deque_iterator(const deque_iterator& x) BOOST_NOEXCEPT_OR_NOTHROW 163 : m_cur(x.get_cur()), m_first(x.get_first()), m_last(x.get_last()), m_node(x.get_node()) 164 {} 165 deque_iterator(const nonconst_iterator & x)166 BOOST_CONTAINER_FORCEINLINE deque_iterator(const nonconst_iterator& x) BOOST_NOEXCEPT_OR_NOTHROW 167 : m_cur(x.get_cur()), m_first(x.get_first()), m_last(x.get_last()), m_node(x.get_node()) 168 {} 169 deque_iterator(Pointer cur,Pointer first,Pointer last,index_pointer node)170 deque_iterator(Pointer cur, Pointer first, Pointer last, index_pointer node) BOOST_NOEXCEPT_OR_NOTHROW 171 : m_cur(cur), m_first(first), m_last(last), m_node(node) 172 {} 173 operator =(const deque_iterator & x)174 BOOST_CONTAINER_FORCEINLINE deque_iterator& operator=(const deque_iterator& x) BOOST_NOEXCEPT_OR_NOTHROW 175 { m_cur = x.get_cur(); m_first = x.get_first(); m_last = x.get_last(); m_node = x.get_node(); return *this; } 176 unconst() const177 BOOST_CONTAINER_FORCEINLINE deque_iterator<Pointer, false> unconst() const BOOST_NOEXCEPT_OR_NOTHROW 178 { 179 return deque_iterator<Pointer, false>(this->get_cur(), this->get_first(), this->get_last(), this->get_node()); 180 } 181 operator *() const182 BOOST_CONTAINER_FORCEINLINE reference operator*() const BOOST_NOEXCEPT_OR_NOTHROW 183 { return *this->m_cur; } 184 operator ->() const185 BOOST_CONTAINER_FORCEINLINE pointer operator->() const BOOST_NOEXCEPT_OR_NOTHROW 186 { return this->m_cur; } 187 operator -(const deque_iterator & x) const188 difference_type operator-(const deque_iterator& x) const BOOST_NOEXCEPT_OR_NOTHROW 189 { 190 if(!this->m_cur && !x.m_cur){ 191 return 0; 192 } 193 return difference_type(this->s_buffer_size()) * (this->m_node - x.m_node - 1) + 194 (this->m_cur - this->m_first) + (x.m_last - x.m_cur); 195 } 196 operator ++()197 deque_iterator& operator++() BOOST_NOEXCEPT_OR_NOTHROW 198 { 199 ++this->m_cur; 200 if (this->m_cur == this->m_last) { 201 this->priv_set_node(this->m_node + 1); 202 this->m_cur = this->m_first; 203 } 204 return *this; 205 } 206 operator ++(int)207 BOOST_CONTAINER_FORCEINLINE deque_iterator operator++(int) BOOST_NOEXCEPT_OR_NOTHROW 208 { 209 deque_iterator tmp(*this); 210 ++*this; 211 return tmp; 212 } 213 operator --()214 deque_iterator& operator--() BOOST_NOEXCEPT_OR_NOTHROW 215 { 216 if (this->m_cur == this->m_first) { 217 this->priv_set_node(this->m_node - 1); 218 this->m_cur = this->m_last; 219 } 220 --this->m_cur; 221 return *this; 222 } 223 operator --(int)224 BOOST_CONTAINER_FORCEINLINE deque_iterator operator--(int) BOOST_NOEXCEPT_OR_NOTHROW 225 { 226 deque_iterator tmp(*this); 227 --*this; 228 return tmp; 229 } 230 operator +=(difference_type n)231 deque_iterator& operator+=(difference_type n) BOOST_NOEXCEPT_OR_NOTHROW 232 { 233 difference_type offset = n + (this->m_cur - this->m_first); 234 if (offset >= 0 && offset < difference_type(this->s_buffer_size())) 235 this->m_cur += n; 236 else { 237 difference_type node_offset = 238 offset > 0 ? offset / difference_type(this->s_buffer_size()) 239 : -difference_type((-offset - 1) / this->s_buffer_size()) - 1; 240 this->priv_set_node(this->m_node + node_offset); 241 this->m_cur = this->m_first + 242 (offset - node_offset * difference_type(this->s_buffer_size())); 243 } 244 return *this; 245 } 246 operator +(difference_type n) const247 BOOST_CONTAINER_FORCEINLINE deque_iterator operator+(difference_type n) const BOOST_NOEXCEPT_OR_NOTHROW 248 { deque_iterator tmp(*this); return tmp += n; } 249 operator -=(difference_type n)250 BOOST_CONTAINER_FORCEINLINE deque_iterator& operator-=(difference_type n) BOOST_NOEXCEPT_OR_NOTHROW 251 { return *this += -n; } 252 operator -(difference_type n) const253 BOOST_CONTAINER_FORCEINLINE deque_iterator operator-(difference_type n) const BOOST_NOEXCEPT_OR_NOTHROW 254 { deque_iterator tmp(*this); return tmp -= n; } 255 operator [](difference_type n) const256 BOOST_CONTAINER_FORCEINLINE reference operator[](difference_type n) const BOOST_NOEXCEPT_OR_NOTHROW 257 { return *(*this + n); } 258 operator ==(const deque_iterator & l,const deque_iterator & r)259 BOOST_CONTAINER_FORCEINLINE friend bool operator==(const deque_iterator& l, const deque_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW 260 { return l.m_cur == r.m_cur; } 261 operator !=(const deque_iterator & l,const deque_iterator & r)262 BOOST_CONTAINER_FORCEINLINE friend bool operator!=(const deque_iterator& l, const deque_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW 263 { return l.m_cur != r.m_cur; } 264 operator <(const deque_iterator & l,const deque_iterator & r)265 BOOST_CONTAINER_FORCEINLINE friend bool operator<(const deque_iterator& l, const deque_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW 266 { return (l.m_node == r.m_node) ? (l.m_cur < r.m_cur) : (l.m_node < r.m_node); } 267 operator >(const deque_iterator & l,const deque_iterator & r)268 BOOST_CONTAINER_FORCEINLINE friend bool operator>(const deque_iterator& l, const deque_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW 269 { return r < l; } 270 operator <=(const deque_iterator & l,const deque_iterator & r)271 BOOST_CONTAINER_FORCEINLINE friend bool operator<=(const deque_iterator& l, const deque_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW 272 { return !(r < l); } 273 operator >=(const deque_iterator & l,const deque_iterator & r)274 BOOST_CONTAINER_FORCEINLINE friend bool operator>=(const deque_iterator& l, const deque_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW 275 { return !(l < r); } 276 priv_set_node(index_pointer new_node)277 BOOST_CONTAINER_FORCEINLINE void priv_set_node(index_pointer new_node) BOOST_NOEXCEPT_OR_NOTHROW 278 { 279 this->m_node = new_node; 280 this->m_first = *new_node; 281 this->m_last = this->m_first + this->s_buffer_size(); 282 } 283 operator +(difference_type n,deque_iterator x)284 BOOST_CONTAINER_FORCEINLINE friend deque_iterator operator+(difference_type n, deque_iterator x) BOOST_NOEXCEPT_OR_NOTHROW 285 { return x += n; } 286 }; 287 288 } //namespace dtl { 289 290 // Deque base class. It has two purposes. First, its constructor 291 // and destructor allocate (but don't initialize) storage. This makes 292 // exception safety easier. 293 template <class Allocator> 294 class deque_base 295 { 296 BOOST_COPYABLE_AND_MOVABLE(deque_base) 297 public: 298 typedef allocator_traits<Allocator> val_alloc_traits_type; 299 typedef typename val_alloc_traits_type::value_type val_alloc_val; 300 typedef typename val_alloc_traits_type::pointer val_alloc_ptr; 301 typedef typename val_alloc_traits_type::const_pointer val_alloc_cptr; 302 typedef typename val_alloc_traits_type::reference val_alloc_ref; 303 typedef typename val_alloc_traits_type::const_reference val_alloc_cref; 304 typedef typename val_alloc_traits_type::difference_type val_alloc_diff; 305 typedef typename val_alloc_traits_type::size_type val_alloc_size; 306 typedef typename val_alloc_traits_type::template 307 portable_rebind_alloc<val_alloc_ptr>::type ptr_alloc_t; 308 typedef allocator_traits<ptr_alloc_t> ptr_alloc_traits_type; 309 typedef typename ptr_alloc_traits_type::value_type ptr_alloc_val; 310 typedef typename ptr_alloc_traits_type::pointer ptr_alloc_ptr; 311 typedef typename ptr_alloc_traits_type::const_pointer ptr_alloc_cptr; 312 typedef typename ptr_alloc_traits_type::reference ptr_alloc_ref; 313 typedef typename ptr_alloc_traits_type::const_reference ptr_alloc_cref; 314 typedef Allocator allocator_type; 315 typedef allocator_type stored_allocator_type; 316 typedef val_alloc_size size_type; 317 318 protected: 319 320 typedef deque_value_traits<val_alloc_val> traits_t; 321 typedef ptr_alloc_t map_allocator_type; 322 s_buffer_size()323 BOOST_CONTAINER_FORCEINLINE static size_type s_buffer_size() BOOST_NOEXCEPT_OR_NOTHROW 324 { return deque_buf_size<val_alloc_val>::value; } 325 priv_allocate_node()326 BOOST_CONTAINER_FORCEINLINE val_alloc_ptr priv_allocate_node() 327 { return this->alloc().allocate(s_buffer_size()); } 328 priv_deallocate_node(val_alloc_ptr p)329 BOOST_CONTAINER_FORCEINLINE void priv_deallocate_node(val_alloc_ptr p) BOOST_NOEXCEPT_OR_NOTHROW 330 { this->alloc().deallocate(p, s_buffer_size()); } 331 priv_allocate_map(size_type n)332 BOOST_CONTAINER_FORCEINLINE ptr_alloc_ptr priv_allocate_map(size_type n) 333 { return this->ptr_alloc().allocate(n); } 334 priv_deallocate_map(ptr_alloc_ptr p,size_type n)335 BOOST_CONTAINER_FORCEINLINE void priv_deallocate_map(ptr_alloc_ptr p, size_type n) BOOST_NOEXCEPT_OR_NOTHROW 336 { this->ptr_alloc().deallocate(p, n); } 337 338 typedef dtl::deque_iterator<val_alloc_ptr, false> iterator; 339 typedef dtl::deque_iterator<val_alloc_ptr, true > const_iterator; 340 deque_base(size_type num_elements,const allocator_type & a)341 BOOST_CONTAINER_FORCEINLINE deque_base(size_type num_elements, const allocator_type& a) 342 : members_(a) 343 { this->priv_initialize_map(num_elements); } 344 deque_base(const allocator_type & a)345 BOOST_CONTAINER_FORCEINLINE explicit deque_base(const allocator_type& a) 346 : members_(a) 347 {} 348 deque_base()349 BOOST_CONTAINER_FORCEINLINE deque_base() 350 : members_() 351 {} 352 deque_base(BOOST_RV_REF (deque_base)x)353 BOOST_CONTAINER_FORCEINLINE explicit deque_base(BOOST_RV_REF(deque_base) x) 354 : members_( boost::move(x.ptr_alloc()) 355 , boost::move(x.alloc()) ) 356 {} 357 ~deque_base()358 ~deque_base() 359 { 360 if (this->members_.m_map) { 361 this->priv_destroy_nodes(this->members_.m_start.m_node, this->members_.m_finish.m_node + 1); 362 this->priv_deallocate_map(this->members_.m_map, this->members_.m_map_size); 363 } 364 } 365 366 private: 367 deque_base(const deque_base&); 368 369 protected: 370 swap_members(deque_base & x)371 void swap_members(deque_base &x) BOOST_NOEXCEPT_OR_NOTHROW 372 { 373 ::boost::adl_move_swap(this->members_.m_start, x.members_.m_start); 374 ::boost::adl_move_swap(this->members_.m_finish, x.members_.m_finish); 375 ::boost::adl_move_swap(this->members_.m_map, x.members_.m_map); 376 ::boost::adl_move_swap(this->members_.m_map_size, x.members_.m_map_size); 377 } 378 priv_initialize_map(size_type num_elements)379 void priv_initialize_map(size_type num_elements) 380 { 381 // if(num_elements){ 382 size_type num_nodes = num_elements / s_buffer_size() + 1; 383 384 this->members_.m_map_size = dtl::max_value((size_type) InitialMapSize, num_nodes + 2); 385 this->members_.m_map = this->priv_allocate_map(this->members_.m_map_size); 386 387 ptr_alloc_ptr nstart = this->members_.m_map + (this->members_.m_map_size - num_nodes) / 2; 388 ptr_alloc_ptr nfinish = nstart + num_nodes; 389 390 BOOST_TRY { 391 this->priv_create_nodes(nstart, nfinish); 392 } 393 BOOST_CATCH(...){ 394 this->priv_deallocate_map(this->members_.m_map, this->members_.m_map_size); 395 this->members_.m_map = 0; 396 this->members_.m_map_size = 0; 397 BOOST_RETHROW 398 } 399 BOOST_CATCH_END 400 401 this->members_.m_start.priv_set_node(nstart); 402 this->members_.m_finish.priv_set_node(nfinish - 1); 403 this->members_.m_start.m_cur = this->members_.m_start.m_first; 404 this->members_.m_finish.m_cur = this->members_.m_finish.m_first + 405 num_elements % s_buffer_size(); 406 // } 407 } 408 priv_create_nodes(ptr_alloc_ptr nstart,ptr_alloc_ptr nfinish)409 void priv_create_nodes(ptr_alloc_ptr nstart, ptr_alloc_ptr nfinish) 410 { 411 ptr_alloc_ptr cur = nstart; 412 BOOST_TRY { 413 for (; cur < nfinish; ++cur) 414 *cur = this->priv_allocate_node(); 415 } 416 BOOST_CATCH(...){ 417 this->priv_destroy_nodes(nstart, cur); 418 BOOST_RETHROW 419 } 420 BOOST_CATCH_END 421 } 422 priv_destroy_nodes(ptr_alloc_ptr nstart,ptr_alloc_ptr nfinish)423 void priv_destroy_nodes(ptr_alloc_ptr nstart, ptr_alloc_ptr nfinish) BOOST_NOEXCEPT_OR_NOTHROW 424 { 425 for (ptr_alloc_ptr n = nstart; n < nfinish; ++n) 426 this->priv_deallocate_node(*n); 427 } 428 priv_clear_map()429 void priv_clear_map() BOOST_NOEXCEPT_OR_NOTHROW 430 { 431 if (this->members_.m_map) { 432 this->priv_destroy_nodes(this->members_.m_start.m_node, this->members_.m_finish.m_node + 1); 433 this->priv_deallocate_map(this->members_.m_map, this->members_.m_map_size); 434 this->members_.m_map = 0; 435 this->members_.m_map_size = 0; 436 this->members_.m_start = iterator(); 437 this->members_.m_finish = this->members_.m_start; 438 } 439 } 440 441 enum { InitialMapSize = 8 }; 442 443 protected: 444 struct members_holder 445 : public ptr_alloc_t 446 , public allocator_type 447 { members_holderboost::container::deque_base::members_holder448 members_holder() 449 : map_allocator_type(), allocator_type() 450 , m_map(0), m_map_size(0) 451 , m_start(), m_finish(m_start) 452 {} 453 members_holderboost::container::deque_base::members_holder454 explicit members_holder(const allocator_type &a) 455 : map_allocator_type(a), allocator_type(a) 456 , m_map(0), m_map_size(0) 457 , m_start(), m_finish(m_start) 458 {} 459 460 template<class ValAllocConvertible, class PtrAllocConvertible> members_holderboost::container::deque_base::members_holder461 members_holder(BOOST_FWD_REF(PtrAllocConvertible) pa, BOOST_FWD_REF(ValAllocConvertible) va) 462 : map_allocator_type(boost::forward<PtrAllocConvertible>(pa)) 463 , allocator_type (boost::forward<ValAllocConvertible>(va)) 464 , m_map(0), m_map_size(0) 465 , m_start(), m_finish(m_start) 466 {} 467 468 ptr_alloc_ptr m_map; 469 val_alloc_size m_map_size; 470 iterator m_start; 471 iterator m_finish; 472 } members_; 473 ptr_alloc()474 BOOST_CONTAINER_FORCEINLINE ptr_alloc_t &ptr_alloc() BOOST_NOEXCEPT_OR_NOTHROW 475 { return members_; } 476 ptr_alloc() const477 BOOST_CONTAINER_FORCEINLINE const ptr_alloc_t &ptr_alloc() const BOOST_NOEXCEPT_OR_NOTHROW 478 { return members_; } 479 alloc()480 BOOST_CONTAINER_FORCEINLINE allocator_type &alloc() BOOST_NOEXCEPT_OR_NOTHROW 481 { return members_; } 482 alloc() const483 BOOST_CONTAINER_FORCEINLINE const allocator_type &alloc() const BOOST_NOEXCEPT_OR_NOTHROW 484 { return members_; } 485 }; 486 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 487 488 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED 489 //! A double-ended queue is a sequence that supports random access to elements, constant time insertion 490 //! and removal of elements at the end of the sequence, and linear time insertion and removal of elements in the middle. 491 //! 492 //! \tparam T The type of object that is stored in the deque 493 //! \tparam Allocator The allocator used for all internal memory management 494 template <class T, class Allocator = new_allocator<T> > 495 #else 496 template <class T, class Allocator> 497 #endif 498 class deque : protected deque_base<typename real_allocator<T, Allocator>::type> 499 { 500 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 501 private: 502 typedef deque_base<typename real_allocator<T, Allocator>::type> Base; 503 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 504 typedef typename real_allocator<T, Allocator>::type ValAllocator; 505 506 public: 507 508 ////////////////////////////////////////////// 509 // 510 // types 511 // 512 ////////////////////////////////////////////// 513 514 typedef T value_type; 515 typedef ValAllocator allocator_type; 516 typedef typename ::boost::container::allocator_traits<ValAllocator>::pointer pointer; 517 typedef typename ::boost::container::allocator_traits<ValAllocator>::const_pointer const_pointer; 518 typedef typename ::boost::container::allocator_traits<ValAllocator>::reference reference; 519 typedef typename ::boost::container::allocator_traits<ValAllocator>::const_reference const_reference; 520 typedef typename ::boost::container::allocator_traits<ValAllocator>::size_type size_type; 521 typedef typename ::boost::container::allocator_traits<ValAllocator>::difference_type difference_type; 522 typedef BOOST_CONTAINER_IMPDEF(allocator_type) stored_allocator_type; 523 typedef BOOST_CONTAINER_IMPDEF(typename Base::iterator) iterator; 524 typedef BOOST_CONTAINER_IMPDEF(typename Base::const_iterator) const_iterator; 525 typedef BOOST_CONTAINER_IMPDEF(boost::container::reverse_iterator<iterator>) reverse_iterator; 526 typedef BOOST_CONTAINER_IMPDEF(boost::container::reverse_iterator<const_iterator>) const_reverse_iterator; 527 528 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 529 530 private: // Internal typedefs 531 BOOST_COPYABLE_AND_MOVABLE(deque) 532 typedef typename Base::ptr_alloc_ptr index_pointer; s_buffer_size()533 BOOST_CONTAINER_FORCEINLINE static size_type s_buffer_size() 534 { return Base::s_buffer_size(); } 535 typedef allocator_traits<ValAllocator> allocator_traits_type; 536 537 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 538 539 public: 540 ////////////////////////////////////////////// 541 // 542 // construct/copy/destroy 543 // 544 ////////////////////////////////////////////// 545 546 //! <b>Effects</b>: Default constructors a deque. 547 //! 548 //! <b>Throws</b>: If allocator_type's default constructor throws. 549 //! 550 //! <b>Complexity</b>: Constant. deque()551 BOOST_CONTAINER_FORCEINLINE deque() BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<ValAllocator>::value) 552 : Base() 553 {} 554 555 //! <b>Effects</b>: Constructs a deque taking the allocator as parameter. 556 //! 557 //! <b>Throws</b>: Nothing 558 //! 559 //! <b>Complexity</b>: Constant. deque(const allocator_type & a)560 BOOST_CONTAINER_FORCEINLINE explicit deque(const allocator_type& a) BOOST_NOEXCEPT_OR_NOTHROW 561 : Base(a) 562 {} 563 564 //! <b>Effects</b>: Constructs a deque 565 //! and inserts n value initialized values. 566 //! 567 //! <b>Throws</b>: If allocator_type's default constructor 568 //! throws or T's value initialization throws. 569 //! 570 //! <b>Complexity</b>: Linear to n. deque(size_type n)571 BOOST_CONTAINER_FORCEINLINE explicit deque(size_type n) 572 : Base(n, allocator_type()) 573 { 574 dtl::insert_value_initialized_n_proxy<ValAllocator, iterator> proxy; 575 proxy.uninitialized_copy_n_and_update(this->alloc(), this->begin(), n); 576 //deque_base will deallocate in case of exception... 577 } 578 579 //! <b>Effects</b>: Constructs a deque 580 //! and inserts n default initialized values. 581 //! 582 //! <b>Throws</b>: If allocator_type's default constructor 583 //! throws or T's default initialization or copy constructor throws. 584 //! 585 //! <b>Complexity</b>: Linear to n. 586 //! 587 //! <b>Note</b>: Non-standard extension deque(size_type n,default_init_t)588 BOOST_CONTAINER_FORCEINLINE deque(size_type n, default_init_t) 589 : Base(n, allocator_type()) 590 { 591 dtl::insert_default_initialized_n_proxy<ValAllocator, iterator> proxy; 592 proxy.uninitialized_copy_n_and_update(this->alloc(), this->begin(), n); 593 //deque_base will deallocate in case of exception... 594 } 595 596 //! <b>Effects</b>: Constructs a deque that will use a copy of allocator a 597 //! and inserts n value initialized values. 598 //! 599 //! <b>Throws</b>: If allocator_type's default constructor 600 //! throws or T's value initialization throws. 601 //! 602 //! <b>Complexity</b>: Linear to n. deque(size_type n,const allocator_type & a)603 BOOST_CONTAINER_FORCEINLINE explicit deque(size_type n, const allocator_type &a) 604 : Base(n, a) 605 { 606 dtl::insert_value_initialized_n_proxy<ValAllocator, iterator> proxy; 607 proxy.uninitialized_copy_n_and_update(this->alloc(), this->begin(), n); 608 //deque_base will deallocate in case of exception... 609 } 610 611 //! <b>Effects</b>: Constructs a deque that will use a copy of allocator a 612 //! and inserts n default initialized values. 613 //! 614 //! <b>Throws</b>: If allocator_type's default constructor 615 //! throws or T's default initialization or copy constructor throws. 616 //! 617 //! <b>Complexity</b>: Linear to n. 618 //! 619 //! <b>Note</b>: Non-standard extension deque(size_type n,default_init_t,const allocator_type & a)620 BOOST_CONTAINER_FORCEINLINE deque(size_type n, default_init_t, const allocator_type &a) 621 : Base(n, a) 622 { 623 dtl::insert_default_initialized_n_proxy<ValAllocator, iterator> proxy; 624 proxy.uninitialized_copy_n_and_update(this->alloc(), this->begin(), n); 625 //deque_base will deallocate in case of exception... 626 } 627 628 //! <b>Effects</b>: Constructs a deque that will use a copy of allocator a 629 //! and inserts n copies of value. 630 //! 631 //! <b>Throws</b>: If allocator_type's default constructor 632 //! throws or T's copy constructor throws. 633 //! 634 //! <b>Complexity</b>: Linear to n. deque(size_type n,const value_type & value)635 BOOST_CONTAINER_FORCEINLINE deque(size_type n, const value_type& value) 636 : Base(n, allocator_type()) 637 { this->priv_fill_initialize(value); } 638 639 //! <b>Effects</b>: Constructs a deque that will use a copy of allocator a 640 //! and inserts n copies of value. 641 //! 642 //! <b>Throws</b>: If allocator_type's default constructor 643 //! throws or T's copy constructor throws. 644 //! 645 //! <b>Complexity</b>: Linear to n. deque(size_type n,const value_type & value,const allocator_type & a)646 BOOST_CONTAINER_FORCEINLINE deque(size_type n, const value_type& value, const allocator_type& a) 647 : Base(n, a) 648 { this->priv_fill_initialize(value); } 649 650 //! <b>Effects</b>: Constructs a deque that will use a copy of allocator a 651 //! and inserts a copy of the range [first, last) in the deque. 652 //! 653 //! <b>Throws</b>: If allocator_type's default constructor 654 //! throws or T's constructor taking a dereferenced InIt throws. 655 //! 656 //! <b>Complexity</b>: Linear to the range [first, last). 657 template <class InIt> deque(InIt first,InIt last,typename dtl::disable_if_convertible<InIt,size_type>::type * =0)658 BOOST_CONTAINER_FORCEINLINE deque(InIt first, InIt last 659 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 660 , typename dtl::disable_if_convertible 661 <InIt, size_type>::type * = 0 662 #endif 663 ) 664 : Base(allocator_type()) 665 { 666 this->priv_range_initialize(first, last); 667 } 668 669 //! <b>Effects</b>: Constructs a deque that will use a copy of allocator a 670 //! and inserts a copy of the range [first, last) in the deque. 671 //! 672 //! <b>Throws</b>: If allocator_type's default constructor 673 //! throws or T's constructor taking a dereferenced InIt throws. 674 //! 675 //! <b>Complexity</b>: Linear to the range [first, last). 676 template <class InIt> deque(InIt first,InIt last,const allocator_type & a,typename dtl::disable_if_convertible<InIt,size_type>::type * =0)677 BOOST_CONTAINER_FORCEINLINE deque(InIt first, InIt last, const allocator_type& a 678 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 679 , typename dtl::disable_if_convertible 680 <InIt, size_type>::type * = 0 681 #endif 682 ) 683 : Base(a) 684 { 685 this->priv_range_initialize(first, last); 686 } 687 688 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 689 //! <b>Effects</b>: Constructs a deque that will use a copy of allocator a 690 //! and inserts a copy of the range [il.begin(), il.end()) in the deque. 691 //! 692 //! <b>Throws</b>: If allocator_type's default constructor 693 //! throws or T's constructor taking a dereferenced std::initializer_list iterator throws. 694 //! 695 //! <b>Complexity</b>: Linear to the range [il.begin(), il.end()). deque(std::initializer_list<value_type> il,const allocator_type & a=allocator_type ())696 BOOST_CONTAINER_FORCEINLINE deque(std::initializer_list<value_type> il, const allocator_type& a = allocator_type()) 697 : Base(a) 698 { 699 this->priv_range_initialize(il.begin(), il.end()); 700 } 701 #endif 702 703 //! <b>Effects</b>: Copy constructs a deque. 704 //! 705 //! <b>Postcondition</b>: x == *this. 706 //! 707 //! <b>Complexity</b>: Linear to the elements x contains. deque(const deque & x)708 BOOST_CONTAINER_FORCEINLINE deque(const deque& x) 709 : Base(allocator_traits_type::select_on_container_copy_construction(x.alloc())) 710 { 711 if(x.size()){ 712 this->priv_initialize_map(x.size()); 713 boost::container::uninitialized_copy_alloc 714 (this->alloc(), x.begin(), x.end(), this->members_.m_start); 715 } 716 } 717 718 //! <b>Effects</b>: Move constructor. Moves x's resources to *this. 719 //! 720 //! <b>Throws</b>: If allocator_type's copy constructor throws. 721 //! 722 //! <b>Complexity</b>: Constant. deque(BOOST_RV_REF (deque)x)723 BOOST_CONTAINER_FORCEINLINE deque(BOOST_RV_REF(deque) x) BOOST_NOEXCEPT_OR_NOTHROW 724 : Base(BOOST_MOVE_BASE(Base, x)) 725 { this->swap_members(x); } 726 727 //! <b>Effects</b>: Copy constructs a vector using the specified allocator. 728 //! 729 //! <b>Postcondition</b>: x == *this. 730 //! 731 //! <b>Throws</b>: If allocation 732 //! throws or T's copy constructor throws. 733 //! 734 //! <b>Complexity</b>: Linear to the elements x contains. deque(const deque & x,const allocator_type & a)735 deque(const deque& x, const allocator_type &a) 736 : Base(a) 737 { 738 if(x.size()){ 739 this->priv_initialize_map(x.size()); 740 boost::container::uninitialized_copy_alloc 741 (this->alloc(), x.begin(), x.end(), this->members_.m_start); 742 } 743 } 744 745 //! <b>Effects</b>: Move constructor using the specified allocator. 746 //! Moves x's resources to *this if a == allocator_type(). 747 //! Otherwise copies values from x to *this. 748 //! 749 //! <b>Throws</b>: If allocation or T's copy constructor throws. 750 //! 751 //! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise. deque(BOOST_RV_REF (deque)x,const allocator_type & a)752 deque(BOOST_RV_REF(deque) x, const allocator_type &a) 753 : Base(a) 754 { 755 if(x.alloc() == a){ 756 this->swap_members(x); 757 } 758 else{ 759 if(x.size()){ 760 this->priv_initialize_map(x.size()); 761 boost::container::uninitialized_copy_alloc 762 ( this->alloc(), boost::make_move_iterator(x.begin()) 763 , boost::make_move_iterator(x.end()), this->members_.m_start); 764 } 765 } 766 } 767 768 //! <b>Effects</b>: Destroys the deque. All stored values are destroyed 769 //! and used memory is deallocated. 770 //! 771 //! <b>Throws</b>: Nothing. 772 //! 773 //! <b>Complexity</b>: Linear to the number of elements. ~deque()774 BOOST_CONTAINER_FORCEINLINE ~deque() BOOST_NOEXCEPT_OR_NOTHROW 775 { 776 this->priv_destroy_range(this->members_.m_start, this->members_.m_finish); 777 } 778 779 //! <b>Effects</b>: Makes *this contain the same elements as x. 780 //! 781 //! <b>Postcondition</b>: this->size() == x.size(). *this contains a copy 782 //! of each of x's elements. 783 //! 784 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws. 785 //! 786 //! <b>Complexity</b>: Linear to the number of elements in x. operator =(BOOST_COPY_ASSIGN_REF (deque)x)787 deque& operator= (BOOST_COPY_ASSIGN_REF(deque) x) 788 { 789 if (&x != this){ 790 allocator_type &this_alloc = this->alloc(); 791 const allocator_type &x_alloc = x.alloc(); 792 dtl::bool_<allocator_traits_type:: 793 propagate_on_container_copy_assignment::value> flag; 794 if(flag && this_alloc != x_alloc){ 795 this->clear(); 796 this->shrink_to_fit(); 797 } 798 dtl::assign_alloc(this->alloc(), x.alloc(), flag); 799 dtl::assign_alloc(this->ptr_alloc(), x.ptr_alloc(), flag); 800 this->assign(x.cbegin(), x.cend()); 801 } 802 return *this; 803 } 804 805 //! <b>Effects</b>: Move assignment. All x's values are transferred to *this. 806 //! 807 //! <b>Throws</b>: If allocator_traits_type::propagate_on_container_move_assignment 808 //! is false and (allocation throws or value_type's move constructor throws) 809 //! 810 //! <b>Complexity</b>: Constant if allocator_traits_type:: 811 //! propagate_on_container_move_assignment is true or 812 //! this->get>allocator() == x.get_allocator(). Linear otherwise. operator =(BOOST_RV_REF (deque)x)813 deque& operator= (BOOST_RV_REF(deque) x) 814 BOOST_NOEXCEPT_IF(allocator_traits_type::propagate_on_container_move_assignment::value 815 || allocator_traits_type::is_always_equal::value) 816 { 817 BOOST_ASSERT(this != &x); 818 allocator_type &this_alloc = this->alloc(); 819 allocator_type &x_alloc = x.alloc(); 820 const bool propagate_alloc = allocator_traits_type:: 821 propagate_on_container_move_assignment::value; 822 dtl::bool_<propagate_alloc> flag; 823 const bool allocators_equal = this_alloc == x_alloc; (void)allocators_equal; 824 //Resources can be transferred if both allocators are 825 //going to be equal after this function (either propagated or already equal) 826 if(propagate_alloc || allocators_equal){ 827 //Destroy objects but retain memory in case x reuses it in the future 828 this->clear(); 829 //Move allocator if needed 830 dtl::move_alloc(this_alloc, x_alloc, flag); 831 dtl::move_alloc(this->ptr_alloc(), x.ptr_alloc(), flag); 832 //Nothrow swap 833 this->swap_members(x); 834 } 835 //Else do a one by one move 836 else{ 837 this->assign( boost::make_move_iterator(x.begin()) 838 , boost::make_move_iterator(x.end())); 839 } 840 return *this; 841 } 842 843 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 844 //! <b>Effects</b>: Makes *this contain the same elements as il. 845 //! 846 //! <b>Postcondition</b>: this->size() == il.size(). *this contains a copy 847 //! of each of x's elements. 848 //! 849 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws. 850 //! 851 //! <b>Complexity</b>: Linear to the number of elements in il. operator =(std::initializer_list<value_type> il)852 BOOST_CONTAINER_FORCEINLINE deque& operator=(std::initializer_list<value_type> il) 853 { 854 this->assign(il.begin(), il.end()); 855 return *this; 856 } 857 #endif 858 859 //! <b>Effects</b>: Assigns the n copies of val to *this. 860 //! 861 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws. 862 //! 863 //! <b>Complexity</b>: Linear to n. assign(size_type n,const T & val)864 BOOST_CONTAINER_FORCEINLINE void assign(size_type n, const T& val) 865 { 866 typedef constant_iterator<value_type, difference_type> c_it; 867 this->assign(c_it(val, n), c_it()); 868 } 869 870 //! <b>Effects</b>: Assigns the the range [first, last) to *this. 871 //! 872 //! <b>Throws</b>: If memory allocation throws or 873 //! T's constructor from dereferencing InIt throws. 874 //! 875 //! <b>Complexity</b>: Linear to n. 876 template <class InIt> assign(InIt first,InIt last,typename dtl::disable_if_or<void,dtl::is_convertible<InIt,size_type>,dtl::is_not_input_iterator<InIt>>::type * =0)877 void assign(InIt first, InIt last 878 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 879 , typename dtl::disable_if_or 880 < void 881 , dtl::is_convertible<InIt, size_type> 882 , dtl::is_not_input_iterator<InIt> 883 >::type * = 0 884 #endif 885 ) 886 { 887 iterator cur = this->begin(); 888 for ( ; first != last && cur != end(); ++cur, ++first){ 889 *cur = *first; 890 } 891 if (first == last){ 892 this->erase(cur, this->cend()); 893 } 894 else{ 895 this->insert(this->cend(), first, last); 896 } 897 } 898 899 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 900 template <class FwdIt> assign(FwdIt first,FwdIt last,typename dtl::disable_if_or<void,dtl::is_convertible<FwdIt,size_type>,dtl::is_input_iterator<FwdIt>>::type * =0)901 void assign(FwdIt first, FwdIt last 902 , typename dtl::disable_if_or 903 < void 904 , dtl::is_convertible<FwdIt, size_type> 905 , dtl::is_input_iterator<FwdIt> 906 >::type * = 0 907 ) 908 { 909 const size_type len = boost::container::iterator_distance(first, last); 910 if (len > size()) { 911 FwdIt mid = first; 912 boost::container::iterator_advance(mid, this->size()); 913 boost::container::copy(first, mid, begin()); 914 this->insert(this->cend(), mid, last); 915 } 916 else{ 917 this->erase(boost::container::copy(first, last, this->begin()), cend()); 918 } 919 } 920 #endif 921 922 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 923 //! <b>Effects</b>: Assigns the the range [il.begin(), il.end()) to *this. 924 //! 925 //! <b>Throws</b>: If memory allocation throws or 926 //! T's constructor from dereferencing std::initializer_list iterator throws. 927 //! 928 //! <b>Complexity</b>: Linear to il.size(). assign(std::initializer_list<value_type> il)929 BOOST_CONTAINER_FORCEINLINE void assign(std::initializer_list<value_type> il) 930 { this->assign(il.begin(), il.end()); } 931 #endif 932 933 //! <b>Effects</b>: Returns a copy of the internal allocator. 934 //! 935 //! <b>Throws</b>: If allocator's copy constructor throws. 936 //! 937 //! <b>Complexity</b>: Constant. get_allocator() const938 BOOST_CONTAINER_FORCEINLINE allocator_type get_allocator() const BOOST_NOEXCEPT_OR_NOTHROW 939 { return Base::alloc(); } 940 941 //! <b>Effects</b>: Returns a reference to the internal allocator. 942 //! 943 //! <b>Throws</b>: Nothing 944 //! 945 //! <b>Complexity</b>: Constant. 946 //! 947 //! <b>Note</b>: Non-standard extension. get_stored_allocator() const948 BOOST_CONTAINER_FORCEINLINE const stored_allocator_type &get_stored_allocator() const BOOST_NOEXCEPT_OR_NOTHROW 949 { return Base::alloc(); } 950 951 ////////////////////////////////////////////// 952 // 953 // iterators 954 // 955 ////////////////////////////////////////////// 956 957 //! <b>Effects</b>: Returns a reference to the internal allocator. 958 //! 959 //! <b>Throws</b>: Nothing 960 //! 961 //! <b>Complexity</b>: Constant. 962 //! 963 //! <b>Note</b>: Non-standard extension. get_stored_allocator()964 BOOST_CONTAINER_FORCEINLINE stored_allocator_type &get_stored_allocator() BOOST_NOEXCEPT_OR_NOTHROW 965 { return Base::alloc(); } 966 967 //! <b>Effects</b>: Returns an iterator to the first element contained in the deque. 968 //! 969 //! <b>Throws</b>: Nothing. 970 //! 971 //! <b>Complexity</b>: Constant. begin()972 BOOST_CONTAINER_FORCEINLINE iterator begin() BOOST_NOEXCEPT_OR_NOTHROW 973 { return this->members_.m_start; } 974 975 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the deque. 976 //! 977 //! <b>Throws</b>: Nothing. 978 //! 979 //! <b>Complexity</b>: Constant. begin() const980 BOOST_CONTAINER_FORCEINLINE const_iterator begin() const BOOST_NOEXCEPT_OR_NOTHROW 981 { return this->members_.m_start; } 982 983 //! <b>Effects</b>: Returns an iterator to the end of the deque. 984 //! 985 //! <b>Throws</b>: Nothing. 986 //! 987 //! <b>Complexity</b>: Constant. end()988 BOOST_CONTAINER_FORCEINLINE iterator end() BOOST_NOEXCEPT_OR_NOTHROW 989 { return this->members_.m_finish; } 990 991 //! <b>Effects</b>: Returns a const_iterator to the end of the deque. 992 //! 993 //! <b>Throws</b>: Nothing. 994 //! 995 //! <b>Complexity</b>: Constant. end() const996 BOOST_CONTAINER_FORCEINLINE const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW 997 { return this->members_.m_finish; } 998 999 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning 1000 //! of the reversed deque. 1001 //! 1002 //! <b>Throws</b>: Nothing. 1003 //! 1004 //! <b>Complexity</b>: Constant. rbegin()1005 BOOST_CONTAINER_FORCEINLINE reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW 1006 { return reverse_iterator(this->members_.m_finish); } 1007 1008 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning 1009 //! of the reversed deque. 1010 //! 1011 //! <b>Throws</b>: Nothing. 1012 //! 1013 //! <b>Complexity</b>: Constant. rbegin() const1014 BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW 1015 { return const_reverse_iterator(this->members_.m_finish); } 1016 1017 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end 1018 //! of the reversed deque. 1019 //! 1020 //! <b>Throws</b>: Nothing. 1021 //! 1022 //! <b>Complexity</b>: Constant. rend()1023 BOOST_CONTAINER_FORCEINLINE reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW 1024 { return reverse_iterator(this->members_.m_start); } 1025 1026 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end 1027 //! of the reversed deque. 1028 //! 1029 //! <b>Throws</b>: Nothing. 1030 //! 1031 //! <b>Complexity</b>: Constant. rend() const1032 BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW 1033 { return const_reverse_iterator(this->members_.m_start); } 1034 1035 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the deque. 1036 //! 1037 //! <b>Throws</b>: Nothing. 1038 //! 1039 //! <b>Complexity</b>: Constant. cbegin() const1040 BOOST_CONTAINER_FORCEINLINE const_iterator cbegin() const BOOST_NOEXCEPT_OR_NOTHROW 1041 { return this->members_.m_start; } 1042 1043 //! <b>Effects</b>: Returns a const_iterator to the end of the deque. 1044 //! 1045 //! <b>Throws</b>: Nothing. 1046 //! 1047 //! <b>Complexity</b>: Constant. cend() const1048 BOOST_CONTAINER_FORCEINLINE const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW 1049 { return this->members_.m_finish; } 1050 1051 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning 1052 //! of the reversed deque. 1053 //! 1054 //! <b>Throws</b>: Nothing. 1055 //! 1056 //! <b>Complexity</b>: Constant. crbegin() const1057 BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW 1058 { return const_reverse_iterator(this->members_.m_finish); } 1059 1060 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end 1061 //! of the reversed deque. 1062 //! 1063 //! <b>Throws</b>: Nothing. 1064 //! 1065 //! <b>Complexity</b>: Constant. crend() const1066 BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW 1067 { return const_reverse_iterator(this->members_.m_start); } 1068 1069 ////////////////////////////////////////////// 1070 // 1071 // capacity 1072 // 1073 ////////////////////////////////////////////// 1074 1075 //! <b>Effects</b>: Returns true if the deque contains no elements. 1076 //! 1077 //! <b>Throws</b>: Nothing. 1078 //! 1079 //! <b>Complexity</b>: Constant. empty() const1080 BOOST_CONTAINER_FORCEINLINE bool empty() const BOOST_NOEXCEPT_OR_NOTHROW 1081 { return this->members_.m_finish == this->members_.m_start; } 1082 1083 //! <b>Effects</b>: Returns the number of the elements contained in the deque. 1084 //! 1085 //! <b>Throws</b>: Nothing. 1086 //! 1087 //! <b>Complexity</b>: Constant. size() const1088 BOOST_CONTAINER_FORCEINLINE size_type size() const BOOST_NOEXCEPT_OR_NOTHROW 1089 { return this->members_.m_finish - this->members_.m_start; } 1090 1091 //! <b>Effects</b>: Returns the largest possible size of the deque. 1092 //! 1093 //! <b>Throws</b>: Nothing. 1094 //! 1095 //! <b>Complexity</b>: Constant. max_size() const1096 BOOST_CONTAINER_FORCEINLINE size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW 1097 { return allocator_traits_type::max_size(this->alloc()); } 1098 1099 //! <b>Effects</b>: Inserts or erases elements at the end such that 1100 //! the size becomes n. New elements are value initialized. 1101 //! 1102 //! <b>Throws</b>: If memory allocation throws, or T's constructor throws. 1103 //! 1104 //! <b>Complexity</b>: Linear to the difference between size() and new_size. resize(size_type new_size)1105 void resize(size_type new_size) 1106 { 1107 const size_type len = size(); 1108 if (new_size < len) 1109 this->priv_erase_last_n(len - new_size); 1110 else{ 1111 const size_type n = new_size - this->size(); 1112 dtl::insert_value_initialized_n_proxy<ValAllocator, iterator> proxy; 1113 priv_insert_back_aux_impl(n, proxy); 1114 } 1115 } 1116 1117 //! <b>Effects</b>: Inserts or erases elements at the end such that 1118 //! the size becomes n. New elements are default initialized. 1119 //! 1120 //! <b>Throws</b>: If memory allocation throws, or T's constructor throws. 1121 //! 1122 //! <b>Complexity</b>: Linear to the difference between size() and new_size. 1123 //! 1124 //! <b>Note</b>: Non-standard extension resize(size_type new_size,default_init_t)1125 void resize(size_type new_size, default_init_t) 1126 { 1127 const size_type len = size(); 1128 if (new_size < len) 1129 this->priv_erase_last_n(len - new_size); 1130 else{ 1131 const size_type n = new_size - this->size(); 1132 dtl::insert_default_initialized_n_proxy<ValAllocator, iterator> proxy; 1133 priv_insert_back_aux_impl(n, proxy); 1134 } 1135 } 1136 1137 //! <b>Effects</b>: Inserts or erases elements at the end such that 1138 //! the size becomes n. New elements are copy constructed from x. 1139 //! 1140 //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws. 1141 //! 1142 //! <b>Complexity</b>: Linear to the difference between size() and new_size. resize(size_type new_size,const value_type & x)1143 void resize(size_type new_size, const value_type& x) 1144 { 1145 const size_type len = size(); 1146 if (new_size < len) 1147 this->erase(this->members_.m_start + new_size, this->members_.m_finish); 1148 else 1149 this->insert(this->members_.m_finish, new_size - len, x); 1150 } 1151 1152 //! <b>Effects</b>: Tries to deallocate the excess of memory created 1153 //! with previous allocations. The size of the deque is unchanged 1154 //! 1155 //! <b>Throws</b>: If memory allocation throws. 1156 //! 1157 //! <b>Complexity</b>: Constant. shrink_to_fit()1158 void shrink_to_fit() 1159 { 1160 //This deque implementation already 1161 //deallocates excess nodes when erasing 1162 //so there is nothing to do except for 1163 //empty deque 1164 if(this->empty()){ 1165 this->priv_clear_map(); 1166 } 1167 } 1168 1169 ////////////////////////////////////////////// 1170 // 1171 // element access 1172 // 1173 ////////////////////////////////////////////// 1174 1175 //! <b>Requires</b>: !empty() 1176 //! 1177 //! <b>Effects</b>: Returns a reference to the first 1178 //! element of the container. 1179 //! 1180 //! <b>Throws</b>: Nothing. 1181 //! 1182 //! <b>Complexity</b>: Constant. front()1183 BOOST_CONTAINER_FORCEINLINE reference front() BOOST_NOEXCEPT_OR_NOTHROW 1184 { 1185 BOOST_ASSERT(!this->empty()); 1186 return *this->members_.m_start; 1187 } 1188 1189 //! <b>Requires</b>: !empty() 1190 //! 1191 //! <b>Effects</b>: Returns a const reference to the first element 1192 //! from the beginning of the container. 1193 //! 1194 //! <b>Throws</b>: Nothing. 1195 //! 1196 //! <b>Complexity</b>: Constant. front() const1197 BOOST_CONTAINER_FORCEINLINE const_reference front() const BOOST_NOEXCEPT_OR_NOTHROW 1198 { 1199 BOOST_ASSERT(!this->empty()); 1200 return *this->members_.m_start; 1201 } 1202 1203 //! <b>Requires</b>: !empty() 1204 //! 1205 //! <b>Effects</b>: Returns a reference to the last 1206 //! element of the container. 1207 //! 1208 //! <b>Throws</b>: Nothing. 1209 //! 1210 //! <b>Complexity</b>: Constant. back()1211 BOOST_CONTAINER_FORCEINLINE reference back() BOOST_NOEXCEPT_OR_NOTHROW 1212 { 1213 BOOST_ASSERT(!this->empty()); 1214 return *(end()-1); 1215 } 1216 1217 //! <b>Requires</b>: !empty() 1218 //! 1219 //! <b>Effects</b>: Returns a const reference to the last 1220 //! element of the container. 1221 //! 1222 //! <b>Throws</b>: Nothing. 1223 //! 1224 //! <b>Complexity</b>: Constant. back() const1225 BOOST_CONTAINER_FORCEINLINE const_reference back() const BOOST_NOEXCEPT_OR_NOTHROW 1226 { 1227 BOOST_ASSERT(!this->empty()); 1228 return *(cend()-1); 1229 } 1230 1231 //! <b>Requires</b>: size() > n. 1232 //! 1233 //! <b>Effects</b>: Returns a reference to the nth element 1234 //! from the beginning of the container. 1235 //! 1236 //! <b>Throws</b>: Nothing. 1237 //! 1238 //! <b>Complexity</b>: Constant. operator [](size_type n)1239 BOOST_CONTAINER_FORCEINLINE reference operator[](size_type n) BOOST_NOEXCEPT_OR_NOTHROW 1240 { 1241 BOOST_ASSERT(this->size() > n); 1242 return this->members_.m_start[difference_type(n)]; 1243 } 1244 1245 //! <b>Requires</b>: size() > n. 1246 //! 1247 //! <b>Effects</b>: Returns a const reference to the nth element 1248 //! from the beginning of the container. 1249 //! 1250 //! <b>Throws</b>: Nothing. 1251 //! 1252 //! <b>Complexity</b>: Constant. operator [](size_type n) const1253 BOOST_CONTAINER_FORCEINLINE const_reference operator[](size_type n) const BOOST_NOEXCEPT_OR_NOTHROW 1254 { 1255 BOOST_ASSERT(this->size() > n); 1256 return this->members_.m_start[difference_type(n)]; 1257 } 1258 1259 //! <b>Requires</b>: size() >= n. 1260 //! 1261 //! <b>Effects</b>: Returns an iterator to the nth element 1262 //! from the beginning of the container. Returns end() 1263 //! if n == size(). 1264 //! 1265 //! <b>Throws</b>: Nothing. 1266 //! 1267 //! <b>Complexity</b>: Constant. 1268 //! 1269 //! <b>Note</b>: Non-standard extension nth(size_type n)1270 BOOST_CONTAINER_FORCEINLINE iterator nth(size_type n) BOOST_NOEXCEPT_OR_NOTHROW 1271 { 1272 BOOST_ASSERT(this->size() >= n); 1273 return iterator(this->begin()+n); 1274 } 1275 1276 //! <b>Requires</b>: size() >= n. 1277 //! 1278 //! <b>Effects</b>: Returns a const_iterator to the nth element 1279 //! from the beginning of the container. Returns end() 1280 //! if n == size(). 1281 //! 1282 //! <b>Throws</b>: Nothing. 1283 //! 1284 //! <b>Complexity</b>: Constant. 1285 //! 1286 //! <b>Note</b>: Non-standard extension nth(size_type n) const1287 BOOST_CONTAINER_FORCEINLINE const_iterator nth(size_type n) const BOOST_NOEXCEPT_OR_NOTHROW 1288 { 1289 BOOST_ASSERT(this->size() >= n); 1290 return const_iterator(this->cbegin()+n); 1291 } 1292 1293 //! <b>Requires</b>: begin() <= p <= end(). 1294 //! 1295 //! <b>Effects</b>: Returns the index of the element pointed by p 1296 //! and size() if p == end(). 1297 //! 1298 //! <b>Throws</b>: Nothing. 1299 //! 1300 //! <b>Complexity</b>: Constant. 1301 //! 1302 //! <b>Note</b>: Non-standard extension index_of(iterator p)1303 BOOST_CONTAINER_FORCEINLINE size_type index_of(iterator p) BOOST_NOEXCEPT_OR_NOTHROW 1304 { 1305 //Range checked priv_index_of 1306 return this->priv_index_of(p); 1307 } 1308 1309 //! <b>Requires</b>: begin() <= p <= end(). 1310 //! 1311 //! <b>Effects</b>: Returns the index of the element pointed by p 1312 //! and size() if p == end(). 1313 //! 1314 //! <b>Throws</b>: Nothing. 1315 //! 1316 //! <b>Complexity</b>: Constant. 1317 //! 1318 //! <b>Note</b>: Non-standard extension index_of(const_iterator p) const1319 BOOST_CONTAINER_FORCEINLINE size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW 1320 { 1321 //Range checked priv_index_of 1322 return this->priv_index_of(p); 1323 } 1324 1325 //! <b>Requires</b>: size() > n. 1326 //! 1327 //! <b>Effects</b>: Returns a reference to the nth element 1328 //! from the beginning of the container. 1329 //! 1330 //! <b>Throws</b>: std::range_error if n >= size() 1331 //! 1332 //! <b>Complexity</b>: Constant. at(size_type n)1333 BOOST_CONTAINER_FORCEINLINE reference at(size_type n) 1334 { 1335 this->priv_throw_if_out_of_range(n); 1336 return (*this)[n]; 1337 } 1338 1339 //! <b>Requires</b>: size() > n. 1340 //! 1341 //! <b>Effects</b>: Returns a const reference to the nth element 1342 //! from the beginning of the container. 1343 //! 1344 //! <b>Throws</b>: std::range_error if n >= size() 1345 //! 1346 //! <b>Complexity</b>: Constant. at(size_type n) const1347 BOOST_CONTAINER_FORCEINLINE const_reference at(size_type n) const 1348 { 1349 this->priv_throw_if_out_of_range(n); 1350 return (*this)[n]; 1351 } 1352 1353 ////////////////////////////////////////////// 1354 // 1355 // modifiers 1356 // 1357 ////////////////////////////////////////////// 1358 1359 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1360 1361 //! <b>Effects</b>: Inserts an object of type T constructed with 1362 //! std::forward<Args>(args)... in the beginning of the deque. 1363 //! 1364 //! <b>Returns</b>: A reference to the created object. 1365 //! 1366 //! <b>Throws</b>: If memory allocation throws or the in-place constructor throws. 1367 //! 1368 //! <b>Complexity</b>: Amortized constant time 1369 template <class... Args> emplace_front(BOOST_FWD_REF (Args)...args)1370 reference emplace_front(BOOST_FWD_REF(Args)... args) 1371 { 1372 if(this->priv_push_front_simple_available()){ 1373 reference r = *this->priv_push_front_simple_pos(); 1374 allocator_traits_type::construct 1375 ( this->alloc() 1376 , this->priv_push_front_simple_pos() 1377 , boost::forward<Args>(args)...); 1378 this->priv_push_front_simple_commit(); 1379 return r; 1380 } 1381 else{ 1382 typedef dtl::insert_nonmovable_emplace_proxy<ValAllocator, iterator, Args...> type; 1383 return *this->priv_insert_front_aux_impl(1, type(boost::forward<Args>(args)...)); 1384 } 1385 } 1386 1387 //! <b>Effects</b>: Inserts an object of type T constructed with 1388 //! std::forward<Args>(args)... in the end of the deque. 1389 //! 1390 //! <b>Returns</b>: A reference to the created object. 1391 //! 1392 //! <b>Throws</b>: If memory allocation throws or the in-place constructor throws. 1393 //! 1394 //! <b>Complexity</b>: Amortized constant time 1395 template <class... Args> emplace_back(BOOST_FWD_REF (Args)...args)1396 reference emplace_back(BOOST_FWD_REF(Args)... args) 1397 { 1398 if(this->priv_push_back_simple_available()){ 1399 reference r = *this->priv_push_back_simple_pos(); 1400 allocator_traits_type::construct 1401 ( this->alloc() 1402 , this->priv_push_back_simple_pos() 1403 , boost::forward<Args>(args)...); 1404 this->priv_push_back_simple_commit(); 1405 return r; 1406 } 1407 else{ 1408 typedef dtl::insert_nonmovable_emplace_proxy<ValAllocator, iterator, Args...> type; 1409 return *this->priv_insert_back_aux_impl(1, type(boost::forward<Args>(args)...)); 1410 } 1411 } 1412 1413 //! <b>Requires</b>: p must be a valid iterator of *this. 1414 //! 1415 //! <b>Effects</b>: Inserts an object of type T constructed with 1416 //! std::forward<Args>(args)... before p 1417 //! 1418 //! <b>Throws</b>: If memory allocation throws or the in-place constructor throws. 1419 //! 1420 //! <b>Complexity</b>: If p is end(), amortized constant time 1421 //! Linear time otherwise. 1422 template <class... Args> emplace(const_iterator p,BOOST_FWD_REF (Args)...args)1423 iterator emplace(const_iterator p, BOOST_FWD_REF(Args)... args) 1424 { 1425 BOOST_ASSERT(this->priv_in_range_or_end(p)); 1426 if(p == this->cbegin()){ 1427 this->emplace_front(boost::forward<Args>(args)...); 1428 return this->begin(); 1429 } 1430 else if(p == this->cend()){ 1431 this->emplace_back(boost::forward<Args>(args)...); 1432 return (this->end()-1); 1433 } 1434 else{ 1435 typedef dtl::insert_emplace_proxy<ValAllocator, iterator, Args...> type; 1436 return this->priv_insert_aux_impl(p, 1, type(boost::forward<Args>(args)...)); 1437 } 1438 } 1439 1440 #else //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 1441 1442 #define BOOST_CONTAINER_DEQUE_EMPLACE_CODE(N) \ 1443 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N\ 1444 reference emplace_front(BOOST_MOVE_UREF##N)\ 1445 {\ 1446 if(priv_push_front_simple_available()){\ 1447 reference r = *this->priv_push_front_simple_pos();\ 1448 allocator_traits_type::construct\ 1449 ( this->alloc(), this->priv_push_front_simple_pos() BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ 1450 priv_push_front_simple_commit();\ 1451 return r;\ 1452 }\ 1453 else{\ 1454 typedef dtl::insert_nonmovable_emplace_proxy##N\ 1455 <ValAllocator, iterator BOOST_MOVE_I##N BOOST_MOVE_TARG##N> type;\ 1456 return *priv_insert_front_aux_impl(1, type(BOOST_MOVE_FWD##N));\ 1457 }\ 1458 }\ 1459 \ 1460 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N\ 1461 reference emplace_back(BOOST_MOVE_UREF##N)\ 1462 {\ 1463 if(priv_push_back_simple_available()){\ 1464 reference r = *this->priv_push_back_simple_pos();\ 1465 allocator_traits_type::construct\ 1466 ( this->alloc(), this->priv_push_back_simple_pos() BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ 1467 priv_push_back_simple_commit();\ 1468 return r;\ 1469 }\ 1470 else{\ 1471 typedef dtl::insert_nonmovable_emplace_proxy##N\ 1472 <ValAllocator, iterator BOOST_MOVE_I##N BOOST_MOVE_TARG##N> type;\ 1473 return *priv_insert_back_aux_impl(1, type(BOOST_MOVE_FWD##N));\ 1474 }\ 1475 }\ 1476 \ 1477 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N\ 1478 iterator emplace(const_iterator p BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ 1479 {\ 1480 BOOST_ASSERT(this->priv_in_range_or_end(p));\ 1481 if(p == this->cbegin()){\ 1482 this->emplace_front(BOOST_MOVE_FWD##N);\ 1483 return this->begin();\ 1484 }\ 1485 else if(p == cend()){\ 1486 this->emplace_back(BOOST_MOVE_FWD##N);\ 1487 return (--this->end());\ 1488 }\ 1489 else{\ 1490 typedef dtl::insert_emplace_proxy_arg##N\ 1491 <ValAllocator, iterator BOOST_MOVE_I##N BOOST_MOVE_TARG##N> type;\ 1492 return this->priv_insert_aux_impl(p, 1, type(BOOST_MOVE_FWD##N));\ 1493 }\ 1494 } 1495 // 1496 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_DEQUE_EMPLACE_CODE) 1497 #undef BOOST_CONTAINER_DEQUE_EMPLACE_CODE 1498 1499 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 1500 1501 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1502 //! <b>Effects</b>: Inserts a copy of x at the front of the deque. 1503 //! 1504 //! <b>Throws</b>: If memory allocation throws or 1505 //! T's copy constructor throws. 1506 //! 1507 //! <b>Complexity</b>: Amortized constant time. 1508 void push_front(const T &x); 1509 1510 //! <b>Effects</b>: Constructs a new element in the front of the deque 1511 //! and moves the resources of x to this new element. 1512 //! 1513 //! <b>Throws</b>: If memory allocation throws. 1514 //! 1515 //! <b>Complexity</b>: Amortized constant time. 1516 void push_front(T &&x); 1517 #else 1518 BOOST_MOVE_CONVERSION_AWARE_CATCH(push_front, T, void, priv_push_front) 1519 #endif 1520 1521 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1522 //! <b>Effects</b>: Inserts a copy of x at the end of the deque. 1523 //! 1524 //! <b>Throws</b>: If memory allocation throws or 1525 //! T's copy constructor throws. 1526 //! 1527 //! <b>Complexity</b>: Amortized constant time. 1528 void push_back(const T &x); 1529 1530 //! <b>Effects</b>: Constructs a new element in the end of the deque 1531 //! and moves the resources of x to this new element. 1532 //! 1533 //! <b>Throws</b>: If memory allocation throws. 1534 //! 1535 //! <b>Complexity</b>: Amortized constant time. 1536 void push_back(T &&x); 1537 #else 1538 BOOST_MOVE_CONVERSION_AWARE_CATCH(push_back, T, void, priv_push_back) 1539 #endif 1540 1541 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1542 1543 //! <b>Requires</b>: p must be a valid iterator of *this. 1544 //! 1545 //! <b>Effects</b>: Insert a copy of x before p. 1546 //! 1547 //! <b>Returns</b>: an iterator to the inserted element. 1548 //! 1549 //! <b>Throws</b>: If memory allocation throws or x's copy constructor throws. 1550 //! 1551 //! <b>Complexity</b>: If p is end(), amortized constant time 1552 //! Linear time otherwise. 1553 iterator insert(const_iterator p, const T &x); 1554 1555 //! <b>Requires</b>: p must be a valid iterator of *this. 1556 //! 1557 //! <b>Effects</b>: Insert a new element before p with x's resources. 1558 //! 1559 //! <b>Returns</b>: an iterator to the inserted element. 1560 //! 1561 //! <b>Throws</b>: If memory allocation throws. 1562 //! 1563 //! <b>Complexity</b>: If p is end(), amortized constant time 1564 //! Linear time otherwise. 1565 iterator insert(const_iterator p, T &&x); 1566 #else 1567 BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, T, iterator, priv_insert, const_iterator, const_iterator) 1568 #endif 1569 1570 //! <b>Requires</b>: pos must be a valid iterator of *this. 1571 //! 1572 //! <b>Effects</b>: Insert n copies of x before pos. 1573 //! 1574 //! <b>Returns</b>: an iterator to the first inserted element or pos if n is 0. 1575 //! 1576 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws. 1577 //! 1578 //! <b>Complexity</b>: Linear to n. insert(const_iterator pos,size_type n,const value_type & x)1579 BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator pos, size_type n, const value_type& x) 1580 { 1581 //Range check of p is done by insert() 1582 typedef constant_iterator<value_type, difference_type> c_it; 1583 return this->insert(pos, c_it(x, n), c_it()); 1584 } 1585 1586 //! <b>Requires</b>: pos must be a valid iterator of *this. 1587 //! 1588 //! <b>Effects</b>: Insert a copy of the [first, last) range before pos. 1589 //! 1590 //! <b>Returns</b>: an iterator to the first inserted element or pos if first == last. 1591 //! 1592 //! <b>Throws</b>: If memory allocation throws, T's constructor from a 1593 //! dereferenced InIt throws or T's copy constructor throws. 1594 //! 1595 //! <b>Complexity</b>: Linear to distance [first, last). 1596 template <class InIt> insert(const_iterator pos,InIt first,InIt last,typename dtl::disable_if_or<void,dtl::is_convertible<InIt,size_type>,dtl::is_not_input_iterator<InIt>>::type * =0)1597 iterator insert(const_iterator pos, InIt first, InIt last 1598 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1599 , typename dtl::disable_if_or 1600 < void 1601 , dtl::is_convertible<InIt, size_type> 1602 , dtl::is_not_input_iterator<InIt> 1603 >::type * = 0 1604 #endif 1605 ) 1606 { 1607 BOOST_ASSERT(this->priv_in_range_or_end(pos)); 1608 size_type n = 0; 1609 iterator it(pos.unconst()); 1610 for(;first != last; ++first, ++n){ 1611 it = this->emplace(it, *first); 1612 ++it; 1613 } 1614 it -= n; 1615 return it; 1616 } 1617 1618 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 1619 //! <b>Requires</b>: pos must be a valid iterator of *this. 1620 //! 1621 //! <b>Effects</b>: Insert a copy of the [il.begin(), il.end()) range before pos. 1622 //! 1623 //! <b>Returns</b>: an iterator to the first inserted element or pos if il.begin() == il.end(). 1624 //! 1625 //! <b>Throws</b>: If memory allocation throws, T's constructor from a 1626 //! dereferenced std::initializer_list throws or T's copy constructor throws. 1627 //! 1628 //! <b>Complexity</b>: Linear to distance [il.begin(), il.end()). insert(const_iterator pos,std::initializer_list<value_type> il)1629 BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator pos, std::initializer_list<value_type> il) 1630 { 1631 //Range check os pos is done in insert() 1632 return insert(pos, il.begin(), il.end()); 1633 } 1634 #endif 1635 1636 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1637 template <class FwdIt> insert(const_iterator p,FwdIt first,FwdIt last,typename dtl::disable_if_or<void,dtl::is_convertible<FwdIt,size_type>,dtl::is_input_iterator<FwdIt>>::type * =0)1638 BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, FwdIt first, FwdIt last 1639 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1640 , typename dtl::disable_if_or 1641 < void 1642 , dtl::is_convertible<FwdIt, size_type> 1643 , dtl::is_input_iterator<FwdIt> 1644 >::type * = 0 1645 #endif 1646 ) 1647 { 1648 BOOST_ASSERT(this->priv_in_range_or_end(p)); 1649 dtl::insert_range_proxy<ValAllocator, FwdIt, iterator> proxy(first); 1650 return priv_insert_aux_impl(p, boost::container::iterator_distance(first, last), proxy); 1651 } 1652 #endif 1653 1654 //! <b>Effects</b>: Removes the first element from the deque. 1655 //! 1656 //! <b>Throws</b>: Nothing. 1657 //! 1658 //! <b>Complexity</b>: Constant time. pop_front()1659 void pop_front() BOOST_NOEXCEPT_OR_NOTHROW 1660 { 1661 BOOST_ASSERT(!this->empty()); 1662 if (this->members_.m_start.m_cur != this->members_.m_start.m_last - 1) { 1663 allocator_traits_type::destroy 1664 ( this->alloc() 1665 , boost::movelib::to_raw_pointer(this->members_.m_start.m_cur) 1666 ); 1667 ++this->members_.m_start.m_cur; 1668 } 1669 else 1670 this->priv_pop_front_aux(); 1671 } 1672 1673 //! <b>Effects</b>: Removes the last element from the deque. 1674 //! 1675 //! <b>Throws</b>: Nothing. 1676 //! 1677 //! <b>Complexity</b>: Constant time. pop_back()1678 void pop_back() BOOST_NOEXCEPT_OR_NOTHROW 1679 { 1680 BOOST_ASSERT(!this->empty()); 1681 if (this->members_.m_finish.m_cur != this->members_.m_finish.m_first) { 1682 --this->members_.m_finish.m_cur; 1683 allocator_traits_type::destroy 1684 ( this->alloc() 1685 , boost::movelib::to_raw_pointer(this->members_.m_finish.m_cur) 1686 ); 1687 } 1688 else 1689 this->priv_pop_back_aux(); 1690 } 1691 1692 //! <b>Effects</b>: Erases the element at p. 1693 //! 1694 //! <b>Throws</b>: Nothing. 1695 //! 1696 //! <b>Complexity</b>: Linear to the elements between pos and the 1697 //! last element (if pos is near the end) or the first element 1698 //! if(pos is near the beginning). 1699 //! Constant if pos is the first or the last element. erase(const_iterator pos)1700 iterator erase(const_iterator pos) BOOST_NOEXCEPT_OR_NOTHROW 1701 { 1702 BOOST_ASSERT(this->priv_in_range(pos)); 1703 iterator next = pos.unconst(); 1704 ++next; 1705 size_type index = pos - this->members_.m_start; 1706 if (index < (this->size()/2)) { 1707 boost::container::move_backward(this->begin(), pos.unconst(), next); 1708 pop_front(); 1709 } 1710 else { 1711 boost::container::move(next, this->end(), pos.unconst()); 1712 pop_back(); 1713 } 1714 return this->members_.m_start + index; 1715 } 1716 1717 //! <b>Effects</b>: Erases the elements pointed by [first, last). 1718 //! 1719 //! <b>Throws</b>: Nothing. 1720 //! 1721 //! <b>Complexity</b>: Linear to the distance between first and 1722 //! last plus the elements between pos and the 1723 //! last element (if pos is near the end) or the first element 1724 //! if(pos is near the beginning). erase(const_iterator first,const_iterator last)1725 iterator erase(const_iterator first, const_iterator last) BOOST_NOEXCEPT_OR_NOTHROW 1726 { 1727 BOOST_ASSERT(first == last || 1728 (first < last && this->priv_in_range(first) && this->priv_in_range_or_end(last))); 1729 if (first == this->members_.m_start && last == this->members_.m_finish) { 1730 this->clear(); 1731 return this->members_.m_finish; 1732 } 1733 else { 1734 const size_type n = static_cast<size_type>(last - first); 1735 const size_type elems_before = static_cast<size_type>(first - this->members_.m_start); 1736 if (elems_before < (this->size() - n) - elems_before) { 1737 boost::container::move_backward(begin(), first.unconst(), last.unconst()); 1738 iterator new_start = this->members_.m_start + n; 1739 this->priv_destroy_range(this->members_.m_start, new_start); 1740 this->priv_destroy_nodes(this->members_.m_start.m_node, new_start.m_node); 1741 this->members_.m_start = new_start; 1742 } 1743 else { 1744 boost::container::move(last.unconst(), end(), first.unconst()); 1745 iterator new_finish = this->members_.m_finish - n; 1746 this->priv_destroy_range(new_finish, this->members_.m_finish); 1747 this->priv_destroy_nodes(new_finish.m_node + 1, this->members_.m_finish.m_node + 1); 1748 this->members_.m_finish = new_finish; 1749 } 1750 return this->members_.m_start + elems_before; 1751 } 1752 } 1753 1754 //! <b>Effects</b>: Swaps the contents of *this and x. 1755 //! 1756 //! <b>Throws</b>: Nothing. 1757 //! 1758 //! <b>Complexity</b>: Constant. swap(deque & x)1759 BOOST_CONTAINER_FORCEINLINE void swap(deque &x) 1760 BOOST_NOEXCEPT_IF(allocator_traits_type::propagate_on_container_swap::value 1761 || allocator_traits_type::is_always_equal::value) 1762 { 1763 this->swap_members(x); 1764 dtl::bool_<allocator_traits_type::propagate_on_container_swap::value> flag; 1765 dtl::swap_alloc(this->alloc(), x.alloc(), flag); 1766 dtl::swap_alloc(this->ptr_alloc(), x.ptr_alloc(), flag); 1767 } 1768 1769 //! <b>Effects</b>: Erases all the elements of the deque. 1770 //! 1771 //! <b>Throws</b>: Nothing. 1772 //! 1773 //! <b>Complexity</b>: Linear to the number of elements in the deque. clear()1774 void clear() BOOST_NOEXCEPT_OR_NOTHROW 1775 { 1776 for (index_pointer node = this->members_.m_start.m_node + 1; 1777 node < this->members_.m_finish.m_node; 1778 ++node) { 1779 this->priv_destroy_range(*node, *node + this->s_buffer_size()); 1780 this->priv_deallocate_node(*node); 1781 } 1782 1783 if (this->members_.m_start.m_node != this->members_.m_finish.m_node) { 1784 this->priv_destroy_range(this->members_.m_start.m_cur, this->members_.m_start.m_last); 1785 this->priv_destroy_range(this->members_.m_finish.m_first, this->members_.m_finish.m_cur); 1786 this->priv_deallocate_node(this->members_.m_finish.m_first); 1787 } 1788 else 1789 this->priv_destroy_range(this->members_.m_start.m_cur, this->members_.m_finish.m_cur); 1790 1791 this->members_.m_finish = this->members_.m_start; 1792 } 1793 1794 //! <b>Effects</b>: Returns true if x and y are equal 1795 //! 1796 //! <b>Complexity</b>: Linear to the number of elements in the container. operator ==(const deque & x,const deque & y)1797 BOOST_CONTAINER_FORCEINLINE friend bool operator==(const deque& x, const deque& y) 1798 { return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin()); } 1799 1800 //! <b>Effects</b>: Returns true if x and y are unequal 1801 //! 1802 //! <b>Complexity</b>: Linear to the number of elements in the container. operator !=(const deque & x,const deque & y)1803 BOOST_CONTAINER_FORCEINLINE friend bool operator!=(const deque& x, const deque& y) 1804 { return !(x == y); } 1805 1806 //! <b>Effects</b>: Returns true if x is less than y 1807 //! 1808 //! <b>Complexity</b>: Linear to the number of elements in the container. operator <(const deque & x,const deque & y)1809 BOOST_CONTAINER_FORCEINLINE friend bool operator<(const deque& x, const deque& y) 1810 { return ::boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); } 1811 1812 //! <b>Effects</b>: Returns true if x is greater than y 1813 //! 1814 //! <b>Complexity</b>: Linear to the number of elements in the container. operator >(const deque & x,const deque & y)1815 BOOST_CONTAINER_FORCEINLINE friend bool operator>(const deque& x, const deque& y) 1816 { return y < x; } 1817 1818 //! <b>Effects</b>: Returns true if x is equal or less than y 1819 //! 1820 //! <b>Complexity</b>: Linear to the number of elements in the container. operator <=(const deque & x,const deque & y)1821 BOOST_CONTAINER_FORCEINLINE friend bool operator<=(const deque& x, const deque& y) 1822 { return !(y < x); } 1823 1824 //! <b>Effects</b>: Returns true if x is equal or greater than y 1825 //! 1826 //! <b>Complexity</b>: Linear to the number of elements in the container. operator >=(const deque & x,const deque & y)1827 BOOST_CONTAINER_FORCEINLINE friend bool operator>=(const deque& x, const deque& y) 1828 { return !(x < y); } 1829 1830 //! <b>Effects</b>: x.swap(y) 1831 //! 1832 //! <b>Complexity</b>: Constant. swap(deque & x,deque & y)1833 BOOST_CONTAINER_FORCEINLINE friend void swap(deque& x, deque& y) 1834 { x.swap(y); } 1835 1836 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 1837 private: 1838 priv_index_of(const_iterator p) const1839 BOOST_CONTAINER_FORCEINLINE size_type priv_index_of(const_iterator p) const 1840 { 1841 BOOST_ASSERT(this->cbegin() <= p); 1842 BOOST_ASSERT(p <= this->cend()); 1843 return static_cast<size_type>(p - this->cbegin()); 1844 } 1845 priv_erase_last_n(size_type n)1846 void priv_erase_last_n(size_type n) 1847 { 1848 if(n == this->size()) { 1849 this->clear(); 1850 } 1851 else { 1852 iterator new_finish = this->members_.m_finish - n; 1853 this->priv_destroy_range(new_finish, this->members_.m_finish); 1854 this->priv_destroy_nodes(new_finish.m_node + 1, this->members_.m_finish.m_node + 1); 1855 this->members_.m_finish = new_finish; 1856 } 1857 } 1858 priv_throw_if_out_of_range(size_type n) const1859 void priv_throw_if_out_of_range(size_type n) const 1860 { 1861 if (n >= this->size()) 1862 throw_out_of_range("deque::at out of range"); 1863 } 1864 priv_in_range(const_iterator pos) const1865 BOOST_CONTAINER_FORCEINLINE bool priv_in_range(const_iterator pos) const 1866 { 1867 return (this->begin() <= pos) && (pos < this->end()); 1868 } 1869 priv_in_range_or_end(const_iterator pos) const1870 BOOST_CONTAINER_FORCEINLINE bool priv_in_range_or_end(const_iterator pos) const 1871 { 1872 return (this->begin() <= pos) && (pos <= this->end()); 1873 } 1874 1875 template <class U> priv_insert(const_iterator p,BOOST_FWD_REF (U)x)1876 iterator priv_insert(const_iterator p, BOOST_FWD_REF(U) x) 1877 { 1878 BOOST_ASSERT(this->priv_in_range_or_end(p)); 1879 if (p == cbegin()){ 1880 this->push_front(::boost::forward<U>(x)); 1881 return begin(); 1882 } 1883 else if (p == cend()){ 1884 this->push_back(::boost::forward<U>(x)); 1885 return --end(); 1886 } 1887 else { 1888 return priv_insert_aux_impl 1889 ( p, (size_type)1 1890 , dtl::get_insert_value_proxy<iterator, ValAllocator>(::boost::forward<U>(x))); 1891 } 1892 } 1893 1894 template <class U> priv_push_front(BOOST_FWD_REF (U)x)1895 void priv_push_front(BOOST_FWD_REF(U) x) 1896 { 1897 if(this->priv_push_front_simple_available()){ 1898 allocator_traits_type::construct 1899 ( this->alloc(), this->priv_push_front_simple_pos(), ::boost::forward<U>(x)); 1900 this->priv_push_front_simple_commit(); 1901 } 1902 else{ 1903 priv_insert_aux_impl 1904 ( this->cbegin(), (size_type)1 1905 , dtl::get_insert_value_proxy<iterator, ValAllocator>(::boost::forward<U>(x))); 1906 } 1907 } 1908 1909 template <class U> priv_push_back(BOOST_FWD_REF (U)x)1910 void priv_push_back(BOOST_FWD_REF(U) x) 1911 { 1912 if(this->priv_push_back_simple_available()){ 1913 allocator_traits_type::construct 1914 ( this->alloc(), this->priv_push_back_simple_pos(), ::boost::forward<U>(x)); 1915 this->priv_push_back_simple_commit(); 1916 } 1917 else{ 1918 priv_insert_aux_impl 1919 ( this->cend(), (size_type)1 1920 , dtl::get_insert_value_proxy<iterator, ValAllocator>(::boost::forward<U>(x))); 1921 } 1922 } 1923 priv_push_back_simple_available() const1924 BOOST_CONTAINER_FORCEINLINE bool priv_push_back_simple_available() const 1925 { 1926 return this->members_.m_map && 1927 (this->members_.m_finish.m_cur != (this->members_.m_finish.m_last - 1)); 1928 } 1929 priv_push_back_simple_pos() const1930 BOOST_CONTAINER_FORCEINLINE T *priv_push_back_simple_pos() const 1931 { 1932 return boost::movelib::to_raw_pointer(this->members_.m_finish.m_cur); 1933 } 1934 priv_push_back_simple_commit()1935 BOOST_CONTAINER_FORCEINLINE void priv_push_back_simple_commit() 1936 { 1937 ++this->members_.m_finish.m_cur; 1938 } 1939 priv_push_front_simple_available() const1940 BOOST_CONTAINER_FORCEINLINE bool priv_push_front_simple_available() const 1941 { 1942 return this->members_.m_map && 1943 (this->members_.m_start.m_cur != this->members_.m_start.m_first); 1944 } 1945 priv_push_front_simple_pos() const1946 BOOST_CONTAINER_FORCEINLINE T *priv_push_front_simple_pos() const 1947 { return boost::movelib::to_raw_pointer(this->members_.m_start.m_cur) - 1; } 1948 priv_push_front_simple_commit()1949 BOOST_CONTAINER_FORCEINLINE void priv_push_front_simple_commit() 1950 { --this->members_.m_start.m_cur; } 1951 priv_destroy_range(iterator p,iterator p2)1952 void priv_destroy_range(iterator p, iterator p2) 1953 { 1954 if(!Base::traits_t::trivial_dctr){ 1955 for(;p != p2; ++p){ 1956 allocator_traits_type::destroy(this->alloc(), boost::movelib::iterator_to_raw_pointer(p)); 1957 } 1958 } 1959 } 1960 priv_destroy_range(pointer p,pointer p2)1961 void priv_destroy_range(pointer p, pointer p2) 1962 { 1963 if(!Base::traits_t::trivial_dctr){ 1964 for(;p != p2; ++p){ 1965 allocator_traits_type::destroy(this->alloc(), boost::movelib::iterator_to_raw_pointer(p)); 1966 } 1967 } 1968 } 1969 1970 template<class InsertProxy> priv_insert_aux_impl(const_iterator p,size_type n,InsertProxy proxy)1971 iterator priv_insert_aux_impl(const_iterator p, size_type n, InsertProxy proxy) 1972 { 1973 iterator pos(p.unconst()); 1974 const size_type pos_n = p - this->cbegin(); 1975 if(!this->members_.m_map){ 1976 this->priv_initialize_map(0); 1977 pos = this->begin(); 1978 } 1979 1980 const size_type elemsbefore = static_cast<size_type>(pos - this->members_.m_start); 1981 const size_type length = this->size(); 1982 if (elemsbefore < length / 2) { 1983 const iterator new_start = this->priv_reserve_elements_at_front(n); 1984 const iterator old_start = this->members_.m_start; 1985 if(!elemsbefore){ 1986 proxy.uninitialized_copy_n_and_update(this->alloc(), new_start, n); 1987 this->members_.m_start = new_start; 1988 } 1989 else{ 1990 pos = this->members_.m_start + elemsbefore; 1991 if (elemsbefore >= n) { 1992 const iterator start_n = this->members_.m_start + n; 1993 ::boost::container::uninitialized_move_alloc 1994 (this->alloc(), this->members_.m_start, start_n, new_start); 1995 this->members_.m_start = new_start; 1996 boost::container::move(start_n, pos, old_start); 1997 proxy.copy_n_and_update(this->alloc(), pos - n, n); 1998 } 1999 else { 2000 const size_type mid_count = n - elemsbefore; 2001 const iterator mid_start = old_start - mid_count; 2002 proxy.uninitialized_copy_n_and_update(this->alloc(), mid_start, mid_count); 2003 this->members_.m_start = mid_start; 2004 ::boost::container::uninitialized_move_alloc 2005 (this->alloc(), old_start, pos, new_start); 2006 this->members_.m_start = new_start; 2007 proxy.copy_n_and_update(this->alloc(), old_start, elemsbefore); 2008 } 2009 } 2010 } 2011 else { 2012 const iterator new_finish = this->priv_reserve_elements_at_back(n); 2013 const iterator old_finish = this->members_.m_finish; 2014 const size_type elemsafter = length - elemsbefore; 2015 if(!elemsafter){ 2016 proxy.uninitialized_copy_n_and_update(this->alloc(), old_finish, n); 2017 this->members_.m_finish = new_finish; 2018 } 2019 else{ 2020 pos = old_finish - elemsafter; 2021 if (elemsafter >= n) { 2022 iterator finish_n = old_finish - difference_type(n); 2023 ::boost::container::uninitialized_move_alloc 2024 (this->alloc(), finish_n, old_finish, old_finish); 2025 this->members_.m_finish = new_finish; 2026 boost::container::move_backward(pos, finish_n, old_finish); 2027 proxy.copy_n_and_update(this->alloc(), pos, n); 2028 } 2029 else { 2030 const size_type raw_gap = n - elemsafter; 2031 ::boost::container::uninitialized_move_alloc 2032 (this->alloc(), pos, old_finish, old_finish + raw_gap); 2033 BOOST_TRY{ 2034 proxy.copy_n_and_update(this->alloc(), pos, elemsafter); 2035 proxy.uninitialized_copy_n_and_update(this->alloc(), old_finish, raw_gap); 2036 } 2037 BOOST_CATCH(...){ 2038 this->priv_destroy_range(old_finish, old_finish + elemsafter); 2039 BOOST_RETHROW 2040 } 2041 BOOST_CATCH_END 2042 this->members_.m_finish = new_finish; 2043 } 2044 } 2045 } 2046 return this->begin() + pos_n; 2047 } 2048 2049 template <class InsertProxy> priv_insert_back_aux_impl(size_type n,InsertProxy proxy)2050 iterator priv_insert_back_aux_impl(size_type n, InsertProxy proxy) 2051 { 2052 if(!this->members_.m_map){ 2053 this->priv_initialize_map(0); 2054 } 2055 2056 iterator new_finish = this->priv_reserve_elements_at_back(n); 2057 iterator old_finish = this->members_.m_finish; 2058 proxy.uninitialized_copy_n_and_update(this->alloc(), old_finish, n); 2059 this->members_.m_finish = new_finish; 2060 return iterator(this->members_.m_finish - n); 2061 } 2062 2063 template <class InsertProxy> priv_insert_front_aux_impl(size_type n,InsertProxy proxy)2064 iterator priv_insert_front_aux_impl(size_type n, InsertProxy proxy) 2065 { 2066 if(!this->members_.m_map){ 2067 this->priv_initialize_map(0); 2068 } 2069 2070 iterator new_start = this->priv_reserve_elements_at_front(n); 2071 proxy.uninitialized_copy_n_and_update(this->alloc(), new_start, n); 2072 this->members_.m_start = new_start; 2073 return new_start; 2074 } 2075 priv_fill_insert(const_iterator pos,size_type n,const value_type & x)2076 BOOST_CONTAINER_FORCEINLINE iterator priv_fill_insert(const_iterator pos, size_type n, const value_type& x) 2077 { 2078 typedef constant_iterator<value_type, difference_type> c_it; 2079 return this->insert(pos, c_it(x, n), c_it()); 2080 } 2081 2082 // Precondition: this->members_.m_start and this->members_.m_finish have already been initialized, 2083 // but none of the deque's elements have yet been constructed. priv_fill_initialize(const value_type & value)2084 void priv_fill_initialize(const value_type& value) 2085 { 2086 index_pointer cur = this->members_.m_start.m_node; 2087 BOOST_TRY { 2088 for ( ; cur < this->members_.m_finish.m_node; ++cur){ 2089 boost::container::uninitialized_fill_alloc 2090 (this->alloc(), *cur, *cur + this->s_buffer_size(), value); 2091 } 2092 boost::container::uninitialized_fill_alloc 2093 (this->alloc(), this->members_.m_finish.m_first, this->members_.m_finish.m_cur, value); 2094 } 2095 BOOST_CATCH(...){ 2096 this->priv_destroy_range(this->members_.m_start, iterator(*cur, cur)); 2097 BOOST_RETHROW 2098 } 2099 BOOST_CATCH_END 2100 } 2101 2102 template <class InIt> priv_range_initialize(InIt first,InIt last,typename iterator_enable_if_tag<InIt,std::input_iterator_tag>::type * =0)2103 void priv_range_initialize(InIt first, InIt last, typename iterator_enable_if_tag<InIt, std::input_iterator_tag>::type* =0) 2104 { 2105 this->priv_initialize_map(0); 2106 BOOST_TRY { 2107 for ( ; first != last; ++first) 2108 this->emplace_back(*first); 2109 } 2110 BOOST_CATCH(...){ 2111 this->clear(); 2112 BOOST_RETHROW 2113 } 2114 BOOST_CATCH_END 2115 } 2116 2117 template <class FwdIt> priv_range_initialize(FwdIt first,FwdIt last,typename iterator_disable_if_tag<FwdIt,std::input_iterator_tag>::type * =0)2118 void priv_range_initialize(FwdIt first, FwdIt last, typename iterator_disable_if_tag<FwdIt, std::input_iterator_tag>::type* =0) 2119 { 2120 size_type n = 0; 2121 n = boost::container::iterator_distance(first, last); 2122 this->priv_initialize_map(n); 2123 2124 index_pointer cur_node = this->members_.m_start.m_node; 2125 BOOST_TRY { 2126 for (; cur_node < this->members_.m_finish.m_node; ++cur_node) { 2127 FwdIt mid = first; 2128 boost::container::iterator_advance(mid, this->s_buffer_size()); 2129 ::boost::container::uninitialized_copy_alloc(this->alloc(), first, mid, *cur_node); 2130 first = mid; 2131 } 2132 ::boost::container::uninitialized_copy_alloc(this->alloc(), first, last, this->members_.m_finish.m_first); 2133 } 2134 BOOST_CATCH(...){ 2135 this->priv_destroy_range(this->members_.m_start, iterator(*cur_node, cur_node)); 2136 BOOST_RETHROW 2137 } 2138 BOOST_CATCH_END 2139 } 2140 2141 // Called only if this->members_.m_finish.m_cur == this->members_.m_finish.m_first. priv_pop_back_aux()2142 void priv_pop_back_aux() BOOST_NOEXCEPT_OR_NOTHROW 2143 { 2144 this->priv_deallocate_node(this->members_.m_finish.m_first); 2145 this->members_.m_finish.priv_set_node(this->members_.m_finish.m_node - 1); 2146 this->members_.m_finish.m_cur = this->members_.m_finish.m_last - 1; 2147 allocator_traits_type::destroy 2148 ( this->alloc() 2149 , boost::movelib::to_raw_pointer(this->members_.m_finish.m_cur) 2150 ); 2151 } 2152 2153 // Called only if this->members_.m_start.m_cur == this->members_.m_start.m_last - 1. Note that 2154 // if the deque has at least one element (a precondition for this member 2155 // function), and if this->members_.m_start.m_cur == this->members_.m_start.m_last, then the deque 2156 // must have at least two nodes. priv_pop_front_aux()2157 void priv_pop_front_aux() BOOST_NOEXCEPT_OR_NOTHROW 2158 { 2159 allocator_traits_type::destroy 2160 ( this->alloc() 2161 , boost::movelib::to_raw_pointer(this->members_.m_start.m_cur) 2162 ); 2163 this->priv_deallocate_node(this->members_.m_start.m_first); 2164 this->members_.m_start.priv_set_node(this->members_.m_start.m_node + 1); 2165 this->members_.m_start.m_cur = this->members_.m_start.m_first; 2166 } 2167 priv_reserve_elements_at_front(size_type n)2168 iterator priv_reserve_elements_at_front(size_type n) 2169 { 2170 size_type vacancies = this->members_.m_start.m_cur - this->members_.m_start.m_first; 2171 if (n > vacancies){ 2172 size_type new_elems = n-vacancies; 2173 size_type new_nodes = (new_elems + this->s_buffer_size() - 1) / 2174 this->s_buffer_size(); 2175 size_type s = (size_type)(this->members_.m_start.m_node - this->members_.m_map); 2176 if (new_nodes > s){ 2177 this->priv_reallocate_map(new_nodes, true); 2178 } 2179 size_type i = 1; 2180 BOOST_TRY { 2181 for (; i <= new_nodes; ++i) 2182 *(this->members_.m_start.m_node - i) = this->priv_allocate_node(); 2183 } 2184 BOOST_CATCH(...) { 2185 for (size_type j = 1; j < i; ++j) 2186 this->priv_deallocate_node(*(this->members_.m_start.m_node - j)); 2187 BOOST_RETHROW 2188 } 2189 BOOST_CATCH_END 2190 } 2191 return this->members_.m_start - difference_type(n); 2192 } 2193 priv_reserve_elements_at_back(size_type n)2194 iterator priv_reserve_elements_at_back(size_type n) 2195 { 2196 size_type vacancies = (this->members_.m_finish.m_last - this->members_.m_finish.m_cur) - 1; 2197 if (n > vacancies){ 2198 size_type new_elems = n - vacancies; 2199 size_type new_nodes = (new_elems + this->s_buffer_size() - 1)/s_buffer_size(); 2200 size_type s = (size_type)(this->members_.m_map_size - (this->members_.m_finish.m_node - this->members_.m_map)); 2201 if (new_nodes + 1 > s){ 2202 this->priv_reallocate_map(new_nodes, false); 2203 } 2204 size_type i = 1; 2205 BOOST_TRY { 2206 for (; i <= new_nodes; ++i) 2207 *(this->members_.m_finish.m_node + i) = this->priv_allocate_node(); 2208 } 2209 BOOST_CATCH(...) { 2210 for (size_type j = 1; j < i; ++j) 2211 this->priv_deallocate_node(*(this->members_.m_finish.m_node + j)); 2212 BOOST_RETHROW 2213 } 2214 BOOST_CATCH_END 2215 } 2216 return this->members_.m_finish + difference_type(n); 2217 } 2218 priv_reallocate_map(size_type nodes_to_add,bool add_at_front)2219 void priv_reallocate_map(size_type nodes_to_add, bool add_at_front) 2220 { 2221 size_type old_num_nodes = this->members_.m_finish.m_node - this->members_.m_start.m_node + 1; 2222 size_type new_num_nodes = old_num_nodes + nodes_to_add; 2223 2224 index_pointer new_nstart; 2225 if (this->members_.m_map_size > 2 * new_num_nodes) { 2226 new_nstart = this->members_.m_map + (this->members_.m_map_size - new_num_nodes) / 2 2227 + (add_at_front ? nodes_to_add : 0); 2228 if (new_nstart < this->members_.m_start.m_node) 2229 boost::container::move(this->members_.m_start.m_node, this->members_.m_finish.m_node + 1, new_nstart); 2230 else 2231 boost::container::move_backward 2232 (this->members_.m_start.m_node, this->members_.m_finish.m_node + 1, new_nstart + old_num_nodes); 2233 } 2234 else { 2235 size_type new_map_size = 2236 this->members_.m_map_size + dtl::max_value(this->members_.m_map_size, nodes_to_add) + 2; 2237 2238 index_pointer new_map = this->priv_allocate_map(new_map_size); 2239 new_nstart = new_map + (new_map_size - new_num_nodes) / 2 2240 + (add_at_front ? nodes_to_add : 0); 2241 boost::container::move(this->members_.m_start.m_node, this->members_.m_finish.m_node + 1, new_nstart); 2242 this->priv_deallocate_map(this->members_.m_map, this->members_.m_map_size); 2243 2244 this->members_.m_map = new_map; 2245 this->members_.m_map_size = new_map_size; 2246 } 2247 2248 this->members_.m_start.priv_set_node(new_nstart); 2249 this->members_.m_finish.priv_set_node(new_nstart + old_num_nodes - 1); 2250 } 2251 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 2252 }; 2253 2254 #ifndef BOOST_CONTAINER_NO_CXX17_CTAD 2255 template <typename InputIterator> 2256 deque(InputIterator, InputIterator) -> deque<typename iterator_traits<InputIterator>::value_type>; 2257 template <typename InputIterator, typename Allocator> 2258 deque(InputIterator, InputIterator, Allocator const&) -> deque<typename iterator_traits<InputIterator>::value_type, Allocator>; 2259 #endif 2260 2261 }} 2262 2263 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 2264 2265 namespace boost { 2266 2267 //!has_trivial_destructor_after_move<> == true_type 2268 //!specialization for optimizations 2269 template <class T, class Allocator> 2270 struct has_trivial_destructor_after_move<boost::container::deque<T, Allocator> > 2271 { 2272 typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer; 2273 static const bool value = ::boost::has_trivial_destructor_after_move<Allocator>::value && 2274 ::boost::has_trivial_destructor_after_move<pointer>::value; 2275 }; 2276 2277 } 2278 2279 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 2280 2281 #include <boost/container/detail/config_end.hpp> 2282 2283 #endif // #ifndef BOOST_CONTAINER_DEQUE_HPP 2284