1 ////////////////////////////////////////////////////////////////////////////// 2 // 3 // (C) Copyright Ion Gaztanaga 2004-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 11 #ifndef BOOST_CONTAINER_SLIST_HPP 12 #define BOOST_CONTAINER_SLIST_HPP 13 14 #ifndef BOOST_CONFIG_HPP 15 # include <boost/config.hpp> 16 #endif 17 18 #if defined(BOOST_HAS_PRAGMA_ONCE) 19 # pragma once 20 #endif 21 22 #include <boost/container/detail/config_begin.hpp> 23 #include <boost/container/detail/workaround.hpp> 24 25 // container 26 #include <boost/container/container_fwd.hpp> 27 #include <boost/container/new_allocator.hpp> //new_allocator 28 #include <boost/container/throw_exception.hpp> 29 // container/detail 30 #include <boost/container/detail/algorithm.hpp> //algo_equal(), algo_lexicographical_compare 31 #include <boost/container/detail/compare_functors.hpp> 32 #include <boost/container/detail/iterator.hpp> 33 #include <boost/container/detail/iterators.hpp> 34 #include <boost/container/detail/mpl.hpp> 35 #include <boost/container/detail/node_alloc_holder.hpp> 36 #include <boost/container/detail/type_traits.hpp> 37 #include <boost/container/detail/value_functors.hpp> 38 // intrusive 39 #include <boost/intrusive/pointer_traits.hpp> 40 #include <boost/intrusive/slist.hpp> 41 // move 42 #include <boost/move/iterator.hpp> 43 #include <boost/move/traits.hpp> 44 #include <boost/move/utility_core.hpp> 45 // move/detail 46 #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 47 #include <boost/move/detail/fwd_macros.hpp> 48 #endif 49 #include <boost/move/detail/move_helpers.hpp> 50 // other 51 #include <boost/core/no_exceptions_support.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 62 template <class T, class Allocator> 63 class slist; 64 65 namespace dtl { 66 67 template<class VoidPointer> 68 struct slist_hook 69 { 70 typedef typename dtl::bi::make_slist_base_hook 71 <dtl::bi::void_pointer<VoidPointer>, dtl::bi::link_mode<dtl::bi::normal_link> >::type type; 72 }; 73 74 75 template <class T, class VoidPointer> 76 struct slist_node 77 : public slist_hook<VoidPointer>::type 78 { 79 public: 80 typedef T value_type; 81 typedef T internal_type; 82 typedef typename slist_hook<VoidPointer>::type hook_type; 83 84 typedef typename aligned_storage<sizeof(T), alignment_of<T>::value>::type storage_t; 85 storage_t m_storage; 86 87 #if defined(BOOST_GCC) && (BOOST_GCC >= 40600) && (BOOST_GCC < 80000) 88 #pragma GCC diagnostic push 89 #pragma GCC diagnostic ignored "-Wstrict-aliasing" 90 #define BOOST_CONTAINER_DISABLE_ALIASING_WARNING 91 # endif 92 get_databoost::container::dtl::slist_node93 BOOST_CONTAINER_FORCEINLINE T &get_data() 94 { return *reinterpret_cast<T*>(this->m_storage.data); } 95 get_databoost::container::dtl::slist_node96 BOOST_CONTAINER_FORCEINLINE const T &get_data() const 97 { return *reinterpret_cast<const T*>(this->m_storage.data); } 98 get_data_ptrboost::container::dtl::slist_node99 BOOST_CONTAINER_FORCEINLINE T *get_data_ptr() 100 { return reinterpret_cast<T*>(this->m_storage.data); } 101 get_data_ptrboost::container::dtl::slist_node102 BOOST_CONTAINER_FORCEINLINE const T *get_data_ptr() const 103 { return reinterpret_cast<T*>(this->m_storage.data); } 104 get_real_databoost::container::dtl::slist_node105 BOOST_CONTAINER_FORCEINLINE internal_type &get_real_data() 106 { return *reinterpret_cast<internal_type*>(this->m_storage.data); } 107 get_real_databoost::container::dtl::slist_node108 BOOST_CONTAINER_FORCEINLINE const internal_type &get_real_data() const 109 { return *reinterpret_cast<const internal_type*>(this->m_storage.data); } 110 get_real_data_ptrboost::container::dtl::slist_node111 BOOST_CONTAINER_FORCEINLINE internal_type *get_real_data_ptr() 112 { return reinterpret_cast<internal_type*>(this->m_storage.data); } 113 get_real_data_ptrboost::container::dtl::slist_node114 BOOST_CONTAINER_FORCEINLINE const internal_type *get_real_data_ptr() const 115 { return reinterpret_cast<internal_type*>(this->m_storage.data); } 116 ~slist_nodeboost::container::dtl::slist_node117 BOOST_CONTAINER_FORCEINLINE ~slist_node() 118 { reinterpret_cast<T*>(this->m_storage.data)->~T(); } 119 120 #if defined(BOOST_CONTAINER_DISABLE_ALIASING_WARNING) 121 #pragma GCC diagnostic pop 122 #undef BOOST_CONTAINER_DISABLE_ALIASING_WARNING 123 # endif 124 destroy_headerboost::container::dtl::slist_node125 BOOST_CONTAINER_FORCEINLINE void destroy_header() 126 { static_cast<hook_type*>(this)->~hook_type(); } 127 }; 128 129 130 template <class T, class VoidPointer> 131 struct iiterator_node_value_type< slist_node<T,VoidPointer> > { 132 typedef T type; 133 }; 134 135 template<class Allocator> 136 struct intrusive_slist_type 137 { 138 typedef boost::container::allocator_traits<Allocator> allocator_traits_type; 139 typedef typename allocator_traits_type::value_type value_type; 140 typedef typename boost::intrusive::pointer_traits 141 <typename allocator_traits_type::pointer>::template 142 rebind_pointer<void>::type 143 void_pointer; 144 typedef typename dtl::slist_node 145 <value_type, void_pointer> node_type; 146 147 typedef typename dtl::bi::make_slist 148 <node_type 149 ,dtl::bi::base_hook<typename slist_hook<void_pointer>::type> 150 ,dtl::bi::constant_time_size<true> 151 , dtl::bi::size_type 152 <typename allocator_traits_type::size_type> 153 >::type container_type; 154 typedef container_type type ; 155 }; 156 157 } //namespace dtl { 158 159 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 160 161 //! An slist is a singly linked list: a list where each element is linked to the next 162 //! element, but not to the previous element. That is, it is a Sequence that 163 //! supports forward but not backward traversal, and (amortized) constant time 164 //! insertion and removal of elements. Slists, like lists, have the important 165 //! property that insertion and splicing do not invalidate iterators to list elements, 166 //! and that even removal invalidates only the iterators that point to the elements 167 //! that are removed. The ordering of iterators may be changed (that is, 168 //! slist<T>::iterator might have a different predecessor or successor after a list 169 //! operation than it did before), but the iterators themselves will not be invalidated 170 //! or made to point to different elements unless that invalidation or mutation is explicit. 171 //! 172 //! The main difference between slist and list is that list's iterators are bidirectional 173 //! iterators, while slist's iterators are forward iterators. This means that slist is 174 //! less versatile than list; frequently, however, bidirectional iterators are 175 //! unnecessary. You should usually use slist unless you actually need the extra 176 //! functionality of list, because singly linked lists are smaller and faster than double 177 //! linked lists. 178 //! 179 //! Important performance note: like every other Sequence, slist defines the member 180 //! functions insert and erase. Using these member functions carelessly, however, can 181 //! result in disastrously slow programs. The problem is that insert's first argument is 182 //! an iterator p, and that it inserts the new element(s) before p. This means that 183 //! insert must find the iterator just before p; this is a constant-time operation 184 //! for list, since list has bidirectional iterators, but for slist it must find that 185 //! iterator by traversing the list from the beginning up to p. In other words: 186 //! insert and erase are slow operations anywhere but near the beginning of the slist. 187 //! 188 //! Slist provides the member functions insert_after and erase_after, which are constant 189 //! time operations: you should always use insert_after and erase_after whenever 190 //! possible. If you find that insert_after and erase_after aren't adequate for your 191 //! needs, and that you often need to use insert and erase in the middle of the list, 192 //! then you should probably use list instead of slist. 193 //! 194 //! \tparam T The type of object that is stored in the list 195 //! \tparam Allocator The allocator used for all internal memory management, use void 196 //! for the default allocator 197 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED 198 template <class T, class Allocator = void > 199 #else 200 template <class T, class Allocator> 201 #endif 202 class slist 203 : protected dtl::node_alloc_holder 204 < typename real_allocator<T, Allocator>::type 205 , typename dtl::intrusive_slist_type<typename real_allocator<T, Allocator>::type>::type> 206 { 207 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 208 typedef typename real_allocator<T, Allocator>::type ValueAllocator; 209 typedef typename 210 dtl::intrusive_slist_type<ValueAllocator>::type Icont; 211 typedef dtl::node_alloc_holder<ValueAllocator, Icont> AllocHolder; 212 typedef typename AllocHolder::NodePtr NodePtr; 213 typedef typename AllocHolder::NodeAlloc NodeAlloc; 214 typedef typename AllocHolder::ValAlloc ValAlloc; 215 typedef typename AllocHolder::Node Node; 216 typedef dtl::allocator_destroyer<NodeAlloc> Destroyer; 217 typedef typename AllocHolder::alloc_version alloc_version; 218 typedef boost::container:: 219 allocator_traits<ValueAllocator> allocator_traits_type; 220 typedef boost::container::equal_to_value 221 <typename allocator_traits_type::value_type> equal_to_value_type; 222 223 BOOST_COPYABLE_AND_MOVABLE(slist) 224 typedef dtl::iterator_from_iiterator<typename Icont::iterator, false> iterator_impl; 225 typedef dtl::iterator_from_iiterator<typename Icont::iterator, true > const_iterator_impl; 226 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 227 228 public: 229 ////////////////////////////////////////////// 230 // 231 // types 232 // 233 ////////////////////////////////////////////// 234 235 typedef T value_type; 236 typedef typename ::boost::container::allocator_traits<ValueAllocator>::pointer pointer; 237 typedef typename ::boost::container::allocator_traits<ValueAllocator>::const_pointer const_pointer; 238 typedef typename ::boost::container::allocator_traits<ValueAllocator>::reference reference; 239 typedef typename ::boost::container::allocator_traits<ValueAllocator>::const_reference const_reference; 240 typedef typename ::boost::container::allocator_traits<ValueAllocator>::size_type size_type; 241 typedef typename ::boost::container::allocator_traits<ValueAllocator>::difference_type difference_type; 242 typedef ValueAllocator allocator_type; 243 typedef BOOST_CONTAINER_IMPDEF(NodeAlloc) stored_allocator_type; 244 typedef BOOST_CONTAINER_IMPDEF(iterator_impl) iterator; 245 typedef BOOST_CONTAINER_IMPDEF(const_iterator_impl) const_iterator; 246 247 public: 248 249 ////////////////////////////////////////////// 250 // 251 // construct/copy/destroy 252 // 253 ////////////////////////////////////////////// 254 255 //! <b>Effects</b>: Constructs a list taking the allocator as parameter. 256 //! 257 //! <b>Throws</b>: If allocator_type's copy constructor throws. 258 //! 259 //! <b>Complexity</b>: Constant. BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<ValueAllocator>::value)260 slist() BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<ValueAllocator>::value) 261 : AllocHolder() 262 {} 263 264 //! <b>Effects</b>: Constructs a list taking the allocator as parameter. 265 //! 266 //! <b>Throws</b>: Nothing 267 //! 268 //! <b>Complexity</b>: Constant. slist(const allocator_type & a)269 explicit slist(const allocator_type& a) BOOST_NOEXCEPT_OR_NOTHROW 270 : AllocHolder(a) 271 {} 272 273 //! <b>Effects</b>: Constructs a list 274 //! and inserts n value-initialized value_types. 275 //! 276 //! <b>Throws</b>: If allocator_type's default constructor 277 //! throws or T's default or copy constructor throws. 278 //! 279 //! <b>Complexity</b>: Linear to n. slist(size_type n)280 explicit slist(size_type n) 281 : AllocHolder(allocator_type()) 282 { this->resize(n); } 283 284 //! <b>Effects</b>: Constructs a list that will use a copy of allocator a 285 //! and inserts n copies of value. 286 //! 287 //! <b>Throws</b>: If allocator_type's default constructor 288 //! throws or T's default or copy constructor throws. 289 //! 290 //! <b>Complexity</b>: Linear to n. slist(size_type n,const allocator_type & a)291 slist(size_type n, const allocator_type &a) 292 : AllocHolder(a) 293 { this->resize(n); } 294 295 //! <b>Effects</b>: Constructs a list that will use a copy of allocator a 296 //! and inserts n copies of value. 297 //! 298 //! <b>Throws</b>: If allocator_type's default constructor 299 //! throws or T's default or copy constructor throws. 300 //! 301 //! <b>Complexity</b>: Linear to n. slist(size_type n,const value_type & x,const allocator_type & a=allocator_type ())302 explicit slist(size_type n, const value_type& x, const allocator_type& a = allocator_type()) 303 : AllocHolder(a) 304 { this->insert_after(this->cbefore_begin(), n, x); } 305 306 //! <b>Effects</b>: Constructs a list that will use a copy of allocator a 307 //! and inserts a copy of the range [first, last) in the list. 308 //! 309 //! <b>Throws</b>: If allocator_type's default constructor 310 //! throws or T's constructor taking a dereferenced InIt throws. 311 //! 312 //! <b>Complexity</b>: Linear to the range [first, last). 313 template <class InpIt> slist(InpIt first,InpIt last,const allocator_type & a=allocator_type ())314 slist(InpIt first, InpIt last, const allocator_type& a = allocator_type()) 315 : AllocHolder(a) 316 { this->insert_after(this->cbefore_begin(), first, last); } 317 318 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 319 //! <b>Effects</b>: Constructs a list that will use a copy of allocator a 320 //! and inserts a copy of the range [il.begin(), il.end()) in the list. 321 //! 322 //! <b>Throws</b>: If allocator_type's default constructor 323 //! throws or T's constructor taking a dereferenced std::initializer_list iterator throws. 324 //! 325 //! <b>Complexity</b>: Linear to the range [il.begin(), il.end()). slist(std::initializer_list<value_type> il,const allocator_type & a=allocator_type ())326 slist(std::initializer_list<value_type> il, const allocator_type& a = allocator_type()) 327 : AllocHolder(a) 328 { this->insert_after(this->cbefore_begin(), il.begin(), il.end()); } 329 #endif 330 331 //! <b>Effects</b>: Copy constructs a list. 332 //! 333 //! <b>Postcondition</b>: x == *this. 334 //! 335 //! <b>Throws</b>: If allocator_type's default constructor 336 //! 337 //! <b>Complexity</b>: Linear to the elements x contains. slist(const slist & x)338 slist(const slist& x) 339 : AllocHolder(x) 340 { this->insert_after(this->cbefore_begin(), x.begin(), x.end()); } 341 342 //! <b>Effects</b>: Move constructor. Moves x's resources to *this. 343 //! 344 //! <b>Throws</b>: If allocator_type's copy constructor throws. 345 //! 346 //! <b>Complexity</b>: Constant. slist(BOOST_RV_REF (slist)x)347 slist(BOOST_RV_REF(slist) x) BOOST_NOEXCEPT_OR_NOTHROW 348 : AllocHolder(BOOST_MOVE_BASE(AllocHolder, x)) 349 {} 350 351 //! <b>Effects</b>: Copy constructs a list using the specified allocator. 352 //! 353 //! <b>Postcondition</b>: x == *this. 354 //! 355 //! <b>Throws</b>: If allocator_type's default constructor 356 //! 357 //! <b>Complexity</b>: Linear to the elements x contains. slist(const slist & x,const allocator_type & a)358 slist(const slist& x, const allocator_type &a) 359 : AllocHolder(a) 360 { this->insert_after(this->cbefore_begin(), x.begin(), x.end()); } 361 362 //! <b>Effects</b>: Move constructor using the specified allocator. 363 //! Moves x's resources to *this. 364 //! 365 //! <b>Throws</b>: If allocation or value_type's copy constructor throws. 366 //! 367 //! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise. slist(BOOST_RV_REF (slist)x,const allocator_type & a)368 slist(BOOST_RV_REF(slist) x, const allocator_type &a) 369 : AllocHolder(a) 370 { 371 if(this->node_alloc() == x.node_alloc()){ 372 this->icont().swap(x.icont()); 373 } 374 else{ 375 this->insert_after(this->cbefore_begin(), boost::make_move_iterator(x.begin()), boost::make_move_iterator(x.end())); 376 } 377 } 378 379 //! <b>Effects</b>: Destroys the list. All stored values are destroyed 380 //! and used memory is deallocated. 381 //! 382 //! <b>Throws</b>: Nothing. 383 //! 384 //! <b>Complexity</b>: Linear to the number of elements. ~slist()385 ~slist() BOOST_NOEXCEPT_OR_NOTHROW 386 {} //AllocHolder clears the slist 387 388 //! <b>Effects</b>: Makes *this contain the same elements as x. 389 //! 390 //! <b>Postcondition</b>: this->size() == x.size(). *this contains a copy 391 //! of each of x's elements. 392 //! 393 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws. 394 //! 395 //! <b>Complexity</b>: Linear to the number of elements in x. operator =(BOOST_COPY_ASSIGN_REF (slist)x)396 slist& operator= (BOOST_COPY_ASSIGN_REF(slist) x) 397 { 398 if (&x != this){ 399 NodeAlloc &this_alloc = this->node_alloc(); 400 const NodeAlloc &x_alloc = x.node_alloc(); 401 dtl::bool_<allocator_traits_type:: 402 propagate_on_container_copy_assignment::value> flag; 403 if(flag && this_alloc != x_alloc){ 404 this->clear(); 405 } 406 this->AllocHolder::copy_assign_alloc(x); 407 this->assign(x.begin(), x.end()); 408 } 409 return *this; 410 } 411 412 //! <b>Effects</b>: Makes *this contain the same elements as x. 413 //! 414 //! <b>Postcondition</b>: this->size() == x.size(). *this contains a copy 415 //! of each of x's elements. 416 //! 417 //! <b>Throws</b>: If allocator_traits_type::propagate_on_container_move_assignment 418 //! is false and (allocation throws or value_type's move constructor throws) 419 //! 420 //! <b>Complexity</b>: Constant if allocator_traits_type:: 421 //! propagate_on_container_move_assignment is true or 422 //! this->get>allocator() == x.get_allocator(). Linear otherwise. operator =(BOOST_RV_REF (slist)x)423 slist& operator=(BOOST_RV_REF(slist) x) 424 BOOST_NOEXCEPT_IF(allocator_traits_type::propagate_on_container_move_assignment::value 425 || allocator_traits_type::is_always_equal::value) 426 { 427 BOOST_ASSERT(this != &x); 428 NodeAlloc &this_alloc = this->node_alloc(); 429 NodeAlloc &x_alloc = x.node_alloc(); 430 const bool propagate_alloc = allocator_traits_type:: 431 propagate_on_container_move_assignment::value; 432 const bool allocators_equal = this_alloc == x_alloc; (void)allocators_equal; 433 //Resources can be transferred if both allocators are 434 //going to be equal after this function (either propagated or already equal) 435 if(propagate_alloc || allocators_equal){ 436 //Destroy 437 this->clear(); 438 //Move allocator if needed 439 this->AllocHolder::move_assign_alloc(x); 440 //Obtain resources 441 this->icont() = boost::move(x.icont()); 442 } 443 //Else do a one by one move 444 else{ 445 this->assign( boost::make_move_iterator(x.begin()) 446 , boost::make_move_iterator(x.end())); 447 } 448 return *this; 449 } 450 451 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 452 //! <b>Effects</b>: Makes *this contain the same elements as in il. 453 //! 454 //! <b>Postcondition</b>: this->size() == il.size(). *this contains a copy 455 //! of each of il's elements. 456 //! 457 //! <b>Throws</b>: If allocator_traits_type::propagate_on_container_move_assignment 458 //! is false and (allocation throws or value_type's move constructor throws) operator =(std::initializer_list<value_type> il)459 slist& operator=(std::initializer_list<value_type> il) 460 { 461 assign(il.begin(), il.end()); 462 return *this; 463 } 464 #endif 465 466 //! <b>Effects</b>: Assigns the n copies of val to *this. 467 //! 468 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws. 469 //! 470 //! <b>Complexity</b>: Linear to n. assign(size_type n,const T & val)471 void assign(size_type n, const T& val) 472 { 473 typedef constant_iterator<value_type, difference_type> cvalue_iterator; 474 return this->assign(cvalue_iterator(val, n), cvalue_iterator()); 475 } 476 477 //! <b>Effects</b>: Assigns the range [first, last) to *this. 478 //! 479 //! <b>Throws</b>: If memory allocation throws or 480 //! T's constructor from dereferencing InpIt throws. 481 //! 482 //! <b>Complexity</b>: Linear to n. 483 template <class InpIt> assign(InpIt first,InpIt last,typename dtl::disable_if_convertible<InpIt,size_type>::type * =0)484 void assign(InpIt first, InpIt last 485 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 486 , typename dtl::disable_if_convertible<InpIt, size_type>::type * = 0 487 #endif 488 ) 489 { 490 iterator end_n(this->end()); 491 iterator prev(this->before_begin()); 492 iterator node(this->begin()); 493 while (node != end_n && first != last){ 494 *node = *first; 495 prev = node; 496 ++node; 497 ++first; 498 } 499 if (first != last) 500 this->insert_after(prev, first, last); 501 else 502 this->erase_after(prev, end_n); 503 } 504 505 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 506 //! <b>Effects</b>: Assigns the range [il.begin(), il.end()) to *this. 507 //! 508 //! <b>Throws</b>: If memory allocation throws or 509 //! T's constructor from dereferencing std::initializer_list iterator throws. 510 //! 511 //! <b>Complexity</b>: Linear to range [il.begin(), il.end()). 512 assign(std::initializer_list<value_type> il)513 void assign(std::initializer_list<value_type> il) 514 { 515 assign(il.begin(), il.end()); 516 } 517 #endif 518 //! <b>Effects</b>: Returns a copy of the internal allocator. 519 //! 520 //! <b>Throws</b>: If allocator's copy constructor throws. 521 //! 522 //! <b>Complexity</b>: Constant. get_allocator() const523 allocator_type get_allocator() const BOOST_NOEXCEPT_OR_NOTHROW 524 { return allocator_type(this->node_alloc()); } 525 526 //! <b>Effects</b>: Returns a reference to the internal allocator. 527 //! 528 //! <b>Throws</b>: Nothing 529 //! 530 //! <b>Complexity</b>: Constant. 531 //! 532 //! <b>Note</b>: Non-standard extension. get_stored_allocator()533 stored_allocator_type &get_stored_allocator() BOOST_NOEXCEPT_OR_NOTHROW 534 { return this->node_alloc(); } 535 536 //! <b>Effects</b>: Returns a reference to the internal allocator. 537 //! 538 //! <b>Throws</b>: Nothing 539 //! 540 //! <b>Complexity</b>: Constant. 541 //! 542 //! <b>Note</b>: Non-standard extension. get_stored_allocator() const543 const stored_allocator_type &get_stored_allocator() const BOOST_NOEXCEPT_OR_NOTHROW 544 { return this->node_alloc(); } 545 546 ////////////////////////////////////////////// 547 // 548 // iterators 549 // 550 ////////////////////////////////////////////// 551 552 //! <b>Effects</b>: Returns a non-dereferenceable iterator that, 553 //! when incremented, yields begin(). This iterator may be used 554 //! as the argument to insert_after, erase_after, etc. 555 //! 556 //! <b>Throws</b>: Nothing. 557 //! 558 //! <b>Complexity</b>: Constant. before_begin()559 iterator before_begin() BOOST_NOEXCEPT_OR_NOTHROW 560 { return iterator(end()); } 561 562 //! <b>Effects</b>: Returns a non-dereferenceable const_iterator 563 //! that, when incremented, yields begin(). This iterator may be used 564 //! as the argument to insert_after, erase_after, etc. 565 //! 566 //! <b>Throws</b>: Nothing. 567 //! 568 //! <b>Complexity</b>: Constant. before_begin() const569 const_iterator before_begin() const BOOST_NOEXCEPT_OR_NOTHROW 570 { return this->cbefore_begin(); } 571 572 //! <b>Effects</b>: Returns an iterator to the first element contained in the list. 573 //! 574 //! <b>Throws</b>: Nothing. 575 //! 576 //! <b>Complexity</b>: Constant. begin()577 iterator begin() BOOST_NOEXCEPT_OR_NOTHROW 578 { return iterator(this->icont().begin()); } 579 580 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the list. 581 //! 582 //! <b>Throws</b>: Nothing. 583 //! 584 //! <b>Complexity</b>: Constant. begin() const585 const_iterator begin() const BOOST_NOEXCEPT_OR_NOTHROW 586 { return this->cbegin(); } 587 588 //! <b>Effects</b>: Returns an iterator to the end of the list. 589 //! 590 //! <b>Throws</b>: Nothing. 591 //! 592 //! <b>Complexity</b>: Constant. end()593 iterator end() BOOST_NOEXCEPT_OR_NOTHROW 594 { return iterator(this->icont().end()); } 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. end() const601 const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW 602 { return this->cend(); } 603 604 //! <b>Effects</b>: Returns a non-dereferenceable const_iterator 605 //! that, when incremented, yields begin(). This iterator may be used 606 //! as the argument to insert_after, erase_after, etc. 607 //! 608 //! <b>Throws</b>: Nothing. 609 //! 610 //! <b>Complexity</b>: Constant. cbefore_begin() const611 const_iterator cbefore_begin() const BOOST_NOEXCEPT_OR_NOTHROW 612 { return const_iterator(end()); } 613 614 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the list. 615 //! 616 //! <b>Throws</b>: Nothing. 617 //! 618 //! <b>Complexity</b>: Constant. cbegin() const619 const_iterator cbegin() const BOOST_NOEXCEPT_OR_NOTHROW 620 { return const_iterator(this->non_const_icont().begin()); } 621 622 //! <b>Effects</b>: Returns a const_iterator to the end of the list. 623 //! 624 //! <b>Throws</b>: Nothing. 625 //! 626 //! <b>Complexity</b>: Constant. cend() const627 const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW 628 { return const_iterator(this->non_const_icont().end()); } 629 630 //! <b>Returns</b>: The iterator to the element before i in the sequence. 631 //! Returns the end-iterator, if either i is the begin-iterator or the 632 //! sequence is empty. 633 //! 634 //! <b>Throws</b>: Nothing. 635 //! 636 //! <b>Complexity</b>: Linear to the number of elements before i. 637 //! 638 //! <b>Note</b>: Non-standard extension. previous(iterator p)639 iterator previous(iterator p) BOOST_NOEXCEPT_OR_NOTHROW 640 { return iterator(this->icont().previous(p.get())); } 641 642 //! <b>Returns</b>: The const_iterator to the element before i in the sequence. 643 //! Returns the end-const_iterator, if either i is the begin-const_iterator or 644 //! the sequence is empty. 645 //! 646 //! <b>Throws</b>: Nothing. 647 //! 648 //! <b>Complexity</b>: Linear to the number of elements before i. 649 //! 650 //! <b>Note</b>: Non-standard extension. previous(const_iterator p)651 const_iterator previous(const_iterator p) 652 { return const_iterator(this->icont().previous(p.get())); } 653 654 ////////////////////////////////////////////// 655 // 656 // capacity 657 // 658 ////////////////////////////////////////////// 659 660 //! <b>Effects</b>: Returns true if the list contains no elements. 661 //! 662 //! <b>Throws</b>: Nothing. 663 //! 664 //! <b>Complexity</b>: Constant. empty() const665 bool empty() const 666 { return !this->size(); } 667 668 //! <b>Effects</b>: Returns the number of the elements contained in the list. 669 //! 670 //! <b>Throws</b>: Nothing. 671 //! 672 //! <b>Complexity</b>: Constant. size() const673 size_type size() const 674 { return this->icont().size(); } 675 676 //! <b>Effects</b>: Returns the largest possible size of the list. 677 //! 678 //! <b>Throws</b>: Nothing. 679 //! 680 //! <b>Complexity</b>: Constant. max_size() const681 size_type max_size() const 682 { return AllocHolder::max_size(); } 683 684 //! <b>Effects</b>: Inserts or erases elements at the end such that 685 //! the size becomes n. New elements are value initialized. 686 //! 687 //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws. 688 //! 689 //! <b>Complexity</b>: Linear to the difference between size() and new_size. resize(size_type new_size)690 void resize(size_type new_size) 691 { 692 const_iterator last_pos; 693 if(!priv_try_shrink(new_size, last_pos)){ 694 typedef value_init_construct_iterator<value_type, difference_type> value_init_iterator; 695 this->insert_after(last_pos, value_init_iterator(new_size - this->size()), value_init_iterator()); 696 } 697 } 698 699 //! <b>Effects</b>: Inserts or erases elements at the end such that 700 //! the size becomes n. New elements are copy constructed from x. 701 //! 702 //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws. 703 //! 704 //! <b>Complexity</b>: Linear to the difference between size() and new_size. resize(size_type new_size,const T & x)705 void resize(size_type new_size, const T& x) 706 { 707 const_iterator last_pos; 708 if(!priv_try_shrink(new_size, last_pos)){ 709 this->insert_after(last_pos, new_size, x); 710 } 711 } 712 713 ////////////////////////////////////////////// 714 // 715 // element access 716 // 717 ////////////////////////////////////////////// 718 719 //! <b>Requires</b>: !empty() 720 //! 721 //! <b>Effects</b>: Returns a reference to the first element 722 //! from the beginning of the container. 723 //! 724 //! <b>Throws</b>: Nothing. 725 //! 726 //! <b>Complexity</b>: Constant. front()727 reference front() 728 { 729 BOOST_ASSERT(!this->empty()); 730 return *this->begin(); 731 } 732 733 //! <b>Requires</b>: !empty() 734 //! 735 //! <b>Effects</b>: Returns a const reference to the first element 736 //! from the beginning of the container. 737 //! 738 //! <b>Throws</b>: Nothing. 739 //! 740 //! <b>Complexity</b>: Constant. front() const741 const_reference front() const 742 { 743 BOOST_ASSERT(!this->empty()); 744 return *this->begin(); 745 } 746 747 ////////////////////////////////////////////// 748 // 749 // modifiers 750 // 751 ////////////////////////////////////////////// 752 753 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 754 755 //! <b>Effects</b>: Inserts an object of type T constructed with 756 //! std::forward<Args>(args)... in the front of the list 757 //! 758 //! <b>Returns</b>: A reference to the created object. 759 //! 760 //! <b>Throws</b>: If memory allocation throws or 761 //! T's copy constructor throws. 762 //! 763 //! <b>Complexity</b>: Amortized constant time. 764 template <class... Args> emplace_front(BOOST_FWD_REF (Args)...args)765 reference emplace_front(BOOST_FWD_REF(Args)... args) 766 { return *this->emplace_after(this->cbefore_begin(), boost::forward<Args>(args)...); } 767 768 //! <b>Effects</b>: Inserts an object of type T constructed with 769 //! std::forward<Args>(args)... after prev 770 //! 771 //! <b>Throws</b>: If memory allocation throws or 772 //! T's in-place constructor throws. 773 //! 774 //! <b>Complexity</b>: Constant 775 template <class... Args> emplace_after(const_iterator prev,BOOST_FWD_REF (Args)...args)776 iterator emplace_after(const_iterator prev, BOOST_FWD_REF(Args)... args) 777 { 778 NodePtr pnode(AllocHolder::create_node(boost::forward<Args>(args)...)); 779 return iterator(this->icont().insert_after(prev.get(), *pnode)); 780 } 781 782 #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 783 784 #define BOOST_CONTAINER_SLIST_EMPLACE_CODE(N) \ 785 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 786 reference emplace_front(BOOST_MOVE_UREF##N)\ 787 { return *this->emplace_after(this->cbefore_begin() BOOST_MOVE_I##N BOOST_MOVE_FWD##N);}\ 788 \ 789 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 790 iterator emplace_after(const_iterator p BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ 791 {\ 792 NodePtr pnode (AllocHolder::create_node(BOOST_MOVE_FWD##N));\ 793 return iterator(this->icont().insert_after(p.get(), *pnode));\ 794 }\ 795 // 796 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_SLIST_EMPLACE_CODE) 797 #undef BOOST_CONTAINER_SLIST_EMPLACE_CODE 798 799 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 800 801 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 802 //! <b>Effects</b>: Inserts a copy of x at the beginning of the list. 803 //! 804 //! <b>Throws</b>: If memory allocation throws or 805 //! T's copy constructor throws. 806 //! 807 //! <b>Complexity</b>: Amortized constant time. 808 void push_front(const T &x); 809 810 //! <b>Effects</b>: Constructs a new element in the beginning of the list 811 //! and moves the resources of x to this new element. 812 //! 813 //! <b>Throws</b>: If memory allocation throws. 814 //! 815 //! <b>Complexity</b>: Amortized constant time. 816 void push_front(T &&x); 817 #else 818 BOOST_MOVE_CONVERSION_AWARE_CATCH(push_front, T, void, priv_push_front) 819 #endif 820 821 822 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 823 //! <b>Requires</b>: p must be a valid iterator of *this. 824 //! 825 //! <b>Effects</b>: Inserts a copy of the value after prev_p. 826 //! 827 //! <b>Returns</b>: An iterator to the inserted element. 828 //! 829 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws. 830 //! 831 //! <b>Complexity</b>: Amortized constant time. 832 //! 833 //! <b>Note</b>: Does not affect the validity of iterators and references of 834 //! previous values. 835 iterator insert_after(const_iterator prev_p, const T &x); 836 837 //! <b>Requires</b>: prev_p must be a valid iterator of *this. 838 //! 839 //! <b>Effects</b>: Inserts a move constructed copy object from the value after the 840 //! element pointed by prev_p. 841 //! 842 //! <b>Returns</b>: An iterator to the inserted element. 843 //! 844 //! <b>Throws</b>: If memory allocation throws. 845 //! 846 //! <b>Complexity</b>: Amortized constant time. 847 //! 848 //! <b>Note</b>: Does not affect the validity of iterators and references of 849 //! previous values. 850 iterator insert_after(const_iterator prev_p, T &&x); 851 #else BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert_after,T,iterator,priv_insert_after,const_iterator,const_iterator)852 BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert_after, T, iterator, priv_insert_after, const_iterator, const_iterator) 853 #endif 854 855 //! <b>Requires</b>: prev_p must be a valid iterator of *this. 856 //! 857 //! <b>Effects</b>: Inserts n copies of x after prev_p. 858 //! 859 //! <b>Returns</b>: an iterator to the last inserted element or prev_p if n is 0. 860 //! 861 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws. 862 //! 863 //! 864 //! <b>Complexity</b>: Linear to n. 865 //! 866 //! <b>Note</b>: Does not affect the validity of iterators and references of 867 //! previous values. 868 iterator insert_after(const_iterator prev_p, size_type n, const value_type& x) 869 { 870 typedef constant_iterator<value_type, difference_type> cvalue_iterator; 871 return this->insert_after(prev_p, cvalue_iterator(x, n), cvalue_iterator()); 872 } 873 874 //! <b>Requires</b>: prev_p must be a valid iterator of *this. 875 //! 876 //! <b>Effects</b>: Inserts the range pointed by [first, last) after prev_p. 877 //! 878 //! <b>Returns</b>: an iterator to the last inserted element or prev_p if first == last. 879 //! 880 //! <b>Throws</b>: If memory allocation throws, T's constructor from a 881 //! dereferenced InpIt throws. 882 //! 883 //! <b>Complexity</b>: Linear to the number of elements inserted. 884 //! 885 //! <b>Note</b>: Does not affect the validity of iterators and references of 886 //! previous values. 887 template <class InpIt> insert_after(const_iterator prev_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)888 iterator insert_after(const_iterator prev_p, InpIt first, InpIt last 889 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 890 , typename dtl::enable_if_c 891 < !dtl::is_convertible<InpIt, size_type>::value 892 && (dtl::is_input_iterator<InpIt>::value 893 || dtl::is_same<alloc_version, version_1>::value 894 ) 895 >::type * = 0 896 #endif 897 ) 898 { 899 iterator ret_it(prev_p.get()); 900 for (; first != last; ++first){ 901 ret_it = iterator(this->icont().insert_after(ret_it.get(), *this->create_node_from_it(first))); 902 } 903 return ret_it; 904 } 905 906 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 907 //! <b>Requires</b>: prev_p must be a valid iterator of *this. 908 //! 909 //! <b>Effects</b>: Inserts the range pointed by [il.begin(), il.end()) after prev_p. 910 //! 911 //! <b>Returns</b>: an iterator to the last inserted element or prev_p if il.begin() == il.end(). 912 //! 913 //! <b>Throws</b>: If memory allocation throws, T's constructor from a 914 //! dereferenced std::initializer_list iterator throws. 915 //! 916 //! <b>Complexity</b>: Linear to the number of elements inserted. 917 //! 918 //! <b>Note</b>: Does not affect the validity of iterators and references of 919 //! previous values. insert_after(const_iterator prev_p,std::initializer_list<value_type> il)920 iterator insert_after(const_iterator prev_p, std::initializer_list<value_type> il) 921 { 922 return insert_after(prev_p, il.begin(), il.end()); 923 } 924 #endif 925 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 926 template <class FwdIt> insert_after(const_iterator prev,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)927 iterator insert_after(const_iterator prev, FwdIt first, FwdIt last 928 , typename dtl::enable_if_c 929 < !dtl::is_convertible<FwdIt, size_type>::value 930 && !(dtl::is_input_iterator<FwdIt>::value 931 || dtl::is_same<alloc_version, version_1>::value 932 ) 933 >::type * = 0 934 ) 935 { 936 //Optimized allocation and construction 937 insertion_functor func(this->icont(), prev.get()); 938 this->allocate_many_and_construct(first, boost::container::iterator_distance(first, last), func); 939 return iterator(func.inserted_first()); 940 } 941 #endif 942 943 //! <b>Effects</b>: Removes the first element from the list. 944 //! 945 //! <b>Throws</b>: Nothing. 946 //! 947 //! <b>Complexity</b>: Amortized constant time. pop_front()948 void pop_front() 949 { 950 BOOST_ASSERT(!this->empty()); 951 this->icont().pop_front_and_dispose(Destroyer(this->node_alloc())); 952 } 953 954 //! <b>Effects</b>: Erases the element after the element pointed by prev_p 955 //! of the list. 956 //! 957 //! <b>Returns</b>: the first element remaining beyond the removed elements, 958 //! or end() if no such element exists. 959 //! 960 //! <b>Throws</b>: Nothing. 961 //! 962 //! <b>Complexity</b>: Constant. 963 //! 964 //! <b>Note</b>: Does not invalidate iterators or references to non erased elements. erase_after(const_iterator prev_p)965 iterator erase_after(const_iterator prev_p) 966 { 967 return iterator(this->icont().erase_after_and_dispose(prev_p.get(), Destroyer(this->node_alloc()))); 968 } 969 970 //! <b>Effects</b>: Erases the range (before_first, last) from 971 //! the list. 972 //! 973 //! <b>Returns</b>: the first element remaining beyond the removed elements, 974 //! or end() if no such element exists. 975 //! 976 //! <b>Throws</b>: Nothing. 977 //! 978 //! <b>Complexity</b>: Linear to the number of erased elements. 979 //! 980 //! <b>Note</b>: Does not invalidate iterators or references to non erased elements. erase_after(const_iterator before_first,const_iterator last)981 iterator erase_after(const_iterator before_first, const_iterator last) 982 { 983 return iterator(this->icont().erase_after_and_dispose(before_first.get(), last.get(), Destroyer(this->node_alloc()))); 984 } 985 986 //! <b>Effects</b>: Swaps the contents of *this and x. 987 //! 988 //! <b>Throws</b>: Nothing. 989 //! 990 //! <b>Complexity</b>: Linear to the number of elements on *this and x. swap(slist & x)991 void swap(slist& x) 992 BOOST_NOEXCEPT_IF( allocator_traits_type::propagate_on_container_swap::value 993 || allocator_traits_type::is_always_equal::value) 994 { 995 BOOST_ASSERT(allocator_traits_type::propagate_on_container_swap::value || 996 allocator_traits_type::is_always_equal::value || 997 this->get_stored_allocator() == x.get_stored_allocator()); 998 AllocHolder::swap(x); 999 } 1000 1001 //! <b>Effects</b>: Erases all the elements of the list. 1002 //! 1003 //! <b>Throws</b>: Nothing. 1004 //! 1005 //! <b>Complexity</b>: Linear to the number of elements in the list. clear()1006 void clear() 1007 { this->icont().clear_and_dispose(Destroyer(this->node_alloc())); } 1008 1009 ////////////////////////////////////////////// 1010 // 1011 // slist operations 1012 // 1013 ////////////////////////////////////////////// 1014 1015 //! <b>Requires</b>: p must point to an element contained 1016 //! by the list. x != *this 1017 //! 1018 //! <b>Effects</b>: Transfers all the elements of list x to this list, after the 1019 //! the element pointed by p. No destructors or copy constructors are called. 1020 //! 1021 //! <b>Throws</b>: std::runtime_error if this' allocator and x's allocator 1022 //! are not equal. 1023 //! 1024 //! <b>Complexity</b>: Linear to the elements in x. 1025 //! 1026 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of 1027 //! this list. Iterators of this list and all the references are not invalidated. splice_after(const_iterator prev_p,slist & x)1028 void splice_after(const_iterator prev_p, slist& x) BOOST_NOEXCEPT_OR_NOTHROW 1029 { 1030 BOOST_ASSERT(this != &x); 1031 BOOST_ASSERT(this->node_alloc() == x.node_alloc()); 1032 this->icont().splice_after(prev_p.get(), x.icont()); 1033 } 1034 1035 //! <b>Requires</b>: p must point to an element contained 1036 //! by the list. x != *this 1037 //! 1038 //! <b>Effects</b>: Transfers all the elements of list x to this list, after the 1039 //! the element pointed by p. No destructors or copy constructors are called. 1040 //! 1041 //! <b>Throws</b>: std::runtime_error if this' allocator and x's allocator 1042 //! are not equal. 1043 //! 1044 //! <b>Complexity</b>: Linear to the elements in x. 1045 //! 1046 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of 1047 //! this list. Iterators of this list and all the references are not invalidated. splice_after(const_iterator prev_p,BOOST_RV_REF (slist)x)1048 void splice_after(const_iterator prev_p, BOOST_RV_REF(slist) x) BOOST_NOEXCEPT_OR_NOTHROW 1049 { this->splice_after(prev_p, static_cast<slist&>(x)); } 1050 1051 //! <b>Requires</b>: prev_p must be a valid iterator of this. 1052 //! i must point to an element contained in list x. 1053 //! this' allocator and x's allocator shall compare equal. 1054 //! 1055 //! <b>Effects</b>: Transfers the value pointed by i, from list x to this list, 1056 //! after the element pointed by prev_p. 1057 //! If prev_p == prev or prev_p == ++prev, this function is a null operation. 1058 //! 1059 //! <b>Throws</b>: Nothing 1060 //! 1061 //! <b>Complexity</b>: Constant. 1062 //! 1063 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this 1064 //! list. Iterators of this list and all the references are not invalidated. splice_after(const_iterator prev_p,slist & x,const_iterator prev)1065 void splice_after(const_iterator prev_p, slist& x, const_iterator prev) BOOST_NOEXCEPT_OR_NOTHROW 1066 { 1067 BOOST_ASSERT(this->node_alloc() == x.node_alloc()); 1068 this->icont().splice_after(prev_p.get(), x.icont(), prev.get()); 1069 } 1070 1071 //! <b>Requires</b>: prev_p must be a valid iterator of this. 1072 //! i must point to an element contained in list x. 1073 //! this' allocator and x's allocator shall compare equal. 1074 //! 1075 //! <b>Effects</b>: Transfers the value pointed by i, from list x to this list, 1076 //! after the element pointed by prev_p. 1077 //! If prev_p == prev or prev_p == ++prev, this function is a null operation. 1078 //! 1079 //! <b>Throws</b>: Nothing 1080 //! 1081 //! <b>Complexity</b>: Constant. 1082 //! 1083 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this 1084 //! list. Iterators of this list and all the references are not invalidated. splice_after(const_iterator prev_p,BOOST_RV_REF (slist)x,const_iterator prev)1085 void splice_after(const_iterator prev_p, BOOST_RV_REF(slist) x, const_iterator prev) BOOST_NOEXCEPT_OR_NOTHROW 1086 { this->splice_after(prev_p, static_cast<slist&>(x), prev); } 1087 1088 //! <b>Requires</b>: prev_p must be a valid iterator of this. 1089 //! before_first and before_last must be valid iterators of x. 1090 //! prev_p must not be contained in [before_first, before_last) range. 1091 //! this' allocator and x's allocator shall compare equal. 1092 //! 1093 //! <b>Effects</b>: Transfers the range [before_first + 1, before_last + 1) 1094 //! from list x to this list, after the element pointed by prev_p. 1095 //! 1096 //! <b>Throws</b>: Nothing 1097 //! 1098 //! <b>Complexity</b>: Linear to the number of transferred elements. 1099 //! 1100 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this 1101 //! list. Iterators of this list and all the references are not invalidated. splice_after(const_iterator prev_p,slist & x,const_iterator before_first,const_iterator before_last)1102 void splice_after(const_iterator prev_p, slist& x, 1103 const_iterator before_first, const_iterator before_last) BOOST_NOEXCEPT_OR_NOTHROW 1104 { 1105 BOOST_ASSERT(this->node_alloc() == x.node_alloc()); 1106 this->icont().splice_after 1107 (prev_p.get(), x.icont(), before_first.get(), before_last.get()); 1108 } 1109 1110 //! <b>Requires</b>: prev_p must be a valid iterator of this. 1111 //! before_first and before_last must be valid iterators of x. 1112 //! prev_p must not be contained in [before_first, before_last) range. 1113 //! this' allocator and x's allocator shall compare equal. 1114 //! 1115 //! <b>Effects</b>: Transfers the range [before_first + 1, before_last + 1) 1116 //! from list x to this list, after the element pointed by prev_p. 1117 //! 1118 //! <b>Throws</b>: Nothing 1119 //! 1120 //! <b>Complexity</b>: Linear to the number of transferred elements. 1121 //! 1122 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this 1123 //! list. Iterators of this list and all the references are not invalidated. splice_after(const_iterator prev_p,BOOST_RV_REF (slist)x,const_iterator before_first,const_iterator before_last)1124 void splice_after(const_iterator prev_p, BOOST_RV_REF(slist) x, 1125 const_iterator before_first, const_iterator before_last) BOOST_NOEXCEPT_OR_NOTHROW 1126 { this->splice_after(prev_p, static_cast<slist&>(x), before_first, before_last); } 1127 1128 //! <b>Requires</b>: prev_p must be a valid iterator of this. 1129 //! before_first and before_last must be valid iterators of x. 1130 //! prev_p must not be contained in [before_first, before_last) range. 1131 //! n == distance(before_first, before_last). 1132 //! this' allocator and x's allocator shall compare equal. 1133 //! 1134 //! <b>Effects</b>: Transfers the range [before_first + 1, before_last + 1) 1135 //! from list x to this list, after the element pointed by prev_p. 1136 //! 1137 //! <b>Throws</b>: Nothing 1138 //! 1139 //! <b>Complexity</b>: Constant. 1140 //! 1141 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this 1142 //! list. Iterators of this list and all the references are not invalidated. splice_after(const_iterator prev_p,slist & x,const_iterator before_first,const_iterator before_last,size_type n)1143 void splice_after(const_iterator prev_p, slist& x, 1144 const_iterator before_first, const_iterator before_last, 1145 size_type n) BOOST_NOEXCEPT_OR_NOTHROW 1146 { 1147 BOOST_ASSERT(this->node_alloc() == x.node_alloc()); 1148 this->icont().splice_after 1149 (prev_p.get(), x.icont(), before_first.get(), before_last.get(), n); 1150 } 1151 1152 //! <b>Requires</b>: prev_p must be a valid iterator of this. 1153 //! before_first and before_last must be valid iterators of x. 1154 //! prev_p must not be contained in [before_first, before_last) range. 1155 //! n == distance(before_first, before_last). 1156 //! this' allocator and x's allocator shall compare equal. 1157 //! 1158 //! <b>Effects</b>: Transfers the range [before_first + 1, before_last + 1) 1159 //! from list x to this list, after the element pointed by prev_p. 1160 //! 1161 //! <b>Throws</b>: Nothing 1162 //! 1163 //! <b>Complexity</b>: Constant. 1164 //! 1165 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this 1166 //! list. Iterators of this list and all the references are not invalidated. splice_after(const_iterator prev_p,BOOST_RV_REF (slist)x,const_iterator before_first,const_iterator before_last,size_type n)1167 void splice_after(const_iterator prev_p, BOOST_RV_REF(slist) x, 1168 const_iterator before_first, const_iterator before_last, 1169 size_type n) BOOST_NOEXCEPT_OR_NOTHROW 1170 { this->splice_after(prev_p, static_cast<slist&>(x), before_first, before_last, n); } 1171 1172 //! <b>Effects</b>: Removes all the elements that compare equal to value. 1173 //! 1174 //! <b>Throws</b>: Nothing. 1175 //! 1176 //! <b>Complexity</b>: Linear time. It performs exactly size() comparisons for equality. 1177 //! 1178 //! <b>Note</b>: The relative order of elements that are not removed is unchanged, 1179 //! and iterators to elements that are not removed remain valid. remove(const T & value)1180 void remove(const T& value) 1181 { this->remove_if(equal_to_value_type(value)); } 1182 1183 //! <b>Effects</b>: Removes all the elements for which a specified 1184 //! predicate is satisfied. 1185 //! 1186 //! <b>Throws</b>: If pred throws. 1187 //! 1188 //! <b>Complexity</b>: Linear time. It performs exactly size() calls to the predicate. 1189 //! 1190 //! <b>Note</b>: The relative order of elements that are not removed is unchanged, 1191 //! and iterators to elements that are not removed remain valid. 1192 template <class Pred> remove_if(Pred pred)1193 void remove_if(Pred pred) 1194 { 1195 typedef value_to_node_compare<Node, Pred> value_to_node_compare_type; 1196 this->icont().remove_and_dispose_if(value_to_node_compare_type(pred), Destroyer(this->node_alloc())); 1197 } 1198 1199 //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent 1200 //! elements that are equal from the list. 1201 //! 1202 //! <b>Throws</b>: If comparison throws. 1203 //! 1204 //! <b>Complexity</b>: Linear time (size()-1 comparisons equality comparisons). 1205 //! 1206 //! <b>Note</b>: The relative order of elements that are not removed is unchanged, 1207 //! and iterators to elements that are not removed remain valid. unique()1208 void unique() 1209 { this->unique(value_equal_t()); } 1210 1211 //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent 1212 //! elements that satisfy some binary predicate from the list. 1213 //! 1214 //! <b>Throws</b>: If pred throws. 1215 //! 1216 //! <b>Complexity</b>: Linear time (size()-1 comparisons calls to pred()). 1217 //! 1218 //! <b>Note</b>: The relative order of elements that are not removed is unchanged, 1219 //! and iterators to elements that are not removed remain valid. 1220 template <class Pred> unique(Pred pred)1221 void unique(Pred pred) 1222 { 1223 typedef value_to_node_compare<Node, Pred> value_to_node_compare_type; 1224 this->icont().unique_and_dispose(value_to_node_compare_type(pred), Destroyer(this->node_alloc())); 1225 } 1226 1227 //! <b>Requires</b>: The lists x and *this must be distinct. 1228 //! 1229 //! <b>Effects</b>: This function removes all of x's elements and inserts them 1230 //! in order into *this according to std::less<value_type>. The merge is stable; 1231 //! that is, if an element from *this is equivalent to one from x, then the element 1232 //! from *this will precede the one from x. 1233 //! 1234 //! <b>Throws</b>: If comparison throws. 1235 //! 1236 //! <b>Complexity</b>: This function is linear time: it performs at most 1237 //! size() + x.size() - 1 comparisons. merge(slist & x)1238 void merge(slist & x) 1239 { this->merge(x, value_less_t()); } 1240 1241 //! <b>Requires</b>: The lists x and *this must be distinct. 1242 //! 1243 //! <b>Effects</b>: This function removes all of x's elements and inserts them 1244 //! in order into *this according to std::less<value_type>. The merge is stable; 1245 //! that is, if an element from *this is equivalent to one from x, then the element 1246 //! from *this will precede the one from x. 1247 //! 1248 //! <b>Throws</b>: If comparison throws. 1249 //! 1250 //! <b>Complexity</b>: This function is linear time: it performs at most 1251 //! size() + x.size() - 1 comparisons. merge(BOOST_RV_REF (slist)x)1252 void merge(BOOST_RV_REF(slist) x) 1253 { this->merge(static_cast<slist&>(x)); } 1254 1255 //! <b>Requires</b>: p must be a comparison function that induces a strict weak 1256 //! ordering and both *this and x must be sorted according to that ordering 1257 //! The lists x and *this must be distinct. 1258 //! 1259 //! <b>Effects</b>: This function removes all of x's elements and inserts them 1260 //! in order into *this. The merge is stable; that is, if an element from *this is 1261 //! equivalent to one from x, then the element from *this will precede the one from x. 1262 //! 1263 //! <b>Throws</b>: If comp throws. 1264 //! 1265 //! <b>Complexity</b>: This function is linear time: it performs at most 1266 //! size() + x.size() - 1 comparisons. 1267 //! 1268 //! <b>Note</b>: Iterators and references to *this are not invalidated. 1269 template <class StrictWeakOrdering> merge(slist & x,StrictWeakOrdering comp)1270 void merge(slist& x, StrictWeakOrdering comp) 1271 { 1272 typedef value_to_node_compare<Node, StrictWeakOrdering> value_to_node_compare_type; 1273 BOOST_ASSERT(this->node_alloc() == x.node_alloc()); 1274 this->icont().merge(x.icont(), value_to_node_compare_type(comp)); 1275 } 1276 1277 //! <b>Requires</b>: p must be a comparison function that induces a strict weak 1278 //! ordering and both *this and x must be sorted according to that ordering 1279 //! 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. The merge is stable; that is, if an element from *this is 1283 //! equivalent to one from x, then the element from *this will precede the one from x. 1284 //! 1285 //! <b>Throws</b>: If comp throws. 1286 //! 1287 //! <b>Complexity</b>: This function is linear time: it performs at most 1288 //! size() + x.size() - 1 comparisons. 1289 //! 1290 //! <b>Note</b>: Iterators and references to *this are not invalidated. 1291 template <class StrictWeakOrdering> merge(BOOST_RV_REF (slist)x,StrictWeakOrdering comp)1292 void merge(BOOST_RV_REF(slist) x, StrictWeakOrdering comp) 1293 { this->merge(static_cast<slist&>(x), comp); } 1294 1295 //! <b>Effects</b>: This function sorts the list *this according to std::less<value_type>. 1296 //! The sort is stable, that is, the relative order of equivalent elements is preserved. 1297 //! 1298 //! <b>Throws</b>: If comparison throws. 1299 //! 1300 //! <b>Notes</b>: Iterators and references are not invalidated. 1301 //! 1302 //! <b>Complexity</b>: The number of comparisons is approximately N log N, where N 1303 //! is the list's size. sort()1304 void sort() 1305 { this->sort(value_less_t()); } 1306 1307 //! <b>Effects</b>: This function sorts the list *this according to std::less<value_type>. 1308 //! The sort is stable, that is, the relative order of equivalent elements is preserved. 1309 //! 1310 //! <b>Throws</b>: If comp throws. 1311 //! 1312 //! <b>Notes</b>: Iterators and references are not invalidated. 1313 //! 1314 //! <b>Complexity</b>: The number of comparisons is approximately N log N, where N 1315 //! is the list's size. 1316 template <class StrictWeakOrdering> sort(StrictWeakOrdering comp)1317 void sort(StrictWeakOrdering comp) 1318 { 1319 typedef value_to_node_compare<Node, StrictWeakOrdering> value_to_node_compare_type; 1320 // nothing if the slist has length 0 or 1. 1321 if (this->size() < 2) 1322 return; 1323 this->icont().sort(value_to_node_compare_type(comp)); 1324 } 1325 1326 //! <b>Effects</b>: Reverses the order of elements in the list. 1327 //! 1328 //! <b>Throws</b>: Nothing. 1329 //! 1330 //! <b>Complexity</b>: This function is linear time. 1331 //! 1332 //! <b>Note</b>: Iterators and references are not invalidated reverse()1333 void reverse() BOOST_NOEXCEPT_OR_NOTHROW 1334 { this->icont().reverse(); } 1335 1336 ////////////////////////////////////////////// 1337 // 1338 // list compatibility interface 1339 // 1340 ////////////////////////////////////////////// 1341 1342 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1343 1344 //! <b>Effects</b>: Inserts an object of type T constructed with 1345 //! std::forward<Args>(args)... before p 1346 //! 1347 //! <b>Throws</b>: If memory allocation throws or 1348 //! T's in-place constructor throws. 1349 //! 1350 //! <b>Complexity</b>: Linear to the elements before p 1351 template <class... Args> emplace(const_iterator p,BOOST_FWD_REF (Args)...args)1352 iterator emplace(const_iterator p, BOOST_FWD_REF(Args)... args) 1353 { return this->emplace_after(this->previous(p), boost::forward<Args>(args)...); } 1354 1355 #else 1356 1357 #define BOOST_CONTAINER_SLIST_EMPLACE_CODE(N) \ 1358 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 1359 iterator emplace(const_iterator p BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ 1360 {\ 1361 return this->emplace_after(this->previous(p) BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ 1362 }\ 1363 // 1364 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_SLIST_EMPLACE_CODE) 1365 #undef BOOST_CONTAINER_SLIST_EMPLACE_CODE 1366 1367 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 1368 1369 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1370 //! <b>Requires</b>: p must be a valid iterator of *this. 1371 //! 1372 //! <b>Effects</b>: Insert a copy of x before p. 1373 //! 1374 //! <b>Returns</b>: an iterator to the inserted element. 1375 //! 1376 //! <b>Throws</b>: If memory allocation throws or x's copy constructor throws. 1377 //! 1378 //! <b>Complexity</b>: Linear to the elements before p. 1379 iterator insert(const_iterator p, const T &x); 1380 1381 //! <b>Requires</b>: p must be a valid iterator of *this. 1382 //! 1383 //! <b>Effects</b>: Insert a new element before p with x's resources. 1384 //! 1385 //! <b>Returns</b>: an iterator to the inserted element. 1386 //! 1387 //! <b>Throws</b>: If memory allocation throws. 1388 //! 1389 //! <b>Complexity</b>: Linear to the elements before p. 1390 iterator insert(const_iterator prev_p, T &&x); 1391 #else 1392 BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, T, iterator, priv_insert, const_iterator, const_iterator) 1393 #endif 1394 1395 //! <b>Requires</b>: p must be a valid iterator of *this. 1396 //! 1397 //! <b>Effects</b>: Inserts n copies of x before p. 1398 //! 1399 //! <b>Returns</b>: an iterator to the first inserted element or p if n == 0. 1400 //! 1401 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws. 1402 //! 1403 //! <b>Complexity</b>: Linear to n plus linear to the elements before p. insert(const_iterator p,size_type n,const value_type & x)1404 iterator insert(const_iterator p, size_type n, const value_type& x) 1405 { 1406 const_iterator prev(this->previous(p)); 1407 this->insert_after(prev, n, x); 1408 return ++iterator(prev.get()); 1409 } 1410 1411 //! <b>Requires</b>: p must be a valid iterator of *this. 1412 //! 1413 //! <b>Effects</b>: Insert a copy of the [first, last) range before p. 1414 //! 1415 //! <b>Returns</b>: an iterator to the first inserted element or p if first == last. 1416 //! 1417 //! <b>Throws</b>: If memory allocation throws, T's constructor from a 1418 //! dereferenced InpIt throws. 1419 //! 1420 //! <b>Complexity</b>: Linear to distance [first, last) plus 1421 //! linear to the elements before p. 1422 template <class InIter> insert(const_iterator p,InIter first,InIter last)1423 iterator insert(const_iterator p, InIter first, InIter last) 1424 { 1425 const_iterator prev(this->previous(p)); 1426 this->insert_after(prev, first, last); 1427 return ++iterator(prev.get()); 1428 } 1429 1430 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 1431 //! <b>Requires</b>: p must be a valid iterator of *this. 1432 //! 1433 //! <b>Effects</b>: Insert a copy of the [il.begin(), il.end()) range before p. 1434 //! 1435 //! <b>Returns</b>: an iterator to the first inserted element or p if il.begin() == il.end(). 1436 //! 1437 //! <b>Throws</b>: If memory allocation throws, T's constructor from a 1438 //! dereferenced std::initializer_list iterator throws. 1439 //! 1440 //! <b>Complexity</b>: Linear to the range [il.begin(), il.end()) plus 1441 //! linear to the elements before p. insert(const_iterator p,std::initializer_list<value_type> il)1442 iterator insert(const_iterator p, std::initializer_list<value_type> il) 1443 { 1444 return insert(p, il.begin(), il.end()); 1445 } 1446 #endif 1447 1448 //! <b>Requires</b>: p must be a valid iterator of *this. 1449 //! 1450 //! <b>Effects</b>: Erases the element at p. 1451 //! 1452 //! <b>Throws</b>: Nothing. 1453 //! 1454 //! <b>Complexity</b>: Linear to the number of elements before p. erase(const_iterator p)1455 iterator erase(const_iterator p) BOOST_NOEXCEPT_OR_NOTHROW 1456 { return iterator(this->erase_after(previous(p))); } 1457 1458 //! <b>Requires</b>: first and last must be valid iterator to elements in *this. 1459 //! 1460 //! <b>Effects</b>: Erases the elements pointed by [first, last). 1461 //! 1462 //! <b>Throws</b>: Nothing. 1463 //! 1464 //! <b>Complexity</b>: Linear to the distance between first and last plus 1465 //! linear to the elements before first. erase(const_iterator first,const_iterator last)1466 iterator erase(const_iterator first, const_iterator last) BOOST_NOEXCEPT_OR_NOTHROW 1467 { return iterator(this->erase_after(previous(first), last)); } 1468 1469 //! <b>Requires</b>: p must point to an element contained 1470 //! by the list. x != *this. this' allocator and x's allocator shall compare equal 1471 //! 1472 //! <b>Effects</b>: Transfers all the elements of list x to this list, before the 1473 //! the element pointed by p. No destructors or copy constructors are called. 1474 //! 1475 //! <b>Throws</b>: Nothing 1476 //! 1477 //! <b>Complexity</b>: Linear in distance(begin(), p), and linear in x.size(). 1478 //! 1479 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of 1480 //! this list. Iterators of this list and all the references are not invalidated. splice(const_iterator p,slist & x)1481 void splice(const_iterator p, slist& x) BOOST_NOEXCEPT_OR_NOTHROW 1482 { this->splice_after(this->previous(p), x); } 1483 1484 //! <b>Requires</b>: p must point to an element contained 1485 //! by the list. x != *this. this' allocator and x's allocator shall compare equal 1486 //! 1487 //! <b>Effects</b>: Transfers all the elements of list x to this list, before the 1488 //! the element pointed by p. No destructors or copy constructors are called. 1489 //! 1490 //! <b>Throws</b>: Nothing 1491 //! 1492 //! <b>Complexity</b>: Linear in distance(begin(), p), and linear in x.size(). 1493 //! 1494 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of 1495 //! this list. Iterators of this list and all the references are not invalidated. splice(const_iterator p,BOOST_RV_REF (slist)x)1496 void splice(const_iterator p, BOOST_RV_REF(slist) x) BOOST_NOEXCEPT_OR_NOTHROW 1497 { this->splice(p, static_cast<slist&>(x)); } 1498 1499 //! <b>Requires</b>: p must point to an element contained 1500 //! by this list. i must point to an element contained in list x. 1501 //! this' allocator and x's allocator shall compare equal 1502 //! 1503 //! <b>Effects</b>: Transfers the value pointed by i, from list x to this list, 1504 //! before the element pointed by p. No destructors or copy constructors are called. 1505 //! If p == i or p == ++i, this function is a null operation. 1506 //! 1507 //! <b>Throws</b>: Nothing 1508 //! 1509 //! <b>Complexity</b>: Linear in distance(begin(), p), and in distance(x.begin(), i). 1510 //! 1511 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this 1512 //! list. Iterators of this list and all the references are not invalidated. splice(const_iterator p,slist & x,const_iterator i)1513 void splice(const_iterator p, slist& x, const_iterator i) BOOST_NOEXCEPT_OR_NOTHROW 1514 { this->splice_after(this->previous(p), x, x.previous(i)); } 1515 1516 //! <b>Requires</b>: p must point to an element contained 1517 //! by this list. i must point to an element contained in list x. 1518 //! this' allocator and x's allocator shall compare equal. 1519 //! 1520 //! <b>Effects</b>: Transfers the value pointed by i, from list x to this list, 1521 //! before the element pointed by p. No destructors or copy constructors are called. 1522 //! If p == i or p == ++i, this function is a null operation. 1523 //! 1524 //! <b>Throws</b>: Nothing 1525 //! 1526 //! <b>Complexity</b>: Linear in distance(begin(), p), and in distance(x.begin(), i). 1527 //! 1528 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this 1529 //! list. Iterators of this list and all the references are not invalidated. splice(const_iterator p,BOOST_RV_REF (slist)x,const_iterator i)1530 void splice(const_iterator p, BOOST_RV_REF(slist) x, const_iterator i) BOOST_NOEXCEPT_OR_NOTHROW 1531 { this->splice(p, static_cast<slist&>(x), i); } 1532 1533 //! <b>Requires</b>: p must point to an element contained 1534 //! by this list. first and last must point to elements contained in list x. 1535 //! 1536 //! <b>Effects</b>: Transfers the range pointed by first and last from list x to this list, 1537 //! before the element pointed by p. No destructors or copy constructors are called. 1538 //! this' allocator and x's allocator shall compare equal. 1539 //! 1540 //! <b>Throws</b>: Nothing 1541 //! 1542 //! <b>Complexity</b>: Linear in distance(begin(), p), in distance(x.begin(), first), 1543 //! and in distance(first, last). 1544 //! 1545 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this 1546 //! list. Iterators of this list and all the references are not invalidated. splice(const_iterator p,slist & x,const_iterator first,const_iterator last)1547 void splice(const_iterator p, slist& x, const_iterator first, const_iterator last) BOOST_NOEXCEPT_OR_NOTHROW 1548 { this->splice_after(this->previous(p), x, x.previous(first), x.previous(last)); } 1549 1550 //! <b>Requires</b>: p must point to an element contained 1551 //! by this list. first and last must point to elements contained in list x. 1552 //! this' allocator and x's allocator shall compare equal 1553 //! 1554 //! <b>Effects</b>: Transfers the range pointed by first and last from list x to this list, 1555 //! before the element pointed by p. No destructors or copy constructors are called. 1556 //! 1557 //! <b>Throws</b>: Nothing 1558 //! 1559 //! <b>Complexity</b>: Linear in distance(begin(), p), in distance(x.begin(), first), 1560 //! and in distance(first, last). 1561 //! 1562 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this 1563 //! list. Iterators of this list and all the references are not invalidated. splice(const_iterator p,BOOST_RV_REF (slist)x,const_iterator first,const_iterator last)1564 void splice(const_iterator p, BOOST_RV_REF(slist) x, const_iterator first, const_iterator last) BOOST_NOEXCEPT_OR_NOTHROW 1565 { this->splice(p, static_cast<slist&>(x), first, last); } 1566 1567 //! <b>Effects</b>: Returns true if x and y are equal 1568 //! 1569 //! <b>Complexity</b>: Linear to the number of elements in the container. operator ==(const slist & x,const slist & y)1570 friend bool operator==(const slist& x, const slist& y) 1571 { return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin()); } 1572 1573 //! <b>Effects</b>: Returns true if x and y are unequal 1574 //! 1575 //! <b>Complexity</b>: Linear to the number of elements in the container. operator !=(const slist & x,const slist & y)1576 friend bool operator!=(const slist& x, const slist& y) 1577 { return !(x == y); } 1578 1579 //! <b>Effects</b>: Returns true if x is less than y 1580 //! 1581 //! <b>Complexity</b>: Linear to the number of elements in the container. operator <(const slist & x,const slist & y)1582 friend bool operator<(const slist& x, const slist& y) 1583 { return ::boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); } 1584 1585 //! <b>Effects</b>: Returns true if x is greater than y 1586 //! 1587 //! <b>Complexity</b>: Linear to the number of elements in the container. operator >(const slist & x,const slist & y)1588 friend bool operator>(const slist& x, const slist& y) 1589 { return y < x; } 1590 1591 //! <b>Effects</b>: Returns true if x is equal or less than y 1592 //! 1593 //! <b>Complexity</b>: Linear to the number of elements in the container. operator <=(const slist & x,const slist & y)1594 friend bool operator<=(const slist& x, const slist& y) 1595 { return !(y < x); } 1596 1597 //! <b>Effects</b>: Returns true if x is equal or greater than y 1598 //! 1599 //! <b>Complexity</b>: Linear to the number of elements in the container. operator >=(const slist & x,const slist & y)1600 friend bool operator>=(const slist& x, const slist& y) 1601 { return !(x < y); } 1602 1603 //! <b>Effects</b>: x.swap(y) 1604 //! 1605 //! <b>Complexity</b>: Constant. swap(slist & x,slist & y)1606 friend void swap(slist& x, slist& y) 1607 { x.swap(y); } 1608 1609 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 1610 private: 1611 priv_push_front(const T & x)1612 void priv_push_front (const T &x) 1613 { this->insert_after(this->cbefore_begin(), x); } 1614 priv_push_front(BOOST_RV_REF (T)x)1615 void priv_push_front (BOOST_RV_REF(T) x) 1616 { this->insert_after(this->cbefore_begin(), ::boost::move(x)); } 1617 priv_try_shrink(size_type new_size,const_iterator & last_pos)1618 bool priv_try_shrink(size_type new_size, const_iterator &last_pos) 1619 { 1620 typename Icont::iterator end_n(this->icont().end()), cur(this->icont().before_begin()), cur_next; 1621 while (++(cur_next = cur) != end_n && new_size > 0){ 1622 --new_size; 1623 cur = cur_next; 1624 } 1625 last_pos = const_iterator(cur); 1626 if (cur_next != end_n){ 1627 this->erase_after(last_pos, const_iterator(end_n)); 1628 return true; 1629 } 1630 else{ 1631 return false; 1632 } 1633 } 1634 1635 template<class U> priv_insert(const_iterator p,BOOST_FWD_REF (U)x)1636 iterator priv_insert(const_iterator p, BOOST_FWD_REF(U) x) 1637 { return this->insert_after(previous(p), ::boost::forward<U>(x)); } 1638 1639 template<class U> priv_insert_after(const_iterator prev_p,BOOST_FWD_REF (U)x)1640 iterator priv_insert_after(const_iterator prev_p, BOOST_FWD_REF(U) x) 1641 { return iterator(this->icont().insert_after(prev_p.get(), *this->create_node(::boost::forward<U>(x)))); } 1642 1643 class insertion_functor; 1644 friend class insertion_functor; 1645 1646 class insertion_functor 1647 { 1648 Icont &icont_; 1649 typedef typename Icont::iterator iiterator; 1650 typedef typename Icont::const_iterator iconst_iterator; 1651 const iconst_iterator prev_; 1652 iiterator ret_; 1653 1654 public: insertion_functor(Icont & icont,typename Icont::const_iterator prev)1655 insertion_functor(Icont &icont, typename Icont::const_iterator prev) 1656 : icont_(icont), prev_(prev), ret_(prev.unconst()) 1657 {} 1658 operator ()(Node & n)1659 void operator()(Node &n) 1660 { 1661 ret_ = this->icont_.insert_after(prev_, n); 1662 } 1663 inserted_first() const1664 iiterator inserted_first() const 1665 { return ret_; } 1666 }; 1667 1668 //Functors for member algorithm defaults 1669 typedef value_less<value_type> value_less_t; 1670 typedef value_equal<value_type> value_equal_t; 1671 1672 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 1673 }; 1674 1675 #ifndef BOOST_CONTAINER_NO_CXX17_CTAD 1676 1677 template <typename InpIt> 1678 slist(InpIt, InpIt) -> 1679 slist<typename iterator_traits<InpIt>::value_type>; 1680 1681 template <typename InpIt, typename Allocator> 1682 slist(InpIt, InpIt, Allocator const&) -> 1683 slist<typename iterator_traits<InpIt>::value_type, Allocator>; 1684 1685 #endif 1686 1687 }} 1688 1689 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 1690 1691 namespace boost { 1692 1693 //!has_trivial_destructor_after_move<> == true_type 1694 //!specialization for optimizations 1695 template <class T, class Allocator> 1696 struct has_trivial_destructor_after_move<boost::container::slist<T, Allocator> > 1697 { 1698 typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer; 1699 static const bool value = ::boost::has_trivial_destructor_after_move<Allocator>::value && 1700 ::boost::has_trivial_destructor_after_move<pointer>::value; 1701 }; 1702 1703 namespace container { 1704 1705 }} //namespace boost{ namespace container { 1706 1707 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 1708 1709 // Specialization of insert_iterator so that insertions will be constant 1710 // time rather than linear time. 1711 1712 #include <boost/move/detail/std_ns_begin.hpp> 1713 BOOST_CONTAINER_DOC1ST(namespace std {, BOOST_MOVE_STD_NS_BEG) 1714 1715 //! A specialization of insert_iterator 1716 //! that works with slist 1717 template <class T, class ValueAllocator> 1718 class insert_iterator<boost::container::slist<T, ValueAllocator> > 1719 { 1720 private: 1721 typedef boost::container::slist<T, ValueAllocator> Container; 1722 Container* container; 1723 typename Container::iterator iter; 1724 1725 public: 1726 typedef Container container_type; 1727 typedef output_iterator_tag iterator_category; 1728 typedef void value_type; 1729 typedef void difference_type; 1730 typedef void pointer; 1731 typedef void reference; 1732 1733 insert_iterator(Container& x, 1734 typename Container::iterator i, 1735 bool is_previous = false) 1736 : container(&x), iter(is_previous ? i : x.previous(i)){ } 1737 1738 insert_iterator<Container>& 1739 operator=(const typename Container::value_type& value) 1740 { 1741 iter = container->insert_after(iter, value); 1742 return *this; 1743 } 1744 insert_iterator<Container>& operator*(){ return *this; } 1745 insert_iterator<Container>& operator++(){ return *this; } 1746 insert_iterator<Container>& operator++(int){ return *this; } 1747 }; 1748 1749 BOOST_CONTAINER_DOC1ST( }, BOOST_MOVE_STD_NS_END) 1750 #include <boost/move/detail/std_ns_end.hpp> 1751 1752 #include <boost/container/detail/config_end.hpp> 1753 1754 #endif // BOOST_CONTAINER_SLIST_HPP 1755