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 dtl::aligned_storage<sizeof(T), dtl::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 (BOOST_LIKELY(this != &x)) { 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 if (BOOST_LIKELY(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 } 449 return *this; 450 } 451 452 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 453 //! <b>Effects</b>: Makes *this contain the same elements as in il. 454 //! 455 //! <b>Postcondition</b>: this->size() == il.size(). *this contains a copy 456 //! of each of il's elements. 457 //! 458 //! <b>Throws</b>: If allocator_traits_type::propagate_on_container_move_assignment 459 //! is false and (allocation throws or value_type's move constructor throws) operator =(std::initializer_list<value_type> il)460 slist& operator=(std::initializer_list<value_type> il) 461 { 462 assign(il.begin(), il.end()); 463 return *this; 464 } 465 #endif 466 467 //! <b>Effects</b>: Assigns the n copies of val to *this. 468 //! 469 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws. 470 //! 471 //! <b>Complexity</b>: Linear to n. assign(size_type n,const T & val)472 void assign(size_type n, const T& val) 473 { 474 typedef constant_iterator<value_type, difference_type> cvalue_iterator; 475 return this->assign(cvalue_iterator(val, n), cvalue_iterator()); 476 } 477 478 //! <b>Effects</b>: Assigns the range [first, last) to *this. 479 //! 480 //! <b>Throws</b>: If memory allocation throws or 481 //! T's constructor from dereferencing InpIt throws. 482 //! 483 //! <b>Complexity</b>: Linear to n. 484 template <class InpIt> assign(InpIt first,InpIt last,typename dtl::disable_if_convertible<InpIt,size_type>::type * =0)485 void assign(InpIt first, InpIt last 486 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 487 , typename dtl::disable_if_convertible<InpIt, size_type>::type * = 0 488 #endif 489 ) 490 { 491 iterator end_n(this->end()); 492 iterator prev(this->before_begin()); 493 iterator node(this->begin()); 494 while (node != end_n && first != last){ 495 *node = *first; 496 prev = node; 497 ++node; 498 ++first; 499 } 500 if (first != last) 501 this->insert_after(prev, first, last); 502 else 503 this->erase_after(prev, end_n); 504 } 505 506 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 507 //! <b>Effects</b>: Assigns the range [il.begin(), il.end()) to *this. 508 //! 509 //! <b>Throws</b>: If memory allocation throws or 510 //! T's constructor from dereferencing std::initializer_list iterator throws. 511 //! 512 //! <b>Complexity</b>: Linear to range [il.begin(), il.end()). 513 assign(std::initializer_list<value_type> il)514 void assign(std::initializer_list<value_type> il) 515 { 516 assign(il.begin(), il.end()); 517 } 518 #endif 519 //! <b>Effects</b>: Returns a copy of the internal allocator. 520 //! 521 //! <b>Throws</b>: If allocator's copy constructor throws. 522 //! 523 //! <b>Complexity</b>: Constant. get_allocator() const524 allocator_type get_allocator() const BOOST_NOEXCEPT_OR_NOTHROW 525 { return allocator_type(this->node_alloc()); } 526 527 //! <b>Effects</b>: Returns a reference to the internal allocator. 528 //! 529 //! <b>Throws</b>: Nothing 530 //! 531 //! <b>Complexity</b>: Constant. 532 //! 533 //! <b>Note</b>: Non-standard extension. get_stored_allocator()534 stored_allocator_type &get_stored_allocator() BOOST_NOEXCEPT_OR_NOTHROW 535 { return this->node_alloc(); } 536 537 //! <b>Effects</b>: Returns a reference to the internal allocator. 538 //! 539 //! <b>Throws</b>: Nothing 540 //! 541 //! <b>Complexity</b>: Constant. 542 //! 543 //! <b>Note</b>: Non-standard extension. get_stored_allocator() const544 const stored_allocator_type &get_stored_allocator() const BOOST_NOEXCEPT_OR_NOTHROW 545 { return this->node_alloc(); } 546 547 ////////////////////////////////////////////// 548 // 549 // iterators 550 // 551 ////////////////////////////////////////////// 552 553 //! <b>Effects</b>: Returns a non-dereferenceable iterator that, 554 //! when incremented, yields begin(). This iterator may be used 555 //! as the argument to insert_after, erase_after, etc. 556 //! 557 //! <b>Throws</b>: Nothing. 558 //! 559 //! <b>Complexity</b>: Constant. before_begin()560 iterator before_begin() BOOST_NOEXCEPT_OR_NOTHROW 561 { return iterator(end()); } 562 563 //! <b>Effects</b>: Returns a non-dereferenceable const_iterator 564 //! that, when incremented, yields begin(). This iterator may be used 565 //! as the argument to insert_after, erase_after, etc. 566 //! 567 //! <b>Throws</b>: Nothing. 568 //! 569 //! <b>Complexity</b>: Constant. before_begin() const570 const_iterator before_begin() const BOOST_NOEXCEPT_OR_NOTHROW 571 { return this->cbefore_begin(); } 572 573 //! <b>Effects</b>: Returns an iterator to the first element contained in the list. 574 //! 575 //! <b>Throws</b>: Nothing. 576 //! 577 //! <b>Complexity</b>: Constant. begin()578 iterator begin() BOOST_NOEXCEPT_OR_NOTHROW 579 { return iterator(this->icont().begin()); } 580 581 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the list. 582 //! 583 //! <b>Throws</b>: Nothing. 584 //! 585 //! <b>Complexity</b>: Constant. begin() const586 const_iterator begin() const BOOST_NOEXCEPT_OR_NOTHROW 587 { return this->cbegin(); } 588 589 //! <b>Effects</b>: Returns an iterator to the end of the list. 590 //! 591 //! <b>Throws</b>: Nothing. 592 //! 593 //! <b>Complexity</b>: Constant. end()594 iterator end() BOOST_NOEXCEPT_OR_NOTHROW 595 { return iterator(this->icont().end()); } 596 597 //! <b>Effects</b>: Returns a const_iterator to the end of the list. 598 //! 599 //! <b>Throws</b>: Nothing. 600 //! 601 //! <b>Complexity</b>: Constant. end() const602 const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW 603 { return this->cend(); } 604 605 //! <b>Effects</b>: Returns a non-dereferenceable const_iterator 606 //! that, when incremented, yields begin(). This iterator may be used 607 //! as the argument to insert_after, erase_after, etc. 608 //! 609 //! <b>Throws</b>: Nothing. 610 //! 611 //! <b>Complexity</b>: Constant. cbefore_begin() const612 const_iterator cbefore_begin() const BOOST_NOEXCEPT_OR_NOTHROW 613 { return const_iterator(end()); } 614 615 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the list. 616 //! 617 //! <b>Throws</b>: Nothing. 618 //! 619 //! <b>Complexity</b>: Constant. cbegin() const620 const_iterator cbegin() const BOOST_NOEXCEPT_OR_NOTHROW 621 { return const_iterator(this->non_const_icont().begin()); } 622 623 //! <b>Effects</b>: Returns a const_iterator to the end of the list. 624 //! 625 //! <b>Throws</b>: Nothing. 626 //! 627 //! <b>Complexity</b>: Constant. cend() const628 const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW 629 { return const_iterator(this->non_const_icont().end()); } 630 631 //! <b>Returns</b>: The iterator to the element before i in the sequence. 632 //! Returns the end-iterator, if either i is the begin-iterator or the 633 //! sequence is empty. 634 //! 635 //! <b>Throws</b>: Nothing. 636 //! 637 //! <b>Complexity</b>: Linear to the number of elements before i. 638 //! 639 //! <b>Note</b>: Non-standard extension. previous(iterator p)640 iterator previous(iterator p) BOOST_NOEXCEPT_OR_NOTHROW 641 { return iterator(this->icont().previous(p.get())); } 642 643 //! <b>Returns</b>: The const_iterator to the element before i in the sequence. 644 //! Returns the end-const_iterator, if either i is the begin-const_iterator or 645 //! the sequence is empty. 646 //! 647 //! <b>Throws</b>: Nothing. 648 //! 649 //! <b>Complexity</b>: Linear to the number of elements before i. 650 //! 651 //! <b>Note</b>: Non-standard extension. previous(const_iterator p)652 const_iterator previous(const_iterator p) 653 { return const_iterator(this->icont().previous(p.get())); } 654 655 ////////////////////////////////////////////// 656 // 657 // capacity 658 // 659 ////////////////////////////////////////////// 660 661 //! <b>Effects</b>: Returns true if the list contains no elements. 662 //! 663 //! <b>Throws</b>: Nothing. 664 //! 665 //! <b>Complexity</b>: Constant. empty() const666 bool empty() const 667 { return !this->size(); } 668 669 //! <b>Effects</b>: Returns the number of the elements contained in the list. 670 //! 671 //! <b>Throws</b>: Nothing. 672 //! 673 //! <b>Complexity</b>: Constant. size() const674 size_type size() const 675 { return this->icont().size(); } 676 677 //! <b>Effects</b>: Returns the largest possible size of the list. 678 //! 679 //! <b>Throws</b>: Nothing. 680 //! 681 //! <b>Complexity</b>: Constant. max_size() const682 size_type max_size() const 683 { return AllocHolder::max_size(); } 684 685 //! <b>Effects</b>: Inserts or erases elements at the end such that 686 //! the size becomes n. New elements are value initialized. 687 //! 688 //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws. 689 //! 690 //! <b>Complexity</b>: Linear to the difference between size() and new_size. resize(size_type new_size)691 void resize(size_type new_size) 692 { 693 const_iterator last_pos; 694 if(!priv_try_shrink(new_size, last_pos)){ 695 typedef value_init_construct_iterator<value_type, difference_type> value_init_iterator; 696 this->insert_after(last_pos, value_init_iterator(new_size - this->size()), value_init_iterator()); 697 } 698 } 699 700 //! <b>Effects</b>: Inserts or erases elements at the end such that 701 //! the size becomes n. New elements are copy constructed from x. 702 //! 703 //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws. 704 //! 705 //! <b>Complexity</b>: Linear to the difference between size() and new_size. resize(size_type new_size,const T & x)706 void resize(size_type new_size, const T& x) 707 { 708 const_iterator last_pos; 709 if(!priv_try_shrink(new_size, last_pos)){ 710 this->insert_after(last_pos, new_size, x); 711 } 712 } 713 714 ////////////////////////////////////////////// 715 // 716 // element access 717 // 718 ////////////////////////////////////////////// 719 720 //! <b>Requires</b>: !empty() 721 //! 722 //! <b>Effects</b>: Returns a reference to the first element 723 //! from the beginning of the container. 724 //! 725 //! <b>Throws</b>: Nothing. 726 //! 727 //! <b>Complexity</b>: Constant. front()728 reference front() 729 { 730 BOOST_ASSERT(!this->empty()); 731 return *this->begin(); 732 } 733 734 //! <b>Requires</b>: !empty() 735 //! 736 //! <b>Effects</b>: Returns a const reference to the first element 737 //! from the beginning of the container. 738 //! 739 //! <b>Throws</b>: Nothing. 740 //! 741 //! <b>Complexity</b>: Constant. front() const742 const_reference front() const 743 { 744 BOOST_ASSERT(!this->empty()); 745 return *this->begin(); 746 } 747 748 ////////////////////////////////////////////// 749 // 750 // modifiers 751 // 752 ////////////////////////////////////////////// 753 754 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 755 756 //! <b>Effects</b>: Inserts an object of type T constructed with 757 //! std::forward<Args>(args)... in the front of the list 758 //! 759 //! <b>Returns</b>: A reference to the created object. 760 //! 761 //! <b>Throws</b>: If memory allocation throws or 762 //! T's copy constructor throws. 763 //! 764 //! <b>Complexity</b>: Amortized constant time. 765 template <class... Args> emplace_front(BOOST_FWD_REF (Args)...args)766 reference emplace_front(BOOST_FWD_REF(Args)... args) 767 { return *this->emplace_after(this->cbefore_begin(), boost::forward<Args>(args)...); } 768 769 //! <b>Effects</b>: Inserts an object of type T constructed with 770 //! std::forward<Args>(args)... after prev 771 //! 772 //! <b>Throws</b>: If memory allocation throws or 773 //! T's in-place constructor throws. 774 //! 775 //! <b>Complexity</b>: Constant 776 template <class... Args> emplace_after(const_iterator prev,BOOST_FWD_REF (Args)...args)777 iterator emplace_after(const_iterator prev, BOOST_FWD_REF(Args)... args) 778 { 779 NodePtr pnode(AllocHolder::create_node(boost::forward<Args>(args)...)); 780 return iterator(this->icont().insert_after(prev.get(), *pnode)); 781 } 782 783 #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 784 785 #define BOOST_CONTAINER_SLIST_EMPLACE_CODE(N) \ 786 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 787 reference emplace_front(BOOST_MOVE_UREF##N)\ 788 { return *this->emplace_after(this->cbefore_begin() BOOST_MOVE_I##N BOOST_MOVE_FWD##N);}\ 789 \ 790 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 791 iterator emplace_after(const_iterator p BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ 792 {\ 793 NodePtr pnode (AllocHolder::create_node(BOOST_MOVE_FWD##N));\ 794 return iterator(this->icont().insert_after(p.get(), *pnode));\ 795 }\ 796 // 797 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_SLIST_EMPLACE_CODE) 798 #undef BOOST_CONTAINER_SLIST_EMPLACE_CODE 799 800 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 801 802 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 803 //! <b>Effects</b>: Inserts a copy of x at the beginning of the list. 804 //! 805 //! <b>Throws</b>: If memory allocation throws or 806 //! T's copy constructor throws. 807 //! 808 //! <b>Complexity</b>: Amortized constant time. 809 void push_front(const T &x); 810 811 //! <b>Effects</b>: Constructs a new element in the beginning of the list 812 //! and moves the resources of x to this new element. 813 //! 814 //! <b>Throws</b>: If memory allocation throws. 815 //! 816 //! <b>Complexity</b>: Amortized constant time. 817 void push_front(T &&x); 818 #else 819 BOOST_MOVE_CONVERSION_AWARE_CATCH(push_front, T, void, priv_push_front) 820 #endif 821 822 823 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 824 //! <b>Requires</b>: p must be a valid iterator of *this. 825 //! 826 //! <b>Effects</b>: Inserts a copy of the value after prev_p. 827 //! 828 //! <b>Returns</b>: An iterator to the inserted element. 829 //! 830 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws. 831 //! 832 //! <b>Complexity</b>: Amortized constant time. 833 //! 834 //! <b>Note</b>: Does not affect the validity of iterators and references of 835 //! previous values. 836 iterator insert_after(const_iterator prev_p, const T &x); 837 838 //! <b>Requires</b>: prev_p must be a valid iterator of *this. 839 //! 840 //! <b>Effects</b>: Inserts a move constructed copy object from the value after the 841 //! element pointed by prev_p. 842 //! 843 //! <b>Returns</b>: An iterator to the inserted element. 844 //! 845 //! <b>Throws</b>: If memory allocation throws. 846 //! 847 //! <b>Complexity</b>: Amortized constant time. 848 //! 849 //! <b>Note</b>: Does not affect the validity of iterators and references of 850 //! previous values. 851 iterator insert_after(const_iterator prev_p, T &&x); 852 #else BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert_after,T,iterator,priv_insert_after,const_iterator,const_iterator)853 BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert_after, T, iterator, priv_insert_after, const_iterator, const_iterator) 854 #endif 855 856 //! <b>Requires</b>: prev_p must be a valid iterator of *this. 857 //! 858 //! <b>Effects</b>: Inserts n copies of x after prev_p. 859 //! 860 //! <b>Returns</b>: an iterator to the last inserted element or prev_p if n is 0. 861 //! 862 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws. 863 //! 864 //! 865 //! <b>Complexity</b>: Linear to n. 866 //! 867 //! <b>Note</b>: Does not affect the validity of iterators and references of 868 //! previous values. 869 iterator insert_after(const_iterator prev_p, size_type n, const value_type& x) 870 { 871 typedef constant_iterator<value_type, difference_type> cvalue_iterator; 872 return this->insert_after(prev_p, cvalue_iterator(x, n), cvalue_iterator()); 873 } 874 875 //! <b>Requires</b>: prev_p must be a valid iterator of *this. 876 //! 877 //! <b>Effects</b>: Inserts the range pointed by [first, last) after prev_p. 878 //! 879 //! <b>Returns</b>: an iterator to the last inserted element or prev_p if first == last. 880 //! 881 //! <b>Throws</b>: If memory allocation throws, T's constructor from a 882 //! dereferenced InpIt throws. 883 //! 884 //! <b>Complexity</b>: Linear to the number of elements inserted. 885 //! 886 //! <b>Note</b>: Does not affect the validity of iterators and references of 887 //! previous values. 888 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)889 iterator insert_after(const_iterator prev_p, InpIt first, InpIt last 890 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 891 , typename dtl::enable_if_c 892 < !dtl::is_convertible<InpIt, size_type>::value 893 && (dtl::is_input_iterator<InpIt>::value 894 || dtl::is_same<alloc_version, version_1>::value 895 ) 896 >::type * = 0 897 #endif 898 ) 899 { 900 iterator ret_it(prev_p.get()); 901 for (; first != last; ++first){ 902 ret_it = iterator(this->icont().insert_after(ret_it.get(), *this->create_node_from_it(first))); 903 } 904 return ret_it; 905 } 906 907 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 908 //! <b>Requires</b>: prev_p must be a valid iterator of *this. 909 //! 910 //! <b>Effects</b>: Inserts the range pointed by [il.begin(), il.end()) after prev_p. 911 //! 912 //! <b>Returns</b>: an iterator to the last inserted element or prev_p if il.begin() == il.end(). 913 //! 914 //! <b>Throws</b>: If memory allocation throws, T's constructor from a 915 //! dereferenced std::initializer_list iterator throws. 916 //! 917 //! <b>Complexity</b>: Linear to the number of elements inserted. 918 //! 919 //! <b>Note</b>: Does not affect the validity of iterators and references of 920 //! previous values. insert_after(const_iterator prev_p,std::initializer_list<value_type> il)921 iterator insert_after(const_iterator prev_p, std::initializer_list<value_type> il) 922 { 923 return insert_after(prev_p, il.begin(), il.end()); 924 } 925 #endif 926 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 927 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)928 iterator insert_after(const_iterator prev, FwdIt first, FwdIt last 929 , typename dtl::enable_if_c 930 < !dtl::is_convertible<FwdIt, size_type>::value 931 && !(dtl::is_input_iterator<FwdIt>::value 932 || dtl::is_same<alloc_version, version_1>::value 933 ) 934 >::type * = 0 935 ) 936 { 937 //Optimized allocation and construction 938 insertion_functor func(this->icont(), prev.get()); 939 this->allocate_many_and_construct(first, boost::container::iterator_distance(first, last), func); 940 return iterator(func.inserted_first()); 941 } 942 #endif 943 944 //! <b>Effects</b>: Removes the first element from the list. 945 //! 946 //! <b>Throws</b>: Nothing. 947 //! 948 //! <b>Complexity</b>: Amortized constant time. pop_front()949 void pop_front() 950 { 951 BOOST_ASSERT(!this->empty()); 952 this->icont().pop_front_and_dispose(Destroyer(this->node_alloc())); 953 } 954 955 //! <b>Effects</b>: Erases the element after the element pointed by prev_p 956 //! of the list. 957 //! 958 //! <b>Returns</b>: the first element remaining beyond the removed elements, 959 //! or end() if no such element exists. 960 //! 961 //! <b>Throws</b>: Nothing. 962 //! 963 //! <b>Complexity</b>: Constant. 964 //! 965 //! <b>Note</b>: Does not invalidate iterators or references to non erased elements. erase_after(const_iterator prev_p)966 iterator erase_after(const_iterator prev_p) 967 { 968 return iterator(this->icont().erase_after_and_dispose(prev_p.get(), Destroyer(this->node_alloc()))); 969 } 970 971 //! <b>Effects</b>: Erases the range (before_first, last) from 972 //! the list. 973 //! 974 //! <b>Returns</b>: the first element remaining beyond the removed elements, 975 //! or end() if no such element exists. 976 //! 977 //! <b>Throws</b>: Nothing. 978 //! 979 //! <b>Complexity</b>: Linear to the number of erased elements. 980 //! 981 //! <b>Note</b>: Does not invalidate iterators or references to non erased elements. erase_after(const_iterator before_first,const_iterator last)982 iterator erase_after(const_iterator before_first, const_iterator last) 983 { 984 return iterator(this->icont().erase_after_and_dispose(before_first.get(), last.get(), Destroyer(this->node_alloc()))); 985 } 986 987 //! <b>Effects</b>: Swaps the contents of *this and x. 988 //! 989 //! <b>Throws</b>: Nothing. 990 //! 991 //! <b>Complexity</b>: Linear to the number of elements on *this and x. swap(slist & x)992 void swap(slist& x) 993 BOOST_NOEXCEPT_IF( allocator_traits_type::propagate_on_container_swap::value 994 || allocator_traits_type::is_always_equal::value) 995 { 996 BOOST_ASSERT(allocator_traits_type::propagate_on_container_swap::value || 997 allocator_traits_type::is_always_equal::value || 998 this->get_stored_allocator() == x.get_stored_allocator()); 999 AllocHolder::swap(x); 1000 } 1001 1002 //! <b>Effects</b>: Erases all the elements of the list. 1003 //! 1004 //! <b>Throws</b>: Nothing. 1005 //! 1006 //! <b>Complexity</b>: Linear to the number of elements in the list. clear()1007 void clear() 1008 { this->icont().clear_and_dispose(Destroyer(this->node_alloc())); } 1009 1010 ////////////////////////////////////////////// 1011 // 1012 // slist operations 1013 // 1014 ////////////////////////////////////////////// 1015 1016 //! <b>Requires</b>: p must point to an element contained 1017 //! by the list. x != *this 1018 //! 1019 //! <b>Effects</b>: Transfers all the elements of list x to this list, after the 1020 //! the element pointed by p. No destructors or copy constructors are called. 1021 //! 1022 //! <b>Throws</b>: std::runtime_error if this' allocator and x's allocator 1023 //! are not equal. 1024 //! 1025 //! <b>Complexity</b>: Linear to the elements in x. 1026 //! 1027 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of 1028 //! this list. Iterators of this list and all the references are not invalidated. splice_after(const_iterator prev_p,slist & x)1029 void splice_after(const_iterator prev_p, slist& x) BOOST_NOEXCEPT_OR_NOTHROW 1030 { 1031 BOOST_ASSERT(this != &x); 1032 BOOST_ASSERT(this->node_alloc() == x.node_alloc()); 1033 this->icont().splice_after(prev_p.get(), x.icont()); 1034 } 1035 1036 //! <b>Requires</b>: p must point to an element contained 1037 //! by the list. x != *this 1038 //! 1039 //! <b>Effects</b>: Transfers all the elements of list x to this list, after the 1040 //! the element pointed by p. No destructors or copy constructors are called. 1041 //! 1042 //! <b>Throws</b>: std::runtime_error if this' allocator and x's allocator 1043 //! are not equal. 1044 //! 1045 //! <b>Complexity</b>: Linear to the elements in x. 1046 //! 1047 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of 1048 //! this list. Iterators of this list and all the references are not invalidated. splice_after(const_iterator prev_p,BOOST_RV_REF (slist)x)1049 void splice_after(const_iterator prev_p, BOOST_RV_REF(slist) x) BOOST_NOEXCEPT_OR_NOTHROW 1050 { this->splice_after(prev_p, static_cast<slist&>(x)); } 1051 1052 //! <b>Requires</b>: prev_p must be a valid iterator of this. 1053 //! i must point to an element contained in list x. 1054 //! this' allocator and x's allocator shall compare equal. 1055 //! 1056 //! <b>Effects</b>: Transfers the value pointed by i, from list x to this list, 1057 //! after the element pointed by prev_p. 1058 //! If prev_p == prev or prev_p == ++prev, this function is a null operation. 1059 //! 1060 //! <b>Throws</b>: Nothing 1061 //! 1062 //! <b>Complexity</b>: Constant. 1063 //! 1064 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this 1065 //! list. Iterators of this list and all the references are not invalidated. splice_after(const_iterator prev_p,slist & x,const_iterator prev)1066 void splice_after(const_iterator prev_p, slist& x, const_iterator prev) BOOST_NOEXCEPT_OR_NOTHROW 1067 { 1068 BOOST_ASSERT(this->node_alloc() == x.node_alloc()); 1069 this->icont().splice_after(prev_p.get(), x.icont(), prev.get()); 1070 } 1071 1072 //! <b>Requires</b>: prev_p must be a valid iterator of this. 1073 //! i must point to an element contained in list x. 1074 //! this' allocator and x's allocator shall compare equal. 1075 //! 1076 //! <b>Effects</b>: Transfers the value pointed by i, from list x to this list, 1077 //! after the element pointed by prev_p. 1078 //! If prev_p == prev or prev_p == ++prev, this function is a null operation. 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. splice_after(const_iterator prev_p,BOOST_RV_REF (slist)x,const_iterator prev)1086 void splice_after(const_iterator prev_p, BOOST_RV_REF(slist) x, const_iterator prev) BOOST_NOEXCEPT_OR_NOTHROW 1087 { this->splice_after(prev_p, static_cast<slist&>(x), prev); } 1088 1089 //! <b>Requires</b>: prev_p must be a valid iterator of this. 1090 //! before_first and before_last must be valid iterators of x. 1091 //! prev_p must not be contained in [before_first, before_last) range. 1092 //! this' allocator and x's allocator shall compare equal. 1093 //! 1094 //! <b>Effects</b>: Transfers the range [before_first + 1, before_last + 1) 1095 //! from list x to this list, after the element pointed by prev_p. 1096 //! 1097 //! <b>Throws</b>: Nothing 1098 //! 1099 //! <b>Complexity</b>: Linear to the number of transferred elements. 1100 //! 1101 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this 1102 //! 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)1103 void splice_after(const_iterator prev_p, slist& x, 1104 const_iterator before_first, const_iterator before_last) BOOST_NOEXCEPT_OR_NOTHROW 1105 { 1106 BOOST_ASSERT(this->node_alloc() == x.node_alloc()); 1107 this->icont().splice_after 1108 (prev_p.get(), x.icont(), before_first.get(), before_last.get()); 1109 } 1110 1111 //! <b>Requires</b>: prev_p must be a valid iterator of this. 1112 //! before_first and before_last must be valid iterators of x. 1113 //! prev_p must not be contained in [before_first, before_last) range. 1114 //! this' allocator and x's allocator shall compare equal. 1115 //! 1116 //! <b>Effects</b>: Transfers the range [before_first + 1, before_last + 1) 1117 //! from list x to this list, after the element pointed by prev_p. 1118 //! 1119 //! <b>Throws</b>: Nothing 1120 //! 1121 //! <b>Complexity</b>: Linear to the number of transferred elements. 1122 //! 1123 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this 1124 //! 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)1125 void splice_after(const_iterator prev_p, BOOST_RV_REF(slist) x, 1126 const_iterator before_first, const_iterator before_last) BOOST_NOEXCEPT_OR_NOTHROW 1127 { this->splice_after(prev_p, static_cast<slist&>(x), before_first, before_last); } 1128 1129 //! <b>Requires</b>: prev_p must be a valid iterator of this. 1130 //! before_first and before_last must be valid iterators of x. 1131 //! prev_p must not be contained in [before_first, before_last) range. 1132 //! n == distance(before_first, before_last). 1133 //! this' allocator and x's allocator shall compare equal. 1134 //! 1135 //! <b>Effects</b>: Transfers the range [before_first + 1, before_last + 1) 1136 //! from list x to this list, after the element pointed by prev_p. 1137 //! 1138 //! <b>Throws</b>: Nothing 1139 //! 1140 //! <b>Complexity</b>: Constant. 1141 //! 1142 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this 1143 //! 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)1144 void splice_after(const_iterator prev_p, slist& x, 1145 const_iterator before_first, const_iterator before_last, 1146 size_type n) BOOST_NOEXCEPT_OR_NOTHROW 1147 { 1148 BOOST_ASSERT(this->node_alloc() == x.node_alloc()); 1149 this->icont().splice_after 1150 (prev_p.get(), x.icont(), before_first.get(), before_last.get(), n); 1151 } 1152 1153 //! <b>Requires</b>: prev_p must be a valid iterator of this. 1154 //! before_first and before_last must be valid iterators of x. 1155 //! prev_p must not be contained in [before_first, before_last) range. 1156 //! n == distance(before_first, before_last). 1157 //! this' allocator and x's allocator shall compare equal. 1158 //! 1159 //! <b>Effects</b>: Transfers the range [before_first + 1, before_last + 1) 1160 //! from list x to this list, after the element pointed by prev_p. 1161 //! 1162 //! <b>Throws</b>: Nothing 1163 //! 1164 //! <b>Complexity</b>: Constant. 1165 //! 1166 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this 1167 //! 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)1168 void splice_after(const_iterator prev_p, BOOST_RV_REF(slist) x, 1169 const_iterator before_first, const_iterator before_last, 1170 size_type n) BOOST_NOEXCEPT_OR_NOTHROW 1171 { this->splice_after(prev_p, static_cast<slist&>(x), before_first, before_last, n); } 1172 1173 //! <b>Effects</b>: Removes all the elements that compare equal to value. 1174 //! 1175 //! <b>Throws</b>: Nothing. 1176 //! 1177 //! <b>Complexity</b>: Linear time. It performs exactly size() comparisons for equality. 1178 //! 1179 //! <b>Note</b>: The relative order of elements that are not removed is unchanged, 1180 //! and iterators to elements that are not removed remain valid. remove(const T & value)1181 void remove(const T& value) 1182 { this->remove_if(equal_to_value_type(value)); } 1183 1184 //! <b>Effects</b>: Removes all the elements for which a specified 1185 //! predicate is satisfied. 1186 //! 1187 //! <b>Throws</b>: If pred throws. 1188 //! 1189 //! <b>Complexity</b>: Linear time. It performs exactly size() calls to the predicate. 1190 //! 1191 //! <b>Note</b>: The relative order of elements that are not removed is unchanged, 1192 //! and iterators to elements that are not removed remain valid. 1193 template <class Pred> remove_if(Pred pred)1194 void remove_if(Pred pred) 1195 { 1196 typedef value_to_node_compare<Node, Pred> value_to_node_compare_type; 1197 this->icont().remove_and_dispose_if(value_to_node_compare_type(pred), Destroyer(this->node_alloc())); 1198 } 1199 1200 //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent 1201 //! elements that are equal from the list. 1202 //! 1203 //! <b>Throws</b>: If comparison throws. 1204 //! 1205 //! <b>Complexity</b>: Linear time (size()-1 comparisons equality comparisons). 1206 //! 1207 //! <b>Note</b>: The relative order of elements that are not removed is unchanged, 1208 //! and iterators to elements that are not removed remain valid. unique()1209 void unique() 1210 { this->unique(value_equal_t()); } 1211 1212 //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent 1213 //! elements that satisfy some binary predicate from the list. 1214 //! 1215 //! <b>Throws</b>: If pred throws. 1216 //! 1217 //! <b>Complexity</b>: Linear time (size()-1 comparisons calls to pred()). 1218 //! 1219 //! <b>Note</b>: The relative order of elements that are not removed is unchanged, 1220 //! and iterators to elements that are not removed remain valid. 1221 template <class Pred> unique(Pred pred)1222 void unique(Pred pred) 1223 { 1224 typedef value_to_node_compare<Node, Pred> value_to_node_compare_type; 1225 this->icont().unique_and_dispose(value_to_node_compare_type(pred), Destroyer(this->node_alloc())); 1226 } 1227 1228 //! <b>Requires</b>: The lists x and *this must be distinct. 1229 //! 1230 //! <b>Effects</b>: This function removes all of x's elements and inserts them 1231 //! in order into *this according to std::less<value_type>. The merge is stable; 1232 //! that is, if an element from *this is equivalent to one from x, then the element 1233 //! from *this will precede the one from x. 1234 //! 1235 //! <b>Throws</b>: If comparison throws. 1236 //! 1237 //! <b>Complexity</b>: This function is linear time: it performs at most 1238 //! size() + x.size() - 1 comparisons. merge(slist & x)1239 void merge(slist & x) 1240 { this->merge(x, value_less_t()); } 1241 1242 //! <b>Requires</b>: The lists x and *this must be distinct. 1243 //! 1244 //! <b>Effects</b>: This function removes all of x's elements and inserts them 1245 //! in order into *this according to std::less<value_type>. The merge is stable; 1246 //! that is, if an element from *this is equivalent to one from x, then the element 1247 //! from *this will precede the one from x. 1248 //! 1249 //! <b>Throws</b>: If comparison throws. 1250 //! 1251 //! <b>Complexity</b>: This function is linear time: it performs at most 1252 //! size() + x.size() - 1 comparisons. merge(BOOST_RV_REF (slist)x)1253 void merge(BOOST_RV_REF(slist) x) 1254 { this->merge(static_cast<slist&>(x)); } 1255 1256 //! <b>Requires</b>: p must be a comparison function that induces a strict weak 1257 //! ordering and both *this and x must be sorted according to that ordering 1258 //! The lists x and *this must be distinct. 1259 //! 1260 //! <b>Effects</b>: This function removes all of x's elements and inserts them 1261 //! in order into *this. The merge is stable; that is, if an element from *this is 1262 //! equivalent to one from x, then the element from *this will precede the one from x. 1263 //! 1264 //! <b>Throws</b>: If comp throws. 1265 //! 1266 //! <b>Complexity</b>: This function is linear time: it performs at most 1267 //! size() + x.size() - 1 comparisons. 1268 //! 1269 //! <b>Note</b>: Iterators and references to *this are not invalidated. 1270 template <class StrictWeakOrdering> merge(slist & x,StrictWeakOrdering comp)1271 void merge(slist& x, StrictWeakOrdering comp) 1272 { 1273 typedef value_to_node_compare<Node, StrictWeakOrdering> value_to_node_compare_type; 1274 BOOST_ASSERT(this->node_alloc() == x.node_alloc()); 1275 this->icont().merge(x.icont(), value_to_node_compare_type(comp)); 1276 } 1277 1278 //! <b>Requires</b>: p must be a comparison function that induces a strict weak 1279 //! ordering and both *this and x must be sorted according to that ordering 1280 //! The lists x and *this must be distinct. 1281 //! 1282 //! <b>Effects</b>: This function removes all of x's elements and inserts them 1283 //! in order into *this. The merge is stable; that is, if an element from *this is 1284 //! equivalent to one from x, then the element from *this will precede the one from x. 1285 //! 1286 //! <b>Throws</b>: If comp throws. 1287 //! 1288 //! <b>Complexity</b>: This function is linear time: it performs at most 1289 //! size() + x.size() - 1 comparisons. 1290 //! 1291 //! <b>Note</b>: Iterators and references to *this are not invalidated. 1292 template <class StrictWeakOrdering> merge(BOOST_RV_REF (slist)x,StrictWeakOrdering comp)1293 void merge(BOOST_RV_REF(slist) x, StrictWeakOrdering comp) 1294 { this->merge(static_cast<slist&>(x), comp); } 1295 1296 //! <b>Effects</b>: This function sorts the list *this according to std::less<value_type>. 1297 //! The sort is stable, that is, the relative order of equivalent elements is preserved. 1298 //! 1299 //! <b>Throws</b>: If comparison throws. 1300 //! 1301 //! <b>Notes</b>: Iterators and references are not invalidated. 1302 //! 1303 //! <b>Complexity</b>: The number of comparisons is approximately N log N, where N 1304 //! is the list's size. sort()1305 void sort() 1306 { this->sort(value_less_t()); } 1307 1308 //! <b>Effects</b>: This function sorts the list *this according to std::less<value_type>. 1309 //! The sort is stable, that is, the relative order of equivalent elements is preserved. 1310 //! 1311 //! <b>Throws</b>: If comp throws. 1312 //! 1313 //! <b>Notes</b>: Iterators and references are not invalidated. 1314 //! 1315 //! <b>Complexity</b>: The number of comparisons is approximately N log N, where N 1316 //! is the list's size. 1317 template <class StrictWeakOrdering> sort(StrictWeakOrdering comp)1318 void sort(StrictWeakOrdering comp) 1319 { 1320 typedef value_to_node_compare<Node, StrictWeakOrdering> value_to_node_compare_type; 1321 // nothing if the slist has length 0 or 1. 1322 if (this->size() < 2) 1323 return; 1324 this->icont().sort(value_to_node_compare_type(comp)); 1325 } 1326 1327 //! <b>Effects</b>: Reverses the order of elements in the list. 1328 //! 1329 //! <b>Throws</b>: Nothing. 1330 //! 1331 //! <b>Complexity</b>: This function is linear time. 1332 //! 1333 //! <b>Note</b>: Iterators and references are not invalidated reverse()1334 void reverse() BOOST_NOEXCEPT_OR_NOTHROW 1335 { this->icont().reverse(); } 1336 1337 ////////////////////////////////////////////// 1338 // 1339 // list compatibility interface 1340 // 1341 ////////////////////////////////////////////// 1342 1343 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1344 1345 //! <b>Effects</b>: Inserts an object of type T constructed with 1346 //! std::forward<Args>(args)... before p 1347 //! 1348 //! <b>Throws</b>: If memory allocation throws or 1349 //! T's in-place constructor throws. 1350 //! 1351 //! <b>Complexity</b>: Linear to the elements before p 1352 template <class... Args> emplace(const_iterator p,BOOST_FWD_REF (Args)...args)1353 iterator emplace(const_iterator p, BOOST_FWD_REF(Args)... args) 1354 { return this->emplace_after(this->previous(p), boost::forward<Args>(args)...); } 1355 1356 #else 1357 1358 #define BOOST_CONTAINER_SLIST_EMPLACE_CODE(N) \ 1359 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 1360 iterator emplace(const_iterator p BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ 1361 {\ 1362 return this->emplace_after(this->previous(p) BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ 1363 }\ 1364 // 1365 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_SLIST_EMPLACE_CODE) 1366 #undef BOOST_CONTAINER_SLIST_EMPLACE_CODE 1367 1368 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 1369 1370 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1371 //! <b>Requires</b>: p must be a valid iterator of *this. 1372 //! 1373 //! <b>Effects</b>: Insert a copy of x before p. 1374 //! 1375 //! <b>Returns</b>: an iterator to the inserted element. 1376 //! 1377 //! <b>Throws</b>: If memory allocation throws or x's copy constructor throws. 1378 //! 1379 //! <b>Complexity</b>: Linear to the elements before p. 1380 iterator insert(const_iterator p, const T &x); 1381 1382 //! <b>Requires</b>: p must be a valid iterator of *this. 1383 //! 1384 //! <b>Effects</b>: Insert a new element before p with x's resources. 1385 //! 1386 //! <b>Returns</b>: an iterator to the inserted element. 1387 //! 1388 //! <b>Throws</b>: If memory allocation throws. 1389 //! 1390 //! <b>Complexity</b>: Linear to the elements before p. 1391 iterator insert(const_iterator prev_p, T &&x); 1392 #else 1393 BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, T, iterator, priv_insert, const_iterator, const_iterator) 1394 #endif 1395 1396 //! <b>Requires</b>: p must be a valid iterator of *this. 1397 //! 1398 //! <b>Effects</b>: Inserts n copies of x before p. 1399 //! 1400 //! <b>Returns</b>: an iterator to the first inserted element or p if n == 0. 1401 //! 1402 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws. 1403 //! 1404 //! <b>Complexity</b>: Linear to n plus linear to the elements before p. insert(const_iterator p,size_type n,const value_type & x)1405 iterator insert(const_iterator p, size_type n, const value_type& x) 1406 { 1407 const_iterator prev(this->previous(p)); 1408 this->insert_after(prev, n, x); 1409 return ++iterator(prev.get()); 1410 } 1411 1412 //! <b>Requires</b>: p must be a valid iterator of *this. 1413 //! 1414 //! <b>Effects</b>: Insert a copy of the [first, last) range before p. 1415 //! 1416 //! <b>Returns</b>: an iterator to the first inserted element or p if first == last. 1417 //! 1418 //! <b>Throws</b>: If memory allocation throws, T's constructor from a 1419 //! dereferenced InpIt throws. 1420 //! 1421 //! <b>Complexity</b>: Linear to distance [first, last) plus 1422 //! linear to the elements before p. 1423 template <class InIter> insert(const_iterator p,InIter first,InIter last)1424 iterator insert(const_iterator p, InIter first, InIter last) 1425 { 1426 const_iterator prev(this->previous(p)); 1427 this->insert_after(prev, first, last); 1428 return ++iterator(prev.get()); 1429 } 1430 1431 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 1432 //! <b>Requires</b>: p must be a valid iterator of *this. 1433 //! 1434 //! <b>Effects</b>: Insert a copy of the [il.begin(), il.end()) range before p. 1435 //! 1436 //! <b>Returns</b>: an iterator to the first inserted element or p if il.begin() == il.end(). 1437 //! 1438 //! <b>Throws</b>: If memory allocation throws, T's constructor from a 1439 //! dereferenced std::initializer_list iterator throws. 1440 //! 1441 //! <b>Complexity</b>: Linear to the range [il.begin(), il.end()) plus 1442 //! linear to the elements before p. insert(const_iterator p,std::initializer_list<value_type> il)1443 iterator insert(const_iterator p, std::initializer_list<value_type> il) 1444 { 1445 return insert(p, il.begin(), il.end()); 1446 } 1447 #endif 1448 1449 //! <b>Requires</b>: p must be a valid iterator of *this. 1450 //! 1451 //! <b>Effects</b>: Erases the element at p. 1452 //! 1453 //! <b>Throws</b>: Nothing. 1454 //! 1455 //! <b>Complexity</b>: Linear to the number of elements before p. erase(const_iterator p)1456 iterator erase(const_iterator p) BOOST_NOEXCEPT_OR_NOTHROW 1457 { return iterator(this->erase_after(previous(p))); } 1458 1459 //! <b>Requires</b>: first and last must be valid iterator to elements in *this. 1460 //! 1461 //! <b>Effects</b>: Erases the elements pointed by [first, last). 1462 //! 1463 //! <b>Throws</b>: Nothing. 1464 //! 1465 //! <b>Complexity</b>: Linear to the distance between first and last plus 1466 //! linear to the elements before first. erase(const_iterator first,const_iterator last)1467 iterator erase(const_iterator first, const_iterator last) BOOST_NOEXCEPT_OR_NOTHROW 1468 { return iterator(this->erase_after(previous(first), last)); } 1469 1470 //! <b>Requires</b>: p must point to an element contained 1471 //! by the list. x != *this. this' allocator and x's allocator shall compare equal 1472 //! 1473 //! <b>Effects</b>: Transfers all the elements of list x to this list, before the 1474 //! the element pointed by p. No destructors or copy constructors are called. 1475 //! 1476 //! <b>Throws</b>: Nothing 1477 //! 1478 //! <b>Complexity</b>: Linear in distance(begin(), p), and linear in x.size(). 1479 //! 1480 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of 1481 //! this list. Iterators of this list and all the references are not invalidated. splice(const_iterator p,slist & x)1482 void splice(const_iterator p, slist& x) BOOST_NOEXCEPT_OR_NOTHROW 1483 { this->splice_after(this->previous(p), x); } 1484 1485 //! <b>Requires</b>: p must point to an element contained 1486 //! by the list. x != *this. this' allocator and x's allocator shall compare equal 1487 //! 1488 //! <b>Effects</b>: Transfers all the elements of list x to this list, before the 1489 //! the element pointed by p. No destructors or copy constructors are called. 1490 //! 1491 //! <b>Throws</b>: Nothing 1492 //! 1493 //! <b>Complexity</b>: Linear in distance(begin(), p), and linear in x.size(). 1494 //! 1495 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of 1496 //! this list. Iterators of this list and all the references are not invalidated. splice(const_iterator p,BOOST_RV_REF (slist)x)1497 void splice(const_iterator p, BOOST_RV_REF(slist) x) BOOST_NOEXCEPT_OR_NOTHROW 1498 { this->splice(p, static_cast<slist&>(x)); } 1499 1500 //! <b>Requires</b>: p must point to an element contained 1501 //! by this list. i must point to an element contained in list x. 1502 //! this' allocator and x's allocator shall compare equal 1503 //! 1504 //! <b>Effects</b>: Transfers the value pointed by i, from list x to this list, 1505 //! before the element pointed by p. No destructors or copy constructors are called. 1506 //! If p == i or p == ++i, this function is a null operation. 1507 //! 1508 //! <b>Throws</b>: Nothing 1509 //! 1510 //! <b>Complexity</b>: Linear in distance(begin(), p), and in distance(x.begin(), i). 1511 //! 1512 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this 1513 //! list. Iterators of this list and all the references are not invalidated. splice(const_iterator p,slist & x,const_iterator i)1514 void splice(const_iterator p, slist& x, const_iterator i) BOOST_NOEXCEPT_OR_NOTHROW 1515 { this->splice_after(this->previous(p), x, x.previous(i)); } 1516 1517 //! <b>Requires</b>: p must point to an element contained 1518 //! by this list. i must point to an element contained in list x. 1519 //! this' allocator and x's allocator shall compare equal. 1520 //! 1521 //! <b>Effects</b>: Transfers the value pointed by i, from list x to this list, 1522 //! before the element pointed by p. No destructors or copy constructors are called. 1523 //! If p == i or p == ++i, this function is a null operation. 1524 //! 1525 //! <b>Throws</b>: Nothing 1526 //! 1527 //! <b>Complexity</b>: Linear in distance(begin(), p), and in distance(x.begin(), i). 1528 //! 1529 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this 1530 //! list. Iterators of this list and all the references are not invalidated. splice(const_iterator p,BOOST_RV_REF (slist)x,const_iterator i)1531 void splice(const_iterator p, BOOST_RV_REF(slist) x, const_iterator i) BOOST_NOEXCEPT_OR_NOTHROW 1532 { this->splice(p, static_cast<slist&>(x), i); } 1533 1534 //! <b>Requires</b>: p must point to an element contained 1535 //! by this list. first and last must point to elements contained in list x. 1536 //! 1537 //! <b>Effects</b>: Transfers the range pointed by first and last from list x to this list, 1538 //! before the element pointed by p. No destructors or copy constructors are called. 1539 //! this' allocator and x's allocator shall compare equal. 1540 //! 1541 //! <b>Throws</b>: Nothing 1542 //! 1543 //! <b>Complexity</b>: Linear in distance(begin(), p), in distance(x.begin(), first), 1544 //! and in distance(first, last). 1545 //! 1546 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this 1547 //! list. Iterators of this list and all the references are not invalidated. splice(const_iterator p,slist & x,const_iterator first,const_iterator last)1548 void splice(const_iterator p, slist& x, const_iterator first, const_iterator last) BOOST_NOEXCEPT_OR_NOTHROW 1549 { this->splice_after(this->previous(p), x, x.previous(first), x.previous(last)); } 1550 1551 //! <b>Requires</b>: p must point to an element contained 1552 //! by this list. first and last must point to elements contained in list x. 1553 //! this' allocator and x's allocator shall compare equal 1554 //! 1555 //! <b>Effects</b>: Transfers the range pointed by first and last from list x to this list, 1556 //! before the element pointed by p. No destructors or copy constructors are called. 1557 //! 1558 //! <b>Throws</b>: Nothing 1559 //! 1560 //! <b>Complexity</b>: Linear in distance(begin(), p), in distance(x.begin(), first), 1561 //! and in distance(first, last). 1562 //! 1563 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this 1564 //! 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)1565 void splice(const_iterator p, BOOST_RV_REF(slist) x, const_iterator first, const_iterator last) BOOST_NOEXCEPT_OR_NOTHROW 1566 { this->splice(p, static_cast<slist&>(x), first, last); } 1567 1568 //! <b>Effects</b>: Returns true if x and y are equal 1569 //! 1570 //! <b>Complexity</b>: Linear to the number of elements in the container. operator ==(const slist & x,const slist & y)1571 friend bool operator==(const slist& x, const slist& y) 1572 { return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin()); } 1573 1574 //! <b>Effects</b>: Returns true if x and y are unequal 1575 //! 1576 //! <b>Complexity</b>: Linear to the number of elements in the container. operator !=(const slist & x,const slist & y)1577 friend bool operator!=(const slist& x, const slist& y) 1578 { return !(x == y); } 1579 1580 //! <b>Effects</b>: Returns true if x is less than y 1581 //! 1582 //! <b>Complexity</b>: Linear to the number of elements in the container. operator <(const slist & x,const slist & y)1583 friend bool operator<(const slist& x, const slist& y) 1584 { return ::boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); } 1585 1586 //! <b>Effects</b>: Returns true if x is greater than y 1587 //! 1588 //! <b>Complexity</b>: Linear to the number of elements in the container. operator >(const slist & x,const slist & y)1589 friend bool operator>(const slist& x, const slist& y) 1590 { return y < x; } 1591 1592 //! <b>Effects</b>: Returns true if x is equal or less than y 1593 //! 1594 //! <b>Complexity</b>: Linear to the number of elements in the container. operator <=(const slist & x,const slist & y)1595 friend bool operator<=(const slist& x, const slist& y) 1596 { return !(y < x); } 1597 1598 //! <b>Effects</b>: Returns true if x is equal or greater than y 1599 //! 1600 //! <b>Complexity</b>: Linear to the number of elements in the container. operator >=(const slist & x,const slist & y)1601 friend bool operator>=(const slist& x, const slist& y) 1602 { return !(x < y); } 1603 1604 //! <b>Effects</b>: x.swap(y) 1605 //! 1606 //! <b>Complexity</b>: Constant. swap(slist & x,slist & y)1607 friend void swap(slist& x, slist& y) 1608 { x.swap(y); } 1609 1610 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 1611 private: 1612 priv_push_front(const T & x)1613 void priv_push_front (const T &x) 1614 { this->insert_after(this->cbefore_begin(), x); } 1615 priv_push_front(BOOST_RV_REF (T)x)1616 void priv_push_front (BOOST_RV_REF(T) x) 1617 { this->insert_after(this->cbefore_begin(), ::boost::move(x)); } 1618 priv_try_shrink(size_type new_size,const_iterator & last_pos)1619 bool priv_try_shrink(size_type new_size, const_iterator &last_pos) 1620 { 1621 typename Icont::iterator end_n(this->icont().end()), cur(this->icont().before_begin()), cur_next; 1622 while (++(cur_next = cur) != end_n && new_size > 0){ 1623 --new_size; 1624 cur = cur_next; 1625 } 1626 last_pos = const_iterator(cur); 1627 if (cur_next != end_n){ 1628 this->erase_after(last_pos, const_iterator(end_n)); 1629 return true; 1630 } 1631 else{ 1632 return false; 1633 } 1634 } 1635 1636 template<class U> priv_insert(const_iterator p,BOOST_FWD_REF (U)x)1637 iterator priv_insert(const_iterator p, BOOST_FWD_REF(U) x) 1638 { return this->insert_after(previous(p), ::boost::forward<U>(x)); } 1639 1640 template<class U> priv_insert_after(const_iterator prev_p,BOOST_FWD_REF (U)x)1641 iterator priv_insert_after(const_iterator prev_p, BOOST_FWD_REF(U) x) 1642 { return iterator(this->icont().insert_after(prev_p.get(), *this->create_node(::boost::forward<U>(x)))); } 1643 1644 class insertion_functor; 1645 friend class insertion_functor; 1646 1647 class insertion_functor 1648 { 1649 Icont &icont_; 1650 typedef typename Icont::iterator iiterator; 1651 typedef typename Icont::const_iterator iconst_iterator; 1652 const iconst_iterator prev_; 1653 iiterator ret_; 1654 1655 public: insertion_functor(Icont & icont,typename Icont::const_iterator prev)1656 insertion_functor(Icont &icont, typename Icont::const_iterator prev) 1657 : icont_(icont), prev_(prev), ret_(prev.unconst()) 1658 {} 1659 operator ()(Node & n)1660 void operator()(Node &n) 1661 { 1662 ret_ = this->icont_.insert_after(prev_, n); 1663 } 1664 inserted_first() const1665 iiterator inserted_first() const 1666 { return ret_; } 1667 }; 1668 1669 //Functors for member algorithm defaults 1670 typedef value_less<value_type> value_less_t; 1671 typedef value_equal<value_type> value_equal_t; 1672 1673 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 1674 }; 1675 1676 #ifndef BOOST_CONTAINER_NO_CXX17_CTAD 1677 1678 template <typename InpIt> 1679 slist(InpIt, InpIt) -> 1680 slist<typename iterator_traits<InpIt>::value_type>; 1681 1682 template <typename InpIt, typename Allocator> 1683 slist(InpIt, InpIt, Allocator const&) -> 1684 slist<typename iterator_traits<InpIt>::value_type, Allocator>; 1685 1686 #endif 1687 1688 }} 1689 1690 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 1691 1692 namespace boost { 1693 1694 //!has_trivial_destructor_after_move<> == true_type 1695 //!specialization for optimizations 1696 template <class T, class Allocator> 1697 struct has_trivial_destructor_after_move<boost::container::slist<T, Allocator> > 1698 { 1699 typedef typename boost::container::slist<T, Allocator>::allocator_type allocator_type; 1700 typedef typename ::boost::container::allocator_traits<allocator_type>::pointer pointer; 1701 static const bool value = ::boost::has_trivial_destructor_after_move<allocator_type>::value && 1702 ::boost::has_trivial_destructor_after_move<pointer>::value; 1703 }; 1704 1705 namespace container { 1706 1707 }} //namespace boost{ namespace container { 1708 1709 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 1710 1711 // Specialization of insert_iterator so that insertions will be constant 1712 // time rather than linear time. 1713 1714 #include <boost/move/detail/std_ns_begin.hpp> 1715 BOOST_CONTAINER_DOC1ST(namespace std {, BOOST_MOVE_STD_NS_BEG) 1716 1717 //! A specialization of insert_iterator 1718 //! that works with slist 1719 template <class T, class ValueAllocator> 1720 class insert_iterator<boost::container::slist<T, ValueAllocator> > 1721 { 1722 private: 1723 typedef boost::container::slist<T, ValueAllocator> Container; 1724 Container* container; 1725 typename Container::iterator iter; 1726 1727 public: 1728 typedef Container container_type; 1729 typedef output_iterator_tag iterator_category; 1730 typedef void value_type; 1731 typedef void difference_type; 1732 typedef void pointer; 1733 typedef void reference; 1734 1735 insert_iterator(Container& x, 1736 typename Container::iterator i, 1737 bool is_previous = false) 1738 : container(&x), iter(is_previous ? i : x.previous(i)){ } 1739 1740 insert_iterator<Container>& 1741 operator=(const typename Container::value_type& value) 1742 { 1743 iter = container->insert_after(iter, value); 1744 return *this; 1745 } 1746 insert_iterator<Container>& operator*(){ return *this; } 1747 insert_iterator<Container>& operator++(){ return *this; } 1748 insert_iterator<Container>& operator++(int){ return *this; } 1749 }; 1750 1751 BOOST_CONTAINER_DOC1ST( }, BOOST_MOVE_STD_NS_END) 1752 #include <boost/move/detail/std_ns_end.hpp> 1753 1754 #include <boost/container/detail/config_end.hpp> 1755 1756 #endif // BOOST_CONTAINER_SLIST_HPP 1757