?? hashedassociativecontainer.html
字號(hào):
<HTML>
<HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
<META NAME="Author" CONTENT="Zafir Anjum">
<TITLE>MFC Programmer's SourceBook : STL Programmer's Guide</TITLE>
<META name="description"
content="A freely available implementation
of the C++ Standard Template Library, including
hypertext documentation.">
<META name="keywords"
content="generic programming, STL, standard template library">
</HEAD>
<SCRIPT LANGUAGE="JavaScript"><!--
var adcategory = "cpp";
// -->
</SCRIPT>
<body background="../../fancyhome/back.gif" bgcolor="#FFFFFF" >
<SCRIPT LANGUAGE="JavaScript"><!--
var nfrm = location.href.indexOf("_nfrm_");
var validframes = (top.frames.length > 0 && top.frames['ad'] && top.frames['logo'] );
var random = Math.random();
if( !validframes && nfrm == -1 )
{
var dclkPage = "www.codeguru.com/";
if( self.adcategory )
dclkPage += adcategory;
else
dclkPage += "mfc";
document.write('<nolayer><center>');
document.write('<iframe src="http://ad.doubleclick.net/adi/' + dclkPage + ';ord='
+ random + '" width=470 height=62 marginwidth=0 marginheight=0 hspace=0 vspace=0 '
+ 'frameborder=0 scrolling=no bordercolor="#000000">');
document.write('<a href="http://ad.doubleclick.net/jump/' + dclkPage + ';ord='
+ random + '">');
document.write('<img src="http://ad.doubleclick.net/ad/' + dclkPage + ';ord='
+ random + '" height=60 width=468>' + '</a>');
document.write('</iframe>');
document.write('</center></nolayer>');
document.write('<layer src="http://ad.doubleclick.net/adl/' + dclkPage +
';ord=' + random + '"></layer>');
document.write('<ilayer visibility=hide width=468 height=83></ilayer>');
}
// top.location = "/show.cgi?" + adcategory + "=" + location.pathname;
// -->
</SCRIPT>
<noscript>
<p align="center">
<a href="http://ad.doubleclick.net/jump/www.codeguru.com/cpp;ord=NupaH9FCY34AAHbHHhQ">
<img src="http://ad.doubleclick.net/ad/www.codeguru.com/cpp;ord=NupaH9FCY34AAHbHHhQ"></a>
</p>
</noscript>
<BR Clear>
<H1>Hashed 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>
A Hashed Associative Container is an <A href="AssociativeContainer.html">Associative Container</A> whose
implementation is a hash table. <A href="#1">[1]</A> The elements of a Hashed
Associative Container are not guaranteed to be in any meaningful
order; in particular, they are not sorted. The worst case complexity
of most operations on Hashed Associative Containers is linear in the
size of the container, but the average case complexity is constant
time; this means that for applications where values are simply stored
and retrieved, and where ordering is unimportant, Hashed Associative
Containers are usually much faster than <A href="SortedAssociativeContainer.html">Sorted Associative
Containers</A>.
<h3>Refinement of</h3>
<A href="AssociativeContainer.html">Associative Container</A>
<h3>Associated types</h3>
The following new types are introduced, in addition to the types defined in the
<A href="AssociativeContainer.html">Associative Container</A> requirements.
<Table border>
<TR>
<TD VAlign=top>
Hash function
<TD VAlign=top>
<tt>X::hasher</tt>
</TD>
<TD VAlign=top>
A type that is a model of <A href="HashFunction.html">Hash Function</A>. <tt>X::hasher</tt>'s argument
type must be <tt>X::key_type</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
Key equal
</TD>
<TD VAlign=top>
<tt>X::key_equal</tt>
</TD>
<TD VAlign=top>
A <A href="BinaryPredicate.html">Binary Predicate</A> whose argument type is <tt>X::key_type</tt>. An
object of type <tt>key_equal</tt> returns <tt>true</tt> if its arguments are
the same key, and <tt>false</tt> otherwise. <tt>X::key_equal</tt> must be
an equivalence relation.
</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 Hashed 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>
<TR>
<TD VAlign=top>
<tt>n</tt>
</TD>
<TD VAlign=top>
Object of type <tt>X::size_type</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>h</tt>
</TD>
<TD VAlign=top>
Object of type <tt>X::hasher</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>c</tt>
</TD>
<TD VAlign=top>
Object of type <tt>X::key_equal</tt>
</TD>
</tr>
</table>
<h3>Definitions</h3>
A <i>hash function</i> for a Hashed Associative Container <tt>X</tt> is a
<A href="UnaryFunction.html">Unary Function</A> whose argument type is <tt>X::key_type</tt> and whose
return type is <tt>size_t</tt>. A hash function must be deterministic (that
is, it must always return the same value whenever it is called with
the same argument), but return values of the hash function should be
as uniform as possible: ideally, no two keys will hash to the same
value. <A href="#2">[2]</A>
<P>
Elements in a Hashed Associative Container are organized into
<i>buckets</i>. A Hashed Associative Container uses the value of the
hash function to determine which bucket an element is assigned to.
<P>
The number of elements in a Hashed Associative Container divided by
the number of buckets is called the <i>load factor</i>. A Hashed
Associative Container with a small load factor is faster than one with
a large load factor.
<h3>Valid expressions</h3>
In addition to the expressions defined in <A href="AssociativeContainer.html">Associative 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>
</TD>
<TD VAlign=top>
</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>
</TD>
<TD VAlign=top>
</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>
</TD>
<TD VAlign=top>
</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>
</TD>
<TD VAlign=top>
</TD>
</TR>
<TR>
<TD VAlign=top>
Hash function
</TD>
<TD VAlign=top>
<tt>a.hash_funct()</tt>
</TD>
<TD VAlign=top>
</TD>
<TD VAlign=top>
<tt>X::hasher</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
Key equal
</TD>
<TD VAlign=top>
<tt>a.key_eq()</tt>
</TD>
<TD VAlign=top>
</TD>
<TD VAlign=top>
<tt>X::key_equal</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
Erase key
</TD>
<TD VAlign=top>
<tt>a.erase(k)</tt>
</TD>
<TD VAlign=top>
</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>
</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>
</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>
</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>
</TD>
<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>
</TD>
<TD VAlign=top>
<tt>pair<iterator, iterator></tt> if <tt>a</tt> is mutable, otherwise
<tt>pair<const_iterator, const_iterator></tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
Bucket count
</TD>
<TD VAlign=top>
<tt>a.bucket_count()</tt>
</TD>
<TD VAlign=top>
</TD>
<TD VAlign=top>
<tt>X::size_type</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
Resize
</TD>
<TD VAlign=top>
<tt>a.resize(n)</tt>
</TD>
<TD VAlign=top>
</TD>
<TD VAlign=top>
<tt>void</tt>
</TD>
</tr>
</table>
<h3>Expression semantics</h3>
<Table border>
<TR>
<TH>
Name
?? 快捷鍵說(shuō)明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -