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

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