File: Container.html

package info (click to toggle)
stl-manual 3.30-9
links: PTS, VCS
area: main
in suites: lenny
size: 4,092 kB
ctags: 4,448
sloc: cpp: 17,845; ansic: 2,842; makefile: 41
file content (646 lines) | stat: -rw-r--r-- 17,277 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>Container</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>Container</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 Container is an object that stores other objects (its <i>elements</i>),
and that has methods for accessing its elements.  In particular, 
every type that is a model of Container has an associated <A href="Iterators.html">iterator</A>
type that can be used to iterate through the Container's elements.
<P>
There is no guarantee that the elements of a Container are stored
in any definite order; the order might, in fact, be different upon
each iteration through the Container.  Nor is there a guarantee that
more than one iterator into a Container may be active at any one time.
(Specific types of Containers, such as <A href="ForwardContainer.html">Forward Container</A>, do 
provide such guarantees.)
<P>
A Container &quot;owns&quot; its elements: the lifetime of an element stored in 
a container cannot exceed that of the Container itself. <A href="#1">[1]</A>
<h3>Refinement of</h3>
<A href="Assignable.html">Assignable</A>
<h3>Associated types</h3>
<Table border>
<TR>
<TD VAlign=top>
Value type
</TD>
<TD VAlign=top>
<tt>X::value_type</tt>
</TD>
<TD VAlign=top>
The type of the object stored in a container.  The value type
   must be <A href="Assignable.html">Assignable</A>, but need not be <A href="DefaultConstructible.html">DefaultConstructible</A>. <A href="#2">[2]</A>
</TD>
</TR>
<TR>
<TD VAlign=top>
Iterator type
</TD>
<TD VAlign=top>
<tt>X::iterator</tt>
</TD>
<TD VAlign=top>
The type of iterator used to iterate through a container's
   elements.  The iterator's value type is expected to be the
   container's value type.  A conversion
   from the iterator type to the const iterator type must exist.
   The iterator type must be an <A href="InputIterator.html">input iterator</A>. <A href="#3">[3]</A>
</TD>
</TR>
<TR>
<TD VAlign=top>
Const iterator type
</TD>
<TD VAlign=top>
<tt>X::const_iterator</tt>
</TD>
<TD VAlign=top>
A type of iterator that may be used to examine, but not to modify,
   a container's elements. <A href="#3">[3]</A> <A href="#4">[4]</A>
</TD>
</TR>
<TR>
<TD VAlign=top>
Reference type
</TD>
<TD VAlign=top>
<tt>X::reference</tt>
</TD>
<TD VAlign=top>
A type that behaves as a reference to the container's value type. <A href="#5">[5]</A>
</TD>
</TR>
<TR>
<TD VAlign=top>
Const reference type
</TD>
<TD VAlign=top>
<tt>X::const_reference</tt>
</TD>
<TD VAlign=top>
A type that behaves as a const reference to the container's value
type. <A href="#5">[5]</A>
</TD>
</TR>
<TR>
<TD VAlign=top>
Pointer type
</TD>
<TD VAlign=top>
<tt>X::pointer</tt>
</TD>
<TD VAlign=top>
A type that behaves as a pointer to the container's value type. <A href="#6">[6]</A>
</TD>
</TR>
<TR>
<TD VAlign=top>
Distance type
</TD>
<TD VAlign=top>
<tt>X::difference_type</tt>
</TD>
<TD VAlign=top>
A signed integral type used to represent the distance between two
   of the container's iterators.  This type must be the same as 
   the iterator's distance type. <A href="#2">[2]</A>
</TD>
</TR>
<TR>
<TD VAlign=top>
Size type
</TD>
<TD VAlign=top>
<tt>X::size_type</tt>
</TD>
<TD VAlign=top>
An unsigned integral type that can represent any nonnegative value
   of the container's distance type. <A href="#2">[2]</A>
</TD>
</tr>
</table>
<h3>Notation</h3>
<Table>
<TR>
<TD VAlign=top>
<tt>X</tt>
</TD>
<TD VAlign=top>
A type that is a model of Container
</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>
</table>
<h3>Definitions</h3>
The <i>size</i> of a container is the number of elements it contains.
The size is a nonnegative number.
<P>
The <i>area</i> of a container is the total number of bytes that it
occupies.  More specifically, it is the sum of the elements' areas
plus whatever overhead is associated with the container itself.  If a
container's value type <tt>T</tt> is a simple type (as opposed to a container
type), then the container's area is bounded above by a constant times
the container's size times <tt>sizeof(T)</tt>.  That is, if <tt>a</tt> is a
container with a simple value type, then <tt>a</tt>'s area is <tt>O(a.size())</tt>.
<P>
A <i>variable sized</i> container is one that provides methods for
inserting and/or removing elements; its size may vary during a
container's lifetime.  A <i>fixed size</i> container is one where 
the size is constant throughout the container's lifetime.  In some
fixed-size container types, the size is determined at compile time.
<h3>Valid expressions</h3>
In addition to the expressions defined in 
<A href="Assignable.html">Assignable</A>, <A href="EqualityComparable.html">EqualityComparable</A>, and <A href="LessThanComparable.html">LessThanComparable</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>
Beginning of range
</TD>
<TD VAlign=top>
<tt>a.begin()</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
<tt>iterator</tt> if <tt>a</tt> is mutable, <tt>const_iterator</tt> otherwise <A href="#4">[4]</A> <A href="#7">[7]</A>
</TD>
</TR>
<TR>
<TD VAlign=top>
End of range
</TD>
<TD VAlign=top>
<tt>a.end()</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
<tt>iterator</tt> if <tt>a</tt> is mutable, <tt>const_iterator</tt> otherwise <A href="#4">[4]</A>
</TD>
</TR>
<TR>
<TD VAlign=top>
Size
</TD>
<TD VAlign=top>
<tt>a.size()</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
<tt>size_type</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
Maximum size
</TD>
<TD VAlign=top>
<tt>a.max_size()</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
<tt>size_type</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
Empty container
</TD>
<TD VAlign=top>
<tt>a.empty()</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
Convertible to <tt>bool</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
Swap
</TD>
<TD VAlign=top>
<tt>a.swap(b)</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
<tt>void</tt>
</TD>
</tr>
</table>
<h3>Expression semantics</h3>
Semantics of an expression is defined only where it differs from, or 
is not defined in,
<A href="Assignable.html">Assignable</A>, <A href="EqualityComparable.html">Equality Comparable</A>,
or <A href="LessThanComparable.html">LessThan Comparable</A>
<Table border>
<TR>
<TH>
Name
</TH>
<TH>
Expression
</TH>
<TH>
Precondition
</TH>
<TH>
Semantics
</TH>
<TH>
Postcondition
</TH>
</TR>
<TR>
<TD VAlign=top>
Copy constructor
</TD>
<TD VAlign=top>
<tt>X(a)</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
<tt>X().size() == a.size()</tt>.  <tt>X()</tt> contains a copy of each of <tt>a</tt>'s elements.
</TD>
</TR>
<TR>
<TD VAlign=top>
Copy constructor
</TD>
<TD VAlign=top>
<tt>X b(a);</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
<tt>b.size() == a.size()</tt>.  <tt>b</tt> contains a copy of each of <tt>a</tt>'s elements.
</TD>
</TR>
<TR>
<TD VAlign=top>
Assignment operator
</TD>
<TD VAlign=top>
<tt>b = a</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
<tt>b.size() == a.size()</tt>.  <tt>b</tt> contains a copy of each of <tt>a</tt>'s elements.
</TD>
</TR>
<TR>
<TD VAlign=top>
Destructor
</TD>
<TD VAlign=top>
<tt>a.~X()</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
Each of <tt>a</tt>'s elements is destroyed, and memory allocated for them
   (if any) is deallocated.
</TD>
<TD VAlign=top>
&nbsp;
</TD>
</TR>
<TR>
<TD VAlign=top>
Beginning of range
</TD>
<TD VAlign=top>
<tt>a.begin()</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
Returns an iterator pointing to the first element in the container. <A href="#7">[7]</A>
</TD>
<TD VAlign=top>
<tt>a.begin()</tt> is either dereferenceable or past-the-end.  It is
   past-the-end if and only if <tt>a.size() == 0</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
End of range
</TD>
<TD VAlign=top>
<tt>a.end()</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
Returns an iterator pointing one past the last element in the
   container.
</TD>
<TD VAlign=top>
<tt>a.end()</tt> is past-the-end.
</TD>
</TR>
<TR>
<TD VAlign=top>
Size
</TD>
<TD VAlign=top>
<tt>a.size()</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
Returns the size of the container, that is, its number of elements. <A href="#8">[8]</A>
</TD>
<TD VAlign=top>
<tt>a.size() &gt;= 0 &amp;&amp; a.size() &lt;= max_size()</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
Maximum size
</TD>
<TD VAlign=top>
<tt>a.max_size()</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
Returns the largest size that this container can ever have. <A href="#8">[8]</A>
</TD>
<TD VAlign=top>
<tt>a.max_size() &gt;= 0 &amp;&amp; a.max_size() &gt;= a.size()</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
Empty container
</TD>
<TD VAlign=top>
<tt>a.empty()</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
Equivalent to <tt>a.size() == 0</tt>.  (But possibly faster.)
</TD>
<TD VAlign=top>
&nbsp;
</TD>
</TR>
<TR>
<TD VAlign=top>
Swap
</TD>
<TD VAlign=top>
<tt>a.swap(b)</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
Equivalent to <tt>swap(a,b)</tt> <A href="#9">[9]</A>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
</tr>
</table>
<h3>Complexity guarantees</h3>
The copy constructor, the assignment operator, and the destructor
   are linear in the container's size.
<P>
<tt>begin()</tt> and <tt>end()</tt> are amortized constant time.
<P>
<tt>size()</tt> is linear in the
   container's size. <A href="#10">[10]</A>  <tt>max_size()</tt> and 
   <tt>empty()</tt> are amortized constant time.  If you are
   testing whether a container is empty, you should always write
   <tt>c.empty()</tt> instead of <tt>c.size() == 0</tt>.  The two expressions are
   equivalent, but the former may be much faster.
<P>
<tt>swap()</tt> is amortized constant time. <A href="#9">[9]</A>
<h3>Invariants</h3>
<Table border>
<TR>
<TD VAlign=top>
Valid range
</TD>
<TD VAlign=top>
For any container <tt>a</tt>, <tt>[a.begin(), a.end())</tt> is a valid
   range. <A href="#11">[11]</A>
</TD>
</TR>
<TR>
<TD VAlign=top>
Range size
</TD>
<TD VAlign=top>
<tt>a.size()</tt> is equal to the distance from <tt>a.begin()</tt> to <tt>a.end()</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
Completeness
</TD>
<TD VAlign=top>
An algorithm that iterates through the range <tt>[a.begin(), a.end())</tt>
   will pass through every element of <tt>a</tt>. <A href="#11">[11]</A>
</TD>
</tr>
</table>
<h3>Models</h3>
<UL>
<LI>
 <A href="Vector.html">vector</A>
</UL>
<h3>Notes</h3>
<P><A name="1">[1]</A>
The fact that the lifetime of elements cannot exceed that of of
their container may seem like a severe restriction.  In fact, though,
it is not.  Note that pointers and iterators are objects; like any
other objects, they may be stored in a container.  The container, in
that case, &quot;owns&quot; the pointers themselves, but not the objects that
they point to.
<P><A name="2">[2]</A>
This expression must be a <tt>typedef</tt>, that is, a synonym for
a type that already has some other name.
<P><A name="3">[3]</A>
This may either be a <tt>typedef</tt> for some other type, or else
a unique type that is defined as a nested class within the class 
<tt>X</tt>.
<P><A name="4">[4]</A>
A container's iterator type and const iterator type may be the
same: there is no guarantee that every container must have an
associated mutable iterator type.  For example, <tt><A href="set.html">set</A></tt> and
<tt><A href="hash_set.html">hash_set</A></tt> define <tt>iterator</tt> and <tt>const_iterator</tt> to be
the same type.
<P><A name="5">[5]</A>
It is required that the reference type has the same semantics as
an ordinary C++ reference, but it need not actually be an ordinary C++
reference.  Some implementations, for example, might provide
additional reference types to support non-standard memory models.
Note, however, that &quot;smart references&quot; (user-defined reference types
that provide additional functionality) are not a viable option.  It is
impossible for a user-defined type to have the same semantics as C++
references, because the C++ language does not support redefining the
member access operator (<tt>operator.</tt>).
<P><A name="6">[6]</A>
As in the case of references <A href="#5">[5]</A>, the pointer type must have the
same semantics as C++ pointers but need not actually be a C++ pointer.
&quot;Smart pointers,&quot; however, unlike &quot;smart references&quot;, are possible.
This is because it is possible for user-defined types to define the
dereference operator and the pointer member access operator, 
<tt>operator*</tt> and <tt>operator-&gt;</tt>.
<P><A name="7">[7]</A>
The iterator type need only be an <i>input iterator</i>, which
provides a very weak set of guarantees; in particular, all algorithms
on input iterators must be &quot;single pass&quot;.  It follows that only a single
iterator into a container may be active at any one time.  This restriction
is removed in <A href="ForwardContainer.html">Forward Container</A>.
<P><A name="8">[8]</A>
In the case of a fixed-size container, <tt>size() == max_size()</tt>.
<P><A name="9">[9]</A>
For any <A href="Assignable.html">Assignable</A> type, <A href="swap.html">swap</A> can be defined in terms of
assignment.  This requires three assignments, each of which, for 
a container type, is linear in the container's size.  In a sense,
then, <tt>a.swap(b)</tt> is redundant.  It exists solely for the sake of
efficiency: for many containers, such as <A href="Vector.html">vector</A> and <A href="List.html">list</A>,
it is possible to implement <tt>swap</tt> such that its run-time complexity
is constant rather than linear.  If this is possible for some container
type <tt>X</tt>, then the template specialization <tt><A href="swap.html">swap</A>(X&amp;, X&amp;)</tt> can
simply be written in terms of <tt>X::swap(X&amp;)</tt>.  The implication of this
is that <tt>X::swap(X&amp;)</tt> should <b>only</b> be defined if there exists such
a constant-time implementation.  Not every container class <tt>X</tt> need
have such a member function, but if the member function exists at all then
it is guaranteed to be amortized constant time.
<P><A name="10">[10]</A>
For many containers, such as <tt><A href="Vector.html">vector</A></tt> and <tt><A href="Deque.html">deque</A></tt>, <tt>size</tt> is
<i>O(1</i>).  This satisfies the requirement that it be <i>O(N</i>).
<P><A name="11">[11]</A>
Although <tt>[a.begin(), a.end())</tt> must be a valid range, and must
include every element in the container, the order in which the elements
appear in that range is unspecified.  If you iterate through a container
twice, it is not guaranteed that the order will be the same both
times.  This restriction is removed in <A href="ForwardContainer.html">Forward Container</A>.
<h3>See also</h3>
The <A href="Iterators.html">Iterator overview</A>, <A href="InputIterator.html">Input Iterator</A>, <A href="Sequence.html">Sequence</A>

<!--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>