# slist<T, Alloc>

Category: containers | Component type: type

### 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. [1] That is, it is a Sequence that supports forward but not backward traversal, and (amortized) constant time insertion and removal of elements. `Slist`s, like `list`s, 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. [2]

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 `pos`, and that it inserts the new element(s) before `pos`. This means that `insert` must find the iterator just before `pos`; 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 `pos`. 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`.

### Definition

Defined in the header slist, and in the backward-compatibility header slist.h. The `slist` class, and the slist header, are an SGI extension; they are not part of the C++ standard.

### Example

    int main() {
      slist<int> L;
      L.push_front(0);
      L.push_front(1);
      L.insert_after(L.begin(), 2);
      copy(L.begin(), L.end(),        // The output is 1 2 0
           ostream_iterator<int>(cout, " "));
      cout << endl;

      slist<int>::iterator back = L.previous(L.end());
      back = L.insert_after(back, 3);
      back = L.insert_after(back, 4);
      back = L.insert_after(back, 5);
      copy(L.begin(), L.end(),        // The output is 1 2 0 3 4 5
           ostream_iterator<int>(cout, " "));
      cout << endl;
    }

### Template parameters

Parameter | Description | Default
--- | --- | ---
`T` | The `slist`'s value type: the type of object that is stored in the list. |
`Alloc` | The `slist`'s allocator, used for all internal memory management. | `alloc`

### Model of

Front Insertion Sequence

### Type requirements

None, except for those imposed by the requirements of Front Insertion Sequence.

### Public base classes

None.

### Members

Member | Where defined | Description
--- | --- | ---
`value_type` | Container | The type of object, `T`, stored in the `slist`.
`pointer` | Container | Pointer to `T`.
`reference` | Container | Reference to `T`
`const_reference` | Container | Const reference to `T`
`size_type` | Container | An unsigned integral type.
`difference_type` | Container | A signed integral type.
`iterator` | Container | Iterator used to iterate through an `slist`.
`const_iterator` | Container | Const iterator used to iterate through an `slist`.
`iterator begin()` | Container | Returns an `iterator` pointing to the beginning of the `slist`.
`iterator end()` | Container | Returns an `iterator` pointing to the end of the `slist`.
`const_iterator begin() const` | Container | Returns a `const_iterator` pointing to the beginning of the `slist`.
`const_iterator end() const` | Container | Returns a `const_iterator` pointing to the end of the `slist`.
`size_type size() const` | Container | Returns the size of the `slist`. Note: you should not assume that this function is constant time. It is permitted to be O(N), where N is the number of elements in the `slist`. If you wish to test whether an `slist` is empty, you should write `L.empty()` rather than `L.size() == 0`.
`size_type max_size() const` | Container | Returns the largest possible size of the `slist`.
`bool empty() const` | Container | `true` if the `slist`'s size is `0`.
`slist()` | Container | Creates an empty slist.
`slist(size_type n)` | Sequence | Creates an `slist` with `n` elements, each of which is a copy of `T()`.
`slist(size_type n, const T& t)` | Sequence | Creates an slist with `n` copies of `t`.
`slist(const slist&)` | Container | The copy constructor.
    template <class InputIterator>
    slist(InputIterator f, InputIterator l)
    [3]
| Sequence | Creates an `slist` with a copy of a range.
`~slist()` | Container | The destructor.
`slist& operator=(const slist&)` | Container | The assignment operator
`void swap(slist&)` | Container | Swaps the contents of two slists.
`reference front()` | Front Insertion Sequence | Returns the first element.
`const_reference front() const` | Front Insertion Sequence | Returns the first element.
`void push_front(const T&)` | Front Insertion Sequence | Inserts a new element at the beginning.
`void pop_front()` | Front Insertion Sequence | Removes the first element.
`iterator previous(iterator pos)` | `slist` | See below
`const_iterator previous(const_iterator pos)` | `slist` | See below
`iterator insert(iterator pos, const T& x)` | Sequence | Inserts `x` before `pos`.
    template<class InputIterator>
    void insert(iterator pos, InputIterator f, InputIterator l)
    [3]
| Sequence | Inserts the range `[first, last)` before `pos`.
    void insert(iterator pos,
                size_type n, const value_type& x)
| Sequence | Inserts `n` copies of `x` before `pos`.
`iterator erase(iterator pos)` | Sequence | Erases the element at position `pos`.
`iterator erase(iterator first, iterator last)` | Sequence | Erases the range `[first, last)`
`void clear()` | Sequence | Erases all of the elements.
`iterator insert_after(iterator pos)` | `slist` | See below.
`iterator insert_after(iterator pos, const value_type& x)` | `slist` | See below.
    template<class InputIterator>
    void insert_after(iterator pos,
                      InputIterator f, InputIterator l)
| `slist` | See below.
    void insert_after(iterator pos,
                      size_type n, const value_type& x)
| `slist` | See below.
`iterator erase_after(iterator pos)` | `slist` | See below.
`iterator erase_after(iterator before_first, iterator last)` | `slist` | See below.
`void splice(iterator position, slist& L)` | `slist` | See below.
`void splice(iterator position, slist& L, iterator i)` | `slist` | See below.
`void splice(iterator position, slist& L, iterator f, iterator l)` | `slist` | See below.
`void splice_after(iterator pos, iterator prev)` | `slist` | See below.
    void splice_after(iterator pos,
                      iterator before_first,
                      iterator before_last)
| `slist` | See below.
`void remove(const T& value)` | `slist` | See below.
`void unique()` | `slist` | See below.
`void merge(slist& L)` | `slist` | See below.
`void sort()` | `slist` | See below.
    bool operator==(const slist&,
                    const slist&)
| Forward Container | Tests two slists for equality. This is a global function, not a member function.
    bool operator<(const slist&,
                   const slist&)
| Forward Container | Lexicographical comparison. This is a global function, not a member function.

### New members

These members are not defined in the Front Insertion Sequence requirements, but are specific to `slist`:

Function | Description
--- | ---
`iterator previous(iterator pos)` | `pos` must be a valid iterator in `*this`. The return value is an iterator `prev` such that `++prev == pos`. Complexity: linear in the number of iterators in the range `[begin(), pos)`.
`const_iterator previous(const_iterator pos)` | `pos` must be a valid iterator in `*this`. The return value is an iterator `prev` such that `++prev == pos`. Complexity: linear in the number of iterators in the range `[begin(), pos)`.
`iterator insert_after(iterator pos)` | `pos` must be a dereferenceable iterator in `*this`. (That is, `pos` may not be `end()`.) Inserts a copy of `T()` immediately following `pos`. The return value is an iterator that points to the new element. Complexity: constant time.
    iterator insert_after(iterator pos,
                          const value_type& x)
| `pos` must be a dereferenceable iterator in `*this`. (That is, `pos` may not be `end()`.) Inserts a copy of `x` immediately following `pos`. The return value is an iterator that points to the new element. Complexity: constant time.
    template<class InputIterator>
    void insert_after(iterator pos,
                      InputIterator f, InputIterator l)
| Inserts elements from the range `[f, l)` immediately following `pos`. Complexity: linear in `last - first`.
    void insert_after(iterator pos,
                      size_type n, const value_type& x)
| Inserts `n` copies of `x` immediately following `pos`. Complexity: linear in `n`.
`iterator erase_after(iterator pos)` | Erases the element pointed to by the iterator following `pos`. Complexity: constant time.
`iterator erase_after(iterator before_first, iterator last)` | Erases all elements in the range `[before_first + 1, last)`. Complexity: linear in `last - (before_first + 1)`.
    void splice(iterator position,
                slist<T, Alloc>& x);
| `position` must be a valid iterator in `*this`, and `x` must be an slist that is distinct from `*this`. (That is, it is required that `&x != this`.) All of the elements of `x` are inserted before `position` and removed from `x`. All iterators remain valid, including iterators that point to elements of `x`. [4] Complexity: proportional to `c1 (position - begin()) + c2(x.size())`, where `c1` and `c2` are unknown constants.
    void splice(iterator position,
                slist<T, Alloc>& x,
                iterator i);
| `position` must be a valid iterator in `*this`, and `i` must be a dereferenceable iterator in `x`. `Splice` moves the element pointed to by `i` from `x` to `*this`, inserting it before `position`. All iterators remain valid, including iterators that point to elements of `x`. [4] If `position == i` or `position == ++i`, this function is a null operation. Complexity: proportional to `c1 (position - begin()) + c2 (i - x.begin())`, where `c1` and `c2` are unknown constants.
    void splice(iterator position,
                slist<T, Alloc>& x,
                iterator f, iterator l);
| `position` must be a valid iterator in `*this`, and `[first, last)` must be a valid range in `x`. `position` may not be an iterator in the range `[first, last)`. `Splice` moves the elements in `[first, last)` from `x` to `*this`, inserting them before `position`. All iterators remain valid, including iterators that point to elements of `x`. [4] Complexity: proportional to `c1 (position - begin()) + c2 (f - x.begin()) + c3 (l - f)`, where `c1`, `c2`, and `c3` are unknown constants.
`void remove(const T& val);` | Removes all elements that compare equal to `val`. The relative order of elements that are not removed is unchanged, and iterators to elements that are not removed remain valid. This function is linear time: it performs exactly `size()` comparisons for equality.
`void splice_after(iterator pos, iterator prev)` | `pos` must be a dereferenceable iterator in `*this`, and `prev` must be a dereferenceable iterator either in `*this` or in some other `slist`. (Note: "dereferenceable iterator" implies that neither `pos` nor `prev` may be an off-the-end iterator.) Moves the element following `prev` to `*this`, inserting it immediately after `pos`. Complexity: constant time.
    void splice_after(iterator pos,
                      iterator before_first,
                      iterator before_last)
| `pos` must be a dereferenceable iterator in `*this`, and `before_first` and `before_last` must be dereferenceable iterators either in `*this` or in some other `slist`. (Note: "dereferenceable iterator" implies that none of these iterators may be off-the-end iterators.) Moves the elements in the range `[before_first + 1, before_last + 1)` to `*this`, inserting them immediately after `pos`. Complexity: constant time.
    template<class Predicate>
    void remove_if(Predicate p);
    [5]
| Removes all elements `*i` such that `p(*i)` is true. The relative order of elements that are not removed is unchanged, and iterators to elements that are not removed remain valid. This function is linear time: it performs exactly `size()` applications of `p`.
`void unique();` | Removes all but the first element in every consecutive group of equal elements. The relative order of elements that are not removed is unchanged, and iterators to elements that are not removed remain valid. This function is linear time: it performs exactly `size() - 1` comparisons for equality.
    template<class BinaryPredicate>
    void unique(BinaryPredicate p);
    [5]
| Removes all but the first element in every consecutive group of equivalent elements, where two elements `*i` and `*j` are considered equivalent if `p(*i, *j)` is true. The relative order of elements that are not removed is unchanged, and iterators to elements that are not removed remain valid. This function is linear time: it performs exactly `size() - 1` comparisons for equality.
`void merge(slist<T, Alloc>& x);` | Both `*this` and `x` must be sorted according to `operator<`, and they must be distinct. (That is, it is required that `&x != this`.) 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`. All iterators to elements in `*this` and `x` remain valid. This function is linear time: it performs at most `size() + x.size() - 1` comparisons.
    template<class BinaryPredicate>
    void merge(slist<T, Alloc>& x,
               BinaryPredicate Comp);
    [5]
| `Comp` must be a comparison function that induces a strict weak ordering (as defined in the LessThan Comparable requirements) on objects of type `T`, and both `*this` and `x` must be sorted according to that ordering. The slists `x` and `*this` must be distinct. (That is, it is required that `&x != this`.) 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`. All iterators to elements in `*this` and `x` remain valid. This function is linear time: it performs at most `size() + x.size() - 1` applications of `Comp`.
`void reverse();` | Reverses the order of elements in the slist. All iterators remain valid and continue to point to the same elements. [6] This function is linear time.
`void sort();` | Sorts `*this` according to `operator<`. The sort is stable, that is, the relative order of equivalent elements is preserved. All iterators remain valid and continue to point to the same elements. [7] The number of comparisons is approximately `N log N`, where `N` is the `slist`'s size.
    template<class BinaryPredicate>
    void sort(BinaryPredicate comp);
    [5]
| `Comp` must be a comparison function that induces a strict weak ordering (as defined in the LessThan Comparable requirements) on objects of type `T`. This function sorts the slist `*this` according to `Comp`. The sort is stable, that is, the relative order of equivalent elements is preserved. All iterators remain valid and continue to point to the same elements. [7] The number of comparisons is approximately `N log N`, where `N` is the `slist`'s size.

### Notes

[1] The lists in such languages as Common Lisp, Scheme, and ML are singly linked lists. In some programming languages, almost all data structures are represented as singly linked lists.

[2] A comparison with `vector` is instructive. Suppose that `i` is a valid `vector<T>::iterator`. If an element is inserted or removed in a position that precedes `i`, then this operation will either result in `i` pointing to a different element than it did before, or else it will invalidate `i` entirely. (A `vector<T>::iterator` will be invalidated, for example, if an insertion requires a reallocation.) However, suppose that `i` and `j` are both iterators into a vector, and there exists some integer `n` such that `i == j + n`. In that case, even if elements are inserted into the vector and `i` and `j` point to different elements, the relation between the two iterators will still hold. An `slist` is exactly the opposite: iterators will not be invalidated, and will not be made to point to different elements, but, for `slist` iterators, the predecessor/successor relationship is not invariant.

[3] This member function relies on member template functions, which at present (early 1998) are not supported by all compilers. If your compiler supports member templates, you can call this function with any type of input iterator. If your compiler does not yet support member templates, though, then the arguments must either be of type `const value_type*` or of type `slist::const_iterator`.

[4] A similar property holds for all versions of `insert()` and `erase()`. `Slist<T, Alloc>::insert()` never invalidates any iterators, and `slist<T, Alloc>::erase()` only invalidates iterators pointing to the elements that are actually being erased.

[5] This member function relies on member template functions, which at present (early 1998) are not supported by all compilers. You can only use this member function if your compiler supports member templates.

[6] The `reverse` algorithm works only for bidirectional iterators. Even if `reverse` were extended to work with forward iterators, however, it would still be useful to have the `reverse` member function: it has different iterator invalidation semantics. That is, the `reverse` member function preserves the value that each iterator points to. Note also that the algorithm `reverse(L.begin(), L.end())` uses `T`'s assignment operator, but the member function `L.reverse()` does not.

[7] The `sort` algorithm works only for random access iterators. In principle, however, it would be possible to write a sort algorithm that also accepted forward iterators. Even if there were such a version of `sort`, it would still be useful for `slist` to have a `sort` member function. That is, `sort` is provided as a member function not only for the sake of efficiency, but also because of the property that it preserves the values that list iterators point to.

### See also

Bidirectional Iterator, Reversible Container, Sequence, `list`, `vector`

Copyright © 1999 Silicon Graphics, Inc. All Rights Reserved. TrademarkInformation