File: AssociativeContainer.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 (572 lines) | stat: -rw-r--r-- 15,711 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>Associative 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>Associative 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>
An Associative Container is a variable-sized <A href="Container.html">Container</A> that
supports efficient retrieval of elements (values) based on keys.  It
supports insertion and removal of elements, but differs from a
<A href="Sequence.html">Sequence</A> in that it does not provide a mechanism for inserting an
element at a specific position. <A href="#1">[1]</A>
<P>
As with all containers, the elements in an Associative Container are
of type <tt>value_type</tt>.  Additionally, each element in an Associative
Container has a <i>key</i>, of type <tt>key_type</tt>.  In some Associative
Containers, <A href="SimpleAssociativeContainer.html">Simple Associative Containers</A>, the <tt>value_type</tt> and
<tt>key_type</tt> are the same: elements are their own keys.  In others, the
key is some specific part of the value.  Since elements are stored
according to their keys, it is essential that the key associated with
each element is immutable.  In <A href="SimpleAssociativeContainer.html">Simple Associative Containers</A> this
means that the elements themselves are immutable, while 
in other types of Associative Containers, such as 
<A href="PairAssociativeContainer.html">Pair Associative Containers</A>, the elements themselves are mutable but
the part of an element that is its key cannot be modified.  This means
that an Associative Container's value type is not <A href="Assignable.html">Assignable</A>.
<P>
The fact that the value type of an Associative Container is not
<A href="Assignable.html">Assignable</A> has an important consequence: associative
containers cannot have mutable iterators.  This is simply because
a mutable iterator (as defined in the <A href="trivial.html">Trivial Iterator</A> requirements)
must allow assignment.  That is, if <tt>i</tt> is a mutable iterator and 
<tt>t</tt> is an object of <tt>i</tt>'s value type, then <tt>*i = t</tt> must be a valid
expression.  
<P>
In <A href="SimpleAssociativeContainer.html">Simple Associative Containers</A>, where the elements are the keys,
the elements are completely immutable; the nested types <tt>iterator</tt> and
<tt>const_iterator</tt> are therefore the same.  Other types of associative
containers, however, do have mutable elements, and do provide
iterators through which elements can be modified.  
<A href="PairAssociativeContainer.html">Pair Associative Containers</A>, for example, have two different
nested types <tt>iterator</tt> and <tt>const_iterator</tt>.  Even in this case,
<tt>iterator</tt> is not a mutable iterator: as explained above,
it does not provide the expression <tt>*i = t</tt>.  It is, however, possible
to modify an element through such an iterator: if, for example, <tt>i</tt>
is of type <tt><A href="Map.html">map</A>&lt;int, double&gt;</tt>, then <tt>(*i).second = 3</tt> is a valid
expression.
<P>
In some associative containers, <A href="UniqueAssociativeContainer.html">Unique Associative Containers</A>,
it is guaranteed that no two elements have the same key. <A href="#2">[2]</A>  In other
associative containers, <A href="MultipleAssociativeContainer.html">Multiple Associative Containers</A>, multiple
elements with the same key are permitted.
<h3>Refinement of</h3>
<A href="ForwardContainer.html">Forward Container</A>, <A href="DefaultConstructible.html">Default Constructible</A>
<h3>Associated types</h3>
One new type is introduced, in addition to the types defined in the
<A href="ForwardContainer.html">Forward Container</A> requirements.
<Table border>
<TR>
<TD VAlign=top>
Key type
</TD>
<TD VAlign=top>
<tt>X::key_type</tt>
</TD>
<TD VAlign=top>
The type of the key associated with <tt>X::value_type</tt>.  Note that the
   key type and value type might be the same.
</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 Associative Container
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>a</tt>
</TD>
<TD VAlign=top>
Object of type <tt>X</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>t</tt>
</TD>
<TD VAlign=top>
Object of type <tt>X::value_type</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>k</tt>
</TD>
<TD VAlign=top>
Object of type <tt>X::key_type</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>
</table>
<h3>Definitions</h3>
If <tt>a</tt> is an associative container, then <tt>p</tt> is a
<i>valid iterator in a</i> if it is a valid iterator that is 
reachable from <tt>a.begin()</tt>.
<P>
If <tt>a</tt> is an associative container, then <tt>[p, q)</tt> is a <i>valid range in a</i>
if <tt>[p, q)</tt> is a valid range and <tt>p</tt> is a valid iterator in <tt>a</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>
Default constructor
</TD>
<TD VAlign=top>
<pre>
X()
X a;
</pre>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
&nbsp;
</TD>
</TR>
<TR>
<TD VAlign=top>
Erase key
</TD>
<TD VAlign=top>
<tt>a.erase(k)</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
<tt>size_type</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
Erase element
</TD>
<TD VAlign=top>
<tt>a.erase(p)</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
<tt>void</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
Erase range
</TD>
<TD VAlign=top>
<tt>a.erase(p, q)</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
<tt>void</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
Clear
</TD>
<TD VAlign=top>
<tt>a.clear()</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
<tt>void</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
Find
</TD>
<TD VAlign=top>
<tt>a.find(k)</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
<tt>iterator</tt> if <tt>a</tt> is mutable, otherwise <tt>const_iterator</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
Count
</TD>
<TD VAlign=top>
<tt>a.count(k)</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
<tt>size_type</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
Equal range
</TD>
<TD VAlign=top>
<tt>a.equal_range(k)</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
<tt>pair&lt;iterator, iterator&gt;</tt> if <tt>a</tt> is mutable, otherwise
   <tt>pair&lt;const_iterator, const_iterator&gt;</tt>.
</TD>
</tr>
</table>
<h3>Expression semantics</h3>
<Table border>
<TR>
<TH>
Name
</TH>
<TH>
Expression
</TH>
<TH>
Precondition
</TH>
<TH>
Semantics
</TH>
<TH>
Postcondition
</TH>
</TR>
<TR>
<TD VAlign=top>
Default constructor
</TD>
<TD VAlign=top>
<pre>
X()
X a;
</pre>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
Creates an empty container.
</TD>
<TD VAlign=top>
The size of the container is <tt>0</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
Erase key
</TD>
<TD VAlign=top>
<tt>a.erase(k)</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
Destroys all elements whose key is the same as <tt>k</tt>, and removes
   them from <tt>a</tt>. <A href="#2">[2]</A>  The return value is the number of elements that
   were erased, <i>i.e.</i> the old value of <tt>a.count(k)</tt>.
</TD>
<TD VAlign=top>
<tt>a.size()</tt> is decremented by <tt>a.count(k)</tt>.
   <tt>a</tt> contains no elements with key <tt>k</tt>.  
</TD>
</TR>
<TR>
<TD VAlign=top>
Erase element
</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>.
</TD>
<TD VAlign=top>
<tt>a.size()</tt> is decremented by 1.
</TD>
</TR>
<TR>
<TD VAlign=top>
Erase range
</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>. 
</TD>
<TD VAlign=top>
<tt>a.size()</tt> is decremented by the distance from <tt>i</tt> to <tt>j</tt>.
</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>
Find
</TD>
<TD VAlign=top>
<tt>a.find(k)</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
Returns an iterator pointing to an element whose key is the same
   as <tt>k</tt>, or <tt>a.end()</tt> if no such element exists.
</TD>
<TD VAlign=top>
Either the return value is <tt>a.end()</tt>, or else the return value has
   a key that is the same as <tt>k</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
Count
</TD>
<TD VAlign=top>
<tt>a.count(k)</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
Returns the number of elements in <tt>a</tt> whose keys are the same as <tt>k</tt>.
</TD>
<TD VAlign=top>
&nbsp;
</TD>
</TR>
<TR>
<TD VAlign=top>
Equal range
</TD>
<TD VAlign=top>
<tt>a.equal_range(k)</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
Returns a pair <tt>P</tt> such that <tt>[P.first, P.second)</tt> is a range
   containing all elements in <tt>a</tt> whose keys are the same as <tt>k</tt>. <A href="#3">[3]</A>
   If no elements have the same key as <tt>k</tt>, the return value is an empty
   range.
</TD>
<TD VAlign=top>
The distance between <tt>P.first</tt> and <tt>P.second</tt> is equal to
   <tt>a.count(k)</tt>.  If <tt>p</tt> is a dereferenceable iterator in <tt>a</tt>, then
   either <tt>p</tt> lies in the range <tt>[P.first, P.second)</tt>, or else
   <tt>*p</tt> has a key that is not the same as <tt>k</tt>.
</TD>
</tr>
</table>
<h3>Complexity guarantees</h3>
Average complexity for erase key is at most <tt>O(log(size()) + count(k))</tt>.
<P>
Average complexity for erase element is constant time.
<P>
Average complexity for erase range is at most 
   <tt>O(log(size()) + N)</tt>, where <tt>N</tt> is the number of elements in the range.
<P>
Average complexity for count is at most <tt>O(log(size()) + count(k))</tt>.
<P>
Average complexity for find is at most logarithmic.
<P>
Average complexity for equal range is at most logarithmic.
<h3>Invariants</h3>
<Table border>
<TR>
<TD VAlign=top>
Contiguous storage
</TD>
<TD VAlign=top>
All elements with the same key are adjacent to each other.  That
   is, if <tt>p</tt> and <tt>q</tt> are iterators that point to elements that have
   the same key, and if <tt>p</tt> precedes <tt>q</tt>, then every element in the
   range <tt>[p, q)</tt> has the same key as every other element.
</TD>
</TR>
<TR>
<TD VAlign=top>
Immutability of keys
</TD>
<TD VAlign=top>
Every element of an Associative Container has an immutable key.
   Objects may be inserted and erased, but an element in an 
   Associative Container may not be modified in such a way as to change
   its key.
</TD>
</tr>
</table>
<h3>Models</h3>
<UL>
<LI>
<tt><A href="set.html">set</A></tt>
<LI>
<tt><A href="multiset.html">multiset</A></tt>
<LI>
<tt><A href="hash_set.html">hash_set</A></tt>
<LI>
<tt><A href="hash_multiset.html">hash_multiset</A></tt>
<LI>
<tt><A href="Map.html">map</A></tt>
<LI>
<tt><A href="Multimap.html">multimap</A></tt>
<LI>
<tt><A href="hash_map.html">hash_map</A></tt>
<LI>
<tt><A href="hash_multimap.html">hash_multimap</A></tt>
</UL>
<h3>Notes</h3>
<P><A name="1">[1]</A>
The reason there is no such mechanism is that the way in which
elements are arranged in an associative container is typically a class
invariant; elements in a <A href="SortedAssociativeContainer.html">Sorted Associative Container</A>, for
example, are always stored in ascending order, and elements in a 
<A href="HashedAssociativeContainer.html">Hashed Associative Container</A> are always stored according to the
hash function.  It would make no sense to allow the position of an
element to be chosen arbitrarily.
<P><A name="2">[2]</A>
Keys are not required to be <A href="EqualityComparable.html">Equality Comparable</A>: associative
containers do not necessarily use <tt>operator==</tt> to determine whether two
keys are the same.  In <A href="SortedAssociativeContainer.html">Sorted Associative Containers</A>, for example,
where keys are ordered by a comparison function, two keys are considered
to be the same if neither one is less than the other.
<P><A name="3">[3]</A>
Note the implications of this member function: it means that if
two elements have the same key, there must be no elements with
different keys in between them.  The requirement that elements with
the same key be stored contiguously is an associative container
invariant.
<h3>See also</h3>
<A href="SimpleAssociativeContainer.html">Simple Associative Container</A>, <A href="PairAssociativeContainer.html">Pair Associative Container</A>,
<A href="UniqueAssociativeContainer.html">Unique Associative Container</A>, <A href="MultipleAssociativeContainer.html">Multiple Associative Container</A>,
<A href="SortedAssociativeContainer.html">Sorted Associative Container</A>, 
<A href="UniqueSortedAssociativeContainer.html">Unique Sorted Associative Container</A>, 
<A href="MultipleSortedAssociativeContainer.html">Multiple Sorted Associative Container</A>,
<A href="HashedAssociativeContainer.html">Hashed Associative Container</A>,
<A href="UniqueHashedAssociativeContainer.html">Unique Hashed Associative Container</A>, 
<A href="MultipleHashedAssociativeContainer.html">Multiple Hashed Associative Container</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>