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