Slist

Definition

The slist template is defined in the standard header <slist>, and in the nonstandard backward-compatibility header <slist.h>.

#include <slist>
namespace std {
    template <class T, class Allocator = allocator<T> >
    class slist;
}

Description

An slist is a singly linked list, each element is linked to the next element, but not to the previous element.

The main difference between slist and list is that list's iterators are bidirectional iterators, while slist's iterators are forward iterators.

Short example:

slist<int> sL; // Creates a slist with sL elements of type int
sL.push_back(0); // Insert a new element at the end
sL.push_front(0); // Insert a new element at the beginning

Performance

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

Singly linked lists are smaller and faster than double linked lists, so you should use slist unless you actually need the extra functionality of list.

Slist Operations

Create, Copy and Destroy Operations

Operation	Effect
slist< El > c	Creates an empty slist with no elements
slist< El > c1(c2)	Creates a copy of another slist of the same type (all elements are copied)
slist< El > c(nr)	Creates an slist with nr elements that are created by the default constructor
slist< El > c(nr,el)	Creates an slist initialized with nr copies of element el
slist< El > c(beg,end)	Creates an slist initialized with the elements of the range [beg,end)
c.~slist< El >()	Destroys all elements and frees the memory

Nonmodifying Operations

Operation	Effect
c.size()	Returns the actual number of elements
c.empty()	Returns if the container is empty
c.max_size()	Returns the maximum number of elements possible
c1==c2	Returns if c1 is equal to c2
c1!=c2	Returns if c1 is not equal to c2 (equivalent to !(c1==c2))
c1<c2	Returns if c1 is less than c2
c1>c2	Returns if c1 is greater than c2 (equivalent to c2<c1)
c1<=c2	Returns if c1 is less than or equal to c2 (equivalent to !(c2<c1))
c1>=c2	Returns if c1 is greater than or equal to c2 (equivalent to !(c1<c2))

Assignments

Operation	Effect
c1=c2	Assigns all elements of c2 to c1
c.assign(nr,el)	Assigns nr copies of element el
c.assign(beg,end)	Assigns the elements of the range [beg,end)
c1.swap(c2)	Swaps the data of c1 and c2
swap(c1,c2)	Same (as global function)

Element Access

Operation	Effect
c.front()	Returns the first element (without range checking if a first element exists)
c.back()	Returns the last element (without range checking if a last element exists)

Iterator Functions

Operation	Effect
c.begin()	Returns a bidirectional iterator for the first element
c.end()	Returns a bidirectional iterator for the position after the last element

Inserting and Removing Elements

Operation	Effect
c.insert(prev_pos,el)	Inserts before iterator position prev_pos a copy of el and returns the position of the new element
c.insert(prev_pos,nr,el)	Inserts before iterator position prev_pos nr copies of el (returns nothing)
c.insert(prev_pos,beg,end)	Inserts before iterator position prev_pos a copy of all elements of the range [beg,end) (returns nothing)
c.push_back(el)	Appens a copy of el at the end
c.pop_back()	Removes the last element (does not return it)
c.push_front(el)	Inserts a copy of el at the beginning
c.pop_front()	Removes the first element (does not return it)
c.remove(v)	Removes all elements with value v
c.remove_if(op)	Removes all elements for which op(elem) yields true
c.erase(prev_pos)	Removes the element at iterator position prev_pos
c.erase(beg,end)	Removes all elements of the range [beg,end)
c.erase_after(prev_pos)	Removes the element after the element pointed by prev_pos of the slist and returns the first element remaining beyond the removed elements, or end() if no such element exists
c.erase_after(before_first,last)	Removes the range (before_first, last) from the slist and returns the first element remaining beyond the removed elements, or end() if no such element exists
c.resize(nr)	Inserts or removes elements at the end such that the size becomes nr (new elements are default constructed)
c.resize(nr,el)	Inserts or removes elements at the end such that the size becomes nr. New elements are copy constructed from el
c.clear()	Removes all elements (makes the slist empty)

Splice Functions

Operation	Effect
c.unique()	Removes duplicates of consecutive elements with the same value
c.unique(op)	Removes duplicates of consecutive elements, for which op() yields true
c1.splice(pos,c2)	Moves all elements of c2 to c1 in front of the iterator position pos
c1.splice(pos,c2,c2pos)	Moves the element at c2pos in c2 in front of pos of slist c1 (c1 and c2 may be the same)
c1.splice(pos,c2,c2beg,c2end)	Moves all elements of the range [c2beg,c2end) in c2 in front of pos of slist c1 (c1 and c2 may be the same)
c1.splice_after(pos,c2)	Transfers all the elements of slist c2 to c1, after the element pointed by pos
c.sort()	Sorts all elements with operator <
c1.merge(c2)	Assuming both slist contain the elements sorted, moves all elements of c2 into c1 so that all elements are merged and still sorted
c1.merge(c2,op)	Assuming both slist contain the elements sorted due to the sorting criterion op(), moves all elements of c2 into c1 so that all elements are merged and still sorted according to op()
c.reverse()	Reverses the order of all elements