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_LIST_HPP 11 #define BOOST_CONTAINER_LIST_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 24 // container 25 #include <boost/container/container_fwd.hpp> 26 #include <boost/container/new_allocator.hpp> //new_allocator 27 #include <boost/container/throw_exception.hpp> 28 // container/detail 29 #include <boost/container/detail/algorithm.hpp> 30 #include <boost/container/detail/compare_functors.hpp> 31 #include <boost/container/detail/iterator.hpp> 32 #include <boost/container/detail/iterators.hpp> 33 #include <boost/container/detail/mpl.hpp> 34 #include <boost/container/detail/node_alloc_holder.hpp> 35 #include <boost/container/detail/version_type.hpp> 36 #include <boost/container/detail/value_functors.hpp> 37 // move 38 #include <boost/move/utility_core.hpp> 39 #include <boost/move/iterator.hpp> 40 #include <boost/move/traits.hpp> 41 // move/detail 42 #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 43 # include <boost/move/detail/fwd_macros.hpp> 44 #endif 45 #include <boost/move/detail/move_helpers.hpp> 46 47 // intrusive 48 #include <boost/intrusive/pointer_traits.hpp> 49 #include <boost/intrusive/list.hpp> 50 // other 51 #include <boost/assert.hpp> 52 // std 53 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 54 #include <initializer_list> 55 #endif 56 57 namespace boost { 58 namespace container { 59 60 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 61 namespace dtl { 62 63 template<class VoidPointer> 64 struct list_hook 65 { 66 typedef typename dtl::bi::make_list_base_hook 67 <dtl::bi::void_pointer<VoidPointer>, dtl::bi::link_mode<dtl::bi::normal_link> >::type type; 68 }; 69 70 template <class T, class VoidPointer> 71 struct list_node 72 : public list_hook<VoidPointer>::type 73 { 74 public: 75 typedef T value_type; 76 typedef T internal_type; 77 typedef typename list_hook<VoidPointer>::type hook_type; 78 79 typedef typename dtl::aligned_storage<sizeof(T), dtl::alignment_of<T>::value>::type storage_t; 80 storage_t m_storage; 81 82 #if defined(BOOST_GCC) && (BOOST_GCC >= 40600) && (BOOST_GCC < 80000) 83 #pragma GCC diagnostic push 84 #pragma GCC diagnostic ignored "-Wstrict-aliasing" 85 #define BOOST_CONTAINER_DISABLE_ALIASING_WARNING 86 # endif 87 get_databoost::container::dtl::list_node88 BOOST_CONTAINER_FORCEINLINE T &get_data() 89 { return *reinterpret_cast<T*>(this->m_storage.data); } 90 get_databoost::container::dtl::list_node91 BOOST_CONTAINER_FORCEINLINE const T &get_data() const 92 { return *reinterpret_cast<const T*>(this->m_storage.data); } 93 get_data_ptrboost::container::dtl::list_node94 BOOST_CONTAINER_FORCEINLINE T *get_data_ptr() 95 { return reinterpret_cast<T*>(this->m_storage.data); } 96 get_data_ptrboost::container::dtl::list_node97 BOOST_CONTAINER_FORCEINLINE const T *get_data_ptr() const 98 { return reinterpret_cast<T*>(this->m_storage.data); } 99 get_real_databoost::container::dtl::list_node100 BOOST_CONTAINER_FORCEINLINE internal_type &get_real_data() 101 { return *reinterpret_cast<internal_type*>(this->m_storage.data); } 102 get_real_databoost::container::dtl::list_node103 BOOST_CONTAINER_FORCEINLINE const internal_type &get_real_data() const 104 { return *reinterpret_cast<const internal_type*>(this->m_storage.data); } 105 get_real_data_ptrboost::container::dtl::list_node106 BOOST_CONTAINER_FORCEINLINE internal_type *get_real_data_ptr() 107 { return reinterpret_cast<internal_type*>(this->m_storage.data); } 108 get_real_data_ptrboost::container::dtl::list_node109 BOOST_CONTAINER_FORCEINLINE const internal_type *get_real_data_ptr() const 110 { return reinterpret_cast<internal_type*>(this->m_storage.data); } 111 ~list_nodeboost::container::dtl::list_node112 BOOST_CONTAINER_FORCEINLINE ~list_node() 113 { reinterpret_cast<T*>(this->m_storage.data)->~T(); } 114 115 #if defined(BOOST_CONTAINER_DISABLE_ALIASING_WARNING) 116 #pragma GCC diagnostic pop 117 #undef BOOST_CONTAINER_DISABLE_ALIASING_WARNING 118 # endif 119 destroy_headerboost::container::dtl::list_node120 BOOST_CONTAINER_FORCEINLINE void destroy_header() 121 { static_cast<hook_type*>(this)->~hook_type(); } 122 }; 123 124 template <class T, class VoidPointer> 125 struct iiterator_node_value_type< list_node<T,VoidPointer> > { 126 typedef T type; 127 }; 128 129 template<class Allocator> 130 struct intrusive_list_type 131 { 132 typedef boost::container::allocator_traits<Allocator> allocator_traits_type; 133 typedef typename allocator_traits_type::value_type value_type; 134 typedef typename boost::intrusive::pointer_traits 135 <typename allocator_traits_type::pointer>::template 136 rebind_pointer<void>::type 137 void_pointer; 138 typedef typename dtl::list_node 139 <value_type, void_pointer> node_type; 140 typedef typename dtl::bi::make_list 141 < node_type 142 , dtl::bi::base_hook<typename list_hook<void_pointer>::type> 143 , dtl::bi::constant_time_size<true> 144 , dtl::bi::size_type 145 <typename allocator_traits_type::size_type> 146 >::type container_type; 147 typedef container_type type ; 148 }; 149 150 } //namespace dtl { 151 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 152 153 //! A list is a doubly linked list. That is, it is a Sequence that supports both 154 //! forward and backward traversal, and (amortized) constant time insertion and 155 //! removal of elements at the beginning or the end, or in the middle. Lists have 156 //! the important property that insertion and splicing do not invalidate iterators 157 //! to list elements, and that even removal invalidates only the iterators that point 158 //! to the elements that are removed. The ordering of iterators may be changed 159 //! (that is, list<T>::iterator might have a different predecessor or successor 160 //! after a list operation than it did before), but the iterators themselves will 161 //! not be invalidated or made to point to different elements unless that invalidation 162 //! or mutation is explicit. 163 //! 164 //! \tparam T The type of object that is stored in the list 165 //! \tparam Allocator The allocator used for all internal memory management, use void 166 //! for the default allocator 167 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED 168 template <class T, class Allocator = void > 169 #else 170 template <class T, class Allocator> 171 #endif 172 class list 173 : protected dtl::node_alloc_holder 174 < typename real_allocator<T, Allocator>::type 175 , typename dtl::intrusive_list_type<typename real_allocator<T, Allocator>::type>::type> 176 { 177 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 178 typedef typename real_allocator<T, Allocator>::type ValueAllocator; 179 typedef typename 180 dtl::intrusive_list_type<ValueAllocator>::type Icont; 181 typedef dtl::node_alloc_holder<ValueAllocator, Icont> AllocHolder; 182 typedef typename AllocHolder::NodePtr NodePtr; 183 typedef typename AllocHolder::NodeAlloc NodeAlloc; 184 typedef typename AllocHolder::ValAlloc ValAlloc; 185 typedef typename AllocHolder::Node Node; 186 typedef dtl::allocator_destroyer<NodeAlloc> Destroyer; 187 typedef typename AllocHolder::alloc_version alloc_version; 188 typedef boost::container::allocator_traits<ValueAllocator> allocator_traits_type; 189 typedef boost::container::equal_to_value 190 <typename allocator_traits_type::value_type> equal_to_value_type; 191 192 BOOST_COPYABLE_AND_MOVABLE(list) 193 194 typedef dtl::iterator_from_iiterator<typename Icont::iterator, false> iterator_impl; 195 typedef dtl::iterator_from_iiterator<typename Icont::iterator, true> const_iterator_impl; 196 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 197 198 public: 199 ////////////////////////////////////////////// 200 // 201 // types 202 // 203 ////////////////////////////////////////////// 204 205 typedef T value_type; 206 typedef typename ::boost::container::allocator_traits<ValueAllocator>::pointer pointer; 207 typedef typename ::boost::container::allocator_traits<ValueAllocator>::const_pointer const_pointer; 208 typedef typename ::boost::container::allocator_traits<ValueAllocator>::reference reference; 209 typedef typename ::boost::container::allocator_traits<ValueAllocator>::const_reference const_reference; 210 typedef typename ::boost::container::allocator_traits<ValueAllocator>::size_type size_type; 211 typedef typename ::boost::container::allocator_traits<ValueAllocator>::difference_type difference_type; 212 typedef ValueAllocator allocator_type; 213 typedef BOOST_CONTAINER_IMPDEF(NodeAlloc) stored_allocator_type; 214 typedef BOOST_CONTAINER_IMPDEF(iterator_impl) iterator; 215 typedef BOOST_CONTAINER_IMPDEF(const_iterator_impl) const_iterator; 216 typedef BOOST_CONTAINER_IMPDEF(boost::container::reverse_iterator<iterator>) reverse_iterator; 217 typedef BOOST_CONTAINER_IMPDEF(boost::container::reverse_iterator<const_iterator>) const_reverse_iterator; 218 219 ////////////////////////////////////////////// 220 // 221 // construct/copy/destroy 222 // 223 ////////////////////////////////////////////// 224 225 //! <b>Effects</b>: Default constructs a list. 226 //! 227 //! <b>Throws</b>: If allocator_type's default constructor throws. 228 //! 229 //! <b>Complexity</b>: Constant. BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<ValueAllocator>::value)230 list() BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<ValueAllocator>::value) 231 : AllocHolder() 232 {} 233 234 //! <b>Effects</b>: Constructs a list taking the allocator as parameter. 235 //! 236 //! <b>Throws</b>: Nothing 237 //! 238 //! <b>Complexity</b>: Constant. list(const allocator_type & a)239 explicit list(const allocator_type &a) BOOST_NOEXCEPT_OR_NOTHROW 240 : AllocHolder(a) 241 {} 242 243 //! <b>Effects</b>: Constructs a list 244 //! and inserts n value-initialized value_types. 245 //! 246 //! <b>Throws</b>: If allocator_type's default constructor 247 //! throws or T's default or copy constructor throws. 248 //! 249 //! <b>Complexity</b>: Linear to n. list(size_type n)250 explicit list(size_type n) 251 : AllocHolder(ValueAllocator()) 252 { this->resize(n); } 253 254 //! <b>Effects</b>: Constructs a list that will use a copy of allocator a 255 //! and inserts n copies of value. 256 //! 257 //! <b>Throws</b>: If allocator_type's default constructor 258 //! throws or T's default or copy constructor throws. 259 //! 260 //! <b>Complexity</b>: Linear to n. list(size_type n,const allocator_type & a)261 list(size_type n, const allocator_type &a) 262 : AllocHolder(a) 263 { this->resize(n); } 264 265 //! <b>Effects</b>: Constructs a list that will use a copy of allocator a 266 //! and inserts n copies of value. 267 //! 268 //! <b>Throws</b>: If allocator_type's default constructor 269 //! throws or T's default or copy constructor throws. 270 //! 271 //! <b>Complexity</b>: Linear to n. list(size_type n,const T & value,const ValueAllocator & a=ValueAllocator ())272 list(size_type n, const T& value, const ValueAllocator& a = ValueAllocator()) 273 : AllocHolder(a) 274 { this->insert(this->cbegin(), n, value); } 275 276 //! <b>Effects</b>: Copy constructs a list. 277 //! 278 //! <b>Postcondition</b>: x == *this. 279 //! 280 //! <b>Throws</b>: If allocator_type's default constructor throws. 281 //! 282 //! <b>Complexity</b>: Linear to the elements x contains. list(const list & x)283 list(const list& x) 284 : AllocHolder(x) 285 { this->insert(this->cbegin(), x.begin(), x.end()); } 286 287 //! <b>Effects</b>: Move constructor. Moves x's resources to *this. 288 //! 289 //! <b>Throws</b>: If allocator_type's copy constructor throws. 290 //! 291 //! <b>Complexity</b>: Constant. list(BOOST_RV_REF (list)x)292 list(BOOST_RV_REF(list) x) BOOST_NOEXCEPT_OR_NOTHROW 293 : AllocHolder(BOOST_MOVE_BASE(AllocHolder, x)) 294 {} 295 296 //! <b>Effects</b>: Copy constructs a list using the specified allocator. 297 //! 298 //! <b>Postcondition</b>: x == *this. 299 //! 300 //! <b>Throws</b>: If allocator_type's default constructor or copy constructor throws. 301 //! 302 //! <b>Complexity</b>: Linear to the elements x contains. list(const list & x,const allocator_type & a)303 list(const list& x, const allocator_type &a) 304 : AllocHolder(a) 305 { this->insert(this->cbegin(), x.begin(), x.end()); } 306 307 //! <b>Effects</b>: Move constructor sing the specified allocator. 308 //! Moves x's resources to *this. 309 //! 310 //! <b>Throws</b>: If allocation or value_type's copy constructor throws. 311 //! 312 //! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise. list(BOOST_RV_REF (list)x,const allocator_type & a)313 list(BOOST_RV_REF(list) x, const allocator_type &a) 314 : AllocHolder(a) 315 { 316 if(this->node_alloc() == x.node_alloc()){ 317 this->icont().swap(x.icont()); 318 } 319 else{ 320 this->insert(this->cbegin(), boost::make_move_iterator(x.begin()), boost::make_move_iterator(x.end())); 321 } 322 } 323 324 //! <b>Effects</b>: Constructs a list that will use a copy of allocator a 325 //! and inserts a copy of the range [first, last) in the list. 326 //! 327 //! <b>Throws</b>: If allocator_type's default constructor 328 //! throws or T's constructor taking a dereferenced InIt throws. 329 //! 330 //! <b>Complexity</b>: Linear to the range [first, last). 331 template <class InpIt> list(InpIt first,InpIt last,const ValueAllocator & a=ValueAllocator ())332 list(InpIt first, InpIt last, const ValueAllocator &a = ValueAllocator()) 333 : AllocHolder(a) 334 { this->insert(this->cbegin(), first, last); } 335 336 337 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 338 //! <b>Effects</b>: Constructs a list that will use a copy of allocator a 339 //! and inserts a copy of the range [il.begin(), il.end()) in the list. 340 //! 341 //! <b>Throws</b>: If allocator_type's default constructor 342 //! throws or T's constructor taking a dereferenced 343 //! std::initializer_list iterator throws. 344 //! 345 //! <b>Complexity</b>: Linear to the range [il.begin(), il.end()). list(std::initializer_list<value_type> il,const ValueAllocator & a=ValueAllocator ())346 list(std::initializer_list<value_type> il, const ValueAllocator &a = ValueAllocator()) 347 : AllocHolder(a) 348 { this->insert(this->cbegin(), il.begin(), il.end()); } 349 #endif 350 351 //! <b>Effects</b>: Destroys the list. All stored values are destroyed 352 //! and used memory is deallocated. 353 //! 354 //! <b>Throws</b>: Nothing. 355 //! 356 //! <b>Complexity</b>: Linear to the number of elements. ~list()357 ~list() BOOST_NOEXCEPT_OR_NOTHROW 358 {} //AllocHolder clears the list 359 360 //! <b>Effects</b>: Makes *this contain the same elements as x. 361 //! 362 //! <b>Postcondition</b>: this->size() == x.size(). *this contains a copy 363 //! of each of x's elements. 364 //! 365 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws. 366 //! 367 //! <b>Complexity</b>: Linear to the number of elements in x. operator =(BOOST_COPY_ASSIGN_REF (list)x)368 list& operator=(BOOST_COPY_ASSIGN_REF(list) x) 369 { 370 if (BOOST_LIKELY(this != &x)) { 371 NodeAlloc &this_alloc = this->node_alloc(); 372 const NodeAlloc &x_alloc = x.node_alloc(); 373 dtl::bool_<allocator_traits_type:: 374 propagate_on_container_copy_assignment::value> flag; 375 if(flag && this_alloc != x_alloc){ 376 this->clear(); 377 } 378 this->AllocHolder::copy_assign_alloc(x); 379 this->assign(x.begin(), x.end()); 380 } 381 return *this; 382 } 383 384 //! <b>Effects</b>: Move assignment. All x's values are transferred to *this. 385 //! 386 //! <b>Postcondition</b>: x.empty(). *this contains a the elements x had 387 //! before the function. 388 //! 389 //! <b>Throws</b>: If allocator_traits_type::propagate_on_container_move_assignment 390 //! is false and (allocation throws or value_type's move constructor throws) 391 //! 392 //! <b>Complexity</b>: Constant if allocator_traits_type:: 393 //! propagate_on_container_move_assignment is true or 394 //! this->get>allocator() == x.get_allocator(). Linear otherwise. operator =(BOOST_RV_REF (list)x)395 list& operator=(BOOST_RV_REF(list) x) 396 BOOST_NOEXCEPT_IF(allocator_traits_type::propagate_on_container_move_assignment::value 397 || allocator_traits_type::is_always_equal::value) 398 { 399 if (BOOST_LIKELY(this != &x)) { 400 NodeAlloc &this_alloc = this->node_alloc(); 401 NodeAlloc &x_alloc = x.node_alloc(); 402 const bool propagate_alloc = allocator_traits_type:: 403 propagate_on_container_move_assignment::value; 404 const bool allocators_equal = this_alloc == x_alloc; (void)allocators_equal; 405 //Resources can be transferred if both allocators are 406 //going to be equal after this function (either propagated or already equal) 407 if(propagate_alloc || allocators_equal){ 408 //Destroy 409 this->clear(); 410 //Move allocator if needed 411 this->AllocHolder::move_assign_alloc(x); 412 //Obtain resources 413 this->icont() = boost::move(x.icont()); 414 } 415 //Else do a one by one move 416 else{ 417 this->assign( boost::make_move_iterator(x.begin()) 418 , boost::make_move_iterator(x.end())); 419 } 420 } 421 return *this; 422 } 423 424 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 425 //! <b>Effects</b>: Makes *this contain the same elements as il. 426 //! 427 //! <b>Postcondition</b>: this->size() == il.size(). *this contains a copy 428 //! of each of x's elements. 429 //! 430 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws. 431 //! 432 //! <b>Complexity</b>: Linear to the number of elements in x. operator =(std::initializer_list<value_type> il)433 list& operator=(std::initializer_list<value_type> il) 434 { 435 assign(il.begin(), il.end()); 436 return *this; 437 } 438 #endif 439 440 //! <b>Effects</b>: Assigns the n copies of val to *this. 441 //! 442 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws. 443 //! 444 //! <b>Complexity</b>: Linear to n. assign(size_type n,const T & val)445 void assign(size_type n, const T& val) 446 { 447 typedef constant_iterator<value_type, difference_type> cvalue_iterator; 448 return this->assign(cvalue_iterator(val, n), cvalue_iterator()); 449 } 450 451 //! <b>Effects</b>: Assigns the range [first, last) to *this. 452 //! 453 //! <b>Throws</b>: If memory allocation throws or 454 //! T's constructor from dereferencing InpIt throws. 455 //! 456 //! <b>Complexity</b>: Linear to n. 457 template <class InpIt> assign(InpIt first,InpIt last,typename dtl::disable_if_convertible<InpIt,size_type>::type * =0)458 void assign(InpIt first, InpIt last 459 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 460 , typename dtl::disable_if_convertible<InpIt, size_type>::type * = 0 461 #endif 462 ) 463 { 464 iterator first1 = this->begin(); 465 const iterator last1 = this->end(); 466 for ( ; first1 != last1 && first != last; ++first1, ++first) 467 *first1 = *first; 468 if (first == last) 469 this->erase(first1, last1); 470 else{ 471 this->insert(last1, first, last); 472 } 473 } 474 475 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 476 //! <b>Effects</b>: Assigns the range [il.begin(), il.end()) to *this. 477 //! 478 //! <b>Throws</b>: If memory allocation throws or 479 //! T's constructor from dereferencing std::initializer_list iterator throws. 480 //! 481 //! <b>Complexity</b>: Linear to n. assign(std::initializer_list<value_type> il)482 void assign(std::initializer_list<value_type> il) 483 { assign(il.begin(), il.end()); } 484 #endif 485 486 //! <b>Effects</b>: Returns a copy of the internal allocator. 487 //! 488 //! <b>Throws</b>: If allocator's copy constructor throws. 489 //! 490 //! <b>Complexity</b>: Constant. get_allocator() const491 allocator_type get_allocator() const BOOST_NOEXCEPT_OR_NOTHROW 492 { return allocator_type(this->node_alloc()); } 493 494 //! <b>Effects</b>: Returns a reference to the internal allocator. 495 //! 496 //! <b>Throws</b>: Nothing 497 //! 498 //! <b>Complexity</b>: Constant. 499 //! 500 //! <b>Note</b>: Non-standard extension. get_stored_allocator()501 stored_allocator_type &get_stored_allocator() BOOST_NOEXCEPT_OR_NOTHROW 502 { return this->node_alloc(); } 503 504 //! <b>Effects</b>: Returns a reference to the internal allocator. 505 //! 506 //! <b>Throws</b>: Nothing 507 //! 508 //! <b>Complexity</b>: Constant. 509 //! 510 //! <b>Note</b>: Non-standard extension. get_stored_allocator() const511 const stored_allocator_type &get_stored_allocator() const BOOST_NOEXCEPT_OR_NOTHROW 512 { return this->node_alloc(); } 513 514 ////////////////////////////////////////////// 515 // 516 // iterators 517 // 518 ////////////////////////////////////////////// 519 520 //! <b>Effects</b>: Returns an iterator to the first element contained in the list. 521 //! 522 //! <b>Throws</b>: Nothing. 523 //! 524 //! <b>Complexity</b>: Constant. begin()525 iterator begin() BOOST_NOEXCEPT_OR_NOTHROW 526 { return iterator(this->icont().begin()); } 527 528 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the list. 529 //! 530 //! <b>Throws</b>: Nothing. 531 //! 532 //! <b>Complexity</b>: Constant. begin() const533 const_iterator begin() const BOOST_NOEXCEPT_OR_NOTHROW 534 { return this->cbegin(); } 535 536 //! <b>Effects</b>: Returns an iterator to the end of the list. 537 //! 538 //! <b>Throws</b>: Nothing. 539 //! 540 //! <b>Complexity</b>: Constant. end()541 iterator end() BOOST_NOEXCEPT_OR_NOTHROW 542 { return iterator(this->icont().end()); } 543 544 //! <b>Effects</b>: Returns a const_iterator to the end of the list. 545 //! 546 //! <b>Throws</b>: Nothing. 547 //! 548 //! <b>Complexity</b>: Constant. end() const549 const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW 550 { return this->cend(); } 551 552 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning 553 //! of the reversed list. 554 //! 555 //! <b>Throws</b>: Nothing. 556 //! 557 //! <b>Complexity</b>: Constant. rbegin()558 reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW 559 { return reverse_iterator(end()); } 560 561 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning 562 //! of the reversed list. 563 //! 564 //! <b>Throws</b>: Nothing. 565 //! 566 //! <b>Complexity</b>: Constant. rbegin() const567 const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW 568 { return this->crbegin(); } 569 570 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end 571 //! of the reversed list. 572 //! 573 //! <b>Throws</b>: Nothing. 574 //! 575 //! <b>Complexity</b>: Constant. rend()576 reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW 577 { return reverse_iterator(begin()); } 578 579 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end 580 //! of the reversed list. 581 //! 582 //! <b>Throws</b>: Nothing. 583 //! 584 //! <b>Complexity</b>: Constant. rend() const585 const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW 586 { return this->crend(); } 587 588 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the list. 589 //! 590 //! <b>Throws</b>: Nothing. 591 //! 592 //! <b>Complexity</b>: Constant. cbegin() const593 const_iterator cbegin() const BOOST_NOEXCEPT_OR_NOTHROW 594 { return const_iterator(this->non_const_icont().begin()); } 595 596 //! <b>Effects</b>: Returns a const_iterator to the end of the list. 597 //! 598 //! <b>Throws</b>: Nothing. 599 //! 600 //! <b>Complexity</b>: Constant. cend() const601 const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW 602 { return const_iterator(this->non_const_icont().end()); } 603 604 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning 605 //! of the reversed list. 606 //! 607 //! <b>Throws</b>: Nothing. 608 //! 609 //! <b>Complexity</b>: Constant. crbegin() const610 const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW 611 { return const_reverse_iterator(this->cend()); } 612 613 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end 614 //! of the reversed list. 615 //! 616 //! <b>Throws</b>: Nothing. 617 //! 618 //! <b>Complexity</b>: Constant. crend() const619 const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW 620 { return const_reverse_iterator(this->cbegin()); } 621 622 ////////////////////////////////////////////// 623 // 624 // capacity 625 // 626 ////////////////////////////////////////////// 627 628 //! <b>Effects</b>: Returns true if the list contains no elements. 629 //! 630 //! <b>Throws</b>: Nothing. 631 //! 632 //! <b>Complexity</b>: Constant. empty() const633 bool empty() const BOOST_NOEXCEPT_OR_NOTHROW 634 { return !this->size(); } 635 636 //! <b>Effects</b>: Returns the number of the elements contained in the list. 637 //! 638 //! <b>Throws</b>: Nothing. 639 //! 640 //! <b>Complexity</b>: Constant. size() const641 size_type size() const BOOST_NOEXCEPT_OR_NOTHROW 642 { return this->icont().size(); } 643 644 //! <b>Effects</b>: Returns the largest possible size of the list. 645 //! 646 //! <b>Throws</b>: Nothing. 647 //! 648 //! <b>Complexity</b>: Constant. max_size() const649 size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW 650 { return AllocHolder::max_size(); } 651 652 //! <b>Effects</b>: Inserts or erases elements at the end such that 653 //! the size becomes n. New elements are value initialized. 654 //! 655 //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws. 656 //! 657 //! <b>Complexity</b>: Linear to the difference between size() and new_size. resize(size_type new_size)658 void resize(size_type new_size) 659 { 660 if(!priv_try_shrink(new_size)){ 661 typedef value_init_construct_iterator<value_type, difference_type> value_init_iterator; 662 this->insert(this->cend(), value_init_iterator(new_size - this->size()), value_init_iterator()); 663 } 664 } 665 666 //! <b>Effects</b>: Inserts or erases elements at the end such that 667 //! the size becomes n. New elements are copy constructed from x. 668 //! 669 //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws. 670 //! 671 //! <b>Complexity</b>: Linear to the difference between size() and new_size. resize(size_type new_size,const T & x)672 void resize(size_type new_size, const T& x) 673 { 674 if(!priv_try_shrink(new_size)){ 675 this->insert(this->cend(), new_size - this->size(), x); 676 } 677 } 678 679 ////////////////////////////////////////////// 680 // 681 // element access 682 // 683 ////////////////////////////////////////////// 684 685 //! <b>Requires</b>: !empty() 686 //! 687 //! <b>Effects</b>: Returns a reference to the first element 688 //! from the beginning of the container. 689 //! 690 //! <b>Throws</b>: Nothing. 691 //! 692 //! <b>Complexity</b>: Constant. front()693 reference front() BOOST_NOEXCEPT_OR_NOTHROW 694 { 695 BOOST_ASSERT(!this->empty()); 696 return *this->begin(); 697 } 698 699 //! <b>Requires</b>: !empty() 700 //! 701 //! <b>Effects</b>: Returns a const reference to the first element 702 //! from the beginning of the container. 703 //! 704 //! <b>Throws</b>: Nothing. 705 //! 706 //! <b>Complexity</b>: Constant. front() const707 const_reference front() const BOOST_NOEXCEPT_OR_NOTHROW 708 { 709 BOOST_ASSERT(!this->empty()); 710 return *this->begin(); 711 } 712 713 //! <b>Requires</b>: !empty() 714 //! 715 //! <b>Effects</b>: Returns a reference to the first element 716 //! from the beginning of the container. 717 //! 718 //! <b>Throws</b>: Nothing. 719 //! 720 //! <b>Complexity</b>: Constant. back()721 reference back() BOOST_NOEXCEPT_OR_NOTHROW 722 { 723 BOOST_ASSERT(!this->empty()); 724 return *(--this->end()); 725 } 726 727 //! <b>Requires</b>: !empty() 728 //! 729 //! <b>Effects</b>: Returns a const reference to the first element 730 //! from the beginning of the container. 731 //! 732 //! <b>Throws</b>: Nothing. 733 //! 734 //! <b>Complexity</b>: Constant. back() const735 const_reference back() const BOOST_NOEXCEPT_OR_NOTHROW 736 { 737 BOOST_ASSERT(!this->empty()); 738 return *(--this->end()); 739 } 740 741 ////////////////////////////////////////////// 742 // 743 // modifiers 744 // 745 ////////////////////////////////////////////// 746 747 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 748 749 //! <b>Effects</b>: Inserts an object of type T constructed with 750 //! std::forward<Args>(args)... in the end of the list. 751 //! 752 //! <b>Returns</b>: A reference to the created object. 753 //! 754 //! <b>Throws</b>: If memory allocation throws or 755 //! T's in-place constructor throws. 756 //! 757 //! <b>Complexity</b>: Constant 758 template <class... Args> emplace_back(BOOST_FWD_REF (Args)...args)759 reference emplace_back(BOOST_FWD_REF(Args)... args) 760 { return *this->emplace(this->cend(), boost::forward<Args>(args)...); } 761 762 //! <b>Effects</b>: Inserts an object of type T constructed with 763 //! std::forward<Args>(args)... in the beginning of the list. 764 //! 765 //! <b>Returns</b>: A reference to the created object. 766 //! 767 //! <b>Throws</b>: If memory allocation throws or 768 //! T's in-place constructor throws. 769 //! 770 //! <b>Complexity</b>: Constant 771 template <class... Args> emplace_front(BOOST_FWD_REF (Args)...args)772 reference emplace_front(BOOST_FWD_REF(Args)... args) 773 { return *this->emplace(this->cbegin(), boost::forward<Args>(args)...); } 774 775 //! <b>Effects</b>: Inserts an object of type T constructed with 776 //! std::forward<Args>(args)... before p. 777 //! 778 //! <b>Throws</b>: If memory allocation throws or 779 //! T's in-place constructor throws. 780 //! 781 //! <b>Complexity</b>: Constant 782 template <class... Args> emplace(const_iterator position,BOOST_FWD_REF (Args)...args)783 iterator emplace(const_iterator position, BOOST_FWD_REF(Args)... args) 784 { 785 BOOST_ASSERT((priv_is_linked)(position)); 786 NodePtr pnode(AllocHolder::create_node(boost::forward<Args>(args)...)); 787 return iterator(this->icont().insert(position.get(), *pnode)); 788 } 789 790 #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 791 792 #define BOOST_CONTAINER_LIST_EMPLACE_CODE(N) \ 793 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 794 reference emplace_back(BOOST_MOVE_UREF##N)\ 795 { return *this->emplace(this->cend() BOOST_MOVE_I##N BOOST_MOVE_FWD##N); }\ 796 \ 797 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 798 reference emplace_front(BOOST_MOVE_UREF##N)\ 799 { return *this->emplace(this->cbegin() BOOST_MOVE_I##N BOOST_MOVE_FWD##N);}\ 800 \ 801 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 802 iterator emplace(const_iterator position BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ 803 {\ 804 BOOST_ASSERT(position == this->cend() || (--(++position) == position) );\ 805 NodePtr pnode (AllocHolder::create_node(BOOST_MOVE_FWD##N));\ 806 return iterator(this->icont().insert(position.get(), *pnode));\ 807 }\ 808 // 809 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_LIST_EMPLACE_CODE) 810 #undef BOOST_CONTAINER_LIST_EMPLACE_CODE 811 812 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 813 814 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 815 //! <b>Effects</b>: Inserts a copy of x at the beginning of the list. 816 //! 817 //! <b>Throws</b>: If memory allocation throws or 818 //! T's copy constructor throws. 819 //! 820 //! <b>Complexity</b>: Amortized constant time. 821 void push_front(const T &x); 822 823 //! <b>Effects</b>: Constructs a new element in the beginning of the list 824 //! and moves the resources of x to this new element. 825 //! 826 //! <b>Throws</b>: If memory allocation throws. 827 //! 828 //! <b>Complexity</b>: Amortized constant time. 829 void push_front(T &&x); 830 #else 831 BOOST_MOVE_CONVERSION_AWARE_CATCH(push_front, T, void, priv_push_front) 832 #endif 833 834 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 835 //! <b>Effects</b>: Inserts a copy of x at the end of the list. 836 //! 837 //! <b>Throws</b>: If memory allocation throws or 838 //! T's copy constructor throws. 839 //! 840 //! <b>Complexity</b>: Amortized constant time. 841 void push_back(const T &x); 842 843 //! <b>Effects</b>: Constructs a new element in the end of the list 844 //! and moves the resources of x to this new element. 845 //! 846 //! <b>Throws</b>: If memory allocation throws. 847 //! 848 //! <b>Complexity</b>: Amortized constant time. 849 void push_back(T &&x); 850 #else 851 BOOST_MOVE_CONVERSION_AWARE_CATCH(push_back, T, void, priv_push_back) 852 #endif 853 854 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 855 //! <b>Requires</b>: p must be a valid iterator of *this. 856 //! 857 //! <b>Effects</b>: Insert a copy of x before p. 858 //! 859 //! <b>Returns</b>: an iterator to the inserted element. 860 //! 861 //! <b>Throws</b>: If memory allocation throws or x's copy constructor throws. 862 //! 863 //! <b>Complexity</b>: Amortized constant time. 864 iterator insert(const_iterator p, const T &x); 865 866 //! <b>Requires</b>: p must be a valid iterator of *this. 867 //! 868 //! <b>Effects</b>: Insert a new element before p with x's resources. 869 //! 870 //! <b>Returns</b>: an iterator to the inserted element. 871 //! 872 //! <b>Throws</b>: If memory allocation throws. 873 //! 874 //! <b>Complexity</b>: Amortized constant time. 875 iterator insert(const_iterator p, T &&x); 876 #else 877 BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, T, iterator, priv_insert, const_iterator, const_iterator) 878 #endif 879 880 //! <b>Requires</b>: p must be a valid iterator of *this. 881 //! 882 //! <b>Effects</b>: Inserts n copies of x before p. 883 //! 884 //! <b>Returns</b>: an iterator to the first inserted element or p if n is 0. 885 //! 886 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws. 887 //! 888 //! <b>Complexity</b>: Linear to n. insert(const_iterator position,size_type n,const T & x)889 iterator insert(const_iterator position, size_type n, const T& x) 890 { 891 //range check is done by insert 892 typedef constant_iterator<value_type, difference_type> cvalue_iterator; 893 return this->insert(position, cvalue_iterator(x, n), cvalue_iterator()); 894 } 895 896 //! <b>Requires</b>: p must be a valid iterator of *this. 897 //! 898 //! <b>Effects</b>: Insert a copy of the [first, last) range before p. 899 //! 900 //! <b>Returns</b>: an iterator to the first inserted element or p if first == last. 901 //! 902 //! <b>Throws</b>: If memory allocation throws, T's constructor from a 903 //! dereferenced InpIt throws. 904 //! 905 //! <b>Complexity</b>: Linear to distance [first, last). 906 template <class InpIt> insert(const_iterator p,InpIt first,InpIt last,typename dtl::enable_if_c<!dtl::is_convertible<InpIt,size_type>::value && (dtl::is_input_iterator<InpIt>::value||dtl::is_same<alloc_version,version_1>::value)>::type * =0)907 iterator insert(const_iterator p, InpIt first, InpIt last 908 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 909 , typename dtl::enable_if_c 910 < !dtl::is_convertible<InpIt, size_type>::value 911 && (dtl::is_input_iterator<InpIt>::value 912 || dtl::is_same<alloc_version, version_1>::value 913 ) 914 >::type * = 0 915 #endif 916 ) 917 { 918 BOOST_ASSERT((priv_is_linked)(p)); 919 const typename Icont::iterator ipos(p.get()); 920 iterator ret_it(ipos); 921 if(first != last){ 922 ret_it = iterator(this->icont().insert(ipos, *this->create_node_from_it(first))); 923 ++first; 924 } 925 for (; first != last; ++first){ 926 this->icont().insert(ipos, *this->create_node_from_it(first)); 927 } 928 return ret_it; 929 } 930 931 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 932 template <class FwdIt> insert(const_iterator position,FwdIt first,FwdIt last,typename dtl::enable_if_c<!dtl::is_convertible<FwdIt,size_type>::value &&!(dtl::is_input_iterator<FwdIt>::value||dtl::is_same<alloc_version,version_1>::value)>::type * =0)933 iterator insert(const_iterator position, FwdIt first, FwdIt last 934 , typename dtl::enable_if_c 935 < !dtl::is_convertible<FwdIt, size_type>::value 936 && !(dtl::is_input_iterator<FwdIt>::value 937 || dtl::is_same<alloc_version, version_1>::value 938 ) 939 >::type * = 0 940 ) 941 { 942 BOOST_ASSERT((priv_is_linked)(position)); 943 //Optimized allocation and construction 944 insertion_functor func(this->icont(), position.get()); 945 iterator before_p(position.get()); 946 --before_p; 947 this->allocate_many_and_construct(first, boost::container::iterator_distance(first, last), func); 948 return ++before_p; 949 } 950 #endif 951 952 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 953 //! <b>Requires</b>: p must be a valid iterator of *this. 954 //! 955 //! <b>Effects</b>: Insert a copy of the [il.begin(), il.end()) range before p. 956 //! 957 //! <b>Returns</b>: an iterator to the first inserted element or p if if.begin() == il.end(). 958 //! 959 //! <b>Throws</b>: If memory allocation throws, T's constructor from a 960 //! dereferenced std::initializer_list iterator throws. 961 //! 962 //! <b>Complexity</b>: Linear to distance [il.begin(), il.end()). insert(const_iterator p,std::initializer_list<value_type> il)963 iterator insert(const_iterator p, std::initializer_list<value_type> il) 964 { 965 //position range check is done by insert() 966 return insert(p, il.begin(), il.end()); 967 } 968 #endif 969 970 //! <b>Effects</b>: Removes the first element from the list. 971 //! 972 //! <b>Throws</b>: Nothing. 973 //! 974 //! <b>Complexity</b>: Amortized constant time. pop_front()975 void pop_front() BOOST_NOEXCEPT_OR_NOTHROW 976 { 977 BOOST_ASSERT(!this->empty()); 978 this->erase(this->cbegin()); 979 } 980 981 //! <b>Effects</b>: Removes the last element from the list. 982 //! 983 //! <b>Throws</b>: Nothing. 984 //! 985 //! <b>Complexity</b>: Amortized constant time. pop_back()986 void pop_back() BOOST_NOEXCEPT_OR_NOTHROW 987 { 988 BOOST_ASSERT(!this->empty()); 989 const_iterator tmp = this->cend(); 990 this->erase(--tmp); 991 } 992 993 //! <b>Requires</b>: p must be a valid iterator of *this. 994 //! 995 //! <b>Effects</b>: Erases the element at p. 996 //! 997 //! <b>Throws</b>: Nothing. 998 //! 999 //! <b>Complexity</b>: Amortized constant time. erase(const_iterator p)1000 iterator erase(const_iterator p) BOOST_NOEXCEPT_OR_NOTHROW 1001 { 1002 BOOST_ASSERT(p != this->cend() && (priv_is_linked)(p)); 1003 return iterator(this->icont().erase_and_dispose(p.get(), Destroyer(this->node_alloc()))); 1004 } 1005 1006 //! <b>Requires</b>: first and last must be valid iterator to elements in *this. 1007 //! 1008 //! <b>Effects</b>: Erases the elements pointed by [first, last). 1009 //! 1010 //! <b>Throws</b>: Nothing. 1011 //! 1012 //! <b>Complexity</b>: Linear to the distance between first and last. erase(const_iterator first,const_iterator last)1013 iterator erase(const_iterator first, const_iterator last) BOOST_NOEXCEPT_OR_NOTHROW 1014 { 1015 BOOST_ASSERT(first == last || (first != this->cend() && (priv_is_linked)(first))); 1016 BOOST_ASSERT(first == last || (priv_is_linked)(last)); 1017 return iterator(AllocHolder::erase_range(first.get(), last.get(), alloc_version())); 1018 } 1019 1020 //! <b>Effects</b>: Swaps the contents of *this and x. 1021 //! 1022 //! <b>Throws</b>: Nothing. 1023 //! 1024 //! <b>Complexity</b>: Constant. swap(list & x)1025 void swap(list& x) 1026 BOOST_NOEXCEPT_IF(allocator_traits_type::propagate_on_container_swap::value 1027 || allocator_traits_type::is_always_equal::value) 1028 { 1029 BOOST_ASSERT(allocator_traits_type::propagate_on_container_swap::value || 1030 allocator_traits_type::is_always_equal::value || 1031 this->get_stored_allocator() == x.get_stored_allocator()); 1032 AllocHolder::swap(x); 1033 } 1034 1035 //! <b>Effects</b>: Erases all the elements of the list. 1036 //! 1037 //! <b>Throws</b>: Nothing. 1038 //! 1039 //! <b>Complexity</b>: Linear to the number of elements in the list. clear()1040 void clear() BOOST_NOEXCEPT_OR_NOTHROW 1041 { AllocHolder::clear(alloc_version()); } 1042 1043 ////////////////////////////////////////////// 1044 // 1045 // slist operations 1046 // 1047 ////////////////////////////////////////////// 1048 1049 //! <b>Requires</b>: p must point to an element contained 1050 //! by the list. x != *this. this' allocator and x's allocator shall compare equal 1051 //! 1052 //! <b>Effects</b>: Transfers all the elements of list x to this list, before the 1053 //! the element pointed by p. No destructors or copy constructors are called. 1054 //! 1055 //! <b>Throws</b>: Nothing 1056 //! 1057 //! <b>Complexity</b>: Constant. 1058 //! 1059 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of 1060 //! this list. Iterators of this list and all the references are not invalidated. splice(const_iterator p,list & x)1061 void splice(const_iterator p, list& x) BOOST_NOEXCEPT_OR_NOTHROW 1062 { 1063 BOOST_ASSERT((priv_is_linked)(p)); 1064 BOOST_ASSERT(this != &x); 1065 BOOST_ASSERT(this->node_alloc() == x.node_alloc()); 1066 this->icont().splice(p.get(), x.icont()); 1067 } 1068 1069 //! <b>Requires</b>: p must point to an element contained 1070 //! by the list. x != *this. this' allocator and x's allocator shall compare equal 1071 //! 1072 //! <b>Effects</b>: Transfers all the elements of list x to this list, before the 1073 //! the element pointed by p. No destructors or copy constructors are called. 1074 //! 1075 //! <b>Throws</b>: Nothing 1076 //! 1077 //! <b>Complexity</b>: Constant. 1078 //! 1079 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of 1080 //! this list. Iterators of this list and all the references are not invalidated. splice(const_iterator p,BOOST_RV_REF (list)x)1081 void splice(const_iterator p, BOOST_RV_REF(list) x) BOOST_NOEXCEPT_OR_NOTHROW 1082 { 1083 //Checks done in splice 1084 this->splice(p, static_cast<list&>(x)); 1085 } 1086 1087 //! <b>Requires</b>: p must point to an element contained 1088 //! by this list. i must point to an element contained in list x. 1089 //! this' allocator and x's allocator shall compare equal 1090 //! 1091 //! <b>Effects</b>: Transfers the value pointed by i, from list x to this list, 1092 //! before the element pointed by p. No destructors or copy constructors are called. 1093 //! If p == i or p == ++i, this function is a null operation. 1094 //! 1095 //! <b>Throws</b>: Nothing 1096 //! 1097 //! <b>Complexity</b>: Constant. 1098 //! 1099 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this 1100 //! list. Iterators of this list and all the references are not invalidated. splice(const_iterator p,list & x,const_iterator i)1101 void splice(const_iterator p, list &x, const_iterator i) BOOST_NOEXCEPT_OR_NOTHROW 1102 { 1103 BOOST_ASSERT((priv_is_linked)(p)); 1104 BOOST_ASSERT(this->node_alloc() == x.node_alloc()); 1105 this->icont().splice(p.get(), x.icont(), i.get()); 1106 } 1107 1108 //! <b>Requires</b>: p must point to an element contained 1109 //! by this list. i must point to an element contained in list x. 1110 //! this' allocator and x's allocator shall compare equal. 1111 //! 1112 //! <b>Effects</b>: Transfers the value pointed by i, from list x to this list, 1113 //! before the element pointed by p. No destructors or copy constructors are called. 1114 //! If p == i or p == ++i, this function is a null operation. 1115 //! 1116 //! <b>Throws</b>: Nothing 1117 //! 1118 //! <b>Complexity</b>: Constant. 1119 //! 1120 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this 1121 //! list. Iterators of this list and all the references are not invalidated. splice(const_iterator p,BOOST_RV_REF (list)x,const_iterator i)1122 void splice(const_iterator p, BOOST_RV_REF(list) x, const_iterator i) BOOST_NOEXCEPT_OR_NOTHROW 1123 { 1124 BOOST_ASSERT(this != &x); 1125 //Additional checks done in splice() 1126 this->splice(p, static_cast<list&>(x), i); 1127 } 1128 1129 //! <b>Requires</b>: p must point to an element contained 1130 //! by this list. first and last must point to elements contained in list x. 1131 //! this' allocator and x's allocator shall compare equal 1132 //! 1133 //! <b>Effects</b>: Transfers the range pointed by first and last from list x to this list, 1134 //! before the element pointed by p. No destructors or copy constructors are called. 1135 //! 1136 //! <b>Throws</b>: Nothing 1137 //! 1138 //! <b>Complexity</b>: Linear to the number of elements transferred. 1139 //! 1140 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this 1141 //! list. Iterators of this list and all the references are not invalidated. splice(const_iterator p,list & x,const_iterator first,const_iterator last)1142 void splice(const_iterator p, list &x, const_iterator first, const_iterator last) BOOST_NOEXCEPT_OR_NOTHROW 1143 { 1144 BOOST_ASSERT((priv_is_linked)(p)); 1145 BOOST_ASSERT(first == last || (first != x.cend() && x.priv_is_linked(first))); 1146 BOOST_ASSERT(first == last || x.priv_is_linked(last)); 1147 BOOST_ASSERT(this->node_alloc() == x.node_alloc()); 1148 this->icont().splice(p.get(), x.icont(), first.get(), last.get()); 1149 } 1150 1151 //! <b>Requires</b>: p must point to an element contained 1152 //! by this list. first and last must point to elements contained in list x. 1153 //! this' allocator and x's allocator shall compare equal. 1154 //! 1155 //! <b>Effects</b>: Transfers the range pointed by first and last from list x to this list, 1156 //! before the element pointed by p. No destructors or copy constructors are called. 1157 //! 1158 //! <b>Throws</b>: Nothing 1159 //! 1160 //! <b>Complexity</b>: Linear to the number of elements transferred. 1161 //! 1162 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this 1163 //! list. Iterators of this list and all the references are not invalidated. splice(const_iterator p,BOOST_RV_REF (list)x,const_iterator first,const_iterator last)1164 void splice(const_iterator p, BOOST_RV_REF(list) x, const_iterator first, const_iterator last) BOOST_NOEXCEPT_OR_NOTHROW 1165 { 1166 BOOST_ASSERT(this != &x); 1167 //Additional checks done in splice() 1168 this->splice(p, static_cast<list&>(x), first, last); 1169 } 1170 1171 //! <b>Requires</b>: p must point to an element contained 1172 //! by this list. first and last must point to elements contained in list x. 1173 //! n == distance(first, last). this' allocator and x's allocator shall compare equal 1174 //! 1175 //! <b>Effects</b>: Transfers the range pointed by first and last from list x to this list, 1176 //! before the element pointed by p. No destructors or copy constructors are called. 1177 //! 1178 //! <b>Throws</b>: Nothing 1179 //! 1180 //! <b>Complexity</b>: Constant. 1181 //! 1182 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this 1183 //! list. Iterators of this list and all the references are not invalidated. 1184 //! 1185 //! <b>Note</b>: Non-standard extension splice(const_iterator p,list & x,const_iterator first,const_iterator last,size_type n)1186 void splice(const_iterator p, list &x, const_iterator first, const_iterator last, size_type n) BOOST_NOEXCEPT_OR_NOTHROW 1187 { 1188 BOOST_ASSERT(this->node_alloc() == x.node_alloc()); 1189 this->icont().splice(p.get(), x.icont(), first.get(), last.get(), n); 1190 } 1191 1192 //! <b>Requires</b>: p must point to an element contained 1193 //! by this list. first and last must point to elements contained in list x. 1194 //! n == distance(first, last). this' allocator and x's allocator shall compare equal 1195 //! 1196 //! <b>Effects</b>: Transfers the range pointed by first and last from list x to this list, 1197 //! before the element pointed by p. No destructors or copy constructors are called. 1198 //! 1199 //! <b>Throws</b>: Nothing 1200 //! 1201 //! <b>Complexity</b>: Constant. 1202 //! 1203 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this 1204 //! list. Iterators of this list and all the references are not invalidated. 1205 //! 1206 //! <b>Note</b>: Non-standard extension splice(const_iterator p,BOOST_RV_REF (list)x,const_iterator first,const_iterator last,size_type n)1207 void splice(const_iterator p, BOOST_RV_REF(list) x, const_iterator first, const_iterator last, size_type n) BOOST_NOEXCEPT_OR_NOTHROW 1208 { this->splice(p, static_cast<list&>(x), first, last, n); } 1209 1210 //! <b>Effects</b>: Removes all the elements that compare equal to value. 1211 //! 1212 //! <b>Throws</b>: If comparison throws. 1213 //! 1214 //! <b>Complexity</b>: Linear time. It performs exactly size() comparisons for equality. 1215 //! 1216 //! <b>Note</b>: The relative order of elements that are not removed is unchanged, 1217 //! and iterators to elements that are not removed remain valid. remove(const T & value)1218 void remove(const T& value) 1219 { this->remove_if(equal_to_value_type(value)); } 1220 1221 //! <b>Effects</b>: Removes all the elements for which a specified 1222 //! predicate is satisfied. 1223 //! 1224 //! <b>Throws</b>: If pred throws. 1225 //! 1226 //! <b>Complexity</b>: Linear time. It performs exactly size() calls to the predicate. 1227 //! 1228 //! <b>Note</b>: The relative order of elements that are not removed is unchanged, 1229 //! and iterators to elements that are not removed remain valid. 1230 template <class Pred> remove_if(Pred pred)1231 void remove_if(Pred pred) 1232 { 1233 typedef value_to_node_compare<Node, Pred> value_to_node_compare_type; 1234 this->icont().remove_and_dispose_if(value_to_node_compare_type(pred), Destroyer(this->node_alloc())); 1235 } 1236 1237 //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent 1238 //! elements that are equal from the list. 1239 //! 1240 //! <b>Throws</b>: If comparison throws. 1241 //! 1242 //! <b>Complexity</b>: Linear time (size()-1 comparisons equality comparisons). 1243 //! 1244 //! <b>Note</b>: The relative order of elements that are not removed is unchanged, 1245 //! and iterators to elements that are not removed remain valid. unique()1246 void unique() 1247 { this->unique(value_equal_t()); } 1248 1249 //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent 1250 //! elements that satisfy some binary predicate from the list. 1251 //! 1252 //! <b>Throws</b>: If pred throws. 1253 //! 1254 //! <b>Complexity</b>: Linear time (size()-1 comparisons calls to pred()). 1255 //! 1256 //! <b>Note</b>: The relative order of elements that are not removed is unchanged, 1257 //! and iterators to elements that are not removed remain valid. 1258 template <class BinaryPredicate> unique(BinaryPredicate binary_pred)1259 void unique(BinaryPredicate binary_pred) 1260 { 1261 typedef value_to_node_compare<Node, BinaryPredicate> value_to_node_compare_type; 1262 this->icont().unique_and_dispose(value_to_node_compare_type(binary_pred), Destroyer(this->node_alloc())); 1263 } 1264 1265 //! <b>Requires</b>: The lists x and *this must be distinct. 1266 //! 1267 //! <b>Effects</b>: This function removes all of x's elements and inserts them 1268 //! in order into *this according to std::less<value_type>. The merge is stable; 1269 //! that is, if an element from *this is equivalent to one from x, then the element 1270 //! from *this will precede the one from x. 1271 //! 1272 //! <b>Throws</b>: If comparison throws. 1273 //! 1274 //! <b>Complexity</b>: This function is linear time: it performs at most 1275 //! size() + x.size() - 1 comparisons. merge(list & x)1276 void merge(list &x) 1277 { this->merge(x, value_less_t()); } 1278 1279 //! <b>Requires</b>: The lists x and *this must be distinct. 1280 //! 1281 //! <b>Effects</b>: This function removes all of x's elements and inserts them 1282 //! in order into *this according to std::less<value_type>. The merge is stable; 1283 //! that is, if an element from *this is equivalent to one from x, then the element 1284 //! from *this will precede the one from x. 1285 //! 1286 //! <b>Throws</b>: If comparison throws. 1287 //! 1288 //! <b>Complexity</b>: This function is linear time: it performs at most 1289 //! size() + x.size() - 1 comparisons. merge(BOOST_RV_REF (list)x)1290 void merge(BOOST_RV_REF(list) x) 1291 { this->merge(static_cast<list&>(x)); } 1292 1293 //! <b>Requires</b>: p must be a comparison function that induces a strict weak 1294 //! ordering and both *this and x must be sorted according to that ordering 1295 //! The lists x and *this must be distinct. 1296 //! 1297 //! <b>Effects</b>: This function removes all of x's elements and inserts them 1298 //! in order into *this. The merge is stable; that is, if an element from *this is 1299 //! equivalent to one from x, then the element from *this will precede the one from x. 1300 //! 1301 //! <b>Throws</b>: If comp throws. 1302 //! 1303 //! <b>Complexity</b>: This function is linear time: it performs at most 1304 //! size() + x.size() - 1 comparisons. 1305 //! 1306 //! <b>Note</b>: Iterators and references to *this are not invalidated. 1307 template <class StrictWeakOrdering> merge(list & x,const StrictWeakOrdering & comp)1308 void merge(list &x, const StrictWeakOrdering &comp) 1309 { 1310 BOOST_ASSERT(this->node_alloc() == x.node_alloc()); 1311 typedef value_to_node_compare<Node, StrictWeakOrdering> value_to_node_compare_type; 1312 this->icont().merge(x.icont(), value_to_node_compare_type(comp)); 1313 } 1314 1315 //! <b>Requires</b>: p must be a comparison function that induces a strict weak 1316 //! ordering and both *this and x must be sorted according to that ordering 1317 //! The lists x and *this must be distinct. 1318 //! 1319 //! <b>Effects</b>: This function removes all of x's elements and inserts them 1320 //! in order into *this. The merge is stable; that is, if an element from *this is 1321 //! equivalent to one from x, then the element from *this will precede the one from x. 1322 //! 1323 //! <b>Throws</b>: If comp throws. 1324 //! 1325 //! <b>Complexity</b>: This function is linear time: it performs at most 1326 //! size() + x.size() - 1 comparisons. 1327 //! 1328 //! <b>Note</b>: Iterators and references to *this are not invalidated. 1329 template <class StrictWeakOrdering> merge(BOOST_RV_REF (list)x,StrictWeakOrdering comp)1330 void merge(BOOST_RV_REF(list) x, StrictWeakOrdering comp) 1331 { this->merge(static_cast<list&>(x), comp); } 1332 1333 //! <b>Effects</b>: This function sorts the list *this according to std::less<value_type>. 1334 //! The sort is stable, that is, the relative order of equivalent elements is preserved. 1335 //! 1336 //! <b>Throws</b>: If comparison throws. 1337 //! 1338 //! <b>Notes</b>: Iterators and references are not invalidated. 1339 //! 1340 //! <b>Complexity</b>: The number of comparisons is approximately N log N, where N 1341 //! is the list's size. sort()1342 void sort() 1343 { this->sort(value_less_t()); } 1344 1345 //! <b>Effects</b>: This function sorts the list *this according to std::less<value_type>. 1346 //! The sort is stable, that is, the relative order of equivalent elements is preserved. 1347 //! 1348 //! <b>Throws</b>: If comp throws. 1349 //! 1350 //! <b>Notes</b>: Iterators and references are not invalidated. 1351 //! 1352 //! <b>Complexity</b>: The number of comparisons is approximately N log N, where N 1353 //! is the list's size. 1354 template <class StrictWeakOrdering> sort(StrictWeakOrdering comp)1355 void sort(StrictWeakOrdering comp) 1356 { 1357 // nothing if the list has length 0 or 1. 1358 if (this->size() < 2) 1359 return; 1360 typedef value_to_node_compare<Node, StrictWeakOrdering> value_to_node_compare_type; 1361 this->icont().sort(value_to_node_compare_type(comp)); 1362 } 1363 1364 //! <b>Effects</b>: Reverses the order of elements in the list. 1365 //! 1366 //! <b>Throws</b>: Nothing. 1367 //! 1368 //! <b>Complexity</b>: This function is linear time. 1369 //! 1370 //! <b>Note</b>: Iterators and references are not invalidated reverse()1371 void reverse() BOOST_NOEXCEPT_OR_NOTHROW 1372 { this->icont().reverse(); } 1373 1374 //! <b>Effects</b>: Returns true if x and y are equal 1375 //! 1376 //! <b>Complexity</b>: Linear to the number of elements in the container. operator ==(const list & x,const list & y)1377 friend bool operator==(const list& x, const list& y) 1378 { return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin()); } 1379 1380 //! <b>Effects</b>: Returns true if x and y are unequal 1381 //! 1382 //! <b>Complexity</b>: Linear to the number of elements in the container. operator !=(const list & x,const list & y)1383 friend bool operator!=(const list& x, const list& y) 1384 { return !(x == y); } 1385 1386 //! <b>Effects</b>: Returns true if x is less than y 1387 //! 1388 //! <b>Complexity</b>: Linear to the number of elements in the container. operator <(const list & x,const list & y)1389 friend bool operator<(const list& x, const list& y) 1390 { return boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); } 1391 1392 //! <b>Effects</b>: Returns true if x is greater than y 1393 //! 1394 //! <b>Complexity</b>: Linear to the number of elements in the container. operator >(const list & x,const list & y)1395 friend bool operator>(const list& x, const list& y) 1396 { return y < x; } 1397 1398 //! <b>Effects</b>: Returns true if x is equal or less than y 1399 //! 1400 //! <b>Complexity</b>: Linear to the number of elements in the container. operator <=(const list & x,const list & y)1401 friend bool operator<=(const list& x, const list& y) 1402 { return !(y < x); } 1403 1404 //! <b>Effects</b>: Returns true if x is equal or greater than y 1405 //! 1406 //! <b>Complexity</b>: Linear to the number of elements in the container. operator >=(const list & x,const list & y)1407 friend bool operator>=(const list& x, const list& y) 1408 { return !(x < y); } 1409 1410 //! <b>Effects</b>: x.swap(y) 1411 //! 1412 //! <b>Complexity</b>: Constant. swap(list & x,list & y)1413 friend void swap(list& x, list& y) 1414 { x.swap(y); } 1415 1416 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 1417 private: 1418 priv_is_linked(const_iterator const position)1419 static bool priv_is_linked(const_iterator const position) 1420 { 1421 const_iterator cur(position); 1422 //This list is circular including end nodes 1423 return (--(++cur)) == position && (++(--cur)) == position; 1424 } 1425 priv_try_shrink(size_type new_size)1426 bool priv_try_shrink(size_type new_size) 1427 { 1428 const size_type len = this->size(); 1429 if(len > new_size){ 1430 const const_iterator iend = this->cend(); 1431 size_type to_erase = len - new_size; 1432 const_iterator ifirst; 1433 if(to_erase < len/2u){ 1434 ifirst = iend; 1435 while(to_erase--){ 1436 --ifirst; 1437 } 1438 } 1439 else{ 1440 ifirst = this->cbegin(); 1441 size_type to_skip = len - to_erase; 1442 while(to_skip--){ 1443 ++ifirst; 1444 } 1445 } 1446 this->erase(ifirst, iend); 1447 return true; 1448 } 1449 else{ 1450 return false; 1451 } 1452 } 1453 priv_insert(const_iterator p,const T & x)1454 iterator priv_insert(const_iterator p, const T &x) 1455 { 1456 BOOST_ASSERT((priv_is_linked)(p)); 1457 NodePtr tmp = AllocHolder::create_node(x); 1458 return iterator(this->icont().insert(p.get(), *tmp)); 1459 } 1460 priv_insert(const_iterator p,BOOST_RV_REF (T)x)1461 iterator priv_insert(const_iterator p, BOOST_RV_REF(T) x) 1462 { 1463 BOOST_ASSERT((priv_is_linked)(p)); 1464 NodePtr tmp = AllocHolder::create_node(boost::move(x)); 1465 return iterator(this->icont().insert(p.get(), *tmp)); 1466 } 1467 priv_push_back(const T & x)1468 void priv_push_back (const T &x) 1469 { this->insert(this->cend(), x); } 1470 priv_push_back(BOOST_RV_REF (T)x)1471 void priv_push_back (BOOST_RV_REF(T) x) 1472 { this->insert(this->cend(), boost::move(x)); } 1473 priv_push_front(const T & x)1474 void priv_push_front (const T &x) 1475 { this->insert(this->cbegin(), x); } 1476 priv_push_front(BOOST_RV_REF (T)x)1477 void priv_push_front (BOOST_RV_REF(T) x) 1478 { this->insert(this->cbegin(), boost::move(x)); } 1479 1480 class insertion_functor; 1481 friend class insertion_functor; 1482 1483 class insertion_functor 1484 { 1485 Icont &icont_; 1486 typedef typename Icont::const_iterator iconst_iterator; 1487 const iconst_iterator pos_; 1488 1489 public: insertion_functor(Icont & icont,typename Icont::const_iterator pos)1490 insertion_functor(Icont &icont, typename Icont::const_iterator pos) 1491 : icont_(icont), pos_(pos) 1492 {} 1493 operator ()(Node & n)1494 void operator()(Node &n) 1495 { 1496 this->icont_.insert(pos_, n); 1497 } 1498 }; 1499 1500 typedef value_less<value_type> value_less_t; 1501 typedef value_equal<value_type> value_equal_t; 1502 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 1503 1504 }; 1505 1506 #ifndef BOOST_CONTAINER_NO_CXX17_CTAD 1507 template <typename InputIterator> 1508 list(InputIterator, InputIterator) -> 1509 list<typename iterator_traits<InputIterator>::value_type>; 1510 1511 template <typename InputIterator, typename ValueAllocator> 1512 list(InputIterator, InputIterator, ValueAllocator const&) -> 1513 list<typename iterator_traits<InputIterator>::value_type, ValueAllocator>; 1514 #endif 1515 1516 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 1517 1518 } //namespace container { 1519 1520 //!has_trivial_destructor_after_move<> == true_type 1521 //!specialization for optimizations 1522 template <class T, class Allocator> 1523 struct has_trivial_destructor_after_move<boost::container::list<T, Allocator> > 1524 { 1525 typedef typename boost::container::list<T, Allocator>::allocator_type allocator_type; 1526 typedef typename ::boost::container::allocator_traits<allocator_type>::pointer pointer; 1527 static const bool value = ::boost::has_trivial_destructor_after_move<allocator_type>::value && 1528 ::boost::has_trivial_destructor_after_move<pointer>::value; 1529 }; 1530 1531 namespace container { 1532 1533 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 1534 1535 }} 1536 1537 #include <boost/container/detail/config_end.hpp> 1538 1539 #endif // BOOST_CONTAINER_LIST_HPP 1540