Standard Template Library Programmer's Guide

supports member templates.

[5] If L is a list, note that L.reverse() and reverse(L.begin(), L.end()) are both correct ways of reversing the list. They differ in that L.reverse() will preserve the value that each iterator into L points to but will not preserve the iterators' predecessor/successor relationships, while reverse (L.begin(), L.end()) will not preserve the value that each iterator points to but will preserve the iterators' predecessor/successor relationships. Note also that the algorithm reverse (L.begin(), L.end ()) will use T 's assignment operator, while the member function L.reverse() will not.

[6] The sort algorithm works only for random access iterators . In principle, however, it would be possible to write a sort algorithm that also accepted bidirectional iterators. Even if there were such a version of sort, it would still be useful for list 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, slist, vector.

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

Model of