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

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