📄 hashedassociativecontainer.html
字号:
<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>Hashed 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>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> whoseimplementation is a hash table. <A href="#1">[1]</A> The elements of a HashedAssociative Container are not guaranteed to be in any meaningfulorder; in particular, they are not sorted. The worst case complexityof most operations on Hashed Associative Containers is linear in thesize of the container, but the average case complexity is constanttime; this means that for applications where values are simply storedand retrieved, and where ordering is unimportant, Hashed AssociativeContainers are usually much faster than <A href="SortedAssociativeContainer.html">Sorted AssociativeContainers</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><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 whosereturn type is <tt>size_t</tt>. A hash function must be deterministic (thatis, it must always return the same value whenever it is called withthe same argument), but return values of the hash function should beas uniform as possible: ideally, no two keys will hash to the samevalue. <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 thehash function to determine which bucket an element is assigned to.<P>The number of elements in a Hashed Associative Container divided bythe number of buckets is called the <i>load factor</i>. A HashedAssociative Container with a small load factor is faster than one witha 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><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> </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>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -