Class template slist

boost::container::slist

Synopsis

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

template<typename T, typename Allocator = new_allocator<T> > 
class slist {
public:
  // types
  typedef T                                                                  value_type;           
  typedef ::boost::container::allocator_traits< Allocator >::pointer         pointer;              
  typedef ::boost::container::allocator_traits< Allocator >::const_pointer   const_pointer;        
  typedef ::boost::container::allocator_traits< Allocator >::reference       reference;            
  typedef ::boost::container::allocator_traits< Allocator >::const_reference const_reference;      
  typedef ::boost::container::allocator_traits< Allocator >::size_type       size_type;            
  typedef ::boost::container::allocator_traits< Allocator >::difference_type difference_type;      
  typedef Allocator                                                          allocator_type;       
  typedef implementation_defined                                             stored_allocator_type;
  typedef implementation_defined                                             iterator;             
  typedef implementation_defined                                             const_iterator;       

  // construct/copy/destruct
  slist();
  explicit slist(const allocator_type &) noexcept;
  explicit slist(size_type);
  slist(size_type, const allocator_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(std::initializer_list< value_type >, 
        const allocator_type & = allocator_type());
  slist(const slist &);
  slist(slist &&);
  slist(const slist &, const allocator_type &);
  slist(slist &&, const allocator_type &);
  slist & operator=(const slist &);
  slist & operator=(slist &&) noexcept(condition);
  slist & operator=(std::initializer_list< value_type >);
  ~slist();

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

  // friend functions
  friend bool operator==(const slist &, const slist &);
  friend bool operator!=(const slist &, const slist &);
  friend bool operator<(const slist &, const slist &);
  friend bool operator>(const slist &, const slist &);
  friend bool operator<=(const slist &, const slist &);
  friend bool operator>=(const slist &, const slist &);
  friend void swap(slist &, slist &);
};

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.

Template Parameters

```
typename T
```
The type of object that is stored in the list
```
typename Allocator = new_allocator<T>
```
The allocator used for all internal memory management

`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) noexcept;
```
Effects: Constructs a list taking the allocator as parameter.

Throws: Nothing

Complexity: Constant.
```
explicit slist(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.
```
slist(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.
```
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 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 throws or T's constructor taking a dereferenced InIt throws.

Complexity: Linear to the range [first, last).
```
slist(std::initializer_list< value_type > il, 
      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 [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()).
```
slist(const slist & x);
```
Effects: Copy constructs a list. Postcondition: x == *this.

Throws: If allocator_type's default constructor

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

Throws: If allocator_type's copy constructor throws.

Complexity: Constant.
```
slist(const slist & x, const allocator_type & a);
```
Effects: Copy constructs a list using the specified allocator.

Postcondition: x == *this.

Throws: If allocator_type's default constructor

Complexity: Linear to the elements x contains.
```
slist(slist && x, const allocator_type & a);
```
Effects: Move constructor using 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.
```
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) noexcept(condition);
```
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 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.
```
slist & operator=(std::initializer_list< value_type > il);
```
Effects: Makes *this contain the same elements as in il.

Postcondition: this->size() == il.size(). *this contains a copy of each of il's elements.

Throws: If allocator_traits_type::propagate_on_container_move_assignment is false and (allocation throws or value_type's move constructor throws)
```
~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

```
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.
```
void assign(std::initializer_list< 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 range [il.begin(), il.end()).
```
allocator_type get_allocator() const noexcept;
```
Effects: Returns a copy of the internal allocator.

Throws: If allocator's copy constructor throws.

Complexity: Constant.
```
stored_allocator_type & get_stored_allocator() noexcept;
```
Effects: Returns a reference to the internal allocator.

Throws: Nothing

Complexity: Constant.

Note: Non-standard extension.
```
const stored_allocator_type & get_stored_allocator() const noexcept;
```
Effects: Returns a reference to the internal allocator.

Throws: Nothing

Complexity: Constant.

Note: Non-standard extension.
```
iterator before_begin() noexcept;
```
Effects: Returns a non-dereferenceable iterator that, when incremented, yields begin(). This iterator may be used as the argument to insert_after, erase_after, etc.

Throws: Nothing.

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

Throws: Nothing.

Complexity: Constant.
```
iterator begin() noexcept;
```
Effects: Returns an iterator to the first element contained in the list.

Throws: Nothing.

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

Throws: Nothing.

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

Throws: Nothing.

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

Throws: Nothing.

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

Throws: Nothing.

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

Throws: Nothing.

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

Throws: Nothing.

Complexity: Constant.
```
iterator previous(iterator p) noexcept;
```
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.

Note: Non-standard extension.
```
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.

Note: Non-standard extension.
```
bool empty() const;
```
Effects: Returns true if the list contains no elements.

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.
```
void resize(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 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.
```
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.
```
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_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
```
void push_front(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 push_front(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.
```
iterator insert_after(const_iterator prev_p, const T & x);
```
Requires: p must be a valid iterator of *this.

Effects: Inserts a copy of the value after 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_p, T && x);
```
Requires: prev_p must be a valid iterator of *this.

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

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.
```
iterator insert_after(const_iterator prev_p, size_type n, 
                      const value_type & x);
```
Requires: prev_p must be a valid iterator of *this.

Effects: Inserts n copies of x after prev_p.

Returns: an iterator to the last inserted element or prev_p if n is 0.

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 InpIt> 
  iterator insert_after(const_iterator prev_p, InpIt first, InpIt last);
```
Requires: prev_p must be a valid iterator of *this.

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

Returns: an iterator to the last inserted element or prev_p if first == last.

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_after(const_iterator prev_p, 
                      std::initializer_list< value_type > il);
```
Requires: prev_p must be a valid iterator of *this.

Effects: Inserts the range pointed by [il.begin(), il.end()) after prev_p.

Returns: an iterator to the last inserted element or prev_p if il.begin() == il.end().

Throws: If memory allocation throws, T's constructor from a dereferenced std::initializer_list iterator throws.

Complexity: Linear to the number of elements inserted.

Note: Does not affect the validity of iterators and references of previous values.
```
void pop_front();
```
Effects: Removes the first element from the list.

Throws: Nothing.

Complexity: Amortized constant time.
```
iterator erase_after(const_iterator prev_p);
```
Effects: Erases the element after the element pointed by prev_p 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.
```
void swap(slist & x) noexcept(condition);
```
Effects: Swaps the contents of *this and x.

Throws: Nothing.

Complexity: Linear to the number of elements on *this and x.
```
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_p, slist & x) noexcept;
```
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_p, slist && x) noexcept;
```
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_p, slist & x, const_iterator prev) noexcept;
```
Requires: prev_p must be a valid iterator of this. 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, after the element pointed by prev_p. If prev_p == prev or prev_p == ++prev, 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 splice_after(const_iterator prev_p, slist && x, const_iterator prev) noexcept;
```
Requires: prev_p must be a valid iterator of this. 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, after the element pointed by prev_p. If prev_p == prev or prev_p == ++prev, 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 splice_after(const_iterator prev_p, slist & x, 
                  const_iterator before_first, const_iterator before_last) noexcept;
```
Requires: prev_p must be a valid iterator of this. before_first and before_last must be valid iterators of x. prev_p must not be contained in [before_first, before_last) range. this' allocator and x's allocator shall compare equal.

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

Throws: Nothing

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_p, slist && x, 
                  const_iterator before_first, const_iterator before_last) noexcept;
```
Requires: prev_p must be a valid iterator of this. before_first and before_last must be valid iterators of x. prev_p must not be contained in [before_first, before_last) range. this' allocator and x's allocator shall compare equal.

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

Throws: Nothing

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_p, slist & x, 
                  const_iterator before_first, const_iterator before_last, 
                  size_type n) noexcept;
```
Requires: prev_p must be a valid iterator of this. before_first and before_last must be valid iterators of x. prev_p must not be contained in [before_first, before_last) range. n == distance(before_first, before_last). this' allocator and x's allocator shall compare equal.

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

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

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

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 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: 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 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 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 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: If comparison throws.

Complexity: This function is linear time: it performs at most size() + x.size() - 1 comparisons.
```
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: If comparison throws.

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

Throws: Nothing.

Complexity: This function is linear time.

Note: Iterators and references are not invalidated
```
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
```
iterator insert(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: Linear to the elements before p.
```
iterator insert(const_iterator prev_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: Linear to the elements before p.
```
iterator 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.

Returns: an iterator to the first inserted element or p if n == 0.

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> 
  iterator 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.

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) plus linear to the elements before p.
```
iterator insert(const_iterator p, std::initializer_list< 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 il.begin() == il.end().

Throws: If memory allocation throws, T's constructor from a dereferenced std::initializer_list iterator throws.

Complexity: Linear to the range [il.begin(), il.end()) plus linear to the elements before p.
```
iterator erase(const_iterator p) noexcept;
```
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) noexcept;
```
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 splice(const_iterator p, slist & x) noexcept;
```
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: 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) noexcept;
```
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: 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) noexcept;
```
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 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: 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 i) noexcept;
```
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 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: 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) noexcept;
```
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. this' allocator and x's allocator shall compare equal.

Throws: Nothing

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 splice(const_iterator p, slist && x, const_iterator first, 
            const_iterator last) noexcept;
```
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 the element pointed by p. No destructors or copy constructors are called.

Throws: Nothing

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.

`slist` friend functions

```
friend bool operator==(const slist & x, const slist & y);
```
Effects: Returns true if x and y are equal

Complexity: Linear to the number of elements in the container.
```
friend bool operator!=(const slist & x, const slist & y);
```
Effects: Returns true if x and y are unequal

Complexity: Linear to the number of elements in the container.
```
friend bool operator<(const slist & x, const slist & y);
```
Effects: Returns true if x is less than y

Complexity: Linear to the number of elements in the container.
```
friend bool operator>(const slist & x, const slist & y);
```
Effects: Returns true if x is greater than y

Complexity: Linear to the number of elements in the container.
```
friend bool operator<=(const slist & x, const slist & y);
```
Effects: Returns true if x is equal or less than y

Complexity: Linear to the number of elements in the container.
```
friend bool operator>=(const slist & x, const slist & y);
```
Effects: Returns true if x is equal or greater than y

Complexity: Linear to the number of elements in the container.
```
friend void swap(slist & x, slist & y);
```
Effects: x.swap(y)

Complexity: Constant.

Boost C++ Libraries