1 //////////////////////////////////////////////////////////////////////////////
3 // (C) Copyright Ion Gaztanaga 2005-2015. Distributed under the Boost
4 // Software License, Version 1.0. (See accompanying file
5 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
7 // See http://www.boost.org/libs/container for documentation.
9 //////////////////////////////////////////////////////////////////////////////
10 #ifndef BOOST_CONTAINER_LIST_HPP
11 #define BOOST_CONTAINER_LIST_HPP
13 #ifndef BOOST_CONFIG_HPP
14 # include <boost/config.hpp>
17 #if defined(BOOST_HAS_PRAGMA_ONCE)
21 #include <boost/container/detail/config_begin.hpp>
22 #include <boost/container/detail/workaround.hpp>
25 #include <boost/container/container_fwd.hpp>
26 #include <boost/container/new_allocator.hpp> //new_allocator
27 #include <boost/container/throw_exception.hpp>
29 #include <boost/container/detail/algorithm.hpp>
30 #include <boost/container/detail/compare_functors.hpp>
31 #include <boost/container/detail/iterator.hpp>
32 #include <boost/container/detail/iterators.hpp>
33 #include <boost/container/detail/mpl.hpp>
34 #include <boost/container/detail/node_alloc_holder.hpp>
35 #include <boost/container/detail/version_type.hpp>
37 #include <boost/move/utility_core.hpp>
38 #include <boost/move/iterator.hpp>
39 #include <boost/move/traits.hpp>
41 #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
42 # include <boost/move/detail/fwd_macros.hpp>
44 #include <boost/move/detail/move_helpers.hpp>
47 #include <boost/intrusive/pointer_traits.hpp>
48 #include <boost/intrusive/list.hpp>
50 #include <boost/assert.hpp>
52 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
53 #include <initializer_list>
59 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
60 namespace container_detail {
62 template<class VoidPointer>
65 typedef typename container_detail::bi::make_list_base_hook
66 <container_detail::bi::void_pointer<VoidPointer>, container_detail::bi::link_mode<container_detail::bi::normal_link> >::type type;
69 template <class T, class VoidPointer>
71 : public list_hook<VoidPointer>::type
78 typedef typename list_hook<VoidPointer>::type hook_type;
83 { return this->m_data; }
85 const T &get_data() const
86 { return this->m_data; }
89 template <class T, class VoidPointer>
90 struct iiterator_node_value_type< list_node<T,VoidPointer> > {
94 template<class Allocator>
95 struct intrusive_list_type
97 typedef boost::container::allocator_traits<Allocator> allocator_traits_type;
98 typedef typename allocator_traits_type::value_type value_type;
99 typedef typename boost::intrusive::pointer_traits
100 <typename allocator_traits_type::pointer>::template
101 rebind_pointer<void>::type
103 typedef typename container_detail::list_node
104 <value_type, void_pointer> node_type;
105 typedef typename container_detail::bi::make_list
107 , container_detail::bi::base_hook<typename list_hook<void_pointer>::type>
108 , container_detail::bi::constant_time_size<true>
109 , container_detail::bi::size_type
110 <typename allocator_traits_type::size_type>
111 >::type container_type;
112 typedef container_type type ;
115 } //namespace container_detail {
116 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
118 //! A list is a doubly linked list. That is, it is a Sequence that supports both
119 //! forward and backward traversal, and (amortized) constant time insertion and
120 //! removal of elements at the beginning or the end, or in the middle. Lists have
121 //! the important property that insertion and splicing do not invalidate iterators
122 //! to list elements, and that even removal invalidates only the iterators that point
123 //! to the elements that are removed. The ordering of iterators may be changed
124 //! (that is, list<T>::iterator might have a different predecessor or successor
125 //! after a list operation than it did before), but the iterators themselves will
126 //! not be invalidated or made to point to different elements unless that invalidation
127 //! or mutation is explicit.
129 //! \tparam T The type of object that is stored in the list
130 //! \tparam Allocator The allocator used for all internal memory management
131 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
132 template <class T, class Allocator = new_allocator<T> >
134 template <class T, class Allocator>
137 : protected container_detail::node_alloc_holder
138 <Allocator, typename container_detail::intrusive_list_type<Allocator>::type>
140 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
142 container_detail::intrusive_list_type<Allocator>::type Icont;
143 typedef container_detail::node_alloc_holder<Allocator, Icont> AllocHolder;
144 typedef typename AllocHolder::NodePtr NodePtr;
145 typedef typename AllocHolder::NodeAlloc NodeAlloc;
146 typedef typename AllocHolder::ValAlloc ValAlloc;
147 typedef typename AllocHolder::Node Node;
148 typedef container_detail::allocator_destroyer<NodeAlloc> Destroyer;
149 typedef typename AllocHolder::alloc_version alloc_version;
150 typedef boost::container::allocator_traits<Allocator> allocator_traits_type;
151 typedef boost::container::equal_to_value<Allocator> equal_to_value_type;
153 BOOST_COPYABLE_AND_MOVABLE(list)
155 typedef container_detail::iterator_from_iiterator<typename Icont::iterator, false> iterator_impl;
156 typedef container_detail::iterator_from_iiterator<typename Icont::iterator, true> const_iterator_impl;
157 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
160 //////////////////////////////////////////////
164 //////////////////////////////////////////////
166 typedef T value_type;
167 typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer;
168 typedef typename ::boost::container::allocator_traits<Allocator>::const_pointer const_pointer;
169 typedef typename ::boost::container::allocator_traits<Allocator>::reference reference;
170 typedef typename ::boost::container::allocator_traits<Allocator>::const_reference const_reference;
171 typedef typename ::boost::container::allocator_traits<Allocator>::size_type size_type;
172 typedef typename ::boost::container::allocator_traits<Allocator>::difference_type difference_type;
173 typedef Allocator allocator_type;
174 typedef BOOST_CONTAINER_IMPDEF(NodeAlloc) stored_allocator_type;
175 typedef BOOST_CONTAINER_IMPDEF(iterator_impl) iterator;
176 typedef BOOST_CONTAINER_IMPDEF(const_iterator_impl) const_iterator;
177 typedef BOOST_CONTAINER_IMPDEF(boost::container::reverse_iterator<iterator>) reverse_iterator;
178 typedef BOOST_CONTAINER_IMPDEF(boost::container::reverse_iterator<const_iterator>) const_reverse_iterator;
180 //////////////////////////////////////////////
182 // construct/copy/destroy
184 //////////////////////////////////////////////
186 //! <b>Effects</b>: Default constructs a list.
188 //! <b>Throws</b>: If allocator_type's default constructor throws.
190 //! <b>Complexity</b>: Constant.
191 list() BOOST_NOEXCEPT_IF(container_detail::is_nothrow_default_constructible<Allocator>::value)
195 //! <b>Effects</b>: Constructs a list taking the allocator as parameter.
197 //! <b>Throws</b>: Nothing
199 //! <b>Complexity</b>: Constant.
200 explicit list(const allocator_type &a) BOOST_NOEXCEPT_OR_NOTHROW
204 //! <b>Effects</b>: Constructs a list
205 //! and inserts n value-initialized value_types.
207 //! <b>Throws</b>: If allocator_type's default constructor
208 //! throws or T's default or copy constructor throws.
210 //! <b>Complexity</b>: Linear to n.
211 explicit list(size_type n)
212 : AllocHolder(Allocator())
215 //! <b>Effects</b>: Constructs a list that will use a copy of allocator a
216 //! and inserts n copies of value.
218 //! <b>Throws</b>: If allocator_type's default constructor
219 //! throws or T's default or copy constructor throws.
221 //! <b>Complexity</b>: Linear to n.
222 list(size_type n, const allocator_type &a)
226 //! <b>Effects</b>: Constructs a list that will use a copy of allocator a
227 //! and inserts n copies of value.
229 //! <b>Throws</b>: If allocator_type's default constructor
230 //! throws or T's default or copy constructor throws.
232 //! <b>Complexity</b>: Linear to n.
233 list(size_type n, const T& value, const Allocator& a = Allocator())
235 { this->insert(this->cbegin(), n, value); }
237 //! <b>Effects</b>: Copy constructs a list.
239 //! <b>Postcondition</b>: x == *this.
241 //! <b>Throws</b>: If allocator_type's default constructor throws.
243 //! <b>Complexity</b>: Linear to the elements x contains.
246 { this->insert(this->cbegin(), x.begin(), x.end()); }
248 //! <b>Effects</b>: Move constructor. Moves x's resources to *this.
250 //! <b>Throws</b>: If allocator_type's copy constructor throws.
252 //! <b>Complexity</b>: Constant.
253 list(BOOST_RV_REF(list) x) BOOST_NOEXCEPT_OR_NOTHROW
254 : AllocHolder(BOOST_MOVE_BASE(AllocHolder, x))
257 //! <b>Effects</b>: Copy constructs a list using the specified allocator.
259 //! <b>Postcondition</b>: x == *this.
261 //! <b>Throws</b>: If allocator_type's default constructor or copy constructor throws.
263 //! <b>Complexity</b>: Linear to the elements x contains.
264 list(const list& x, const allocator_type &a)
266 { this->insert(this->cbegin(), x.begin(), x.end()); }
268 //! <b>Effects</b>: Move constructor sing the specified allocator.
269 //! Moves x's resources to *this.
271 //! <b>Throws</b>: If allocation or value_type's copy constructor throws.
273 //! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise.
274 list(BOOST_RV_REF(list) x, const allocator_type &a)
277 if(this->node_alloc() == x.node_alloc()){
278 this->icont().swap(x.icont());
281 this->insert(this->cbegin(), boost::make_move_iterator(x.begin()), boost::make_move_iterator(x.end()));
285 //! <b>Effects</b>: Constructs a list that will use a copy of allocator a
286 //! and inserts a copy of the range [first, last) in the list.
288 //! <b>Throws</b>: If allocator_type's default constructor
289 //! throws or T's constructor taking a dereferenced InIt throws.
291 //! <b>Complexity</b>: Linear to the range [first, last).
292 template <class InpIt>
293 list(InpIt first, InpIt last, const Allocator &a = Allocator())
295 { this->insert(this->cbegin(), first, last); }
298 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
299 //! <b>Effects</b>: Constructs a list that will use a copy of allocator a
300 //! and inserts a copy of the range [il.begin(), il.end()) in the list.
302 //! <b>Throws</b>: If allocator_type's default constructor
303 //! throws or T's constructor taking a dereferenced
304 //! std::initializer_list iterator throws.
306 //! <b>Complexity</b>: Linear to the range [il.begin(), il.end()).
307 list(std::initializer_list<value_type> il, const Allocator &a = Allocator())
309 { this->insert(this->cbegin(), il.begin(), il.end()); }
312 //! <b>Effects</b>: Destroys the list. All stored values are destroyed
313 //! and used memory is deallocated.
315 //! <b>Throws</b>: Nothing.
317 //! <b>Complexity</b>: Linear to the number of elements.
318 ~list() BOOST_NOEXCEPT_OR_NOTHROW
319 {} //AllocHolder clears the list
321 //! <b>Effects</b>: Makes *this contain the same elements as x.
323 //! <b>Postcondition</b>: this->size() == x.size(). *this contains a copy
324 //! of each of x's elements.
326 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws.
328 //! <b>Complexity</b>: Linear to the number of elements in x.
329 list& operator=(BOOST_COPY_ASSIGN_REF(list) x)
332 NodeAlloc &this_alloc = this->node_alloc();
333 const NodeAlloc &x_alloc = x.node_alloc();
334 container_detail::bool_<allocator_traits_type::
335 propagate_on_container_copy_assignment::value> flag;
336 if(flag && this_alloc != x_alloc){
339 this->AllocHolder::copy_assign_alloc(x);
340 this->assign(x.begin(), x.end());
345 //! <b>Effects</b>: Move assignment. All x's values are transferred to *this.
347 //! <b>Postcondition</b>: x.empty(). *this contains a the elements x had
348 //! before the function.
350 //! <b>Throws</b>: If allocator_traits_type::propagate_on_container_move_assignment
351 //! is false and (allocation throws or value_type's move constructor throws)
353 //! <b>Complexity</b>: Constant if allocator_traits_type::
354 //! propagate_on_container_move_assignment is true or
355 //! this->get>allocator() == x.get_allocator(). Linear otherwise.
356 list& operator=(BOOST_RV_REF(list) x)
357 BOOST_NOEXCEPT_IF(allocator_traits_type::propagate_on_container_move_assignment::value
358 || allocator_traits_type::is_always_equal::value)
360 BOOST_ASSERT(this != &x);
361 NodeAlloc &this_alloc = this->node_alloc();
362 NodeAlloc &x_alloc = x.node_alloc();
363 const bool propagate_alloc = allocator_traits_type::
364 propagate_on_container_move_assignment::value;
365 const bool allocators_equal = this_alloc == x_alloc; (void)allocators_equal;
366 //Resources can be transferred if both allocators are
367 //going to be equal after this function (either propagated or already equal)
368 if(propagate_alloc || allocators_equal){
371 //Move allocator if needed
372 this->AllocHolder::move_assign_alloc(x);
374 this->icont() = boost::move(x.icont());
376 //Else do a one by one move
378 this->assign( boost::make_move_iterator(x.begin())
379 , boost::make_move_iterator(x.end()));
384 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
385 //! <b>Effects</b>: Makes *this contain the same elements as il.
387 //! <b>Postcondition</b>: this->size() == il.size(). *this contains a copy
388 //! of each of x's elements.
390 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws.
392 //! <b>Complexity</b>: Linear to the number of elements in x.
393 list& operator=(std::initializer_list<value_type> il)
395 assign(il.begin(), il.end());
400 //! <b>Effects</b>: Assigns the n copies of val to *this.
402 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws.
404 //! <b>Complexity</b>: Linear to n.
405 void assign(size_type n, const T& val)
407 typedef constant_iterator<value_type, difference_type> cvalue_iterator;
408 return this->assign(cvalue_iterator(val, n), cvalue_iterator());
411 //! <b>Effects</b>: Assigns the range [first, last) to *this.
413 //! <b>Throws</b>: If memory allocation throws or
414 //! T's constructor from dereferencing InpIt throws.
416 //! <b>Complexity</b>: Linear to n.
417 template <class InpIt>
418 void assign(InpIt first, InpIt last
419 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
420 , typename container_detail::disable_if_convertible<InpIt, size_type>::type * = 0
424 iterator first1 = this->begin();
425 const iterator last1 = this->end();
426 for ( ; first1 != last1 && first != last; ++first1, ++first)
429 this->erase(first1, last1);
431 this->insert(last1, first, last);
435 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
436 //! <b>Effects</b>: Assigns the range [il.begin(), il.end()) to *this.
438 //! <b>Throws</b>: If memory allocation throws or
439 //! T's constructor from dereferencing std::initializer_list iterator throws.
441 //! <b>Complexity</b>: Linear to n.
442 void assign(std::initializer_list<value_type> il)
443 { assign(il.begin(), il.end()); }
446 //! <b>Effects</b>: Returns a copy of the internal allocator.
448 //! <b>Throws</b>: If allocator's copy constructor throws.
450 //! <b>Complexity</b>: Constant.
451 allocator_type get_allocator() const BOOST_NOEXCEPT_OR_NOTHROW
452 { return allocator_type(this->node_alloc()); }
454 //! <b>Effects</b>: Returns a reference to the internal allocator.
456 //! <b>Throws</b>: Nothing
458 //! <b>Complexity</b>: Constant.
460 //! <b>Note</b>: Non-standard extension.
461 stored_allocator_type &get_stored_allocator() BOOST_NOEXCEPT_OR_NOTHROW
462 { return this->node_alloc(); }
464 //! <b>Effects</b>: Returns a reference to the internal allocator.
466 //! <b>Throws</b>: Nothing
468 //! <b>Complexity</b>: Constant.
470 //! <b>Note</b>: Non-standard extension.
471 const stored_allocator_type &get_stored_allocator() const BOOST_NOEXCEPT_OR_NOTHROW
472 { return this->node_alloc(); }
474 //////////////////////////////////////////////
478 //////////////////////////////////////////////
480 //! <b>Effects</b>: Returns an iterator to the first element contained in the list.
482 //! <b>Throws</b>: Nothing.
484 //! <b>Complexity</b>: Constant.
485 iterator begin() BOOST_NOEXCEPT_OR_NOTHROW
486 { return iterator(this->icont().begin()); }
488 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the list.
490 //! <b>Throws</b>: Nothing.
492 //! <b>Complexity</b>: Constant.
493 const_iterator begin() const BOOST_NOEXCEPT_OR_NOTHROW
494 { return this->cbegin(); }
496 //! <b>Effects</b>: Returns an iterator to the end of the list.
498 //! <b>Throws</b>: Nothing.
500 //! <b>Complexity</b>: Constant.
501 iterator end() BOOST_NOEXCEPT_OR_NOTHROW
502 { return iterator(this->icont().end()); }
504 //! <b>Effects</b>: Returns a const_iterator to the end of the list.
506 //! <b>Throws</b>: Nothing.
508 //! <b>Complexity</b>: Constant.
509 const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW
510 { return this->cend(); }
512 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning
513 //! of the reversed list.
515 //! <b>Throws</b>: Nothing.
517 //! <b>Complexity</b>: Constant.
518 reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW
519 { return reverse_iterator(end()); }
521 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
522 //! of the reversed list.
524 //! <b>Throws</b>: Nothing.
526 //! <b>Complexity</b>: Constant.
527 const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW
528 { return this->crbegin(); }
530 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
531 //! of the reversed list.
533 //! <b>Throws</b>: Nothing.
535 //! <b>Complexity</b>: Constant.
536 reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW
537 { return reverse_iterator(begin()); }
539 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
540 //! of the reversed list.
542 //! <b>Throws</b>: Nothing.
544 //! <b>Complexity</b>: Constant.
545 const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW
546 { return this->crend(); }
548 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the list.
550 //! <b>Throws</b>: Nothing.
552 //! <b>Complexity</b>: Constant.
553 const_iterator cbegin() const BOOST_NOEXCEPT_OR_NOTHROW
554 { return const_iterator(this->non_const_icont().begin()); }
556 //! <b>Effects</b>: Returns a const_iterator to the end of the list.
558 //! <b>Throws</b>: Nothing.
560 //! <b>Complexity</b>: Constant.
561 const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW
562 { return const_iterator(this->non_const_icont().end()); }
564 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
565 //! of the reversed list.
567 //! <b>Throws</b>: Nothing.
569 //! <b>Complexity</b>: Constant.
570 const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW
571 { return const_reverse_iterator(this->cend()); }
573 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
574 //! of the reversed list.
576 //! <b>Throws</b>: Nothing.
578 //! <b>Complexity</b>: Constant.
579 const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW
580 { return const_reverse_iterator(this->cbegin()); }
582 //////////////////////////////////////////////
586 //////////////////////////////////////////////
588 //! <b>Effects</b>: Returns true if the list contains no elements.
590 //! <b>Throws</b>: Nothing.
592 //! <b>Complexity</b>: Constant.
593 bool empty() const BOOST_NOEXCEPT_OR_NOTHROW
594 { return !this->size(); }
596 //! <b>Effects</b>: Returns the number of the elements contained in the list.
598 //! <b>Throws</b>: Nothing.
600 //! <b>Complexity</b>: Constant.
601 size_type size() const BOOST_NOEXCEPT_OR_NOTHROW
602 { return this->icont().size(); }
604 //! <b>Effects</b>: Returns the largest possible size of the list.
606 //! <b>Throws</b>: Nothing.
608 //! <b>Complexity</b>: Constant.
609 size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW
610 { return AllocHolder::max_size(); }
612 //! <b>Effects</b>: Inserts or erases elements at the end such that
613 //! the size becomes n. New elements are value initialized.
615 //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws.
617 //! <b>Complexity</b>: Linear to the difference between size() and new_size.
618 void resize(size_type new_size)
620 if(!priv_try_shrink(new_size)){
621 typedef value_init_construct_iterator<value_type, difference_type> value_init_iterator;
622 this->insert(this->cend(), value_init_iterator(new_size - this->size()), value_init_iterator());
626 //! <b>Effects</b>: Inserts or erases elements at the end such that
627 //! the size becomes n. New elements are copy constructed from x.
629 //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws.
631 //! <b>Complexity</b>: Linear to the difference between size() and new_size.
632 void resize(size_type new_size, const T& x)
634 if(!priv_try_shrink(new_size)){
635 this->insert(this->cend(), new_size - this->size(), x);
639 //////////////////////////////////////////////
643 //////////////////////////////////////////////
645 //! <b>Requires</b>: !empty()
647 //! <b>Effects</b>: Returns a reference to the first element
648 //! from the beginning of the container.
650 //! <b>Throws</b>: Nothing.
652 //! <b>Complexity</b>: Constant.
653 reference front() BOOST_NOEXCEPT_OR_NOTHROW
655 BOOST_ASSERT(!this->empty());
656 return *this->begin();
659 //! <b>Requires</b>: !empty()
661 //! <b>Effects</b>: Returns a const reference to the first element
662 //! from the beginning of the container.
664 //! <b>Throws</b>: Nothing.
666 //! <b>Complexity</b>: Constant.
667 const_reference front() const BOOST_NOEXCEPT_OR_NOTHROW
669 BOOST_ASSERT(!this->empty());
670 return *this->begin();
673 //! <b>Requires</b>: !empty()
675 //! <b>Effects</b>: Returns a reference to the first element
676 //! from the beginning of the container.
678 //! <b>Throws</b>: Nothing.
680 //! <b>Complexity</b>: Constant.
681 reference back() BOOST_NOEXCEPT_OR_NOTHROW
683 BOOST_ASSERT(!this->empty());
684 return *(--this->end());
687 //! <b>Requires</b>: !empty()
689 //! <b>Effects</b>: Returns a const reference to the first element
690 //! from the beginning of the container.
692 //! <b>Throws</b>: Nothing.
694 //! <b>Complexity</b>: Constant.
695 const_reference back() const BOOST_NOEXCEPT_OR_NOTHROW
697 BOOST_ASSERT(!this->empty());
698 return *(--this->end());
701 //////////////////////////////////////////////
705 //////////////////////////////////////////////
707 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
709 //! <b>Effects</b>: Inserts an object of type T constructed with
710 //! std::forward<Args>(args)... in the end of the list.
712 //! <b>Returns</b>: A reference to the created object.
714 //! <b>Throws</b>: If memory allocation throws or
715 //! T's in-place constructor throws.
717 //! <b>Complexity</b>: Constant
718 template <class... Args>
719 reference emplace_back(BOOST_FWD_REF(Args)... args)
720 { return *this->emplace(this->cend(), boost::forward<Args>(args)...); }
722 //! <b>Effects</b>: Inserts an object of type T constructed with
723 //! std::forward<Args>(args)... in the beginning of the list.
725 //! <b>Returns</b>: A reference to the created object.
727 //! <b>Throws</b>: If memory allocation throws or
728 //! T's in-place constructor throws.
730 //! <b>Complexity</b>: Constant
731 template <class... Args>
732 reference emplace_front(BOOST_FWD_REF(Args)... args)
733 { return *this->emplace(this->cbegin(), boost::forward<Args>(args)...); }
735 //! <b>Effects</b>: Inserts an object of type T constructed with
736 //! std::forward<Args>(args)... before p.
738 //! <b>Throws</b>: If memory allocation throws or
739 //! T's in-place constructor throws.
741 //! <b>Complexity</b>: Constant
742 template <class... Args>
743 iterator emplace(const_iterator position, BOOST_FWD_REF(Args)... args)
745 BOOST_ASSERT((priv_is_linked)(position));
746 NodePtr pnode(AllocHolder::create_node(boost::forward<Args>(args)...));
747 return iterator(this->icont().insert(position.get(), *pnode));
750 #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
752 #define BOOST_CONTAINER_LIST_EMPLACE_CODE(N) \
753 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
754 reference emplace_back(BOOST_MOVE_UREF##N)\
755 { return *this->emplace(this->cend() BOOST_MOVE_I##N BOOST_MOVE_FWD##N); }\
757 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
758 reference emplace_front(BOOST_MOVE_UREF##N)\
759 { return *this->emplace(this->cbegin() BOOST_MOVE_I##N BOOST_MOVE_FWD##N);}\
761 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
762 iterator emplace(const_iterator position BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
764 BOOST_ASSERT(position == this->cend() || (--(++position) == position) );\
765 NodePtr pnode (AllocHolder::create_node(BOOST_MOVE_FWD##N));\
766 return iterator(this->icont().insert(position.get(), *pnode));\
769 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_LIST_EMPLACE_CODE)
770 #undef BOOST_CONTAINER_LIST_EMPLACE_CODE
772 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
774 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
775 //! <b>Effects</b>: Inserts a copy of x at the beginning of the list.
777 //! <b>Throws</b>: If memory allocation throws or
778 //! T's copy constructor throws.
780 //! <b>Complexity</b>: Amortized constant time.
781 void push_front(const T &x);
783 //! <b>Effects</b>: Constructs a new element in the beginning of the list
784 //! and moves the resources of x to this new element.
786 //! <b>Throws</b>: If memory allocation throws.
788 //! <b>Complexity</b>: Amortized constant time.
789 void push_front(T &&x);
791 BOOST_MOVE_CONVERSION_AWARE_CATCH(push_front, T, void, priv_push_front)
794 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
795 //! <b>Effects</b>: Inserts a copy of x at the end of the list.
797 //! <b>Throws</b>: If memory allocation throws or
798 //! T's copy constructor throws.
800 //! <b>Complexity</b>: Amortized constant time.
801 void push_back(const T &x);
803 //! <b>Effects</b>: Constructs a new element in the end of the list
804 //! and moves the resources of x to this new element.
806 //! <b>Throws</b>: If memory allocation throws.
808 //! <b>Complexity</b>: Amortized constant time.
809 void push_back(T &&x);
811 BOOST_MOVE_CONVERSION_AWARE_CATCH(push_back, T, void, priv_push_back)
814 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
815 //! <b>Requires</b>: p must be a valid iterator of *this.
817 //! <b>Effects</b>: Insert a copy of x before p.
819 //! <b>Returns</b>: an iterator to the inserted element.
821 //! <b>Throws</b>: If memory allocation throws or x's copy constructor throws.
823 //! <b>Complexity</b>: Amortized constant time.
824 iterator insert(const_iterator p, const T &x);
826 //! <b>Requires</b>: p must be a valid iterator of *this.
828 //! <b>Effects</b>: Insert a new element before p with x's resources.
830 //! <b>Returns</b>: an iterator to the inserted element.
832 //! <b>Throws</b>: If memory allocation throws.
834 //! <b>Complexity</b>: Amortized constant time.
835 iterator insert(const_iterator p, T &&x);
837 BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, T, iterator, priv_insert, const_iterator, const_iterator)
840 //! <b>Requires</b>: p must be a valid iterator of *this.
842 //! <b>Effects</b>: Inserts n copies of x before p.
844 //! <b>Returns</b>: an iterator to the first inserted element or p if n is 0.
846 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws.
848 //! <b>Complexity</b>: Linear to n.
849 iterator insert(const_iterator position, size_type n, const T& x)
851 //range check is done by insert
852 typedef constant_iterator<value_type, difference_type> cvalue_iterator;
853 return this->insert(position, cvalue_iterator(x, n), cvalue_iterator());
856 //! <b>Requires</b>: p must be a valid iterator of *this.
858 //! <b>Effects</b>: Insert a copy of the [first, last) range before p.
860 //! <b>Returns</b>: an iterator to the first inserted element or p if first == last.
862 //! <b>Throws</b>: If memory allocation throws, T's constructor from a
863 //! dereferenced InpIt throws.
865 //! <b>Complexity</b>: Linear to distance [first, last).
866 template <class InpIt>
867 iterator insert(const_iterator p, InpIt first, InpIt last
868 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
869 , typename container_detail::enable_if_c
870 < !container_detail::is_convertible<InpIt, size_type>::value
871 && (container_detail::is_input_iterator<InpIt>::value
872 || container_detail::is_same<alloc_version, version_1>::value
878 BOOST_ASSERT((priv_is_linked)(p));
879 const typename Icont::iterator ipos(p.get());
880 iterator ret_it(ipos);
882 ret_it = iterator(this->icont().insert(ipos, *this->create_node_from_it(first)));
885 for (; first != last; ++first){
886 this->icont().insert(ipos, *this->create_node_from_it(first));
891 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
892 template <class FwdIt>
893 iterator insert(const_iterator position, FwdIt first, FwdIt last
894 , typename container_detail::enable_if_c
895 < !container_detail::is_convertible<FwdIt, size_type>::value
896 && !(container_detail::is_input_iterator<FwdIt>::value
897 || container_detail::is_same<alloc_version, version_1>::value
902 BOOST_ASSERT((priv_is_linked)(position));
903 //Optimized allocation and construction
904 insertion_functor func(this->icont(), position.get());
905 iterator before_p(position.get());
907 this->allocate_many_and_construct(first, boost::container::iterator_distance(first, last), func);
912 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
913 //! <b>Requires</b>: p must be a valid iterator of *this.
915 //! <b>Effects</b>: Insert a copy of the [il.begin(), il.end()) range before p.
917 //! <b>Returns</b>: an iterator to the first inserted element or p if if.begin() == il.end().
919 //! <b>Throws</b>: If memory allocation throws, T's constructor from a
920 //! dereferenced std::initializer_list iterator throws.
922 //! <b>Complexity</b>: Linear to distance [il.begin(), il.end()).
923 iterator insert(const_iterator p, std::initializer_list<value_type> il)
925 //position range check is done by insert()
926 return insert(p, il.begin(), il.end());
930 //! <b>Effects</b>: Removes the first element from the list.
932 //! <b>Throws</b>: Nothing.
934 //! <b>Complexity</b>: Amortized constant time.
935 void pop_front() BOOST_NOEXCEPT_OR_NOTHROW
937 BOOST_ASSERT(!this->empty());
938 this->erase(this->cbegin());
941 //! <b>Effects</b>: Removes the last element from the list.
943 //! <b>Throws</b>: Nothing.
945 //! <b>Complexity</b>: Amortized constant time.
946 void pop_back() BOOST_NOEXCEPT_OR_NOTHROW
948 BOOST_ASSERT(!this->empty());
949 const_iterator tmp = this->cend();
953 //! <b>Requires</b>: p must be a valid iterator of *this.
955 //! <b>Effects</b>: Erases the element at p.
957 //! <b>Throws</b>: Nothing.
959 //! <b>Complexity</b>: Amortized constant time.
960 iterator erase(const_iterator p) BOOST_NOEXCEPT_OR_NOTHROW
962 BOOST_ASSERT(p != this->cend() && (priv_is_linked)(p));
963 return iterator(this->icont().erase_and_dispose(p.get(), Destroyer(this->node_alloc())));
966 //! <b>Requires</b>: first and last must be valid iterator to elements in *this.
968 //! <b>Effects</b>: Erases the elements pointed by [first, last).
970 //! <b>Throws</b>: Nothing.
972 //! <b>Complexity</b>: Linear to the distance between first and last.
973 iterator erase(const_iterator first, const_iterator last) BOOST_NOEXCEPT_OR_NOTHROW
975 BOOST_ASSERT(first == last || (first != this->cend() && (priv_is_linked)(first)));
976 BOOST_ASSERT(first == last || (priv_is_linked)(last));
977 return iterator(AllocHolder::erase_range(first.get(), last.get(), alloc_version()));
980 //! <b>Effects</b>: Swaps the contents of *this and x.
982 //! <b>Throws</b>: Nothing.
984 //! <b>Complexity</b>: Constant.
986 BOOST_NOEXCEPT_IF(allocator_traits_type::propagate_on_container_swap::value
987 || allocator_traits_type::is_always_equal::value)
989 BOOST_ASSERT(allocator_traits_type::propagate_on_container_swap::value ||
990 allocator_traits_type::is_always_equal::value ||
991 this->get_stored_allocator() == x.get_stored_allocator());
992 AllocHolder::swap(x);
995 //! <b>Effects</b>: Erases all the elements of the list.
997 //! <b>Throws</b>: Nothing.
999 //! <b>Complexity</b>: Linear to the number of elements in the list.
1000 void clear() BOOST_NOEXCEPT_OR_NOTHROW
1001 { AllocHolder::clear(alloc_version()); }
1003 //////////////////////////////////////////////
1007 //////////////////////////////////////////////
1009 //! <b>Requires</b>: p must point to an element contained
1010 //! by the list. x != *this. this' allocator and x's allocator shall compare equal
1012 //! <b>Effects</b>: Transfers all the elements of list x to this list, before the
1013 //! the element pointed by p. No destructors or copy constructors are called.
1015 //! <b>Throws</b>: Nothing
1017 //! <b>Complexity</b>: Constant.
1019 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of
1020 //! this list. Iterators of this list and all the references are not invalidated.
1021 void splice(const_iterator p, list& x) BOOST_NOEXCEPT_OR_NOTHROW
1023 BOOST_ASSERT((priv_is_linked)(p));
1024 BOOST_ASSERT(this != &x);
1025 BOOST_ASSERT(this->node_alloc() == x.node_alloc());
1026 this->icont().splice(p.get(), x.icont());
1029 //! <b>Requires</b>: p must point to an element contained
1030 //! by the list. x != *this. this' allocator and x's allocator shall compare equal
1032 //! <b>Effects</b>: Transfers all the elements of list x to this list, before the
1033 //! the element pointed by p. No destructors or copy constructors are called.
1035 //! <b>Throws</b>: Nothing
1037 //! <b>Complexity</b>: Constant.
1039 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of
1040 //! this list. Iterators of this list and all the references are not invalidated.
1041 void splice(const_iterator p, BOOST_RV_REF(list) x) BOOST_NOEXCEPT_OR_NOTHROW
1043 //Checks done in splice
1044 this->splice(p, static_cast<list&>(x));
1047 //! <b>Requires</b>: p must point to an element contained
1048 //! by this list. i must point to an element contained in list x.
1049 //! this' allocator and x's allocator shall compare equal
1051 //! <b>Effects</b>: Transfers the value pointed by i, from list x to this list,
1052 //! before the element pointed by p. No destructors or copy constructors are called.
1053 //! If p == i or p == ++i, this function is a null operation.
1055 //! <b>Throws</b>: Nothing
1057 //! <b>Complexity</b>: Constant.
1059 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this
1060 //! list. Iterators of this list and all the references are not invalidated.
1061 void splice(const_iterator p, list &x, const_iterator i) BOOST_NOEXCEPT_OR_NOTHROW
1063 BOOST_ASSERT((priv_is_linked)(p));
1064 BOOST_ASSERT(this->node_alloc() == x.node_alloc());
1065 this->icont().splice(p.get(), x.icont(), i.get());
1068 //! <b>Requires</b>: p must point to an element contained
1069 //! by this list. i must point to an element contained in list x.
1070 //! this' allocator and x's allocator shall compare equal.
1072 //! <b>Effects</b>: Transfers the value pointed by i, from list x to this list,
1073 //! before the element pointed by p. No destructors or copy constructors are called.
1074 //! If p == i or p == ++i, this function is a null operation.
1076 //! <b>Throws</b>: Nothing
1078 //! <b>Complexity</b>: Constant.
1080 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this
1081 //! list. Iterators of this list and all the references are not invalidated.
1082 void splice(const_iterator p, BOOST_RV_REF(list) x, const_iterator i) BOOST_NOEXCEPT_OR_NOTHROW
1084 BOOST_ASSERT(this != &x);
1085 //Additional checks done in splice()
1086 this->splice(p, static_cast<list&>(x), i);
1089 //! <b>Requires</b>: p must point to an element contained
1090 //! by this list. first and last must point to elements contained in list x.
1091 //! this' allocator and x's allocator shall compare equal
1093 //! <b>Effects</b>: Transfers the range pointed by first and last from list x to this list,
1094 //! before the element pointed by p. No destructors or copy constructors are called.
1096 //! <b>Throws</b>: Nothing
1098 //! <b>Complexity</b>: Linear to the number of elements transferred.
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.
1102 void splice(const_iterator p, list &x, const_iterator first, const_iterator last) BOOST_NOEXCEPT_OR_NOTHROW
1104 BOOST_ASSERT((priv_is_linked)(p));
1105 BOOST_ASSERT(first == last || (first != x.cend() && x.priv_is_linked(first)));
1106 BOOST_ASSERT(first == last || x.priv_is_linked(last));
1107 BOOST_ASSERT(this->node_alloc() == x.node_alloc());
1108 this->icont().splice(p.get(), x.icont(), first.get(), last.get());
1111 //! <b>Requires</b>: p must point to an element contained
1112 //! by this list. first and last must point to elements contained in list x.
1113 //! this' allocator and x's allocator shall compare equal.
1115 //! <b>Effects</b>: Transfers the range pointed by first and last from list x to this list,
1116 //! before the element pointed by p. No destructors or copy constructors are called.
1118 //! <b>Throws</b>: Nothing
1120 //! <b>Complexity</b>: Linear to the number of elements transferred.
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.
1124 void splice(const_iterator p, BOOST_RV_REF(list) x, const_iterator first, const_iterator last) BOOST_NOEXCEPT_OR_NOTHROW
1126 BOOST_ASSERT(this != &x);
1127 //Additional checks done in splice()
1128 this->splice(p, static_cast<list&>(x), first, last);
1131 //! <b>Requires</b>: p must point to an element contained
1132 //! by this list. first and last must point to elements contained in list x.
1133 //! n == distance(first, last). this' allocator and x's allocator shall compare equal
1135 //! <b>Effects</b>: Transfers the range pointed by first and last from list x to this list,
1136 //! before the element pointed by p. No destructors or copy constructors are called.
1138 //! <b>Throws</b>: Nothing
1140 //! <b>Complexity</b>: Constant.
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.
1145 //! <b>Note</b>: Non-standard extension
1146 void splice(const_iterator p, list &x, const_iterator first, const_iterator last, size_type n) BOOST_NOEXCEPT_OR_NOTHROW
1148 BOOST_ASSERT(this->node_alloc() == x.node_alloc());
1149 this->icont().splice(p.get(), x.icont(), first.get(), last.get(), n);
1152 //! <b>Requires</b>: p must point to an element contained
1153 //! by this list. first and last must point to elements contained in list x.
1154 //! n == distance(first, last). this' allocator and x's allocator shall compare equal
1156 //! <b>Effects</b>: Transfers the range pointed by first and last from list x to this list,
1157 //! before the element pointed by p. No destructors or copy constructors are called.
1159 //! <b>Throws</b>: Nothing
1161 //! <b>Complexity</b>: Constant.
1163 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this
1164 //! list. Iterators of this list and all the references are not invalidated.
1166 //! <b>Note</b>: Non-standard extension
1167 void splice(const_iterator p, BOOST_RV_REF(list) x, const_iterator first, const_iterator last, size_type n) BOOST_NOEXCEPT_OR_NOTHROW
1168 { this->splice(p, static_cast<list&>(x), first, last, n); }
1170 //! <b>Effects</b>: Removes all the elements that compare equal to value.
1172 //! <b>Throws</b>: If comparison throws.
1174 //! <b>Complexity</b>: Linear time. It performs exactly size() comparisons for equality.
1176 //! <b>Note</b>: The relative order of elements that are not removed is unchanged,
1177 //! and iterators to elements that are not removed remain valid.
1178 void remove(const T& value)
1179 { this->remove_if(equal_to_value_type(value)); }
1181 //! <b>Effects</b>: Removes all the elements for which a specified
1182 //! predicate is satisfied.
1184 //! <b>Throws</b>: If pred throws.
1186 //! <b>Complexity</b>: Linear time. It performs exactly size() calls to the predicate.
1188 //! <b>Note</b>: The relative order of elements that are not removed is unchanged,
1189 //! and iterators to elements that are not removed remain valid.
1190 template <class Pred>
1191 void remove_if(Pred pred)
1193 typedef value_to_node_compare<Node, Pred> value_to_node_compare_type;
1194 this->icont().remove_and_dispose_if(value_to_node_compare_type(pred), Destroyer(this->node_alloc()));
1197 //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent
1198 //! elements that are equal from the list.
1200 //! <b>Throws</b>: If comparison throws.
1202 //! <b>Complexity</b>: Linear time (size()-1 comparisons equality comparisons).
1204 //! <b>Note</b>: The relative order of elements that are not removed is unchanged,
1205 //! and iterators to elements that are not removed remain valid.
1207 { this->unique(value_equal()); }
1209 //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent
1210 //! elements that satisfy some binary predicate from the list.
1212 //! <b>Throws</b>: If pred throws.
1214 //! <b>Complexity</b>: Linear time (size()-1 comparisons calls to pred()).
1216 //! <b>Note</b>: The relative order of elements that are not removed is unchanged,
1217 //! and iterators to elements that are not removed remain valid.
1218 template <class BinaryPredicate>
1219 void unique(BinaryPredicate binary_pred)
1221 typedef value_to_node_compare<Node, BinaryPredicate> value_to_node_compare_type;
1222 this->icont().unique_and_dispose(value_to_node_compare_type(binary_pred), Destroyer(this->node_alloc()));
1225 //! <b>Requires</b>: The lists x and *this must be distinct.
1227 //! <b>Effects</b>: This function removes all of x's elements and inserts them
1228 //! in order into *this according to std::less<value_type>. The merge is stable;
1229 //! that is, if an element from *this is equivalent to one from x, then the element
1230 //! from *this will precede the one from x.
1232 //! <b>Throws</b>: If comparison throws.
1234 //! <b>Complexity</b>: This function is linear time: it performs at most
1235 //! size() + x.size() - 1 comparisons.
1237 { this->merge(x, value_less()); }
1239 //! <b>Requires</b>: The lists x and *this must be distinct.
1241 //! <b>Effects</b>: This function removes all of x's elements and inserts them
1242 //! in order into *this according to std::less<value_type>. The merge is stable;
1243 //! that is, if an element from *this is equivalent to one from x, then the element
1244 //! from *this will precede the one from x.
1246 //! <b>Throws</b>: If comparison throws.
1248 //! <b>Complexity</b>: This function is linear time: it performs at most
1249 //! size() + x.size() - 1 comparisons.
1250 void merge(BOOST_RV_REF(list) x)
1251 { this->merge(static_cast<list&>(x)); }
1253 //! <b>Requires</b>: p must be a comparison function that induces a strict weak
1254 //! ordering and both *this and x must be sorted according to that ordering
1255 //! The lists x and *this must be distinct.
1257 //! <b>Effects</b>: This function removes all of x's elements and inserts them
1258 //! in order into *this. The merge is stable; that is, if an element from *this is
1259 //! equivalent to one from x, then the element from *this will precede the one from x.
1261 //! <b>Throws</b>: If comp throws.
1263 //! <b>Complexity</b>: This function is linear time: it performs at most
1264 //! size() + x.size() - 1 comparisons.
1266 //! <b>Note</b>: Iterators and references to *this are not invalidated.
1267 template <class StrictWeakOrdering>
1268 void merge(list &x, const StrictWeakOrdering &comp)
1270 BOOST_ASSERT(this->node_alloc() == x.node_alloc());
1271 typedef value_to_node_compare<Node, StrictWeakOrdering> value_to_node_compare_type;
1272 this->icont().merge(x.icont(), value_to_node_compare_type(comp));
1275 //! <b>Requires</b>: p must be a comparison function that induces a strict weak
1276 //! ordering and both *this and x must be sorted according to that ordering
1277 //! The lists x and *this must be distinct.
1279 //! <b>Effects</b>: This function removes all of x's elements and inserts them
1280 //! in order into *this. The merge is stable; that is, if an element from *this is
1281 //! equivalent to one from x, then the element from *this will precede the one from x.
1283 //! <b>Throws</b>: If comp throws.
1285 //! <b>Complexity</b>: This function is linear time: it performs at most
1286 //! size() + x.size() - 1 comparisons.
1288 //! <b>Note</b>: Iterators and references to *this are not invalidated.
1289 template <class StrictWeakOrdering>
1290 void merge(BOOST_RV_REF(list) x, StrictWeakOrdering comp)
1291 { this->merge(static_cast<list&>(x), comp); }
1293 //! <b>Effects</b>: This function sorts the list *this according to std::less<value_type>.
1294 //! The sort is stable, that is, the relative order of equivalent elements is preserved.
1296 //! <b>Throws</b>: If comparison throws.
1298 //! <b>Notes</b>: Iterators and references are not invalidated.
1300 //! <b>Complexity</b>: The number of comparisons is approximately N log N, where N
1301 //! is the list's size.
1303 { this->sort(value_less()); }
1305 //! <b>Effects</b>: This function sorts the list *this according to std::less<value_type>.
1306 //! The sort is stable, that is, the relative order of equivalent elements is preserved.
1308 //! <b>Throws</b>: If comp throws.
1310 //! <b>Notes</b>: Iterators and references are not invalidated.
1312 //! <b>Complexity</b>: The number of comparisons is approximately N log N, where N
1313 //! is the list's size.
1314 template <class StrictWeakOrdering>
1315 void sort(StrictWeakOrdering comp)
1317 // nothing if the list has length 0 or 1.
1318 if (this->size() < 2)
1320 typedef value_to_node_compare<Node, StrictWeakOrdering> value_to_node_compare_type;
1321 this->icont().sort(value_to_node_compare_type(comp));
1324 //! <b>Effects</b>: Reverses the order of elements in the list.
1326 //! <b>Throws</b>: Nothing.
1328 //! <b>Complexity</b>: This function is linear time.
1330 //! <b>Note</b>: Iterators and references are not invalidated
1331 void reverse() BOOST_NOEXCEPT_OR_NOTHROW
1332 { this->icont().reverse(); }
1334 //! <b>Effects</b>: Returns true if x and y are equal
1336 //! <b>Complexity</b>: Linear to the number of elements in the container.
1337 friend bool operator==(const list& x, const list& y)
1338 { return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin()); }
1340 //! <b>Effects</b>: Returns true if x and y are unequal
1342 //! <b>Complexity</b>: Linear to the number of elements in the container.
1343 friend bool operator!=(const list& x, const list& y)
1344 { return !(x == y); }
1346 //! <b>Effects</b>: Returns true if x is less than y
1348 //! <b>Complexity</b>: Linear to the number of elements in the container.
1349 friend bool operator<(const list& x, const list& y)
1350 { return boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); }
1352 //! <b>Effects</b>: Returns true if x is greater than y
1354 //! <b>Complexity</b>: Linear to the number of elements in the container.
1355 friend bool operator>(const list& x, const list& y)
1358 //! <b>Effects</b>: Returns true if x is equal or less than y
1360 //! <b>Complexity</b>: Linear to the number of elements in the container.
1361 friend bool operator<=(const list& x, const list& y)
1362 { return !(y < x); }
1364 //! <b>Effects</b>: Returns true if x is equal or greater than y
1366 //! <b>Complexity</b>: Linear to the number of elements in the container.
1367 friend bool operator>=(const list& x, const list& y)
1368 { return !(x < y); }
1370 //! <b>Effects</b>: x.swap(y)
1372 //! <b>Complexity</b>: Constant.
1373 friend void swap(list& x, list& y)
1376 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1379 static bool priv_is_linked(const_iterator const position)
1381 const_iterator cur(position);
1382 //This list is circular including end nodes
1383 return (--(++cur)) == position && (++(--cur)) == position;
1386 bool priv_try_shrink(size_type new_size)
1388 const size_type len = this->size();
1390 const const_iterator iend = this->cend();
1391 size_type to_erase = len - new_size;
1392 const_iterator ifirst;
1393 if(to_erase < len/2u){
1400 ifirst = this->cbegin();
1401 size_type to_skip = len - to_erase;
1406 this->erase(ifirst, iend);
1414 iterator priv_insert(const_iterator p, const T &x)
1416 BOOST_ASSERT((priv_is_linked)(p));
1417 NodePtr tmp = AllocHolder::create_node(x);
1418 return iterator(this->icont().insert(p.get(), *tmp));
1421 iterator priv_insert(const_iterator p, BOOST_RV_REF(T) x)
1423 BOOST_ASSERT((priv_is_linked)(p));
1424 NodePtr tmp = AllocHolder::create_node(boost::move(x));
1425 return iterator(this->icont().insert(p.get(), *tmp));
1428 void priv_push_back (const T &x)
1429 { this->insert(this->cend(), x); }
1431 void priv_push_back (BOOST_RV_REF(T) x)
1432 { this->insert(this->cend(), boost::move(x)); }
1434 void priv_push_front (const T &x)
1435 { this->insert(this->cbegin(), x); }
1437 void priv_push_front (BOOST_RV_REF(T) x)
1438 { this->insert(this->cbegin(), boost::move(x)); }
1440 class insertion_functor;
1441 friend class insertion_functor;
1443 class insertion_functor
1446 typedef typename Icont::const_iterator iconst_iterator;
1447 const iconst_iterator pos_;
1450 insertion_functor(Icont &icont, typename Icont::const_iterator pos)
1451 : icont_(icont), pos_(pos)
1454 void operator()(Node &n)
1456 this->icont_.insert(pos_, n);
1460 //Functors for member algorithm defaults
1463 bool operator()(const value_type &a, const value_type &b) const
1469 bool operator()(const value_type &a, const value_type &b) const
1472 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1476 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1478 } //namespace container {
1480 //!has_trivial_destructor_after_move<> == true_type
1481 //!specialization for optimizations
1482 template <class T, class Allocator>
1483 struct has_trivial_destructor_after_move<boost::container::list<T, Allocator> >
1485 typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer;
1486 static const bool value = ::boost::has_trivial_destructor_after_move<Allocator>::value &&
1487 ::boost::has_trivial_destructor_after_move<pointer>::value;
1490 namespace container {
1492 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1496 #include <boost/container/detail/config_end.hpp>
1498 #endif // BOOST_CONTAINER_LIST_HPP