Class template slist

boost::container::slist

Synopsis

// In header: <boost/container/slist.hpp>

template<typename T, typename A = std::allocator<T> > 
class slist {
public:
  // types
  typedef T                                      value_type;           
  typedef allocator_traits_type::pointer         pointer;                // Pointer to T. 
  typedef allocator_traits_type::const_pointer   const_pointer;          // Const pointer to T. 
  typedef allocator_traits_type::reference       reference;              // Reference to T. 
  typedef allocator_traits_type::const_reference const_reference;        // Const reference to T. 
  typedef allocator_traits_type::size_type       size_type;              // An unsigned integral type. 
  typedef allocator_traits_type::difference_type difference_type;        // A signed integral type. 
  typedef A                                      allocator_type;         // The allocator type. 
  typedef NodeAlloc                              stored_allocator_type;  // Non-standard extension: the stored allocator type. 

  // construct/copy/destruct
  slist();
  explicit slist(const allocator_type &);
  explicit slist(size_type);
  explicit slist(size_type, const value_type &, 
                 const allocator_type & = allocator_type());
  template<typename InpIt> 
    slist(InpIt, InpIt, const allocator_type & = allocator_type());
  slist(const slist &);
  slist(slist &&);
  slist& operator=(const slist &);
  slist& operator=(slist &&);
  ~slist();

  // public member functions
  allocator_type get_allocator() const;
  const stored_allocator_type & get_stored_allocator() const;
  stored_allocator_type & get_stored_allocator();
  void assign(size_type, const T &);
  template<typename InpIt> void assign(InpIt, InpIt);
  iterator begin();
  const_iterator begin() const;
  iterator end();
  const_iterator end() const;
  iterator before_begin();
  const_iterator before_begin() const;
  const_iterator cbegin() const;
  const_iterator cend() const;
  const_iterator cbefore_begin() const;
  size_type size() const;
  size_type max_size() const;
  bool empty() const;
  void swap(slist &);
  reference front();
  const_reference front() const;
  void push_front(const T &);
  void push_front(T &&);
  void pop_front();
  iterator previous(iterator);
  const_iterator previous(const_iterator);
  iterator insert_after(const_iterator, const T &);
  iterator insert_after(const_iterator, value_type &&);
  void insert_after(const_iterator, size_type, const value_type &);
  template<typename InIter> void insert_after(const_iterator, InIter, InIter);
  iterator insert(const_iterator, const T &);
  iterator insert(const_iterator, value_type &&);
  void insert(const_iterator, size_type, const value_type &);
  template<typename InIter> void insert(const_iterator, InIter, InIter);
  template<class... Args> void emplace_front(Args &&...);
  template<class... Args> iterator emplace(const_iterator, Args &&...);
  template<class... Args> iterator emplace_after(const_iterator, Args &&...);
  iterator erase_after(const_iterator);
  iterator erase_after(const_iterator, const_iterator);
  iterator erase(const_iterator);
  iterator erase(const_iterator, const_iterator);
  void resize(size_type, const T &);
  void resize(size_type);
  void clear();
  void splice_after(const_iterator, slist &);
  void splice_after(const_iterator, slist &, const_iterator);
  void splice_after(const_iterator, slist &, const_iterator, const_iterator);
  void splice_after(const_iterator, slist &, const_iterator, const_iterator, 
                    size_type);
  void splice(const_iterator, ThisType &);
  void splice(const_iterator, slist &, const_iterator);
  void splice(const_iterator, slist &, const_iterator, const_iterator);
  void reverse();
  void remove(const T &);
  template<typename Pred> void remove_if(Pred);
  void unique();
  template<typename Pred> void unique(Pred);
  void merge(slist &);
  template<typename StrictWeakOrdering> 
    void merge(slist &, StrictWeakOrdering);
  void sort();
  template<typename StrictWeakOrdering> void sort(StrictWeakOrdering);
};

Description

An slist is a singly linked list: a list where each element is linked to the next element, but not to the previous element. That is, it is a Sequence that supports forward but not backward traversal, and (amortized) constant time insertion and removal of elements. Slists, like 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, slist<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.

The main difference between slist and list is that list's iterators are bidirectional iterators, while slist's iterators are forward iterators. This means that slist is less versatile than list; frequently, however, bidirectional iterators are unnecessary. You should usually use slist unless you actually need the extra functionality of list, because singly linked lists are smaller and faster than double linked lists.

Important performance note: like every other Sequence, slist defines the member functions insert and erase. Using these member functions carelessly, however, can result in disastrously slow programs. The problem is that insert's first argument is an iterator p, and that it inserts the new element(s) before p. This means that insert must find the iterator just before p; this is a constant-time operation for list, since list has bidirectional iterators, but for slist it must find that iterator by traversing the list from the beginning up to p. In other words: insert and erase are slow operations anywhere but near the beginning of the slist.

Slist provides the member functions insert_after and erase_after, which are constant time operations: you should always use insert_after and erase_after whenever possible. If you find that insert_after and erase_after aren't adequate for your needs, and that you often need to use insert and erase in the middle of the list, then you should probably use list instead of slist.

`slist` public types

typedef T value_type;

The type of object, T, stored in the list

`slist` public construct/copy/destruct

```
slist();
```
Effects: Constructs a list taking the allocator as parameter.

Throws: If allocator_type's copy constructor throws.

Complexity: Constant.
```
explicit slist(const allocator_type & a);
```
Effects: Constructs a list taking the allocator as parameter.

Throws: If allocator_type's copy constructor throws.

Complexity: Constant.
```
explicit slist(size_type n);
```
```
explicit slist(size_type n, const value_type & x, 
               const allocator_type & a = allocator_type());
```
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 or copy constructor throws or T's default or copy constructor throws.

Complexity: Linear to n.
```
template<typename InpIt> 
  slist(InpIt first, InpIt last, const allocator_type & a = allocator_type());
```
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 or copy constructor throws or T's constructor taking an dereferenced InIt throws.

Complexity: Linear to the range [first, last).
```
slist(const slist & x);
```
Effects: Copy constructs a list.

Postcondition: x == *this.

Throws: If allocator_type's default constructor or copy constructor throws.

Complexity: Linear to the elements x contains.
```
slist(slist && x);
```
Effects: Move constructor. Moves mx's resources to *this.

Throws: If allocator_type's copy constructor throws.

Complexity: Constant.
```
slist& operator=(const slist & 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.
```
slist& operator=(slist && 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.
```
~slist();
```
Effects: Destroys the list. All stored values are destroyed and used memory is deallocated.

Throws: Nothing.

Complexity: Linear to the number of elements.

`slist` public member functions

```
allocator_type get_allocator() const;
```
Effects: Returns a copy of the internal allocator.

Throws: If allocator's copy constructor throws.

Complexity: Constant.

const stored_allocator_type & get_stored_allocator() const;

stored_allocator_type & get_stored_allocator();

```
void assign(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 assign(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.
```
iterator begin();
```
Effects: Returns an iterator to the first element contained in the list.

Throws: Nothing.

Complexity: Constant.
```
const_iterator begin() const;
```
Effects: Returns a const_iterator to the first element contained in the list.

Throws: Nothing.

Complexity: Constant.
```
iterator end();
```
Effects: Returns an iterator to the end of the list.

Throws: Nothing.

Complexity: Constant.
```
const_iterator end() const;
```
Effects: Returns a const_iterator to the end of the list.

Throws: Nothing.

Complexity: Constant.
```
iterator before_begin();
```
Effects: Returns a non-dereferenceable iterator that, when incremented, yields begin(). This iterator may be used as the argument toinsert_after, erase_after, etc.

Throws: Nothing.

Complexity: Constant.
```
const_iterator before_begin() const;
```
Effects: Returns a non-dereferenceable const_iterator that, when incremented, yields begin(). This iterator may be used as the argument toinsert_after, erase_after, etc.

Throws: Nothing.

Complexity: Constant.
```
const_iterator cbegin() const;
```
Effects: Returns a const_iterator to the first element contained in the list.

Throws: Nothing.

Complexity: Constant.
```
const_iterator cend() const;
```
Effects: Returns a const_iterator to the end of the list.

Throws: Nothing.

Complexity: Constant.
```
const_iterator cbefore_begin() const;
```
Effects: Returns a non-dereferenceable const_iterator that, when incremented, yields begin(). This iterator may be used as the argument toinsert_after, erase_after, etc.

Throws: Nothing.

Complexity: Constant.
```
size_type size() const;
```
Effects: Returns the number of the elements contained in the list.

Throws: Nothing.

Complexity: Constant.
```
size_type max_size() const;
```
Effects: Returns the largest possible size of the list.

Throws: Nothing.

Complexity: Constant.
```
bool empty() const;
```
Effects: Returns true if the list contains no elements.

Throws: Nothing.

Complexity: Constant.
```
void swap(slist & x);
```
Effects: Swaps the contents of *this and x.

Throws: Nothing.

Complexity: Linear to the number of elements on *this and x.
```
reference front();
```
Requires: !empty()

Effects: Returns a reference to the first element from the beginning of the container.

Throws: Nothing.

Complexity: Constant.
```
const_reference front() const;
```
Requires: !empty()

Effects: Returns a const reference to the first element from the beginning of the container.

Throws: Nothing.

Complexity: Constant.
```
void push_front(const T & x);
```
Effects: Inserts a copy of t in the beginning of the list.

Throws: If memory allocation throws or T's copy constructor throws.

Complexity: Amortized constant time.
```
void push_front(T && x);
```
Effects: Constructs a new element in the beginning of the list and moves the resources of t to this new element.

Throws: If memory allocation throws.

Complexity: Amortized constant time.
```
void pop_front();
```
Effects: Removes the first element from the list.

Throws: Nothing.

Complexity: Amortized constant time.
```
iterator previous(iterator p);
```
Returns: The iterator to the element before i in the sequence. Returns the end-iterator, if either i is the begin-iterator or the sequence is empty.

Throws: Nothing.

Complexity: Linear to the number of elements before i.
```
const_iterator previous(const_iterator p);
```
Returns: The const_iterator to the element before i in the sequence. Returns the end-const_iterator, if either i is the begin-const_iterator or the sequence is empty.

Throws: Nothing.

Complexity: Linear to the number of elements before i.
```
iterator insert_after(const_iterator prev_pos, const T & x);
```
Requires: p must be a valid iterator of *this.

Effects: Inserts a copy of the value after the p pointed by prev_p.

Returns: An iterator to the inserted element.

Throws: If memory allocation throws or T's copy constructor throws.

Complexity: Amortized constant time.

Note: Does not affect the validity of iterators and references of previous values.
```
iterator insert_after(const_iterator prev_pos, value_type && x);
```
Requires: prev_pos must be a valid iterator of *this.

Effects: Inserts a move constructed copy object from the value after the p pointed by prev_pos.

Returns: An iterator to the inserted element.

Throws: If memory allocation throws.

Complexity: Amortized constant time.

Note: Does not affect the validity of iterators and references of previous values.
```
void insert_after(const_iterator prev_pos, size_type n, const value_type & x);
```
Requires: prev_pos must be a valid iterator of *this.

Effects: Inserts n copies of x after prev_pos.

Throws: If memory allocation throws or T's copy constructor throws.

Complexity: Linear to n.

Note: Does not affect the validity of iterators and references of previous values.
```
template<typename InIter> 
  void insert_after(const_iterator prev_pos, InIter first, InIter last);
```
Requires: prev_pos must be a valid iterator of *this.

Effects: Inserts the range pointed by [first, last) after the p prev_pos.

Throws: If memory allocation throws, T's constructor from a dereferenced InpIt throws.

Complexity: Linear to the number of elements inserted.

Note: Does not affect the validity of iterators and references of previous values.
```
iterator insert(const_iterator position, const T & x);
```
Requires: p must be a valid iterator of *this.

Effects: Insert a copy of x before p.

Throws: If memory allocation throws or x's copy constructor throws.

Complexity: Linear to the elements before p.
```
iterator insert(const_iterator p, value_type && x);
```
Requires: p must be a valid iterator of *this.

Effects: Insert a new element before p with mx's resources.

Throws: If memory allocation throws.

Complexity: Linear to the elements before p.
```
void insert(const_iterator p, size_type n, const value_type & x);
```
Requires: p must be a valid iterator of *this.

Effects: Inserts n copies of x before p.

Throws: If memory allocation throws or T's copy constructor throws.

Complexity: Linear to n plus linear to the elements before p.
```
template<typename InIter> 
  void insert(const_iterator p, InIter first, InIter last);
```
Requires: p must be a valid iterator of *this.

Effects: Insert a copy of the [first, last) range before p.

Throws: If memory allocation throws, T's constructor from a dereferenced InpIt throws.

Complexity: Linear to std::distance [first, last) plus linear to the elements before p.
```
template<class... Args> void emplace_front(Args &&... args);
```
Effects: Inserts an object of type T constructed with std::forward<Args>(args)... in the front of the list

Throws: If memory allocation throws or T's copy constructor throws.

Complexity: Amortized constant time.
```
template<class... Args> iterator emplace(const_iterator p, 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: Linear to the elements before p
```
template<class... Args> 
  iterator emplace_after(const_iterator prev, Args &&... args);
```
Effects: Inserts an object of type T constructed with std::forward<Args>(args)... after prev

Throws: If memory allocation throws or T's in-place constructor throws.

Complexity: Constant
```
iterator erase_after(const_iterator prev_pos);
```
Effects: Erases the element after the element pointed by prev_pos of the list.

Returns: the first element remaining beyond the removed elements, or end() if no such element exists.

Throws: Nothing.

Complexity: Constant.

Note: Does not invalidate iterators or references to non erased elements.
```
iterator erase_after(const_iterator before_first, const_iterator last);
```
Effects: Erases the range (before_first, last) from the list.

Returns: the first element remaining beyond the removed elements, or end() if no such element exists.

Throws: Nothing.

Complexity: Linear to the number of erased elements.

Note: Does not invalidate iterators or references to non erased elements.
```
iterator erase(const_iterator p);
```
Requires: p must be a valid iterator of *this.

Effects: Erases the element at p p.

Throws: Nothing.

Complexity: Linear to the number of elements before p.
```
iterator erase(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 plus linear to the elements before first.
```
void resize(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.
```
void resize(size_type new_size);
```
Effects: Inserts or erases elements at the end such that the size becomes n. New elements are default constructed.

Throws: If memory allocation throws, or T's copy constructor throws.

Complexity: Linear to the difference between size() and new_size.
```
void clear();
```
Effects: Erases all the elements of the list.

Throws: Nothing.

Complexity: Linear to the number of elements in the list.
```
void splice_after(const_iterator prev_pos, slist & x);
```
Requires: p must point to an element contained by the list. x != *this

Effects: Transfers all the elements of list x to this list, after the the element pointed by p. No destructors or copy constructors are called.

Throws: std::runtime_error if this' allocator and x's allocator are not equal.

Complexity: Linear to the elements in x.

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 splice_after(const_iterator prev_pos, slist & x, const_iterator prev);
```
Requires: prev_pos must be a valid iterator of this. i must point to an element contained in list x.

Effects: Transfers the value pointed by i, from list x to this list, after the element pointed by prev_pos. If prev_pos == prev or prev_pos == ++prev, this function is a null operation.

Throws: std::runtime_error if this' allocator and x's allocator are not equal.

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 splice_after(const_iterator prev_pos, slist & x, 
                  const_iterator before_first, const_iterator before_last);
```
Requires: prev_pos must be a valid iterator of this. before_first and before_last must be valid iterators of x. prev_pos must not be contained in [before_first, before_last) range.

Effects: Transfers the range [before_first + 1, before_last + 1) from list x to this list, after the element pointed by prev_pos.

Throws: std::runtime_error if this' allocator and x's allocator are not equal.

Complexity: Linear to the number of transferred elements.

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 splice_after(const_iterator prev_pos, slist & x, 
                  const_iterator before_first, const_iterator before_last, 
                  size_type n);
```
Requires: prev_pos must be a valid iterator of this. before_first and before_last must be valid iterators of x. prev_pos must not be contained in [before_first, before_last) range. n == std::distance(before_first, before_last)

Effects: Transfers the range [before_first + 1, before_last + 1) from list x to this list, after the element pointed by prev_pos.

Throws: std::runtime_error if this' allocator and x's allocator are not equal.

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 splice(const_iterator p, ThisType & x);
```
Requires: p must point to an element contained by the list. x != *this

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: std::runtime_error if this' allocator and x's allocator are not equal.

Complexity: Linear in distance(begin(), p), and linear in x.size().

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 splice(const_iterator p, slist & 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.

Effects: Transfers the value pointed by i, from list x to this list, before the 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: std::runtime_error if this' allocator and x's allocator are not equal.

Complexity: Linear in distance(begin(), p), and in distance(x.begin(), i).

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 splice(const_iterator p, slist & 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.

Effects: Transfers the range pointed by first and last from list x to this list, before the the element pointed by p. No destructors or copy constructors are called.

Throws: std::runtime_error if this' allocator and x's allocator are not equal.

Complexity: Linear in distance(begin(), p), in distance(x.begin(), first), and in distance(first, last).

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 reverse();
```
Effects: Reverses the order of elements in the list.

Throws: Nothing.

Complexity: This function is linear time.

Note: Iterators and references are not invalidated
```
void remove(const T & value);
```
Effects: Removes all the elements that compare equal to value.

Throws: Nothing.

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 remove_if(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 unique();
```
Effects: Removes adjacent duplicate elements or adjacent elements that are equal from the list.

Throws: Nothing.

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.
```
template<typename Pred> void unique(Pred 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 equality comparisons).

Note: The relative order of elements that are not removed is unchanged, and iterators to elements that are not removed remain valid.
```
void merge(slist & 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: Nothing.

Complexity: This function is linear time: it performs at most size() + x.size() - 1 comparisons.
```
template<typename StrictWeakOrdering> 
  void merge(slist & 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: Nothing.

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 sort();
```
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: Nothing.

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 sort(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: Nothing.

Notes: Iterators and references are not invalidated.

Complexity: The number of comparisons is approximately N log N, where N is the list's size.