![]() |
Home | Libraries | People | FAQ | More |
boost::container::list
// In header: <boost/container/list.hpp> template<typename T, typename Allocator = void> class list : protected { public: // types typedef T ; typedef ::boost::container::allocator_traits< ValueAllocator >:: ; typedef ::boost::container::allocator_traits< ValueAllocator >:: ; typedef ::boost::container::allocator_traits< ValueAllocator >:: ; typedef ::boost::container::allocator_traits< ValueAllocator >:: ; typedef ::boost::container::allocator_traits< ValueAllocator >:: ; typedef ::boost::container::allocator_traits< ValueAllocator >:: ; typedef ValueAllocator ; typedef implementation_defined ; typedef implementation_defined ; typedef implementation_defined ; typedef implementation_defined ; typedef implementation_defined ; // construct/copy/destruct () ; (const allocator_type &) ; (size_type); (size_type, const allocator_type &); (size_type, const T &, const ValueAllocator & = ValueAllocator()); (const list &); (list &&) ; (const list &, const allocator_type &); (list &&, const allocator_type &); template<typename InpIt> (InpIt, InpIt, const ValueAllocator & = ValueAllocator()); (value_type >, const ValueAllocator & = ValueAllocator()); list & (const list &); list & (list &&) ; list & (value_type >); ~(); // public member functions void (size_type, const T &); template<typename InpIt> void (InpIt, InpIt); void (value_type >); allocator_type () ; stored_allocator_type & () ; const stored_allocator_type & () ; iterator () ; const_iterator () ; iterator () ; const_iterator () ; reverse_iterator () ; const_reverse_iterator () ; reverse_iterator () ; const_reverse_iterator () ; const_iterator () ; const_iterator () ; const_reverse_iterator () ; const_reverse_iterator () ; bool () ; size_type () ; size_type () ; void (size_type); void (size_type, const T &); reference () ; const_reference () ; reference () ; const_reference () ; template< Args> reference (Args &&...); template< Args> reference (Args &&...); template< Args> iterator (const_iterator, Args &&...); void (const T &); void (T &&); void (const T &); void (T &&); iterator (const_iterator, const T &); iterator (const_iterator, T &&); iterator (const_iterator, size_type, const T &); template<typename InpIt> iterator (const_iterator, InpIt, InpIt); iterator (const_iterator, value_type >); void () ; void () ; iterator (const_iterator) ; iterator (const_iterator, const_iterator) ; void (list &) ; void () ; void (const_iterator, list &) ; void (const_iterator, list &&) ; void (const_iterator, list &, const_iterator) ; void (const_iterator, list &&, const_iterator) ; void (const_iterator, list &, const_iterator, const_iterator) ; void (const_iterator, list &&, const_iterator, const_iterator) ; void (const_iterator, list &, const_iterator, const_iterator, size_type) ; void (const_iterator, list &&, const_iterator, const_iterator, size_type) ; void (const T &); template<typename Pred> void (Pred); void (); template<typename BinaryPredicate> void (BinaryPredicate); void (list &); void (list &&); template<typename StrictWeakOrdering> void (list &, const StrictWeakOrdering &); template<typename StrictWeakOrdering> void (list &&, StrictWeakOrdering); void (); template<typename StrictWeakOrdering> void (StrictWeakOrdering); void () ; // friend functions bool (const list &, const list &); bool (const list &, const list &); bool (const list &, const list &); bool (const list &, const list &); bool (const list &, const list &); bool (const list &, const list &); void (list &, list &) ; };
A list is a doubly linked list. That is, it is a Sequence that supports both forward and backward traversal, and (amortized) constant time insertion and removal of elements at the beginning or the end, or in the middle. Lists have the important property that insertion and splicing do not invalidate iterators to list elements, and that even removal invalidates only the iterators that point to the elements that are removed. The ordering of iterators may be changed (that is, list<T>::iterator might have a different predecessor or successor after a list operation than it did before), but the iterators themselves will not be invalidated or made to point to different elements unless that invalidation or mutation is explicit.
typename T
The type of object that is stored in the list
typename Allocator = void
The allocator used for all internal memory management, use void for the default allocator
list
public
construct/copy/destruct() ;
Effects: Default constructs a list.
Throws: If allocator_type's default constructor throws.
Complexity: Constant.
(const allocator_type & a) ;
Effects: Constructs a list taking the allocator as parameter.
Throws: Nothing
Complexity: Constant.
(size_type n);
Effects: Constructs a list and inserts n value-initialized value_types.
Throws: If allocator_type's default constructor throws or T's default or copy constructor throws.
Complexity: Linear to n.
(size_type n, const allocator_type & a);
Effects: Constructs a list that will use a copy of allocator a and inserts n copies of value.
Throws: If allocator_type's default constructor throws or T's default or copy constructor throws.
Complexity: Linear to n.
(size_type n, const T & value, const ValueAllocator & a = ValueAllocator());
Effects: Constructs a list that will use a copy of allocator a and inserts n copies of value.
Throws: If allocator_type's default constructor throws or T's default or copy constructor throws.
Complexity: Linear to n.
(const list & x);
Effects: Copy constructs a list.
Postcondition: x == *this.
Throws: If allocator_type's default constructor throws.
Complexity: Linear to the elements x contains.
(list && x) ;
Effects: Move constructor. Moves x's resources to *this.
Throws: If allocator_type's copy constructor throws.
Complexity: Constant.
(const list & x, const allocator_type & a);
Effects: Copy constructs a list using the specified allocator.
Postcondition: x == *this.
Throws: If allocator_type's default constructor or copy constructor throws.
Complexity: Linear to the elements x contains.
(list && x, const allocator_type & a);
Effects: Move constructor sing the specified allocator. Moves x's resources to *this.
Throws: If allocation or value_type's copy constructor throws.
Complexity: Constant if a == x.get_allocator(), linear otherwise.
template<typename InpIt> (InpIt first, InpIt last, const ValueAllocator & a = ValueAllocator());
Effects: Constructs a list that will use a copy of allocator a and inserts a copy of the range [first, last) in the list.
Throws: If allocator_type's default constructor throws or T's constructor taking a dereferenced InIt throws.
Complexity: Linear to the range [first, last).
(value_type > il, const ValueAllocator & a = ValueAllocator());
Effects: Constructs a list that will use a copy of allocator a and inserts a copy of the range [il.begin(), il.end()) in the list.
Throws: If allocator_type's default constructor throws or T's constructor taking a dereferenced std::initializer_list iterator throws.
Complexity: Linear to the range [il.begin(), il.end()).
list & (const list & x);
Effects: Makes *this contain the same elements as x.
Postcondition: this->size() == x.size(). *this contains a copy of each of x's elements.
Throws: If memory allocation throws or T's copy constructor throws.
Complexity: Linear to the number of elements in x.
list & (list && x) ;
Effects: Move assignment. All x's values are transferred to *this.
Postcondition: x.empty(). *this contains a the elements x had before the function.
Throws: If allocator_traits_type::propagate_on_container_move_assignment is false and (allocation throws or value_type's move constructor throws)
Complexity: Constant if allocator_traits_type:: propagate_on_container_move_assignment is true or this->get>allocator() == x.get_allocator(). Linear otherwise.
list & (value_type > il);
Effects: Makes *this contain the same elements as il.
Postcondition: this->size() == il.size(). *this contains a copy of each of x's elements.
Throws: If memory allocation throws or T's copy constructor throws.
Complexity: Linear to the number of elements in x.
~();
Effects: Destroys the list. All stored values are destroyed and used memory is deallocated.
Throws: Nothing.
Complexity: Linear to the number of elements.
list
public member functionsvoid (size_type n, const T & val);
Effects: Assigns the n copies of val to *this.
Throws: If memory allocation throws or T's copy constructor throws.
Complexity: Linear to n.
template<typename InpIt> void (InpIt first, InpIt last);
Effects: Assigns the range [first, last) to *this.
Throws: If memory allocation throws or T's constructor from dereferencing InpIt throws.
Complexity: Linear to n.
void (value_type > il);
Effects: Assigns the range [il.begin(), il.end()) to *this.
Throws: If memory allocation throws or T's constructor from dereferencing std::initializer_list iterator throws.
Complexity: Linear to n.
allocator_type () ;
Effects: Returns a copy of the internal allocator.
Throws: If allocator's copy constructor throws.
Complexity: Constant.
stored_allocator_type & () ;
Effects: Returns a reference to the internal allocator.
Throws: Nothing
Complexity: Constant.
Note: Non-standard extension.
const stored_allocator_type & () ;
Effects: Returns a reference to the internal allocator.
Throws: Nothing
Complexity: Constant.
Note: Non-standard extension.
iterator () ;
Effects: Returns an iterator to the first element contained in the list.
Throws: Nothing.
Complexity: Constant.
const_iterator () ;
Effects: Returns a const_iterator to the first element contained in the list.
Throws: Nothing.
Complexity: Constant.
iterator () ;
Effects: Returns an iterator to the end of the list.
Throws: Nothing.
Complexity: Constant.
const_iterator () ;
Effects: Returns a const_iterator to the end of the list.
Throws: Nothing.
Complexity: Constant.
reverse_iterator () ;
Effects: Returns a reverse_iterator pointing to the beginning of the reversed list.
Throws: Nothing.
Complexity: Constant.
const_reverse_iterator () ;
Effects: Returns a const_reverse_iterator pointing to the beginning of the reversed list.
Throws: Nothing.
Complexity: Constant.
reverse_iterator () ;
Effects: Returns a reverse_iterator pointing to the end of the reversed list.
Throws: Nothing.
Complexity: Constant.
const_reverse_iterator () ;
Effects: Returns a const_reverse_iterator pointing to the end of the reversed list.
Throws: Nothing.
Complexity: Constant.
const_iterator () ;
Effects: Returns a const_iterator to the first element contained in the list.
Throws: Nothing.
Complexity: Constant.
const_iterator () ;
Effects: Returns a const_iterator to the end of the list.
Throws: Nothing.
Complexity: Constant.
const_reverse_iterator () ;
Effects: Returns a const_reverse_iterator pointing to the beginning of the reversed list.
Throws: Nothing.
Complexity: Constant.
const_reverse_iterator () ;
Effects: Returns a const_reverse_iterator pointing to the end of the reversed list.
Throws: Nothing.
Complexity: Constant.
bool () ;
Effects: Returns true if the list contains no elements.
Throws: Nothing.
Complexity: Constant.
size_type () ;
Effects: Returns the number of the elements contained in the list.
Throws: Nothing.
Complexity: Constant.
size_type () ;
Effects: Returns the largest possible size of the list.
Throws: Nothing.
Complexity: Constant.
void (size_type new_size);
Effects: Inserts or erases elements at the end such that the size becomes n. New elements are value initialized.
Throws: If memory allocation throws, or T's copy constructor throws.
Complexity: Linear to the difference between size() and new_size.
void (size_type new_size, const T & x);
Effects: Inserts or erases elements at the end such that the size becomes n. New elements are copy constructed from x.
Throws: If memory allocation throws, or T's copy constructor throws.
Complexity: Linear to the difference between size() and new_size.
reference () ;
Requires: !empty()
Effects: Returns a reference to the first element from the beginning of the container.
Throws: Nothing.
Complexity: Constant.
const_reference () ;
Requires: !empty()
Effects: Returns a const reference to the first element from the beginning of the container.
Throws: Nothing.
Complexity: Constant.
reference () ;
Requires: !empty()
Effects: Returns a reference to the first element from the beginning of the container.
Throws: Nothing.
Complexity: Constant.
const_reference () ;
Requires: !empty()
Effects: Returns a const reference to the first element from the beginning of the container.
Throws: Nothing.
Complexity: Constant.
template< Args> reference (Args &&... args);
Effects: Inserts an object of type T constructed with std::forward<Args>(args)... in the end of the list.
Returns: A reference to the created object.
Throws: If memory allocation throws or T's in-place constructor throws.
Complexity: Constant
template< Args> reference (Args &&... args);
Effects: Inserts an object of type T constructed with std::forward<Args>(args)... in the beginning of the list.
Returns: A reference to the created object.
Throws: If memory allocation throws or T's in-place constructor throws.
Complexity: Constant
template< Args> iterator (const_iterator position, Args &&... args);
Effects: Inserts an object of type T constructed with std::forward<Args>(args)... before p.
Throws: If memory allocation throws or T's in-place constructor throws.
Complexity: Constant
void (const T & x);
Effects: Inserts a copy of x at the beginning of the list.
Throws: If memory allocation throws or T's copy constructor throws.
Complexity: Amortized constant time.
void (T && x);
Effects: Constructs a new element in the beginning of the list and moves the resources of x to this new element.
Throws: If memory allocation throws.
Complexity: Amortized constant time.
void (const T & x);
Effects: Inserts a copy of x at the end of the list.
Throws: If memory allocation throws or T's copy constructor throws.
Complexity: Amortized constant time.
void (T && x);
Effects: Constructs a new element in the end of the list and moves the resources of x to this new element.
Throws: If memory allocation throws.
Complexity: Amortized constant time.
iterator (const_iterator p, const T & x);
Requires: p must be a valid iterator of *this.
Effects: Insert a copy of x before p.
Returns: an iterator to the inserted element.
Throws: If memory allocation throws or x's copy constructor throws.
Complexity: Amortized constant time.
iterator (const_iterator p, T && x);
Requires: p must be a valid iterator of *this.
Effects: Insert a new element before p with x's resources.
Returns: an iterator to the inserted element.
Throws: If memory allocation throws.
Complexity: Amortized constant time.
iterator (const_iterator position, size_type n, const T & x);
Requires: p must be a valid iterator of *this.
Effects: Inserts n copies of x before p.
Returns: an iterator to the first inserted element or p if n is 0.
Throws: If memory allocation throws or T's copy constructor throws.
Complexity: Linear to n.
template<typename InpIt> iterator (const_iterator p, InpIt first, InpIt last);
Requires: p must be a valid iterator of *this.
Effects: Insert a copy of the [first, last) range before p.
Returns: an iterator to the first inserted element or p if first == last.
Throws: If memory allocation throws, T's constructor from a dereferenced InpIt throws.
Complexity: Linear to distance [first, last).
iterator (const_iterator p, value_type > il);
Requires: p must be a valid iterator of *this.
Effects: Insert a copy of the [il.begin(), il.end()) range before p.
Returns: an iterator to the first inserted element or p if if.begin() == il.end().
Throws: If memory allocation throws, T's constructor from a dereferenced std::initializer_list iterator throws.
Complexity: Linear to distance [il.begin(), il.end()).
void () ;
Effects: Removes the first element from the list.
Throws: Nothing.
Complexity: Amortized constant time.
void () ;
Effects: Removes the last element from the list.
Throws: Nothing.
Complexity: Amortized constant time.
iterator (const_iterator p) ;
Requires: p must be a valid iterator of *this.
Effects: Erases the element at p.
Throws: Nothing.
Complexity: Amortized constant time.
iterator (const_iterator first, const_iterator last) ;
Requires: first and last must be valid iterator to elements in *this.
Effects: Erases the elements pointed by [first, last).
Throws: Nothing.
Complexity: Linear to the distance between first and last.
void (list & x) ;
Effects: Swaps the contents of *this and x.
Throws: Nothing.
Complexity: Constant.
void () ;
Effects: Erases all the elements of the list.
Throws: Nothing.
Complexity: Linear to the number of elements in the list.
void (const_iterator p, list & x) ;
Requires: p must point to an element contained by the list. x != *this. this' allocator and x's allocator shall compare equal
Effects: Transfers all the elements of list x to this list, before the the element pointed by p. No destructors or copy constructors are called.
Throws: Nothing
Complexity: Constant.
Note: Iterators of values obtained from list x now point to elements of this list. Iterators of this list and all the references are not invalidated.
void (const_iterator p, list && x) ;
Requires: p must point to an element contained by the list. x != *this. this' allocator and x's allocator shall compare equal
Effects: Transfers all the elements of list x to this list, before the the element pointed by p. No destructors or copy constructors are called.
Throws: Nothing
Complexity: Constant.
Note: Iterators of values obtained from list x now point to elements of this list. Iterators of this list and all the references are not invalidated.
void (const_iterator p, list & x, const_iterator i) ;
Requires: p must point to an element contained by this list. i must point to an element contained in list x. this' allocator and x's allocator shall compare equal
Effects: Transfers the value pointed by i, from list x to this list, before the element pointed by p. No destructors or copy constructors are called. If p == i or p == ++i, this function is a null operation.
Throws: Nothing
Complexity: Constant.
Note: Iterators of values obtained from list x now point to elements of this list. Iterators of this list and all the references are not invalidated.
void (const_iterator p, list && x, const_iterator i) ;
Requires: p must point to an element contained by this list. i must point to an element contained in list x. this' allocator and x's allocator shall compare equal.
Effects: Transfers the value pointed by i, from list x to this list, before the element pointed by p. No destructors or copy constructors are called. If p == i or p == ++i, this function is a null operation.
Throws: Nothing
Complexity: Constant.
Note: Iterators of values obtained from list x now point to elements of this list. Iterators of this list and all the references are not invalidated.
void (const_iterator p, list & x, const_iterator first, const_iterator last) ;
Requires: p must point to an element contained by this list. first and last must point to elements contained in list x. this' allocator and x's allocator shall compare equal
Effects: Transfers the range pointed by first and last from list x to this list, before the element pointed by p. No destructors or copy constructors are called.
Throws: Nothing
Complexity: Linear to the number of elements transferred.
Note: Iterators of values obtained from list x now point to elements of this list. Iterators of this list and all the references are not invalidated.
void (const_iterator p, list && x, const_iterator first, const_iterator last) ;
Requires: p must point to an element contained by this list. first and last must point to elements contained in list x. this' allocator and x's allocator shall compare equal.
Effects: Transfers the range pointed by first and last from list x to this list, before the element pointed by p. No destructors or copy constructors are called.
Throws: Nothing
Complexity: Linear to the number of elements transferred.
Note: Iterators of values obtained from list x now point to elements of this list. Iterators of this list and all the references are not invalidated.
void (const_iterator p, list & x, const_iterator first, const_iterator last, size_type n) ;
Requires: p must point to an element contained by this list. first and last must point to elements contained in list x. n == distance(first, last). this' allocator and x's allocator shall compare equal
Effects: Transfers the range pointed by first and last from list x to this list, before the element pointed by p. No destructors or copy constructors are called.
Throws: Nothing
Complexity: Constant.
Note: Iterators of values obtained from list x now point to elements of this list. Iterators of this list and all the references are not invalidated.
Note: Non-standard extension
void (const_iterator p, list && x, const_iterator first, const_iterator last, size_type n) ;
Requires: p must point to an element contained by this list. first and last must point to elements contained in list x. n == distance(first, last). this' allocator and x's allocator shall compare equal
Effects: Transfers the range pointed by first and last from list x to this list, before the element pointed by p. No destructors or copy constructors are called.
Throws: Nothing
Complexity: Constant.
Note: Iterators of values obtained from list x now point to elements of this list. Iterators of this list and all the references are not invalidated.
Note: Non-standard extension
void (const T & value);
Effects: Removes all the elements that compare equal to value.
Throws: If comparison throws.
Complexity: Linear time. It performs exactly size() comparisons for equality.
Note: The relative order of elements that are not removed is unchanged, and iterators to elements that are not removed remain valid.
template<typename Pred> void (Pred pred);
Effects: Removes all the elements for which a specified predicate is satisfied.
Throws: If pred throws.
Complexity: Linear time. It performs exactly size() calls to the predicate.
Note: The relative order of elements that are not removed is unchanged, and iterators to elements that are not removed remain valid.
void ();
Effects: Removes adjacent duplicate elements or adjacent elements that are equal from the list.
Throws: If comparison throws.
Complexity: Linear time (size()-1 comparisons equality comparisons).
Note: The relative order of elements that are not removed is unchanged, and iterators to elements that are not removed remain valid.
template<typename BinaryPredicate> void (BinaryPredicate binary_pred);
Effects: Removes adjacent duplicate elements or adjacent elements that satisfy some binary predicate from the list.
Throws: If pred throws.
Complexity: Linear time (size()-1 comparisons calls to pred()).
Note: The relative order of elements that are not removed is unchanged, and iterators to elements that are not removed remain valid.
void (list & x);
Requires: The lists x and *this must be distinct.
Effects: This function removes all of x's elements and inserts them in order into *this according to std::less<value_type>. The merge is stable; that is, if an element from *this is equivalent to one from x, then the element from *this will precede the one from x.
Throws: If comparison throws.
Complexity: This function is linear time: it performs at most size() + x.size() - 1 comparisons.
void (list && x);
Requires: The lists x and *this must be distinct.
Effects: This function removes all of x's elements and inserts them in order into *this according to std::less<value_type>. The merge is stable; that is, if an element from *this is equivalent to one from x, then the element from *this will precede the one from x.
Throws: If comparison throws.
Complexity: This function is linear time: it performs at most size() + x.size() - 1 comparisons.
template<typename StrictWeakOrdering> void (list & x, const StrictWeakOrdering & comp);
Requires: p must be a comparison function that induces a strict weak ordering and both *this and x must be sorted according to that ordering The lists x and *this must be distinct.
Effects: This function removes all of x's elements and inserts them in order into *this. The merge is stable; that is, if an element from *this is equivalent to one from x, then the element from *this will precede the one from x.
Throws: If comp throws.
Complexity: This function is linear time: it performs at most size() + x.size() - 1 comparisons.
Note: Iterators and references to *this are not invalidated.
template<typename StrictWeakOrdering> void (list && x, StrictWeakOrdering comp);
Requires: p must be a comparison function that induces a strict weak ordering and both *this and x must be sorted according to that ordering The lists x and *this must be distinct.
Effects: This function removes all of x's elements and inserts them in order into *this. The merge is stable; that is, if an element from *this is equivalent to one from x, then the element from *this will precede the one from x.
Throws: If comp throws.
Complexity: This function is linear time: it performs at most size() + x.size() - 1 comparisons.
Note: Iterators and references to *this are not invalidated.
void ();
Effects: This function sorts the list *this according to std::less<value_type>. The sort is stable, that is, the relative order of equivalent elements is preserved.
Throws: If comparison throws.
Notes: Iterators and references are not invalidated.
Complexity: The number of comparisons is approximately N log N, where N is the list's size.
template<typename StrictWeakOrdering> void (StrictWeakOrdering comp);
Effects: This function sorts the list *this according to std::less<value_type>. The sort is stable, that is, the relative order of equivalent elements is preserved.
Throws: If comp throws.
Notes: Iterators and references are not invalidated.
Complexity: The number of comparisons is approximately N log N, where N is the list's size.
void () ;
Effects: Reverses the order of elements in the list.
Throws: Nothing.
Complexity: This function is linear time.
Note: Iterators and references are not invalidated
list
friend functionsbool (const list & x, const list & y);
Effects: Returns true if x and y are equal
Complexity: Linear to the number of elements in the container.
bool (const list & x, const list & y);
Effects: Returns true if x and y are unequal
Complexity: Linear to the number of elements in the container.
bool (const list & x, const list & y);
Effects: Returns true if x is less than y
Complexity: Linear to the number of elements in the container.
bool (const list & x, const list & y);
Effects: Returns true if x is greater than y
Complexity: Linear to the number of elements in the container.
bool (const list & x, const list & y);
Effects: Returns true if x is equal or less than y
Complexity: Linear to the number of elements in the container.
bool (const list & x, const list & y);
Effects: Returns true if x is equal or greater than y
Complexity: Linear to the number of elements in the container.
void (list & x, list & y) ;
Effects: x.swap(y)
Complexity: Constant.