<TD VAlign=top><tt>a.resize(n)</tt></TD><TD VAlign=top>&nbsp;</TD><TD VAlign=top><tt>void</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, using <tt>hasher()</tt> as the hash function   and <tt>key_equal()</tt> as the key equality function.</TD><TD VAlign=top>The size of the container is <tt>0</tt>.  The bucket count is an   unspecified default value.  The hash function is <tt>hasher()</tt>, and   the key equality function is <tt>key_equal()</tt>.</TD></TR><TR><TD VAlign=top>Constructor with bucket count</TD><TD VAlign=top><pre>X(n)X a(n);</pre></TD><TD VAlign=top>&nbsp;</TD><TD VAlign=top>Creates an empty container with at least <tt>n</tt> buckets, using   <tt>hasher()</tt> as the hash function and <tt>key_equal()</tt> as the key    equality function.</TD><TD VAlign=top>The size of the container is <tt>0</tt>.  The bucket count is   greater than or equal to <tt>n</tt>.  The hash function is <tt>hasher()</tt>, and   the key equality function is <tt>key_equal()</tt>.</TD></TR><TR><TD VAlign=top>Constructor with hash function</TD><TD VAlign=top><pre>X(n, h)X a(n, h);</pre></TD><TD VAlign=top>&nbsp;</TD><TD VAlign=top>Creates an empty container with at least <tt>n</tt> buckets, using   <tt>h</tt> as the hash function and <tt>key_equal()</tt> as the key    equality function.</TD><TD VAlign=top>The size of the container is <tt>0</tt>.  The bucket count is   greater than or equal to <tt>n</tt>.  The hash function is <tt>h</tt>, and   the key equality function is <tt>key_equal()</tt>.</TD></TR><TR><TD VAlign=top>Constructor with key equal</TD><TD VAlign=top><pre>X(n, h, k)X a(n, h, k);</pre></TD><TD VAlign=top>&nbsp;</TD><TD VAlign=top>Creates an empty container with at least <tt>n</tt> buckets, using   <tt>h</tt> as the hash function and <tt>k</tt> as the key    equality function.</TD><TD VAlign=top>The size of the container is <tt>0</tt>.  The bucket count is   greater than or equal to <tt>n</tt>.  The hash function is <tt>h</tt>, and   the key equality function is <tt>k</tt>.</TD></TR><TR><TD VAlign=top>Hash function</TD><TD VAlign=top><tt>a.hash_funct()</tt></TD><TD VAlign=top>&nbsp;</TD><TD VAlign=top>Returns the hash function used by <tt>a</tt>.</TD><TD VAlign=top>&nbsp;</TD></TR><TR><TD VAlign=top>Key equal</TD><TD VAlign=top><tt>a.key_eq()</tt></TD><TD VAlign=top>&nbsp;</TD><TD VAlign=top>Returns the key equal function used by <tt>a</tt>.</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>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>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>a</tt> lies in the range <tt>[P.first, P.second)</tt>, or else   <tt>*a</tt> has a key that is not the same as <tt>k</tt>.</TD></TR><TR><TD VAlign=top>Bucket count</TD><TD VAlign=top><tt>a.bucket_count()</tt></TD><TD VAlign=top>&nbsp;</TD><TD VAlign=top>Returns the number of buckets in <tt>a</tt>.</TD><TD VAlign=top>&nbsp;</TD></TR><TR><TD VAlign=top>Resize</TD><TD VAlign=top><tt>a.resize(n)</tt></TD><TD VAlign=top>&nbsp;</TD><TD VAlign=top>Increases the bucket count of <tt>a</tt>.</TD><TD VAlign=top>The bucket count of <tt>a</tt> will be at least <tt>n</tt>.  All iterators pointing   to element in <tt>a</tt> will remain valid. <A href="#3">[3]</A></TD></tr></table><h3>Complexity guarantees</h3>The default constructor, constructor with bucket count,constructor with hash function, and constructor with key equal, are all amortized constant time.<P>Hash Function and Key Equal are amortized constant time.<P>Average complexity for Erase Key is <tt>O(count(k))</tt>.  Worst case islinear in the size of the container.<P>Erase Element is amortized constant time.<P>Average complexity for Erase Range is <tt>O(N)</tt>, where <tt>N</tt> is the lengthof the range being erased.  Worse case is linear in the size of thecontainer.<P>Average complexity for Find is constant time.  Worst case is linear inthe size of the container.<P>Average complexity for Equal Range is <tt>O(count(k))</tt>.  Worst case islinear in the size of the container.<P>Average complexity for Count is <tt>O(count(k))</tt>.  Worst case is linearin the size of the container.<P>Bucket Count is amortized constant time.<P>Resize is linear in the size of the container.<h3>Invariants</h3><h3>Models</h3><UL><LI><tt><A href="hash_set.html">hash_set</A></tt><LI><tt><A href="hash_map.html">hash_map</A></tt><LI><tt><A href="hash_multiset.html">hash_multiset</A></tt><LI><tt><A href="hash_multimap.html">hash_multimap</A></tt></UL><h3>Notes</h3><P><A name="1">[1]</A>There is an extensive literature dealing with hash tables.  See,for example, section 6.4 of Knuth.  (D. E. Knuth, <i>The Art of ComputerProgramming.  Volume 3: Sorting and Searching</i>.Addison-Wesley, 1975.)<P><A name="2">[2]</A>If the hash function is poor (that is, if many different keys hashto the same value) then this will hurt performance.  The worstcase is where every key hashes to the same value; in this case, run-timecomplexity of most Hashed Associative Container operations will belinear in the size of the container.<P><A name="3">[3]</A>Resizing does not invalidate iterators; however, it does notnecessarily preserve the ordering relation between iterators.That is, if <tt>i</tt> and <tt>j</tt> are iterators that point into a Hashed Associative Container such that <tt>i</tt> comes immediatelybefore <tt>j</tt>, then there is no guarantee that <tt>i</tt> will still comeimmediately before <tt>j</tt> after the container is resized.  The onlyguarantee about about the ordering of elements is the contiguousstorage invariant: elements with the same key are always adjacentto each other.<h3>See also</h3><A href="AssociativeContainer.html">Associative Container</A>, <A href="SortedAssociativeContainer.html">Sorted 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>