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