File: Slist.html

package info (click to toggle)
stl-manual 3.30-4
links: PTS
area: main
in suites: sarge, woody
size: 4,088 kB
ctags: 4,449
sloc: cpp: 17,845; ansic: 2,842; makefile: 35
file content (1201 lines) | stat: -rw-r--r-- 33,645 bytes
parent folder | download | duplicates (5)
<HTML>
<!--
  -- Copyright (c) 1996-1999
  -- Silicon Graphics Computer Systems, Inc.
  --
  -- Permission to use, copy, modify, distribute and sell this software
  -- and its documentation for any purpose is hereby granted without fee,
  -- provided that the above copyright notice appears in all copies and
  -- that both that copyright notice and this permission notice appear
  -- in supporting documentation.  Silicon Graphics makes no
  -- representations about the suitability of this software for any
  -- purpose.  It is provided "as is" without express or implied warranty.
  --
  -- Copyright (c) 1994
  -- Hewlett-Packard Company
  --
  -- Permission to use, copy, modify, distribute and sell this software
  -- and its documentation for any purpose is hereby granted without fee,
  -- provided that the above copyright notice appears in all copies and
  -- that both that copyright notice and this permission notice appear
  -- in supporting documentation.  Hewlett-Packard Company makes no
  -- representations about the suitability of this software for any
  -- purpose.  It is provided "as is" without express or implied warranty.
  --
  -->
<Head>
<Title>slist&lt;T, Alloc&gt;</Title>
<!-- Generated by htmldoc -->
</HEAD>
<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 
	ALINK="#ff0000"> 
<IMG SRC="CorpID.gif" 
     ALT="SGI" HEIGHT="43" WIDTH="151"> 
<!--end header-->
<BR Clear>
<H1>slist&lt;T, Alloc&gt;</H1>

<Table CellPadding=0 CellSpacing=0 width=100%>
<TR>
<TD Align=left><Img src = "containers.gif" Alt=""   WIDTH = "194"  HEIGHT = "38" ></TD>
<TD Align=right><Img src = "type.gif" Alt=""   WIDTH = "194"  HEIGHT = "39" ></TD>
</TR>
<TR>
<TD Align=left VAlign=top><b>Category</b>: containers</TD>
<TD Align=right VAlign=top><b>Component type</b>: type</TD>
</TR>
</Table>

<h3>Description</h3>
An <tt>slist</tt> is a singly linked list: a list where each element is
linked to the next element, but not to the previous element.  <A href="#1">[1]</A> That is,
it is a <A href="Sequence.html">Sequence</A> that supports forward but not backward traversal,
and (amortized) constant time insertion and removal of elements.
<tt>Slist</tt>s, like <tt><A href="List.html">list</A></tt>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,
<tt>slist&lt;T&gt;::iterator</tt> 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. <A href="#2">[2]</A>
<P>
The main difference between <tt>slist</tt> and <tt><A href="List.html">list</A></tt> is that <tt><A href="List.html">list</A></tt>'s
iterators are <A href="BidirectionalIterator.html">bidirectional iterators</A>, while <tt>slist</tt>'s iterators
are <A href="ForwardIterator.html">forward iterators</A>.  This means that <tt>slist</tt> is less versatile
than <tt><A href="List.html">list</A></tt>; frequently, however, <A href="BidirectionalIterator.html">bidirectional iterators</A>
are unnecessary.  You should usually use <tt>slist</tt> unless you actually
need the extra functionality of <tt><A href="List.html">list</A></tt>, because singly linked
lists are smaller and faster than double linked lists.
<P>
<b>Important performance note</b>: like every other <A href="Sequence.html">Sequence</A>, <tt>slist</tt>
defines the member functions <tt>insert</tt> and <tt>erase</tt>.  Using these member
functions carelessly, however, can result in disastrously slow
programs.  The problem is that <tt>insert</tt>'s first argument is an
iterator <tt>pos</tt>, and that it inserts the new element(s) <i>before</i>
<tt>pos</tt>.  This means that <tt>insert</tt> must find the iterator just
before <tt>pos</tt>;  this is a constant-time operation for <tt><A href="List.html">list</A></tt>, 
since <tt><A href="List.html">list</A></tt> has bidirectional iterators, but for <tt>slist</tt>
it must find that iterator by traversing the list from the beginning
up to <tt>pos</tt>.  In other words: <tt>insert</tt> and <tt>erase</tt> are slow operations
anywhere but near the beginning of the <tt>slist</tt>.
<P>
<tt>Slist</tt> provides the member functions <tt>insert_after</tt> and
<tt>erase_after</tt>, which are constant time operations: you should always
use <tt>insert_after</tt> and <tt>erase_after</tt> whenever possible.  If you find
that <tt>insert_after</tt> and <tt>erase_after</tt> aren't adequate for your needs,
and that you often need to use <tt>insert</tt> and <tt>erase</tt> in the middle of
the list, then you should probably use <tt><A href="List.html">list</A></tt> instead of <tt>slist</tt>.
<h3>Definition</h3>
Defined in the header <A href="slist">slist</A>, and in the backward-compatibility
header <A href="slist.h">slist.h</A>.  
The <tt>slist</tt> class, and the <A href="slist">slist</A> header, are an SGI extension;
they are not part of the C++ standard.
<h3>Example</h3>
<pre>
int main() {
  slist&lt;int&gt; L;
  L.push_front(0);
  L.push_front(1);
  L.insert_after(L.begin(), 2);
  <A href="copy.html">copy</A>(L.begin(), L.end(),        // The output is 1 2 0
       <A href="ostream_iterator.html">ostream_iterator</A>&lt;int&gt;(cout, &quot; &quot;));
  cout &lt;&lt; endl;

  slist&lt;int&gt;::iterator back = L.previous(L.end());
  back = L.insert_after(back, 3); 
  back = L.insert_after(back, 4);
  back = L.insert_after(back, 5);
  <A href="copy.html">copy</A>(L.begin(), L.end(),        // The output is 1 2 0 3 4 5
       <A href="ostream_iterator.html">ostream_iterator</A>&lt;int&gt;(cout, &quot; &quot;));
  cout &lt;&lt; endl;
}
</pre>
<h3>Template parameters</h3>
<Table border>
<TR>
<TH>
Parameter
</TH>
<TH>
Description
</TH>
<TH>
Default
</TH>
</TR>
<TR>
<TD VAlign=top>
<tt>T</tt>
</TD>
<TD VAlign=top>
The <tt>slist</tt>'s value type: the type of object that is stored in the list.
</TD>
<TD VAlign=top>
&nbsp;
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>Alloc</tt>
</TD>
<TD VAlign=top>
The <tt>slist</tt>'s allocator, used for all internal memory management.
</TD>
<TD VAlign=top>
<tt><A href="Allocators.html">alloc</A></tt>
</TD>
</tr>
</table>
<h3>Model of</h3>
<A href="FrontInsertionSequence.html">Front Insertion Sequence</A>
<h3>Type requirements</h3>
None, except for those imposed by the requirements of 
<A href="FrontInsertionSequence.html">Front Insertion Sequence</A>.
<h3>Public base classes</h3>
None.
<h3>Members</h3>
<Table border>
<TR>
<TH>
Member
</TH>
<TH>
Where defined
</TH>
<TH>
Description
</TH>
</TR>
<TR>
<TD VAlign=top>
<tt>value_type</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
The type of object, <tt>T</tt>, stored in the <tt>slist</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>pointer</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
Pointer to <tt>T</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>reference</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
Reference to <tt>T</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>const_reference</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
Const reference to <tt>T</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>size_type</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
An unsigned integral type.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>difference_type</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
A signed integral type.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>iterator</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
Iterator used to iterate through an <tt>slist</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>const_iterator</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
Const iterator used to iterate through an <tt>slist</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>iterator begin()</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
Returns an <tt>iterator</tt> pointing to the beginning of the <tt>slist</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>iterator end()</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
Returns an <tt>iterator</tt> pointing to the end of the <tt>slist</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>const_iterator begin() const</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
Returns a <tt>const_iterator</tt> pointing to the beginning of the <tt>slist</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>const_iterator end() const</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
Returns a <tt>const_iterator</tt> pointing to the end of the <tt>slist</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>size_type size() const</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
Returns the size of the <tt>slist</tt>.  Note: you should not assume that
   this function is constant time.  It is permitted to be <i>O(N</i>), 
   where <i>N</i> is the number of elements in the <tt>slist</tt>.  If you wish to
   test whether an <tt>slist</tt> is empty, you should write <tt>L.empty()</tt> rather
   than <tt>L.size() == 0</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>size_type max_size() const</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
Returns the largest possible size of the <tt>slist</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>bool empty() const</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
<tt>true</tt> if the <tt>slist</tt>'s size is <tt>0</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>slist()</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
Creates an empty slist.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>slist(size_type n)</tt>
</TD>
<TD VAlign=top>
 <A href="Sequence.html">Sequence</A>
</TD>
<TD VAlign=top>
Creates an <tt>slist</tt> with <tt>n</tt> elements, each of which is a copy of <tt>T()</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>slist(size_type n, const T&amp; t)</tt>
</TD>
<TD VAlign=top>
 <A href="Sequence.html">Sequence</A>
</TD>
<TD VAlign=top>
Creates an slist with <tt>n</tt> copies of <tt>t</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>slist(const slist&amp;)</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
The copy constructor.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>
template &lt;class InputIterator&gt;
slist(InputIterator f, InputIterator l) 
<A href="#3">[3]</A>
</pre>
</TD>
<TD VAlign=top>
 <A href="Sequence.html">Sequence</A>
</TD>
<TD VAlign=top>
Creates an <tt>slist</tt> with a copy of a range.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>~slist()</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
The destructor.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>slist&amp; operator=(const slist&amp;)</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
The assignment operator
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void swap(slist&amp;)</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
Swaps the contents of two slists.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>reference front()</tt>
</TD>
<TD VAlign=top>
 <A href="FrontInsertionSequence.html">Front Insertion Sequence</A>
</TD>
<TD VAlign=top>
Returns the first element.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>const_reference front() const</tt>
</TD>
<TD VAlign=top>
 <A href="FrontInsertionSequence.html">Front Insertion Sequence</A>
</TD>
<TD VAlign=top>
Returns the first element.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void push_front(const T&amp;)</tt>
</TD>
<TD VAlign=top>
 <A href="FrontInsertionSequence.html">Front Insertion Sequence</A>
</TD>
<TD VAlign=top>
Inserts a new element at the beginning.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void pop_front()</tt>
</TD>
<TD VAlign=top>
 <A href="FrontInsertionSequence.html">Front Insertion Sequence</A>
</TD>
<TD VAlign=top>
Removes the first element.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>iterator previous(iterator pos)</tt>
</TD>
<TD VAlign=top>
<tt>slist</tt>
</TD>
<TD VAlign=top>
See below
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>const_iterator previous(const_iterator pos)</tt>
</TD>
<TD VAlign=top>
<tt>slist</tt>
</TD>
<TD VAlign=top>
See below
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>iterator insert(iterator pos, const T&amp; x)</tt>
</TD>
<TD VAlign=top>
 <A href="Sequence.html">Sequence</A>
</TD>
<TD VAlign=top>
Inserts <tt>x</tt> before <tt>pos</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>
template&lt;class InputIterator&gt;
void insert(iterator pos, InputIterator f, InputIterator l)
<A href="#3">[3]</A>
</pre>
</TD>
<TD VAlign=top>
 <A href="Sequence.html">Sequence</A>
</TD>
<TD VAlign=top>
Inserts the range <tt>[first, last)</tt> before <tt>pos</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>
void insert(iterator pos,
            size_type n, const value_type&amp; x)
</pre>
</TD>
<TD VAlign=top>
 <A href="Sequence.html">Sequence</A>
</TD>
<TD VAlign=top>
Inserts <tt>n</tt> copies of <tt>x</tt> before <tt>pos</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>iterator erase(iterator pos)</tt>
</TD>
<TD VAlign=top>
 <A href="Sequence.html">Sequence</A>
</TD>
<TD VAlign=top>
Erases the element at position <tt>pos</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>iterator erase(iterator first, iterator last)</tt>
</TD>
<TD VAlign=top>
 <A href="Sequence.html">Sequence</A>
</TD>
<TD VAlign=top>
Erases the range <tt>[first, last)</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void clear()</tt>
</TD>
<TD VAlign=top>
 <A href="Sequence.html">Sequence</A>
</TD>
<TD VAlign=top>
Erases all of the elements.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void resize(n, t = T())</tt>
</TD>
<TD VAlign=top>
 <A href="Sequence.html">Sequence</A>
</TD>
<TD VAlign=top>
Inserts or erases elements at the end such that the size becomes <tt>n</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>iterator insert_after(iterator pos)</tt>
</TD>
<TD VAlign=top>
<tt>slist</tt>
</TD>
<TD VAlign=top>
See below.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>iterator insert_after(iterator pos, const value_type&amp; x)</tt>
</TD>
<TD VAlign=top>
<tt>slist</tt>
</TD>
<TD VAlign=top>
See below.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>
template&lt;class InputIterator&gt;
void insert_after(iterator pos,
                  InputIterator f, InputIterator l)
</pre>
</TD>
<TD VAlign=top>
<tt>slist</tt>
</TD>
<TD VAlign=top>
See below.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>
void insert_after(iterator pos, 
                  size_type n, const value_type&amp; x)
</pre>
</TD>
<TD VAlign=top>
<tt>slist</tt>
</TD>
<TD VAlign=top>
See below.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>iterator erase_after(iterator pos)</tt>
</TD>
<TD VAlign=top>
<tt>slist</tt>
</TD>
<TD VAlign=top>
See below.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>iterator erase_after(iterator before_first, iterator last)</tt>
</TD>
<TD VAlign=top>
<tt>slist</tt>
</TD>
<TD VAlign=top>
See below.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void splice(iterator position, slist&amp; L)</tt>
</TD>
<TD VAlign=top>
<tt>slist</tt>
</TD>
<TD VAlign=top>
See below.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void splice(iterator position, slist&amp; L, iterator i)</tt>
</TD>
<TD VAlign=top>
<tt>slist</tt>
</TD>
<TD VAlign=top>
See below.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void splice(iterator position, slist&amp; L, iterator f, iterator l)</tt>
</TD>
<TD VAlign=top>
<tt>slist</tt>
</TD>
<TD VAlign=top>
See below.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void splice_after(iterator pos, iterator prev)</tt>
</TD>
<TD VAlign=top>
<tt>slist</tt>
</TD>
<TD VAlign=top>
See below.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>
void splice_after(iterator pos, 
                  iterator before_first, 
                  iterator before_last)
</pre>
</TD>
<TD VAlign=top>
<tt>slist</tt>
</TD>
<TD VAlign=top>
See below.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void remove(const T&amp; value)</tt>
</TD>
<TD VAlign=top>
<tt>slist</tt>
</TD>
<TD VAlign=top>
See below.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void unique()</tt>
</TD>
<TD VAlign=top>
<tt>slist</tt>
</TD>
<TD VAlign=top>
See below.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void merge(slist&amp; L)</tt>
</TD>
<TD VAlign=top>
<tt>slist</tt>
</TD>
<TD VAlign=top>
See below.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void sort()</tt>
</TD>
<TD VAlign=top>
<tt>slist</tt>
</TD>
<TD VAlign=top>
See below.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>
bool operator==(const slist&amp;, 
                const slist&amp;)
</pre>
</TD>
<TD VAlign=top>
 <A href="ForwardContainer.html">Forward Container</A>
</TD>
<TD VAlign=top>
Tests two slists for equality.  This is a global function, not
   a member function.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>
bool operator&lt;(const slist&amp;, 
               const slist&amp;)
</pre> 
</TD>
<TD VAlign=top>
 <A href="ForwardContainer.html">Forward Container</A>
</TD>
<TD VAlign=top>
Lexicographical comparison.  This is a global function, not
   a member function.
</TD>
</tr>
</table>
<h3>New members</h3>
These members are not defined in the 
<A href="FrontInsertionSequence.html">Front Insertion Sequence</A> requirements, but are specific to <tt>slist</tt>:
<Table border>
<TR>
<TH>
Function
</TH>
<TH>
Description
</TH>
</TR>
<TR>
<TD VAlign=top>
<tt>iterator previous(iterator pos)</tt>
</TD>
<TD VAlign=top>
<tt>pos</tt> must be a valid iterator in <tt>*this</tt>.  The return value is
   an iterator <tt>prev</tt> such that <tt>++prev == pos</tt>.  Complexity:
   linear in the number of iterators in the range <tt>[begin(), pos)</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>const_iterator previous(const_iterator pos)</tt>
</TD>
<TD VAlign=top>
<tt>pos</tt> must be a valid iterator in <tt>*this</tt>.  The return value is
   an iterator <tt>prev</tt> such that <tt>++prev == pos</tt>.  Complexity:
   linear in the number of iterators in the range <tt>[begin(), pos)</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>iterator insert_after(iterator pos)</tt>
</TD>
<TD VAlign=top>
<tt>pos</tt> must be a dereferenceable iterator in <tt>*this</tt>.  (That is,
   <tt>pos</tt> may not be <tt>end()</tt>.)  Inserts a copy of <tt>T()</tt> immediately
   <i>following</i> <tt>pos</tt>.  The return value is an iterator that points
   to the new element.  Complexity: constant time.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>
iterator insert_after(iterator pos,
                      const value_type&amp; x)
</pre>
</TD>
<TD VAlign=top>
<tt>pos</tt> must be a dereferenceable iterator in <tt>*this</tt>.  (That is,
   <tt>pos</tt> may not be <tt>end()</tt>.)  Inserts a copy of <tt>x</tt> immediately
   <i>following</i> <tt>pos</tt>.  The return value is an iterator that points
   to the new element.  Complexity: constant time.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>
template&lt;class InputIterator&gt;
void insert_after(iterator pos,
                  InputIterator f, InputIterator l)
</pre>
</TD>
<TD VAlign=top>
Inserts elements from the range <tt>[f, l)</tt> immediately
   <i>following</i> <tt>pos</tt>.  Complexity: linear in <tt>last - first</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>
void insert_after(iterator pos, 
                  size_type n, const value_type&amp; x)
</pre>
</TD>
<TD VAlign=top>
Inserts <tt>n</tt> copies of <tt>x</tt> immediately <i>following</i> <tt>pos</tt>.
   Complexity: linear in <tt>n</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>iterator erase_after(iterator pos)</tt>
</TD>
<TD VAlign=top>
Erases the element pointed to by the iterator <i>following</i> <tt>pos</tt>.
   Complexity: constant time.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>iterator erase_after(iterator before_first, iterator last)</tt>
</TD>
<TD VAlign=top>
Erases all elements in the range <tt>[before_first + 1, last)</tt>.
   Complexity: linear in <tt>last - (before_first + 1)</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>
void splice(iterator position, 
            slist&lt;T, Alloc&gt;&amp; x);
</pre>
</TD>
<TD VAlign=top>
<tt>position</tt> must be a valid iterator in <tt>*this</tt>, and <tt>x</tt> must be an slist
    that is distinct from <tt>*this</tt>.  (That is, it is required that
   <tt>&amp;x != this</tt>.)  All of the elements of <tt>x</tt> are inserted before
   <tt>position</tt> and removed from <tt>x</tt>.  All iterators remain valid, 
   including iterators that point to elements of <tt>x</tt>. <A href="#4">[4]</A> Complexity:
   proportional to <tt>c1 (position - begin()) + c2(x.size())</tt>, where <tt>c1</tt>
   and <tt>c2</tt> are unknown constants.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre> 
void splice(iterator position, 
            slist&lt;T, Alloc&gt;&amp; x,
            iterator i);
</pre>
</TD>
<TD VAlign=top>
<tt>position</tt> must be a valid iterator in <tt>*this</tt>, and <tt>i</tt> must be a
   dereferenceable iterator in <tt>x</tt>.  <tt>Splice</tt> moves the element
   pointed to by <tt>i</tt> from <tt>x</tt> to <tt>*this</tt>, inserting it before
   <tt>position</tt>.  All iterators remain valid, including iterators that point
   to elements of <tt>x</tt>. <A href="#4">[4]</A>  If <tt>position == i</tt> or <tt>position == ++i</tt>,
   this function is a null operation.  Complexity: proportional to
   <tt>c1 (position - begin()) + c2 (i - x.begin())</tt>, where <tt>c1</tt> and
   <tt>c2</tt> are unknown constants.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre> 
void splice(iterator position, 
            slist&lt;T, Alloc&gt;&amp; x,
            iterator f, iterator l);
</pre>
</TD>
<TD VAlign=top>
<tt>position</tt> must be a valid iterator in <tt>*this</tt>, and <tt>[first, last)</tt>
   must be a valid range in <tt>x</tt>.  <tt>position</tt> may not be an iterator
   in the range <tt>[first, last)</tt>.  <tt>Splice</tt> moves the elements 
   in <tt>[first, last)</tt> from <tt>x</tt> to <tt>*this</tt>, inserting them before
   <tt>position</tt>.  All iterators remain valid, including iterators that
   point to elements of <tt>x</tt>. <A href="#4">[4]</A>  Complexity: proportional to
   <tt>c1 (position - begin()) + c2 (f - x.begin()) + c3 (l - f)</tt>, 
   where <tt>c1</tt>, <tt>c2</tt>, and <tt>c3</tt> are unknown constants.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void remove(const T&amp; val);</tt>
</TD>
<TD VAlign=top>
Removes all elements that compare equal to <tt>val</tt>.  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 <tt>size()</tt> comparisons for equality.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void splice_after(iterator pos, iterator prev)</tt>
</TD>
<TD VAlign=top>
<tt>pos</tt> must be a dereferenceable iterator in <tt>*this</tt>, and <tt>prev</tt>
   must be a dereferenceable iterator either in <tt>*this</tt> or in some
   other <tt>slist</tt>.  (Note: &quot;dereferenceable iterator&quot; implies that neither
   <tt>pos</tt> nor <tt>prev</tt> may be an off-the-end iterator.)  Moves the element
   <i>following</i> <tt>prev</tt> to <tt>*this</tt>, inserting it immediately <i>after</i>
   <tt>pos</tt>.  Complexity: constant time.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>
void splice_after(iterator pos, 
                  iterator before_first, 
                  iterator before_last)
</pre>
</TD>
<TD VAlign=top>
<tt>pos</tt> must be a dereferenceable iterator in <tt>*this</tt>, and
   <tt>before_first</tt> and <tt>before_last</tt> must be dereferenceable iterators
   either in <tt>*this</tt> or in some other <tt>slist</tt>.  (Note: 
   &quot;dereferenceable iterator&quot; implies that none of these iterators may
   be off-the-end iterators.)  Moves the elements in the range
   <tt>[before_first + 1, before_last + 1)</tt> to <tt>*this</tt>, inserting
   them immediately <i>after</i> <tt>pos</tt>.  Complexity: constant time.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>
template&lt;class <A href="Predicate.html">Predicate</A>&gt; 
void remove_if(<A href="Predicate.html">Predicate</A> p); 
<A href="#5">[5]</A>
</pre>
</TD>
<TD VAlign=top>
Removes all elements <tt>*i</tt> such that <tt>p(*i)</tt> 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 <tt>size()</tt> applications of <tt>p</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void unique();</tt>
</TD>
<TD VAlign=top>
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 <tt>size() - 1</tt> comparisons for equality.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>
template&lt;class <A href="BinaryPredicate.html">BinaryPredicate</A>&gt;
void unique(<A href="BinaryPredicate.html">BinaryPredicate</A> p); 
<A href="#5">[5]</A>
</pre>
</TD>
<TD VAlign=top>
Removes all but the first element in every consecutive group of
   equivalent elements, where two elements <tt>*i</tt> and <tt>*j</tt> are considered
   equivalent if <tt>p(*i, *j)</tt> 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 <tt>size() - 1</tt> comparisons for
   equality. 
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void merge(slist&lt;T, Alloc&gt;&amp; x);</tt>
</TD>
<TD VAlign=top>
Both <tt>*this</tt> and <tt>x</tt> must be sorted according to <tt>operator&lt;</tt>, and
   they must be distinct.
   (That is, it is required that <tt>&amp;x != this</tt>.)  This function removes
   all of <tt>x</tt>'s elements and inserts them in order into <tt>*this</tt>.  The merge is
   stable; that is, if an element from <tt>*this</tt> is equivalent to one from
   <tt>x</tt>, then the element from <tt>*this</tt> will precede the one from <tt>x</tt>.
   All iterators to elements in <tt>*this</tt> and <tt>x</tt> remain valid.  
   This function is linear time:  it performs at most <tt>size() + x.size()
   - 1</tt> comparisons.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>
template&lt;class <A href="BinaryPredicate.html">BinaryPredicate</A>&gt;
void merge(slist&lt;T, Alloc&gt;&amp; x, 
           BinaryPredicate Comp); 
<A href="#5">[5]</A>
</pre>
</TD>
<TD VAlign=top>
<tt>Comp</tt> must be a comparison function that induces a strict weak
   ordering (as defined in the <A href="LessThanComparable.html">LessThan Comparable</A> requirements)
   on objects of type <tt>T</tt>, and both <tt>*this</tt> and <tt>x</tt> must be sorted
   according to that ordering.  The slists <tt>x</tt> and <tt>*this</tt> must be 
   distinct.  (That is, it is required that <tt>&amp;x != this</tt>.)
   This function removes
   all of <tt>x</tt>'s elements and inserts them in order into <tt>*this</tt>.  The merge is
   stable; that is, if an element from <tt>*this</tt> is equivalent to one from
   <tt>x</tt>, then the element from <tt>*this</tt> will precede the one from <tt>x</tt>.
   All iterators to elements in <tt>*this</tt> and <tt>x</tt> remain valid.  
   This function is linear time:  it performs at most <tt>size() + x.size()
   - 1</tt> applications of <tt>Comp</tt>. 
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void reverse();</tt>
</TD>
<TD VAlign=top>
Reverses the order of elements in the slist.  All iterators remain
   valid and continue to point to the same elements. <A href="#6">[6]</A> This function
   is linear time.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void sort();</tt>
</TD>
<TD VAlign=top>
Sorts <tt>*this</tt> according to <tt>operator&lt;</tt>.  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. <A href="#7">[7]</A>  The number
   of comparisons is approximately <tt>N log N</tt>, where <tt>N</tt> is the <tt>slist</tt>'s
   size.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>
template&lt;class <A href="BinaryPredicate.html">BinaryPredicate</A>&gt;
void sort(BinaryPredicate comp); 
<A href="#5">[5]</A>
</pre>
</TD>
<TD VAlign=top>
<tt>Comp</tt> must be a comparison function that induces a strict weak
   ordering (as defined in the <A href="LessThanComparable.html">LessThan Comparable</A> requirements)
   on objects of type <tt>T</tt>.  This function sorts the slist
   <tt>*this</tt> according to <tt>Comp</tt>.  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. <A href="#7">[7]</A>  The number
   of comparisons is approximately <tt>N log N</tt>, where <tt>N</tt> is the <tt>slist</tt>'s
   size.
</TD>
</tr>
</table>
<h3>Notes</h3>
<P><A name="1">[1]</A>
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.
<P><A name="2">[2]</A>
A comparison with <tt><A href="Vector.html">vector</A></tt> is
instructive.  Suppose that <tt>i</tt> is a valid
<tt><A href="Vector.html">vector</A>&lt;T&gt;::iterator</tt>.  If an element
is inserted or removed in a position that precedes <tt>i</tt>, then
this operation will either result in <tt>i</tt> pointing to a
different element than it did before, or else it will invalidate
<tt>i</tt> entirely.  (A 
<tt><A href="Vector.html">vector</A>&lt;T&gt;::iterator</tt> will be
invalidated, for example, if an insertion requires a reallocation.)
However, suppose that <tt>i</tt> and <tt>j</tt> are both iterators
into a <A href="Vector.html">vector</A>, and there exists some integer
<tt>n</tt> such that <tt>i == j + n</tt>.  In that case, even if
elements are inserted into the vector and <tt>i</tt> and <tt>j</tt>
point to different elements, the relation between the two iterators
will still hold.  An <tt>slist</tt> is exactly the opposite: iterators
will not be invalidated, and will not be made to point to different
elements, but, for <tt>slist</tt> iterators, the predecessor/successor
relationship is not invariant.
<P><A name="3">[3]</A>
This member function relies on <i>member template</i> 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 <A href="InputIterator.html">input iterator</A>.  If your
compiler does not yet support member templates, though, then the
arguments must either be of type <tt>const value_type*</tt> or of type
<tt>slist::const_iterator</tt>.
<P><A name="4">[4]</A>
A similar property holds for all versions of <tt>insert()</tt> and
<tt>erase()</tt>.  <tt>Slist&lt;T, Alloc&gt;::insert()</tt> never
invalidates any iterators, and <tt>slist&lt;T, Alloc&gt;::erase()</tt>
only invalidates iterators pointing to the elements that are actually
being erased.
<P><A name="5">[5]</A>
This member function relies on <i>member template</i> 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.
<P><A name="6">[6]</A>
The <tt><A href="reverse.html">reverse</A></tt> algorithm works only
for <A href="BidirectionalIterator.html">bidirectional iterators</A>.
Even if <tt><A href="reverse.html">reverse</A></tt> were extended to
work with <A href="ForwardIterator.html">forward iterators</A>,
however, it would still be useful to have the <tt>reverse</tt> member
function: it has different iterator invalidation semantics.  That is,
the <tt>reverse</tt> member function preserves the value that each
iterator points to.  Note also that the algorithm
<tt><A href="reverse.html">reverse</A>(L.begin(), L.end())</tt> uses 
<tt>T</tt>'s assignment operator, but the member function
<tt>L.reverse()</tt> does not.
<P><A name="7">[7]</A>
The <tt><A href="sort.html">sort</A></tt> algorithm  works only for
<A href="RandomAccessIterator.html">random access iterators</A>.  In
principle, however, it would be possible to write a sort algorithm
that also accepted
<A href="ForwardIterator.html">forward iterators</A>.  Even if there were such a version
of <tt><A href="sort.html">sort</A></tt>, it would still be useful for
<tt>slist</tt> to have a <tt>sort</tt> member function.  That is,
<tt>sort</tt> 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.
<h3>See also</h3>
<A href="BidirectionalIterator.html">Bidirectional Iterator</A>,
<A href="ReversibleContainer.html">Reversible Container</A>,
<A href="Sequence.html">Sequence</A>,
<tt><A href="List.html">list</A></tt>,
<tt><A href="Vector.html">vector</A></tt>

<!--start footer--> 
<HR SIZE="6">
<A href="http://www.sgi.com/"><IMG SRC="surf.gif" HEIGHT="54" WIDTH="54" 
        ALT="[Silicon Surf]"></A>
<A HREF="index.html"><IMG SRC="stl_home.gif" 
        HEIGHT="54" WIDTH="54" ALT="[STL Home]"></A>
<BR>
<FONT SIZE="-2">
<A href="http://www.sgi.com/Misc/sgi_info.html" TARGET="_top">Copyright &copy; 
1999 Silicon Graphics, Inc.</A> All Rights Reserved.</FONT>
<FONT SIZE="-3"><a href="http://www.sgi.com/Misc/external.list.html" TARGET="_top">TrademarkInformation</A>
</FONT>
<P>
</BODY>
</HTML>