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

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