slist.html

Standard Template Library (SOURCE + COMPLETE html man document)

</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 -->
<!-- Footer Begins -->

<STYLE TYPE="text/css">
<!--
TD.footer, TD.footer A{
		font-family: Arial, helvetica, sans-serif;
        	font-size: 8pt;

}

A.home {
font-family: Arial, helvetica, sans-serif;
}
-->
</STYLE>
<P>
<A CLASS="home" HREF="index.html">STL Home</A>
<P>
<TABLE WIDTH="600" CELLPADDING="0" CELLPADDING="0" BORDER="0">
	<TR>
	    <TD ALIGN="RIGHT" CLASS="footer"><A HREF="/company_info/terms.html" TARGET="_top">terms of use</A> | <A HREF="/company_info/privacy.html" TARGET="_top">privacy policy</A></TD>
	    <TD ALIGN="CENTER" CLASS="footer">&nbsp;|&nbsp;</TD>
	    <TD ALIGN="LEFT" CLASS="footer"><A HREF="/cgi-bin/feedback/" TARGET="_top">contact us</A></TD>
	</TR><TR>
	    <TD ALIGN="RIGHT" CLASS="footer">Copyright &copy; 1993-2003 Silicon Graphics, Inc. All rights reserved.</TD>
	    <TD ALIGN="CENTER" CLASS="footer">&nbsp;|&nbsp;</TD>
	    <TD ALIGN="LEFT" CLASS="footer"><A HREF="/company_info/trademarks/" TARGET="_top">Trademark Information</A></TD>
	</TR>
</TABLE>

<!-- Footer Ends -->

<!-- end footer -->
<P>
</BODY>
</HTML>