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