File: Sequence.html

package info (click to toggle)
stl-manual 3.30-11
links: PTS, VCS
area: main
in suites: squeeze
size: 5,436 kB
ctags: 4,550
sloc: cpp: 17,845; ansic: 2,842; makefile: 41
file content (738 lines) | stat: -rw-r--r-- 16,437 bytes
parent folder | download | duplicates (7)
<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>Sequence</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>Sequence</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 = "concept.gif" Alt=""   WIDTH = "194"  HEIGHT = "38" ></TD>
</TR>
<TR>
<TD Align=left VAlign=top><b>Category</b>: containers</TD>
<TD Align=right VAlign=top><b>Component type</b>: concept</TD>
</TR>
</Table>

<h3>Description</h3>
A Sequence is a variable-sized <A href="Container.html">Container</A> whose
elements are arranged in a strict linear order.  It supports insertion
and removal of elements.
<h3>Refinement of</h3>
<A href="ForwardContainer.html">Forward Container</A>, <A href="DefaultConstructible.html">Default Constructible</A>
<h3>Associated types</h3>
None, except for those of <A href="ForwardContainer.html">Forward Container</A>.
<h3>Notation</h3>
<Table>
<TR>
<TD VAlign=top>
<tt>X</tt>
</TD>
<TD VAlign=top>
A type that is a model of Sequence
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>a</tt>, <tt>b</tt>
</TD>
<TD VAlign=top>
Object of type <tt>X</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>T</tt>
</TD>
<TD VAlign=top>
The value type of <tt>X</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>t</tt>
</TD>
<TD VAlign=top>
Object of type <tt>T</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>p</tt>, <tt>q</tt>
</TD>
<TD VAlign=top>
Object of type <tt>X::iterator</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>n</tt>
</TD>
<TD VAlign=top>
Object of a type convertible to <tt>X::size_type</tt>
</TD>
</tr>
</table>
<h3>Definitions</h3>
If <tt>a</tt> is a Sequence, then <tt>p</tt> is a
<i>valid iterator in a</i> if it is a valid (nonsingular) iterator that is 
reachable from <tt>a.begin()</tt>.
<P>
If <tt>a</tt> is a Sequence, then <tt>[p, q)</tt> is a <i>valid range in a</i>
if <tt>p</tt> and <tt>q</tt> are valid iterators in <tt>a</tt> and if <tt>q</tt> is reachable
from <tt>p</tt>.
<h3>Valid expressions</h3>
In addition to the expressions defined in <A href="ForwardContainer.html">Forward Container</A>, the
following expressions must be valid.
<Table border>
<TR>
<TH>
Name
</TH>
<TH>
Expression
</TH>
<TH>
Type requirements
</TH>
<TH>
Return type
</TH>
</TR>
<TR>
<TD VAlign=top>
Fill constructor
</TD>
<TD VAlign=top>
<tt>X(n, t)</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
<tt>X</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
Fill constructor
</TD>
<TD VAlign=top>
<tt>X a(n, t);</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
&nbsp;
</TD>
</TR>
<TR>
<TD VAlign=top>
Default fill constructor
</TD>
<TD VAlign=top>
<tt>X(n)</tt>
</TD>
<TD VAlign=top>
<tt>T</tt> is <A href="DefaultConstructible.html">DefaultConstructible</A>.
</TD>
<TD VAlign=top>
<tt>X</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
Default fill constructor
</TD>
<TD VAlign=top>
<tt>X a(n);</tt>
</TD>
<TD VAlign=top>
<tt>T</tt> is <A href="DefaultConstructible.html">DefaultConstructible</A>.
</TD>
<TD VAlign=top>
&nbsp;
</TD>
</TR>
<TR>
<TD VAlign=top>
Range constructor
</TD>
<TD VAlign=top>
<tt>X(i, j)</tt>
</TD>
<TD VAlign=top>
<tt>i</tt> and <tt>j</tt> are <A href="InputIterator.html">Input Iterators</A> whose value type is convertible
   to <tt>T</tt> <A href="#1">[1]</A>
</TD>
<TD VAlign=top>
<tt>X</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
Range constructor
</TD>
<TD VAlign=top>
<tt>X a(i, j);</tt>
</TD>
<TD VAlign=top>
<tt>i</tt> and <tt>j</tt> are <A href="InputIterator.html">Input Iterators</A> whose value type is convertible
   to <tt>T</tt> <A href="#1">[1]</A>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
</TR>
<TR>
<TD VAlign=top>
Front
</TD>
<TD VAlign=top>
<tt>a.front()</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
<tt>reference</tt> if <tt>a</tt> is mutable, <tt>const_reference</tt> otherwise.
</TD>
</TR>
<TR>
<TD VAlign=top>
Insert
</TD>
<TD VAlign=top>
<tt>a.insert(p, t)</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
<tt>X::iterator</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
Fill insert
</TD>
<TD VAlign=top>
<tt>a.insert(p, n, t)</tt>
</TD>
<TD VAlign=top>
<tt>a</tt> is mutable
</TD>
<TD VAlign=top>
<tt>void</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
Range insert
</TD>
<TD VAlign=top>
<tt>a.insert(p, i, j)</tt>
</TD>
<TD VAlign=top>
<tt>i</tt> and <tt>j</tt> are <A href="InputIterator.html">Input Iterators</A> whose value type is convertible
   to <tt>T</tt> <A href="#1">[1]</A>.  <tt>a</tt> is mutable
</TD>
<TD VAlign=top>
<tt>void</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
Erase
</TD>
<TD VAlign=top>
<tt>a.erase(p)</tt>
</TD>
<TD VAlign=top>
<tt>a</tt> is mutable
</TD>
<TD VAlign=top>
<tt>iterator</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
Range erase
</TD>
<TD VAlign=top>
<tt>a.erase(p,q)</tt>
</TD>
<TD VAlign=top>
<tt>a</tt> is mutable
</TD>
<TD VAlign=top>
<tt>iterator</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
Clear
</TD>
<TD VAlign=top>
<tt>a.clear()</tt>
</TD>
<TD VAlign=top>
<tt>a</tt> is mutable
</TD>
<TD VAlign=top>
<tt>void</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
Resize
</TD>
<TD VAlign=top>
<tt>a.resize(n, t)</tt>
</TD>
<TD VAlign=top>
<tt>a</tt> is mutable
</TD>
<TD VAlign=top>
<tt>void</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
Resize
</TD>
<TD VAlign=top>
<tt>a.resize(n)</tt>
</TD>
<TD VAlign=top>
<tt>a</tt> is mutable
</TD>
<TD VAlign=top>
<tt>void</tt>
</TD>
</tr>
</table>
<h3>Expression semantics</h3>
Semantics of an expression is defined only where it is not defined in
<A href="ForwardContainer.html">Forward Container</A>, or where it differs.
<Table border>
<TR>
<TH>
Name
</TH>
<TH>
Expression
</TH>
<TH>
Precondition
</TH>
<TH>
Semantics
</TH>
<TH>
Postcondition
</TH>
</TR>
<TR>
<TD VAlign=top>
Fill constructor
</TD>
<TD VAlign=top>
<tt>X(n, t)</tt>
</TD>
<TD VAlign=top>
<tt>n &gt;= 0</tt>
</TD>
<TD VAlign=top>
Creates a sequence with <tt>n</tt> copies of <tt>t</tt>
</TD>
<TD VAlign=top>
<tt>size() == n</tt>.  Every element is a copy of <tt>t</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
Fill constructor
</TD>
<TD VAlign=top>
<tt>X a(n, t);</tt>
</TD>
<TD VAlign=top>
<tt>n &gt;= 0</tt>
</TD>
<TD VAlign=top>
Creates a sequence with <tt>n</tt> copies of <tt>t</tt>
</TD>
<TD VAlign=top>
<tt>a.size() == n</tt>.  Every element of <tt>a</tt> is a copy of <tt>t</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
Default fill constructor
</TD>
<TD VAlign=top>
<tt>X(n)</tt>
</TD>
<TD VAlign=top>
<tt>n &gt;= 0</tt>
</TD>
<TD VAlign=top>
Creates a sequence of <tt>n</tt> elements initialized to a default value.
</TD>
<TD VAlign=top>
<tt>size() == n</tt>.  Every element is a copy of <tt>T()</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
Default fill  constructor
</TD>
<TD VAlign=top>
<tt>X a(n, t);</tt>
</TD>
<TD VAlign=top>
<tt>n &gt;= 0</tt>
</TD>
<TD VAlign=top>
Creates a sequence with <tt>n</tt> elements initialized to a default value.
</TD>
<TD VAlign=top>
<tt>a.size() == n</tt>.  Every element of <tt>a</tt> is a copy of <tt>T()</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
Default constructor
</TD>
<TD VAlign=top>
<tt>X a;</tt> or <tt>X()</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
Equivalent to <tt>X(0)</tt>.
</TD>
<TD VAlign=top>
<tt>size() == 0</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
Range constructor
</TD>
<TD VAlign=top>
<tt>X(i, j)</tt>
</TD>
<TD VAlign=top>
<tt>[i,j)</tt> is a valid range.
</TD>
<TD VAlign=top>
Creates a sequence that is a copy of the range <tt>[i,j)</tt>
</TD>
<TD VAlign=top>
<tt>size()</tt> is equal to the distance from <tt>i</tt> to <tt>j</tt>.  Each element
   is a copy of the corresponding element in the
   range <tt>[i,j)</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
Range constructor
</TD>
<TD VAlign=top>
<tt>X a(i, j);</tt>
</TD>
<TD VAlign=top>
<tt>[i,j)</tt> is a valid range.
</TD>
<TD VAlign=top>
Creates a sequence that is a copy of the range <tt>[i,j)</tt>
</TD>
<TD VAlign=top>
<tt>a.size()</tt> is equal to the distance from <tt>i</tt> to <tt>j</tt>.  Each element
   in <tt>a</tt> is a copy of the corresponding element in the
   range <tt>[i,j)</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
Front
</TD>
<TD VAlign=top>
<tt>a.front()</tt>
</TD>
<TD VAlign=top>
<tt>!a.empty()</tt>
</TD>
<TD VAlign=top>
Equivalent to <tt>*(a.first())</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
</TR>
<TR>
<TD VAlign=top>
Insert
</TD>
<TD VAlign=top>
<tt>a.insert(p, t)</tt>
</TD>
<TD VAlign=top>
<tt>p</tt> is a valid iterator in <tt>a</tt>.  <tt>a.size() &lt; a.max_size()</tt>
</TD>
<TD VAlign=top>
A copy of <tt>t</tt> is inserted before <tt>p</tt>.  <A href="#2">[2]</A>  <A href="#3">[3]</A>
</TD>
<TD VAlign=top>
<tt>a.size()</tt> is incremented by 1.  <tt>*(a.insert(p,t))</tt> is a copy of <tt>t</tt>.
   The relative order of elements already in the sequence is unchanged.
</TD>
</TR>
<TR>
<TD VAlign=top>
Fill insert
</TD>
<TD VAlign=top>
<tt>a.insert(p, n, t)</tt>
</TD>
<TD VAlign=top>
<tt>p</tt> is a valid iterator in <tt>a</tt>.  <tt>n &gt;= 0 &amp;&amp; a.size() + n &lt;= a.max_size()</tt>.
</TD>
<TD VAlign=top>
<tt>n</tt> copies of <tt>t</tt> are inserted before <tt>p</tt>. <A href="#2">[2]</A> <A href="#3">[3]</A> <A href="#4">[4]</A>
</TD>
<TD VAlign=top>
<tt>a.size()</tt> is incremented by n.  The relative order of elements
   already in the sequence is unchanged.  
</TD>
</TR>
<TR>
<TD VAlign=top>
Range insert
</TD>
<TD VAlign=top>
<tt>a.insert(p, i, j)</tt>
</TD>
<TD VAlign=top>
<tt>[i,j)</tt> is a valid range.  <tt>a.size()</tt> plus the distance from <tt>i</tt> to
   <tt>j</tt> does not exceed <tt>a.max_size()</tt>.
</TD>
<TD VAlign=top>
Inserts a copy of the range <tt>[i,j)</tt> before <tt>p</tt>.  <A href="#1">[1]</A> <A href="#2">[2]</A> <A href="#3">[3]</A>
</TD>
<TD VAlign=top>
<tt>a.size()</tt> is incremented by the distance from <tt>i</tt> to <tt>j</tt>.
   The relative order of elements already in the sequence is unchanged.  
</TD>
</TR>
<TR>
<TD VAlign=top>
Erase
</TD>
<TD VAlign=top>
<tt>a.erase(p)</tt>
</TD>
<TD VAlign=top>
<tt>p</tt> is a dereferenceable iterator in <tt>a</tt>.
</TD>
<TD VAlign=top>
Destroys the element pointed to by <tt>p</tt> and removes it from <tt>a</tt>. <A href="#3">[3]</A>
</TD>
<TD VAlign=top>
<tt>a.size()</tt> is decremented by 1.  The relative order of the other
    elements in the sequence is unchanged.  The return value is an iterator
    to the element immediately following the one that was erased.
</TD>
</TR>
<TR>
<TD VAlign=top>
Range erase
</TD>
<TD VAlign=top>
<tt>a.erase(p,q)</tt>
</TD>
<TD VAlign=top>
<tt>[p,q)</tt> is a valid range in <tt>a</tt>.
</TD>
<TD VAlign=top>
Destroys the elements in the range <tt>[p,q)</tt> and removes them from
   <tt>a</tt>. <A href="#3">[3]</A>
</TD>
<TD VAlign=top>
<tt>a.size()</tt> is decremented by the distance from <tt>i</tt> to <tt>j</tt>.
   The relative order of the other elements in the sequence is unchanged.  
   The return value is an iterator to the element immediately
   following the ones that were erased.
</TD>
</TR>
<TR>
<TD VAlign=top>
Clear
</TD>
<TD VAlign=top>
<tt>a.clear()</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
Equivalent to <tt>a.erase(a.begin(), a.end())</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
</TR>
<TR>
<TD VAlign=top>
Resize
</TD>
<TD VAlign=top>
<tt>a.resize(n, t)</tt>
</TD>
<TD VAlign=top>
<tt>n &lt;= a.max_size()</tt>
</TD>
<TD VAlign=top>
Modifies the container so that it has exactly <tt>n</tt> elements, inserting
   elements at the end or erasing elements from the end if necessary.
   If any elements are inserted, they are copies of <tt>t</tt>. If <tt>n &gt; a.size()</tt>, 
   this expression is equivalent to <tt>a.insert(a.end(), n - size(), t)</tt>.
   If <tt>n &lt; a.size()</tt>, it is equivalent to <tt>a.erase(a.begin() + n, a.end())</tt>.
</TD>
<TD VAlign=top>
<tt>a.size() == n</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
Resize
</TD>
<TD VAlign=top>
<tt>a.resize(n)</tt>
</TD>
<TD VAlign=top>
<tt>n &lt;= a.max_size()</tt>
</TD>
<TD VAlign=top>
Equivalent to <tt>a.resize(n, T())</tt>.
</TD>
<TD VAlign=top>
<tt>a.size() == n</tt>
</TD>
</tr>
</table>
<h3>Complexity guarantees</h3>
The fill constructor, default fill
   constructor, and range constructor are linear.
<P>
Front is amortized constant time.
<P>
Fill insert, range insert, and range erase are linear.
<P>
The complexities of single-element insert and erase are sequence 
   dependent.
<h3>Invariants</h3>
<h3>Models</h3>
<UL>
<LI>
 <A href="Vector.html">vector</A> <A href="#5">[5]</A>
<LI>
 <A href="Deque.html">deque</A>
<LI>
 <A href="List.html">list</A>
<LI>
 <A href="Slist.html">slist</A>
</UL>
<h3>Notes</h3>
<P><A name="1">[1]</A>
At present (early 1998), not all compilers support
&quot;member templates&quot;.  If your compiler supports member
templates then <tt>i</tt> and <tt>j</tt> may be of any type that
conforms to the <A href="InputIterator.html">Input Iterator</A>
requirements.  If your compiler does not yet support member
templates, however, then <tt>i</tt> and <tt>j</tt> must be of type
<tt>const T*</tt> or of type <tt>X::const_iterator</tt>.
<P><A name="2">[2]</A>
Note that <tt>p</tt> equal to <tt>a.begin()</tt> means to insert
something at the beginning of <tt>a</tt> (that is, before any elements
already in <tt>a</tt>), and <tt>p</tt> equal to <tt>a.end()</tt> means
to append something to the end of <tt>a</tt>.
<P><A name="3">[3]</A>
<b>Warning</b>: there is no guarantee that a valid iterator on
<tt>a</tt> is still valid after an insertion or an erasure.  In some
cases iterators do remain valid, and in other cases they do not.  The
details are different for each sequence class.
<P><A name="4">[4]</A>
<tt>a.insert(p, n, t)</tt> is guaranteed to be no slower then calling
<tt>a.insert(p, t)</tt> <tt>n</tt> times.  In some cases it is significantly
faster.
<P><A name="5">[5]</A>
<A href="Vector.html">Vector</A> is usually preferable to
<A href="Deque.html">deque</A> and <A href="List.html">list</A>.  
<A href="Deque.html">Deque</A> is useful in the case of frequent
insertions at both the beginning and end of the sequence, and
<A href="List.html">list</A> and <A href="Slist.html">slist</A> are useful in the case of frequent insertions
in the middle of the sequence.  In almost all other situations,
<A href="Vector.html">vector</A> is more efficient.
<h3>See also</h3>
<A href="Container.html">Container</A>, 
<A href="ForwardContainer.html">Forward Container</A>, 
<A href="AssociativeContainer.html">Associative Container</A>, 
<A href="FrontInsertionSequence.html">Front Insertion Sequence</A>, 
<A href="BackInsertionSequence.html">Back Insertion Sequence</A>, 
<tt><A href="Vector.html">vector</A></tt>, 
<tt><A href="Deque.html">deque</A></tt>,
<tt><A href="List.html">list</A></tt>,
<tt><A href="Slist.html">slist</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>