source: GTP/trunk/Lib/Vis/Preprocessing/src/sparsehash/doc/dense_hash_set.html @ 2162

Revision 2162, 32.4 KB checked in by mattausch, 17 years ago (diff)

improved hash performance with google hashmap
Line 
1<HTML>
2<!-- The API of this class and the documentation -- but not the
3     implementation! -- are based on that for SGI's hash_set class:
4  -->
5<!--
6  -- Copyright (c) 1996-1999
7  -- Silicon Graphics Computer Systems, Inc.
8  --
9  -- Permission to use, copy, modify, distribute and sell this software
10  -- and its documentation for any purpose is hereby granted without fee,
11  -- provided that the above copyright notice appears in all copies and
12  -- that both that copyright notice and this permission notice appear
13  -- in supporting documentation.  Silicon Graphics makes no
14  -- representations about the suitability of this software for any
15  -- purpose.  It is provided "as is" without express or implied warranty.
16  --
17  -- Copyright (c) 1994
18  -- Hewlett-Packard Company
19  --
20  -- Permission to use, copy, modify, distribute and sell this software
21  -- and its documentation for any purpose is hereby granted without fee,
22  -- provided that the above copyright notice appears in all copies and
23  -- that both that copyright notice and this permission notice appear
24  -- in supporting documentation.  Hewlett-Packard Company makes no
25  -- representations about the suitability of this software for any
26  -- purpose.  It is provided "as is" without express or implied warranty.
27  --
28  -->
29
30<HEAD>
31<Title>dense_hash_set&lt;Key, HashFcn, EqualKey, Alloc&gt;</Title>
32</HEAD>
33
34<BODY>
35
36<p><i>[Note: this document is formatted similarly to the SGI STL
37implementation documentation pages, and refers to concepts and classes
38defined there.  However, neither this document nor the code it
39describes is associated with SGI, nor is it necessary to have SGI's
40STL implementation installed in order to use this class.]</i></p>
41
42
43<H1>dense_hash_set&lt;Key, HashFcn, EqualKey, Alloc&gt;</H1>
44
45<p><tt>dense_hash_set</tt> is a <A
46href="http://www.sgi.com/tech/stl/HashedAssociativeContainer.html">Hashed
47Associative Container</A> that stores objects of type <tt>Key</tt>.
48<tt>dense_hash_set</tt> is a <A
49href="http://www.sgi.com/tech/stl/SimpleAssociativeContainer.html">Simple
50Associative Container</A>, meaning that its value type, as well as its
51key type, is <tt>key</tt>  It is also a
52<A
53href="http://www.sgi.com/tech/stl/UniqueAssociativeContainer.html">Unique
54Associative Container</A>, meaning that no two elements have keys that
55compare equal using <tt>EqualKey</tt>.</p>
56
57<p>Looking up an element in a <tt>dense_hash_set</tt> by its key is
58efficient, so <tt>dense_hash_set</tt> is useful for &quot;dictionaries&quot;
59where the order of elements is irrelevant.  If it is important for the
60elements to be in a particular order, however, then <tt><A
61href="http://www.sgi.com/tech/stl/Map.html">map</A></tt> is more appropriate.</p>
62
63<p><tt>dense_hash_set</tt> is distinguished from other hash-set
64implementations by its speed and by the ability to save
65and restore contents to disk.  On the other hand, this hash-set
66implementation can use significantly more space than other hash-set
67implementations, and it also has requirements -- for instance, for a
68distinguished "empty key" -- that may not be easy for all
69applications to satisfy.</p>
70
71<p>This class is appropriate for applications that need speedy access
72to relatively small "dictionaries" stored in memory, and for
73applications that need these dictionaries to be persistent. <A
74HREF="#io">[implementation note]</A>)</p>
75
76
77<h3>Example</h3>
78
79<pre>
80#include &lt;google/dense_hash_set&gt;
81
82using std::dense_hash_set;      // namespace where class lives by default
83
84struct eqstr
85{
86  bool operator()(const char* s1, const char* s2) const
87  {
88    return strcmp(s1, s2) == 0;
89  }
90};
91
92void lookup(const hash_set&lt;const char*, hash&lt;const char*&gt;, eqstr&gt;&amp; Set,
93            const char* word)
94{
95  dense_hash_set&lt;const char*, hash&lt;const char*&gt;, eqstr&gt;::const_iterator it
96    = Set.find(word);
97  cout &lt;&lt; word &lt;&lt; &quot;: &quot;
98       &lt;&lt; (it != Set.end() ? &quot;present&quot; : &quot;not present&quot;)
99       &lt;&lt; endl;
100}
101
102int main()
103{
104  dense_hash_set&lt;const char*, hash&lt;const char*&gt;, eqstr&gt; Set;
105  Set.set_empty_key(NULL);
106  Set.insert(&quot;kiwi&quot;);
107  Set.insert(&quot;plum&quot;);
108  Set.insert(&quot;apple&quot;);
109  Set.insert(&quot;mango&quot;);
110  Set.insert(&quot;apricot&quot;);
111  Set.insert(&quot;banana&quot;);
112
113  lookup(Set, &quot;mango&quot;);
114  lookup(Set, &quot;apple&quot;);
115  lookup(Set, &quot;durian&quot;);
116}
117</pre>
118
119
120<h3>Definition</h3>
121
122Defined in the header <A
123href="dense_hash_set.h">dense_hash_set.h</A>.  This class is not
124part of the C++ standard.
125
126
127<h3>Template parameters</h3>
128
129<table border>
130<TR><TH>Parameter</TH><TH>Description</TH><TH>Default</TH></TR>
131
132<TR>
133<TD VAlign=top>
134   <tt>Key</tt>
135</TD>
136<TD VAlign=top>
137   The hash_set's key and value type.  This is also defined as
138   <tt>dense_hash_set::key_type</tt> and
139   <tt>dense_hash_set::value_type</tt>.
140</TD>
141<TD VAlign=top>
142   &nbsp;
143</TD>
144</TR>
145
146<TR>
147<TD VAlign=top>
148   <tt>Data</tt>
149</TD>
150<TD VAlign=top>
151   The hash_set's data type.  This is also defined as
152   <tt>dense_hash_set::data_type</tt>.
153</TD>
154<TD VAlign=top>
155   &nbsp;
156</TD>
157</TR>
158
159<TR>
160<TD VAlign=top>
161   <tt>HashFcn</tt>
162</TD>
163<TD VAlign=top>
164   The <A href="http://www.sgi.com/tech/stl/HashFunction.html">hash function</A> used by the
165   hash_set.  This is also defined as <tt>dense_hash_set::hasher</tt>. 
166   <br><b>Note:</b> Hashtable performance depends heavliy on the choice of
167   hash function.  See <A HREF="performance.html#hashfn">the performance
168   page</A> for more information.
169</TD>
170<TD VAlign=top>
171   <tt><A href="http://www.sgi.com/tech/stl/hash.html">hash</A>&lt;Key&gt;</tt>
172</TD>
173</TR>
174
175<TR>
176<TD VAlign=top>
177   <tt>EqualKey</tt>
178</TD>
179<TD VAlign=top>
180   The hash_set key equality function: a <A
181   href="http://www.sgi.com/tech/stl/BinaryPredicate.html">binary predicate</A> that determines
182   whether two keys are equal.  This is also defined as
183   <tt>dense_hash_set::key_equal</tt>.
184</TD>
185<TD VAlign=top>
186   <tt><A href="http://www.sgi.com/tech/stl/equal_to.html">equal_to</A>&lt;Key&gt;</tt>
187</TD>
188</TR>
189
190<TR>
191<TD VAlign=top>
192   <tt>Alloc</tt>
193</TD>
194<TD VAlign=top>
195   <b>Ignored</b>; this is included only for API-compatibility
196   with SGI's STL implementation.
197</TD>
198<TD VAlign=top>
199    <tt><A href="http://www.sgi.com/tech/stl/Allocators.html">alloc</A></tt>
200</TD>
201</TR>
202
203</table>
204
205
206<h3>Model of</h3>
207
208<A href="http://www.sgi.com/tech/stl/UniqueHashedAssociativeContainer.html">Unique Hashed Associative Container</A>,
209<A href="http://www.sgi.com/tech/stl/SimpleAssociativeContainer.html">Simple Associative Container</A>
210
211
212<h3>Type requirements</h3>
213
214<UL>
215<LI>
216<tt>Key</tt> is Assignable.
217<LI>
218<tt>EqualKey</tt> is a Binary Predicate whose argument type is Key.
219<LI>
220<tt>EqualKey</tt> is an equivalence relation.
221<LI>
222<tt>Alloc</tt> is an Allocator.
223</UL>
224
225
226<h3>Public base classes</h3>
227
228None.
229
230
231<h3>Members</h3>
232
233<table border>
234<TR><TH>Member</TH><TH>Where defined</TH><TH>Description</TH></TR>
235
236<TR>
237<TD VAlign=top>
238   <tt>value_type</tt> <A href="#5">[7]</A>
239</TD>
240<TD VAlign=top>
241    <A
242    href="http://www.sgi.com/tech/stl/Container.html">Container</A>
243</TD>
244<TD VAlign=top>
245   The type of object, <tt>T</tt>, stored in the hash_set.
246</TD>
247</TR>
248
249<TR>
250<TD VAlign=top>
251   <tt>key_type</tt>
252</TD>
253<TD VAlign=top>
254    <A
255    href="http://www.sgi.com/tech/stl/AssociativeContainer.html">Associative
256    Container</A>
257</TD>
258<TD VAlign=top>
259   The key type associated with <tt>value_type</tt>.
260</TD>
261</TR>
262
263<TR>
264<TD VAlign=top>
265   <tt>hasher</tt>
266</TD>
267<TD VAlign=top>
268    <A
269    href="http://www.sgi.com/tech/stl/HashedAssociativeContainer.html">Hashed
270    Associative Container</A>
271</TD>
272<TD VAlign=top>
273   The <tt>dense_hash_set</tt>'s <A
274   href="http://www.sgi.com/tech/stl/HashFunction.html">hash
275   function</A>.
276</TD>
277</TR>
278
279<TR>
280<TD VAlign=top>
281   <tt>key_equal</tt>
282</TD>
283<TD VAlign=top>
284    <A
285    href="http://www.sgi.com/tech/stl/HashedAssociativeContainer.html">Hashed
286    Associative Container</A>
287</TD>
288<TD VAlign=top>
289    <A href="http://www.sgi.com/tech/stl/functors.html">Function
290    object</A> that compares keys for equality.
291</TD>
292</TR>
293
294<TR>
295<TD VAlign=top>
296   <tt>pointer</tt>
297</TD>
298<TD VAlign=top>
299    <A href="http://www.sgi.com/tech/stl/Container.html">Container</A>
300</TD>
301<TD VAlign=top>
302   Pointer to <tt>T</tt>.
303</TD>
304</TR>
305
306<TR>
307<TD VAlign=top>
308   <tt>reference</tt>
309</TD>
310<TD VAlign=top>
311    <A href="http://www.sgi.com/tech/stl/Container.html">Container</A>
312</TD>
313<TD VAlign=top>
314   Reference to <tt>T</tt>
315</TD>
316</TR>
317
318<TR>
319<TD VAlign=top>
320   <tt>const_reference</tt>
321</TD>
322<TD VAlign=top>
323    <A href="http://www.sgi.com/tech/stl/Container.html">Container</A>
324</TD>
325<TD VAlign=top>
326   Const reference to <tt>T</tt>
327</TD>
328</TR>
329
330<TR>
331<TD VAlign=top>
332   <tt>size_type</tt>
333</TD>
334<TD VAlign=top>
335    <A href="http://www.sgi.com/tech/stl/Container.html">Container</A>
336</TD>
337<TD VAlign=top>
338   An unsigned integral type.
339</TD>
340</TR>
341
342<TR>
343<TD VAlign=top>
344   <tt>difference_type</tt>
345</TD>
346<TD VAlign=top>
347    <A href="http://www.sgi.com/tech/stl/Container.html">Container</A>
348</TD>
349<TD VAlign=top>
350   A signed integral type.
351</TD>
352</TR>
353
354<TR>
355<TD VAlign=top>
356   <tt>iterator</tt>
357</TD>
358<TD VAlign=top>
359    <A href="http://www.sgi.com/tech/stl/Container.html">Container</A>
360</TD>
361<TD VAlign=top>
362   Iterator used to iterate through a <tt>dense_hash_set</tt>.
363</TD>
364</TR>
365
366<TR>
367<TD VAlign=top>
368   <tt>const_iterator</tt>
369</TD>
370<TD VAlign=top>
371    <A href="http://www.sgi.com/tech/stl/Container.html">Container</A>
372</TD>
373<TD VAlign=top>
374   Const iterator used to iterate through a <tt>dense_hash_set</tt>.
375   (<tt>iterator</tt> and <tt>const_iterator</tt> are the same type.)
376</TD>
377</TR>
378
379<TR>
380<TD VAlign=top>
381   <tt>iterator begin() const</tt>
382</TD>
383<TD VAlign=top>
384    <A href="http://www.sgi.com/tech/stl/Container.html">Container</A>
385</TD>
386<TD VAlign=top>
387   Returns an <tt>iterator</tt> pointing to the beginning of the
388   <tt>dense_hash_set</tt>.
389</TD>
390</TR>
391
392<TR>
393<TD VAlign=top>
394   <tt>iterator end() const</tt>
395</TD>
396<TD VAlign=top>
397    <A href="http://www.sgi.com/tech/stl/Container.html">Container</A>
398</TD>
399<TD VAlign=top>
400   Returns an <tt>iterator</tt> pointing to the end of the
401   <tt>dense_hash_set</tt>.
402</TD>
403</TR>
404
405<TR>
406<TD VAlign=top>
407   <tt>size_type size() const</tt>
408</TD>
409<TD VAlign=top>
410    <A href="http://www.sgi.com/tech/stl/Container.html">Container</A>
411</TD>
412<TD VAlign=top>
413   Returns the size of the <tt>dense_hash_set</tt>.
414</TD>
415</TR>
416
417<TR>
418<TD VAlign=top>
419   <tt>size_type max_size() const</tt>
420</TD>
421<TD VAlign=top>
422    <A href="http://www.sgi.com/tech/stl/Container.html">Container</A>
423</TD>
424<TD VAlign=top>
425   Returns the largest possible size of the <tt>dense_hash_set</tt>.
426</TD>
427</TR>
428
429<TR>
430<TD VAlign=top>
431   <tt>bool empty() const</tt>
432</TD>
433<TD VAlign=top>
434    <A href="http://www.sgi.com/tech/stl/Container.html">Container</A>
435</TD>
436<TD VAlign=top>
437   <tt>true</tt> if the <tt>dense_hash_set</tt>'s size is <tt>0</tt>.
438</TD>
439</TR>
440
441<TR>
442<TD VAlign=top>
443   <tt>size_type bucket_count() const</tt>
444</TD>
445<TD VAlign=top>
446    <A
447    href="http://www.sgi.com/tech/stl/HashedAssociativeContainer.html">Hashed
448    Associative Container</A>
449</TD>
450<TD VAlign=top>
451   Returns the number of buckets used by the <tt>dense_hash_set</tt>.
452</TD>
453</TR>
454
455<TR>
456<TD VAlign=top>
457   <tt>size_type max_bucket_count() const</tt>
458</TD>
459<TD VAlign=top>
460    <A
461    href="http://www.sgi.com/tech/stl/HashedAssociativeContainer.html">Hashed
462    Associative Container</A>
463</TD>
464<TD VAlign=top>
465   Returns the largest possible number of buckets used by the <tt>dense_hash_set</tt>.
466</TD>
467</TR>
468
469<TR>
470<TD VAlign=top>
471   <tt>void resize(size_type n)</tt>
472</TD>
473<TD VAlign=top>
474    <A
475    href="http://www.sgi.com/tech/stl/HashedAssociativeContainer.html">Hashed
476    Associative Container</A>
477</TD>
478<TD VAlign=top>
479   Increases the bucket count to at least <tt>n</tt>.
480   <A href="#2">[4]</A>
481</TD>
482</TR>
483
484<TR>
485<TD VAlign=top>
486   <tt>hasher hash_funct() const</tt>
487</TD>
488<TD VAlign=top>
489    <A
490    href="http://www.sgi.com/tech/stl/HashedAssociativeContainer.html">Hashed
491    Associative Container</A>
492</TD>
493<TD VAlign=top>
494   Returns the <tt>hasher</tt> object used by the <tt>dense_hash_set</tt>.
495</TD>
496</TR>
497
498<TR>
499<TD VAlign=top>
500   <tt>key_equal key_eq() const</tt>
501</TD>
502<TD VAlign=top>
503    <A
504    href="http://www.sgi.com/tech/stl/HashedAssociativeContainer.html">Hashed
505    Associative Container</A>
506</TD>
507<TD VAlign=top>
508   Returns the <tt>key_equal</tt> object used by the
509   <tt>dense_hash_set</tt>.
510</TD>
511</TR>
512
513<TR>
514<TD VAlign=top>
515   <tt>dense_hash_set()</tt>
516</TD>
517<TD VAlign=top>
518    <A href="http://www.sgi.com/tech/stl/Container.html">Container</A>
519</TD>
520<TD VAlign=top>
521   Creates an empty <tt>dense_hash_set</tt>.
522</TD>
523</TR>
524
525<TR>
526<TD VAlign=top>
527   <tt>dense_hash_set(size_type n)</tt>
528</TD>
529<TD VAlign=top>
530    <A
531    href="http://www.sgi.com/tech/stl/HashedAssociativeContainer.html">Hashed
532    Associative Container</A>
533</TD>
534<TD VAlign=top>
535   Creates an empty <tt>dense_hash_set</tt> that's optimized for holding
536   up to <tt>n</tt> items.
537   <A href="#3">[5]</A>
538</TD>
539</TR>
540
541<TR>
542<TD VAlign=top>
543   <tt>dense_hash_set(size_type n, const hasher&amp; h)</tt>
544</TD>
545<TD VAlign=top>
546    <A
547    href="http://www.sgi.com/tech/stl/HashedAssociativeContainer.html">Hashed
548    Associative Container</A>
549</TD>
550<TD VAlign=top>
551   Creates an empty <tt>dense_hash_set</tt> that's optimized for up
552   to <tt>n</tt> items, using <tt>h</tt> as the hash function.
553</TD>
554</TR>
555
556<TR>
557<TD VAlign=top>
558   <tt>dense_hash_set(size_type n, const hasher&amp; h, const
559   key_equal&amp; k)</tt>
560</TD>
561<TD VAlign=top>
562    <A
563    href="http://www.sgi.com/tech/stl/HashedAssociativeContainer.html">Hashed
564    Associative Container</A>
565</TD>
566<TD VAlign=top>
567   Creates an empty <tt>dense_hash_set</tt> that's optimized for up
568   to <tt>n</tt> items, using <tt>h</tt> as the hash function and
569   <tt>k</tt> as the key equal function.
570</TD>
571</TR>
572
573<TR>
574<TD VAlign=top>
575   <pre>template &lt;class <A
576href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</A>&gt;
577dense_hash_set(InputIterator f, InputIterator l) </pre>
578<A href="#1">[2]</A>
579</TD>
580<TD VAlign=top>
581    <A
582    href="http://www.sgi.com/tech/stl/UniqueHashedAssociativeContainer.html">Unique
583    Hashed Associative Container</A>
584</TD>
585<TD VAlign=top>
586   Creates a dense_hash_set with a copy of a range.
587</TD>
588</TR>
589
590<TR>
591<TD VAlign=top>
592   <pre>template &lt;class <A
593href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</A>&gt;
594dense_hash_set(InputIterator f, InputIterator l, size_type n) </pre>
595<A href="#1">[2]</A>
596</TD>
597<TD VAlign=top>
598    <A
599    href="http://www.sgi.com/tech/stl/UniqueHashedAssociativeContainer.html">Unique
600    Hashed Associative Container</A>
601</TD>
602<TD VAlign=top>
603   Creates a hash_set with a copy of a range that's optimized to
604   hold up to <tt>n</tt> items.
605</TD>
606</TR>
607
608<TR>
609<TD VAlign=top>
610   <pre>template &lt;class <A
611href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</A>&gt;
612dense_hash_set(InputIterator f, InputIterator l, size_type n, const
613hasher&amp; h) </pre> <A href="#1">[2]</A>
614</TD>
615<TD VAlign=top>
616    <A
617    href="http://www.sgi.com/tech/stl/UniqueHashedAssociativeContainer.html">Unique
618    Hashed Associative Container</A>
619</TD>
620<TD VAlign=top>
621   Creates a hash_set with a copy of a range that's optimized to hold
622   up to <tt>n</tt> items, using <tt>h</tt> as the hash function.
623</TD>
624</TR>
625
626<TR>
627<TD VAlign=top>
628   <pre>template &lt;class <A
629href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</A>&gt;
630dense_hash_set(InputIterator f, InputIterator l, size_type n, const
631hasher&amp; h, const key_equal&amp; k) </pre> <A href="#1">[2]</A>
632</TD>
633<TD VAlign=top>
634    <A
635    href="http://www.sgi.com/tech/stl/UniqueHashedAssociativeContainer.html">Unique
636    Hashed Associative Container</A>
637</TD>
638<TD VAlign=top>
639   Creates a hash_set with a copy of a range that's optimized for
640   holding up to <tt>n</tt> items, using <tt>h</tt> as the hash
641   function and <tt>k</tt> as the key equal function.
642</TD>
643</TR>
644
645<TR>
646<TD VAlign=top>
647   <tt>dense_hash_set(const hash_set&amp;)</tt>
648</TD>
649<TD VAlign=top>
650    <A href="http://www.sgi.com/tech/stl/Container.html">Container</A>
651</TD>
652<TD VAlign=top>
653   The copy constructor.
654</TD>
655</TR>
656
657<TR>
658<TD VAlign=top>
659   <tt>dense_hash_set&amp; operator=(const hash_set&amp;)</tt>
660</TD>
661<TD VAlign=top>
662    <A href="http://www.sgi.com/tech/stl/Container.html">Container</A>
663</TD>
664<TD VAlign=top>
665   The assignment operator
666</TD>
667</TR>
668
669<TR>
670<TD VAlign=top>
671   <tt>void swap(hash_set&amp;)</tt>
672</TD>
673<TD VAlign=top>
674    <A href="http://www.sgi.com/tech/stl/Container.html">Container</A>
675</TD>
676<TD VAlign=top>
677   Swaps the contents of two hash_sets.
678</TD>
679</TR>
680
681<TR>
682<TD VAlign=top>
683   <pre>pair&lt;iterator, bool&gt; insert(const value_type&amp; x)
684</pre>
685</TD>
686<TD VAlign=top>
687    <A
688    href="http://www.sgi.com/tech/stl/UniqueAssociativeContainer.html">Unique
689    Associative Container</A>
690</TD>
691<TD VAlign=top>
692   Inserts <tt>x</tt> into the <tt>dense_hash_set</tt>.
693</TD>
694</TR>
695
696<TR>
697<TD VAlign=top>
698   <pre>template &lt;class <A
699href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</A>&gt;
700void insert(InputIterator f, InputIterator l) </pre> <A href="#1">[2]</A>
701</TD>
702<TD VAlign=top>
703    <A
704    href="http://www.sgi.com/tech/stl/UniqueAssociativeContainer.html">Unique
705    Associative Container</A>
706</TD>
707<TD VAlign=top>
708   Inserts a range into the <tt>dense_hash_set</tt>.
709</TD>
710</TR>
711
712<TR>
713<TD VAlign=top>
714   <tt>void set_empty_key(const key_type& key)</tt> <A href="#6">[6]</A>
715</TD>
716<TD VAlign=top>
717   <tt>dense_hash_set</tt>
718</TD>
719<TD VAlign=top>
720   See below.
721</TD>
722</TR>
723
724<TR>
725<TD VAlign=top>
726   <tt>void set_deleted_key(const key_type& key)</tt> <A href="#6">[6]</A>
727</TD>
728<TD VAlign=top>
729   <tt>dense_hash_set</tt>
730</TD>
731<TD VAlign=top>
732   See below.
733</TD>
734</TR>
735
736<TR>
737<TD VAlign=top>
738   <tt>void clear_deleted_key()</tt> <A href="#4">[6]</A>
739</TD>
740<TD VAlign=top>
741   <tt>dense_hash_set</tt>
742</TD>
743<TD VAlign=top>
744   See below.
745</TD>
746</TR>
747
748<TR>
749<TD VAlign=top>
750   <tt>void erase(iterator pos)</tt>
751</TD>
752<TD VAlign=top>
753    <A
754    href="http://www.sgi.com/tech/stl/AssociativeContainer.html">Associative
755    Container</A>
756</TD>
757<TD VAlign=top>
758   Erases the element pointed to by <tt>pos</tt>.
759   <A href="#4">[6]</A>
760</TD>
761</TR>
762
763<TR>
764<TD VAlign=top>
765   <tt>size_type erase(const key_type&amp; k)</tt>
766</TD>
767<TD VAlign=top>
768    <A
769    href="http://www.sgi.com/tech/stl/AssociativeContainer.html">Associative
770    Container</A>
771</TD>
772<TD VAlign=top>
773   Erases the element whose key is <tt>k</tt>.
774   <A href="#4">[6]</A>
775</TD>
776</TR>
777
778<TR>
779<TD VAlign=top>
780   <tt>void erase(iterator first, iterator last)</tt>
781</TD>
782<TD VAlign=top>
783    <A
784    href="http://www.sgi.com/tech/stl/AssociativeContainer.html">Associative
785    Container</A>
786</TD>
787<TD VAlign=top>
788   Erases all elements in a range.
789   <A href="#4">[6]</A>
790</TD>
791</TR>
792
793<TR>
794<TD VAlign=top>
795   <tt>void clear()</tt>
796</TD>
797<TD VAlign=top>
798    <A
799    href="http://www.sgi.com/tech/stl/AssociativeContainer.html">Associative
800    Container</A>
801</TD>
802<TD VAlign=top>
803   Erases all of the elements.
804</TD>
805</TR>
806
807<TR>
808<TD VAlign=top>
809   <tt>iterator find(const key_type&amp; k) const</tt>
810</TD>
811<TD VAlign=top>
812    <A
813    href="http://www.sgi.com/tech/stl/AssociativeContainer.html">Associative
814    Container</A>
815</TD>
816<TD VAlign=top>
817   Finds an element whose key is <tt>k</tt>.
818</TD>
819</TR>
820
821<TR>
822<TD VAlign=top>
823   <tt>size_type count(const key_type&amp; k) const</tt>
824</TD>
825<TD VAlign=top>
826    <A
827    href="http://www.sgi.com/tech/stl/UniqueAssociativeContainer.html">Unique
828    Associative Container</A>
829</TD>
830<TD VAlign=top>
831   Counts the number of elements whose key is <tt>k</tt>.
832</TD>
833</TR>
834
835<TR>
836<TD VAlign=top>
837   <pre>pair&lt;iterator, iterator&gt; equal_range(const
838key_type&amp; k) const</pre>
839</TD>
840<TD VAlign=top>
841    <A
842    href="http://www.sgi.com/tech/stl/AssociativeContainer.html">Associative
843    Container</A>
844</TD>
845<TD VAlign=top>
846   Finds a range containing all elements whose key is <tt>k</tt>.
847</TD>
848</TR>
849
850<TR>
851<TD VAlign=top>
852   <tt>bool write_metadata(FILE *fp)</tt>
853</TD>
854<TD VAlign=top>
855   <tt>dense_hash_set</tt>
856</TD>
857<TD VAlign=top>
858   See below.
859</TD>
860</TR>
861
862<TR>
863<TD VAlign=top>
864   <tt>bool read_metadata(FILE *fp)</tt>
865</TD>
866<TD VAlign=top>
867   <tt>dense_hash_set</tt>
868</TD>
869<TD VAlign=top>
870   See below.
871</TD>
872</TR>
873
874<TR>
875<TD VAlign=top>
876   <tt>bool write_nopointer_data(FILE *fp)</tt>
877</TD>
878<TD VAlign=top>
879   <tt>dense_hash_set</tt>
880</TD>
881<TD VAlign=top>
882   See below.
883</TD>
884</TR>
885
886<TR>
887<TD VAlign=top>
888   <tt>bool read_nopointer_data(FILE *fp)</tt>
889</TD>
890<TD VAlign=top>
891   <tt>dense_hash_set</tt>
892</TD>
893<TD VAlign=top>
894   See below.
895</TD>
896</TR>
897
898<TR>
899<TD VAlign=top>
900   <pre>bool operator==(const hash_set&amp;, const hash_set&amp;)
901</pre>
902</TD>
903<TD VAlign=top>
904    <A
905    href="http://www.sgi.com/tech/stl/HashedAssociativeContainer.html">Hashed
906    Associative Container</A>
907</TD>
908<TD VAlign=top>
909   Tests two hash_sets for equality.  This is a global function, not a
910   member function.
911</TD>
912</TR>
913
914</table>
915
916
917<h3>New members</h3>
918
919These members are not defined in the <A
920href="http://www.sgi.com/tech/stl/UniqueHashedAssociativeContainer.html">Unique
921Hashed Associative Container</A> and <A
922href="http://www.sgi.com/tech/stl/SimpleAssociativeContainer.html">Simple
923Associative Container</A> requirements, but are specific to
924<tt>dense_hash_set</tt>.
925
926<table border>
927<TR><TH>Member</TH><TH>Description</TH></TR>
928
929<TR>
930<TD VAlign=top>
931   <tt>void set_empty_key(const key_type& key)</tt>
932</TD>
933<TD VAlign=top>
934   Sets the distinguished "empty" key to <tt>key</tt>.  This must be
935   called immediately after construct time, before calls to another
936   other <tt>dense_hash_set</tt> operation. <A href="#6">[6]</A>
937</TD>
938</TR>
939
940<TR>
941<TD VAlign=top>
942   <tt>void set_deleted_key(const key_type& key)</tt>
943</TD>
944<TD VAlign=top>
945   Sets the distinguished "deleted" key to <tt>key</tt>.  This must be
946   called before any calls to <tt>erase()</tt>. <A href="#4">[6]</A>
947</TD>
948</TR>
949
950<TR>
951<TD VAlign=top>
952   <tt>void clear_deleted_key()</tt> <A href="#4">[6]</A>
953</TD>
954<TD VAlign=top>
955   Clears the distinguished "deleted" key.  After this is called,
956   calls to <tt>erase()</tt> are not valid on this object.
957   <A href="#4">[6]</A>
958</TD>
959</TR>
960
961<TR>
962<TD VAlign=top>
963   <tt>bool write_metadata(FILE *fp)</tt>
964</TD>
965<TD VAlign=top>
966   Write hashtable metadata to <tt>fp</tt>.  See <A HREF="#io">below</A>.
967</TD>
968</TR>
969
970<TR>
971<TD VAlign=top>
972   <tt>bool read_metadata(FILE *fp)</tt>
973</TD>
974<TD VAlign=top>
975   Read hashtable metadata from <tt>fp</tt>.  See <A HREF="#io">below</A>.
976</TD>
977</TR>
978
979<TR>
980<TD VAlign=top>
981   <tt>bool write_nopointer_data(FILE *fp)</tt>
982</TD>
983<TD VAlign=top>
984   Write hashtable contents to <tt>fp</tt>.  This is valid only if the
985   hashtable key and value are "plain" data.  See <A HREF="#io">below</A>.
986</TD>
987</TR>
988
989<TR>
990<TD VAlign=top>
991   <tt>bool read_nopointer_data(FILE *fp)</tt>
992</TD>
993<TD VAlign=top>
994   Read hashtable contents to <tt>fp</tt>.  This is valid only if the
995   hashtable key and value are "plain" data.  See <A HREF="#io">below</A>.
996</TD>
997</TR>
998
999</table>
1000
1001
1002<h3>Notes</h3>
1003
1004<P><A name="1">[1]</A>
1005
1006This member function relies on <i>member template</i> functions, which
1007may not be supported by all compilers.  If your compiler supports
1008member templates, you can call this function with any type of <A
1009href="http://www.sgi.com/tech/stl/InputIterator.html">input
1010iterator</A>.  If your compiler does not yet support member templates,
1011though, then the arguments must either be of type <tt>const
1012value_type*</tt> or of type <tt>dense_hash_set::const_iterator</tt>.</p>
1013
1014<P><A name="2">[2]</A>
1015
1016In order to preserve iterators, erasing hashtable elements does not
1017cause a hashtable to resize.  This means that after a string of
1018<tt>erase()</tt> calls, the hashtable will use more space than is
1019required.  At a cost of invalidating all current iterators, you can
1020call <tt>resize()</tt> to manually compact the hashtable.  The
1021hashtable promotes too-small <tt>resize()</tt> arguments to the
1022smallest legal value, so to compact a hashtable, it's sufficient to
1023call <tt>resize(0)</tt>.
1024
1025<P><A name="3">[3]</A>
1026
1027Unlike some other hashtable implementations, the optional <i>n</i> in
1028the constructor size indicates not the desired number of buckets that
1029should be allocated, but instead the expected number of items to be
1030inserted.  The class then sizes the hash-set appropriately for the
1031number of items specified.  It's not an error to actually insert more
1032or fewer items into the hashtable, but the implementation is most
1033efficient -- does the fewest hashtable resizes -- if the number of
1034inserted items is close to <i>n</i>.</p>
1035
1036<P><A name="4">[4]</A>
1037
1038<tt>dense_hash_set</tt> <b>requires</b> you call
1039<tt>set_empty_key()</tt> immediately after constructing the hash-set,
1040and before calling any other <tt>dense_hash_set</tt> method.  (This is
1041the largest difference between the <tt>dense_hash_set</tt> API and
1042other hash-set APIs.  See <A HREF="implementation.html">implementation.html</A>
1043for why this is necessary.)
1044The argument to <tt>set_empty_key()</tt> should be a key-value that
1045is never used for legitimate hash-set entries.  If you have no such
1046key value, you will be unable to use <tt>dense_hash_set</tt>.  It is
1047an error to call <tt>insert()</tt> with an item whose key is the
1048"empty key."</p>
1049
1050<tt>dense_hash_set</tt> also requires you call
1051<tt>set_deleted_key()</tt> before calling <tt>erase()</tt>.
1052The argument to <tt>set_deleted_key()</tt> should be a key-value that
1053is never used for legitimate hash-set entries.  It must be different
1054from the key-value used for <tt>set_empty_key()</tt>.  It is an error to call
1055<tt>erase()</tt> without first calling <tt>set_deleted_key()</tt>, and
1056it is also an error to call <tt>insert()</tt> with an item whose key
1057is the "deleted key."</p>
1058
1059<p>There is no need to call <tt>set_deleted_key</tt> if you do not
1060wish to call <tt>erase()</tt> on the hash-set.</p>
1061
1062<p>It is acceptable to change the deleted-key at any time by calling
1063<tt>set_deleted_key()</tt> with a new argument.  You can also call
1064<tt>clear_deleted_key()</tt>, at which point all keys become valid for
1065insertion but no hashtable entries can be deleted until
1066<tt>set_deleted_key()</tt> is called again.</p>
1067
1068<P><A name="5">[5]</A>
1069
1070Both <tt>key_type</tt> and <tt>data_type</tt> must be <A
1071HREF="http://c2.com/cgi/wiki?PlainOldData">plain old data</A> (see
1072<A HREF="implementation.html">implementation.html</A> for why this is
1073necessary).  In addition, there should
1074be no data structures that point directly into parts of key or value,
1075including the key or value itself (for instance, you cannot have a
1076value like <tt>struct {int a = 1, *b = &a}</tt>.  This is because
1077<tt>dense_hash_set</tt> uses <tt>malloc()</tt> and <tt>free()</tt> to
1078allocate space for the key and value, and <tt>memmove()</tt> to
1079reorganize the key and value in memory.</p>
1080
1081<p>Almost all common uses fit this criterion: <tt>key_type</tt> can be
1082a basic C type or an STL type like <tt>string</tt>, for instance.  If
1083<tt>value_type</tt> is complex, consider storing only the pointer to
1084the data in the <tt>dense_hash_set</tt>.  This will speed up the
1085hashtable as well, since hashtable resizes will have to manipulate
1086less memory.</p>
1087
1088
1089<h3><A NAME=io>Input/Output</A></h3>
1090
1091<table border=1 cellpadding=5><tr><td>
1092<p><b>IMPORTANT IMPLEMENTATION NOTE:</b> In the current version of
1093this code, the input/output routines for <tt>dense_hash_set</tt> have
1094<b>not yet been implemented</b>.  This section explains the API, but
1095note that all calls to these routines will fail (return
1096<tt>false</tt>).  It is a TODO to remedy this situation.</p>
1097</td></tr></table>
1098
1099<p>It is possible to save and restore <tt>dense_hash_set</tt> objects
1100to disk.  Storage takes place in two steps.  The first writes the
1101hashtable metadata.  The second writes the actual data.</p>
1102
1103<p>To write a hashtable to disk, first call <tt>write_metadata()</tt>
1104on an open file pointer.  This saves the hashtable information in a
1105byte-order-independent format.</p>
1106
1107<p>After the metadata has been written to disk, you must write the
1108actual data stored in the hash-set to disk.  If both the key and data
1109are "simple" enough, you can do this by calling
1110<tt>write_nopointer_data()</tt>.  "Simple" data is data that can be
1111safely copied to disk via <tt>fwrite()</tt>.  Native C data types fall
1112into this category, as do structs of native C data types.  Pointers
1113and STL objects do not.</p>
1114
1115<p>Note that <tt>write_nopointer_data()</tt> does not do any endian
1116conversion.  Thus, it is only appropriate when you intend to read the
1117data on the same endian architecture as you write the data.</p>
1118
1119<p>If you cannot use <tt>write_nopointer_data()</tt> for any reason,
1120you can write the data yourself by iterating over the
1121<tt>dense_hash_set</tt> with a <tt>const_iterator</tt> and writing
1122the key and data in any manner you wish.</p>
1123
1124<p>To read the hashtable information from disk, first you must create
1125a <tt>dense_hash_set</tt> object.  Then open a file pointer to point
1126to the saved hashtable, and call <tt>read_metadata()</tt>.  If you
1127saved the data via <tt>write_nopointer_data()</tt>, you can follow the
1128<tt>read_metadata()</tt> call with a call to
1129<tt>read_nopointer_data()</tt>.  This is all that is needed.</p>
1130
1131<p>If you saved the data through a custom write routine, you must call
1132a custom read routine to read in the data.  To do this, iterate over
1133the <tt>dense_hash_set</tt> with an <tt>iterator</tt>; this operation
1134is sensical because the metadata has already been set up.  For each
1135iterator item, you can read the key and value from disk, and set it
1136appropriately.  You will need to do a <tt>const_cast</tt> on the
1137iterator, since <tt>it-&gt;first</tt> is always <tt>const</tt>.  The
1138code might look like this:</p>
1139<pre>
1140   for (dense_hash_set&lt;int*, int&gt;::iterator it = ht.begin();
1141        it != ht.end(); ++it) {
1142       const_cast&lt;int*&gt;(it-&gt;first) = new int;
1143       fread(const_cast&lt;int*&gt;(it-&gt;first), sizeof(int), 1, fp);
1144       fread(&it-&gt;second, sizeof(int), 1, fp);
1145   }
1146</pre>
1147
1148
1149<h3><A NAME=iter>Validity of Iterators</A></h3>
1150
1151<p><tt>insert()</tt> invalidates all iterators, as does
1152<tt>resize()</tt>. <tt>erase()</tt> is guaranteed not to invalidate
1153any iterators.</p>
1154
1155<p>This is implemented by making <tt>erase()</tt> not resize the
1156hashtable.  If you desire maximum space efficiency, you can call
1157<tt>resize(0)</tt> after a string of <tt>erase()</tt> calls, to force
1158the hashtable to resize to the smallest possible size.</p>
1159
1160
1161<h3>See also</h3>
1162
1163<p>The following are SGI STL concepts and classes related to
1164<tt>dense_hash_set</tt>.</p>
1165
1166<tt><A href="http://www.sgi.com/tech/stl/hash_set.html">hash_set</A></tt>,
1167<A href="http://www.sgi.com/tech/stl/AssociativeContainer.html">Associative Container</A>,
1168<A href="http://www.sgi.com/tech/stl/HashedAssociativeContainer.html">Hashed Associative Container</A>,
1169<A href="http://www.sgi.com/tech/stl/SimpleAssociativeContainer.html">Simple Associative Container</A>,
1170<A href="http://www.sgi.com/tech/stl/UniqueHashedAssociativeContainer.html">Unique Hashed Associative Container</A>,
1171<tt><A href="http://www.sgi.com/tech/stl/set.html">set</A></tt>,
1172<tt><A href="http://www.sgi.com/tech/stl/Map.html">map</A></tt>
1173<tt><A href="http://www.sgi.com/tech/stl/multiset.html">multiset</A></tt>,
1174<tt><A href="http://www.sgi.com/tech/stl/Multimap.html">multimap</A></tt>,
1175<tt><A href="http://www.sgi.com/tech/stl/hash_map.html">hash_map</A></tt>,
1176<tt><A href="http://www.sgi.com/tech/stl/hash_multiset.html">hash_multiset</A></tt>,
1177<tt><A href="http://www.sgi.com/tech/stl/hash_multimap.html">hash_multimap</A></tt>,
1178<tt><A href="sparse_hash_set.html">sparse_hash_set</A></tt>,
1179<tt><A href="sparse_hash_map.html">sparse_hash_map</A></tt>,
1180<tt><A href="dense_hash_map.html">dense_hash_map</A></tt>
1181
1182</BODY>
1183</HTML>
Note: See TracBrowser for help on using the repository browser.