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.
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. [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) beforepos. 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.
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.
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
followingpos. The return value is an iterator that points
to the new element. Complexity: constant time.
pos must be a dereferenceable iterator in *this. (That is,
pos may not be end().) Inserts a copy of x immediately
followingpos. The return value is an iterator that points
to the new element. Complexity: constant time.
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.
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.
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
followingprev to *this, inserting it immediately afterpos. Complexity: constant time.
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 afterpos. Complexity: constant time.
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.
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.
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.
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.