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

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

improved hash performance with google hashmap
Line 
1<HTML>
2<!-- The API of this class and the documentation -- but not the
3     implementation! -- are based on that for SGI's hash_set class:
4  -->
5<!--
6  -- Copyright (c) 1996-1999
7  -- Silicon Graphics Computer Systems, Inc.
8  --
9  -- Permission to use, copy, modify, distribute and sell this software
10  -- and its documentation for any purpose is hereby granted without fee,
11  -- provided that the above copyright notice appears in all copies and
12  -- that both that copyright notice and this permission notice appear
13  -- in supporting documentation.  Silicon Graphics makes no
14  -- representations about the suitability of this software for any
15  -- purpose.  It is provided "as is" without express or implied warranty.
16  --
17  -- Copyright (c) 1994
18  -- Hewlett-Packard Company
19  --
20  -- Permission to use, copy, modify, distribute and sell this software
21  -- and its documentation for any purpose is hereby granted without fee,
22  -- provided that the above copyright notice appears in all copies and
23  -- that both that copyright notice and this permission notice appear
24  -- in supporting documentation.  Hewlett-Packard Company makes no
25  -- representations about the suitability of this software for any
26  -- purpose.  It is provided "as is" without express or implied warranty.
27  --
28  -->
29
30<HEAD>
31<Title>sparsetable&lt;T, GROUP_SIZE&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<H1>sparsetable&lt;T, GROUP_SIZE&gt;</H1>
43
44<p>A <tt>sparsetable</tt> is a <A
45href="http://www.sgi.com/tech/stl/RandomAccessContainer.html">Random
46Access Container</A> that supports constant time random access to
47elements, and constant time insertion and removal of elements.  It
48implements the "array" or "table" abstract data type.  The number of
49elements in a <tt>sparsetable</tt> is set at constructor time, though
50you can change it at any time by calling <tt>resize()</tt>.</p>
51
52<p><tt>sparsetable</tt> is distinguished from other array
53implementations, including the default C implementation, in its stingy
54use of memory -- in particular, unused array elements require only 1 bit
55of disk space to store, rather than <tt>sizeof(T)</tt> bytes -- and by
56the ability to save and restore contents to disk.  On the other hand,
57this array implementation, while still efficient, is slower than other
58array implementations.</p>
59
60<A NAME="assigned">
61<p>A <tt>sparsetable</tt> distinguishes between table elements that
62have been <i>assigned</i> and those that are <i>unassigned</i>.
63Assigned table elements are those that have had a value set via
64<tt>set()</tt>, <tt>operator()</tt>, assignment via an iterator, and
65so forth.  Unassigned table elements are those that have not had a
66value set in one of these ways, or that have been explicitly
67unassigned via a call to <tt>erase()</tt> or <tt>clear()</tt>.  Lookup
68is valid on both assigned and unassigned table elements; for
69unassigned elements, lookup returns the default value
70<tt>T()</tt>.</p>
71</A>
72
73<p>This class is appropriate for applications that need to store large
74arrays in memory, and for applications that need these arrays to be
75persistent.</p>
76
77
78<h3>Example</h3>
79
80<pre>
81#include &lt;google/sparsetable&gt;
82
83sparsetable&lt;int&gt; t(100);
84t[5] = 6;
85cout &lt;&lt; "t[5] = " &lt;&lt t[5];
86cout &lt;&lt; "Default value = " &lt;&lt t[99];
87</pre>
88
89
90<h3>Definition</h3>
91
92Defined in the header <A
93href="sparsetable.h">sparsetable.h</A>.  This class is not
94part of the C++ standard.
95
96
97<h3>Template parameters</h3>
98
99<table border>
100<TR><TH>Parameter</TH><TH>Description</TH><TH>Default</TH></TR>
101
102<TR>
103<TD VAlign=top>
104   <tt>T</tt>
105</TD>
106<TD VAlign=top>
107   The sparsetable's value type: the type of object that is stored in
108   the table.
109</TD>
110<TD VAlign=top>
111   &nbsp;
112</TD>
113</TR>
114
115<TR>
116<TD VAlign=top>
117   <tt>GROUP_SIZE</tt>
118</TD>
119<TD VAlign=top>
120   The number of elements in each sparsetable group (see <A
121   HREF="implementation.html">the implementation doc</A> for more details
122   on this value).  This almost never need be specified; the default
123   template parameter value works well in all situations.
124</TD>
125<TD VAlign=top>
126   &nbsp;
127</TD>
128</TR>
129
130</table>
131
132
133<h3>Model of</h3>
134
135<A href="http://www.sgi.com/tech/stl/RandomAccessContainer.html">Random Access Container</A>
136
137
138<h3>Type requirements</h3>
139
140None, except for those imposed by the requirements of
141<A
142href="http://www.sgi.com/tech/stl/RandomAccessContainer.html">Random
143Access Container</A>
144
145
146<h3>Public base classes</h3>
147
148None.
149
150
151<h3>Members</h3>
152
153<table border>
154<TR><TH>Member</TH><TH>Where defined</TH><TH>Description</TH></TR>
155
156<TR>
157<TD VAlign=top>
158   <tt>value_type</tt> <A href="#1">[1]</A>
159</TD>
160<TD VAlign=top>
161   <A href="http://www.sgi.com/tech/stl/Container.html">Container</A>
162</TD>
163<TD VAlign=top>
164   The type of object, <tt>T</tt>, stored in the table.
165</TD>
166</TR>
167
168<TR>
169<TD VAlign=top>
170   <tt>pointer</tt>
171</TD>
172<TD VAlign=top>
173   <A href="http://www.sgi.com/tech/stl/Container.html">Container</A>
174</TD>
175<TD VAlign=top>
176   Pointer to <tt>T</tt>.
177</TD>
178</TR>
179
180<TR>
181<TD VAlign=top>
182   <tt>reference</tt>
183</TD>
184<TD VAlign=top>
185   <A href="http://www.sgi.com/tech/stl/Container.html">Container</A>
186</TD>
187<TD VAlign=top>
188   Reference to <tt>T</tt>.
189</TD>
190</TR>
191
192<TR>
193<TD VAlign=top>
194   <tt>const_reference</tt>
195</TD>
196<TD VAlign=top>
197   <A href="http://www.sgi.com/tech/stl/Container.html">Container</A>
198</TD>
199<TD VAlign=top>
200   Const reference to <tt>T</tt>.
201</TD>
202</TR>
203
204<TR>
205<TD VAlign=top>
206   <tt>size_type</tt>
207</TD>
208<TD VAlign=top>
209   <A href="http://www.sgi.com/tech/stl/Container.html">Container</A>
210</TD>
211<TD VAlign=top>
212   An unsigned integral type.
213</TD>
214</TR>
215
216<TR>
217<TD VAlign=top>
218   <tt>difference_type</tt>
219</TD>
220<TD VAlign=top>
221   <A href="http://www.sgi.com/tech/stl/Container.html">Container</A>
222</TD>
223<TD VAlign=top>
224   A signed integral type.
225</TD>
226</TR>
227
228<TR>
229<TD VAlign=top>
230   <tt>iterator</tt>
231</TD>
232<TD VAlign=top>
233   <A href="http://www.sgi.com/tech/stl/Container.html">Container</A>
234</TD>
235<TD VAlign=top>
236   Iterator used to iterate through a <tt>sparsetable</tt>.
237</TD>
238</TR>
239
240<TR>
241<TD VAlign=top>
242   <tt>const_iterator</tt>
243</TD>
244<TD VAlign=top>
245   <A href="http://www.sgi.com/tech/stl/Container.html">Container</A>
246</TD>
247<TD VAlign=top>
248   Const iterator used to iterate through a <tt>sparsetable</tt>.
249</TD>
250</TR>
251
252<TR>
253<TD VAlign=top>
254   <tt>reverse_iterator</tt>
255</TD>
256<TD VAlign=top>
257   <A
258   href="http://www.sgi.com/tech/stl/ReversibleContainer.html">Reversible
259   Container</A>
260</TD>
261<TD VAlign=top>
262   Iterator used to iterate backwards through a <tt>sparsetable</tt>.
263</TD>
264</TR>
265
266<TR>
267<TD VAlign=top>
268   <tt>const_reverse_iterator</tt>
269</TD>
270<TD VAlign=top>
271   <A
272   href="http://www.sgi.com/tech/stl/ReversibleContainer.html">Reversible
273   Container</A>
274</TD>
275<TD VAlign=top>
276   Const iterator used to iterate backwards through a
277   <tt>sparsetable</tt>.
278</TD>
279</TR>
280
281<TR>
282<TD VAlign=top>
283   <tt>nonempty_iterator</tt>
284</TD>
285<TD VAlign=top>
286   <tt>sparsetable</tt>
287</TD>
288<TD VAlign=top>
289   Iterator used to iterate through the
290   <A HREF="#assigned">assigned</A> elements of the
291   <tt>sparsetable</tt>.
292</TD>
293</TR>
294
295<TR>
296<TD VAlign=top>
297   <tt>const_nonempty_iterator</tt>
298</TD>
299<TD VAlign=top>
300   <tt>sparsetable</tt>
301</TD>
302<TD VAlign=top>
303   Const iterator used to iterate through the
304   <A HREF="#assigned">assigned</A> elements of the
305   <tt>sparsetable</tt>.
306</TD>
307</TR>
308
309<TR>
310<TD VAlign=top>
311   <tt>reverse_nonempty_iterator</tt>
312</TD>
313<TD VAlign=top>
314   <tt>sparsetable</tt>
315</TD>
316<TD VAlign=top>
317   Iterator used to iterate backwards through the
318   <A HREF="#assigned">assigned</A> elements of the
319   <tt>sparsetable</tt>.
320</TD>
321</TR>
322
323<TR>
324<TD VAlign=top>
325   <tt>const_reverse_nonempty_iterator</tt>
326</TD>
327<TD VAlign=top>
328   <tt>sparsetable</tt>
329</TD>
330<TD VAlign=top>
331   Const iterator used to iterate backwards through the
332   <A HREF="#assigned">assigned</A> elements of the
333   <tt>sparsetable</tt>.
334</TD>
335</TR>
336
337<TR>
338<TD VAlign=top>
339   <tt>destructive_iterator</tt>
340</TD>
341<TD VAlign=top>
342   <tt>sparsetable</tt>
343</TD>
344<TD VAlign=top>
345   Iterator used to iterate through the
346   <A HREF="#assigned">assigned</A> elements of the
347   <tt>sparsetable</tt>, erasing elements as it iterates.
348   <A href="#2">[2]</A>
349</TD>
350</TR>
351
352<TR>
353<TD VAlign=top>
354   <tt>iterator begin()</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   Returns an <tt>iterator</tt> pointing to the beginning of the
361   <tt>sparsetable</tt>.
362</TD>
363</TR>
364
365<TR>
366<TD VAlign=top>
367   <tt>iterator end()</tt>
368</TD>
369<TD VAlign=top>
370    <A href="http://www.sgi.com/tech/stl/Container.html">Container</A>
371</TD>
372<TD VAlign=top>
373   Returns an <tt>iterator</tt> pointing to the end of the
374   <tt>sparsetable</tt>.
375</TD>
376</TR>
377
378<TR>
379<TD VAlign=top>
380   <tt>const_iterator begin() const</tt>
381</TD>
382<TD VAlign=top>
383    <A href="http://www.sgi.com/tech/stl/Container.html">Container</A>
384</TD>
385<TD VAlign=top>
386   Returns an <tt>const_iterator</tt> pointing to the beginning of the
387   <tt>sparsetable</tt>.
388</TD>
389</TR>
390
391<TR>
392<TD VAlign=top>
393   <tt>const_iterator end() const</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>const_iterator</tt> pointing to the end of the
400   <tt>sparsetable</tt>.
401</TD>
402</TR>
403
404<TR>
405<TD VAlign=top>
406   <tt>reverse_iterator rbegin()</tt>
407</TD>
408<TD VAlign=top>
409   <A
410   href="http://www.sgi.com/tech/stl/ReversibleContainer.html">Reversible
411   Container</A>
412</TD>
413<TD VAlign=top>
414   Returns a <tt>reverse_iterator</tt> pointing to the beginning of the
415   reversed <tt>sparsetable</tt>.
416</TD>
417</TR>
418
419<TR>
420<TD VAlign=top>
421   <tt>reverse_iterator rend()</tt>
422</TD>
423<TD VAlign=top>
424   <A
425   href="http://www.sgi.com/tech/stl/ReversibleContainer.html">Reversible
426   Container</A>
427</TD>
428<TD VAlign=top>
429   Returns a <tt>reverse_iterator</tt> pointing to the end of the
430   reversed <tt>sparsetable</tt>.
431</TD>
432</TR>
433
434<TR>
435<TD VAlign=top>
436   <tt>const_reverse_iterator rbegin() const</tt>
437</TD>
438<TD VAlign=top>
439   <A
440   href="http://www.sgi.com/tech/stl/ReversibleContainer.html">Reversible
441   Container</A>
442</TD>
443<TD VAlign=top>
444   Returns a <tt>const_reverse_iterator</tt> pointing to the beginning
445   of the reversed <tt>sparsetable</tt>.
446</TD>
447</TR>
448
449<TR>
450<TD VAlign=top>
451   <tt>const_reverse_iterator rend() const</tt>
452</TD>
453<TD VAlign=top>
454   <A
455   href="http://www.sgi.com/tech/stl/ReversibleContainer.html">Reversible
456   Container</A>
457</TD>
458<TD VAlign=top>
459   Returns a <tt>const_reverse_iterator</tt> pointing to the end of
460   the reversed <tt>sparsetable</tt>.
461</TD>
462</TR>
463
464<TR>
465<TD VAlign=top>
466   <tt>nonempty_iterator nonempty_begin()</tt>
467</TD>
468<TD VAlign=top>
469   <tt>sparsetable</tt>
470</TD>
471<TD VAlign=top>
472   Returns a <tt>nonempty_iterator</tt> pointing to the first
473   <A HREF="#assigned">assigned</A> element of the
474   <tt>sparsetable</tt>.
475</TD>
476</TR>
477
478<TR>
479<TD VAlign=top>
480   <tt>nonempty_iterator nonempty_end()</tt>
481</TD>
482<TD VAlign=top>
483   <tt>sparsetable</tt>
484</TD>
485<TD VAlign=top>
486   Returns a <tt>nonempty_iterator</tt> pointing to the end of the
487   <tt>sparsetable</tt>.
488</TD>
489</TR>
490
491<TR>
492<TD VAlign=top>
493   <tt>const_nonempty_iterator nonempty_begin() const</tt>
494</TD>
495<TD VAlign=top>
496   <tt>sparsetable</tt>
497</TD>
498<TD VAlign=top>
499   Returns a <tt>const_nonempty_iterator</tt> pointing to the first
500   <A HREF="#assigned">assigned</A> element of the
501   <tt>sparsetable</tt>.
502</TD>
503</TR>
504
505<TR>
506<TD VAlign=top>
507   <tt>const_nonempty_iterator nonempty_end() const</tt>
508</TD>
509<TD VAlign=top>
510   <tt>sparsetable</tt>
511</TD>
512<TD VAlign=top>
513   Returns a <tt>const_nonempty_iterator</tt> pointing to the end of
514   the <tt>sparsetable</tt>.
515</TD>
516</TR>
517
518<TR>
519<TD VAlign=top>
520   <tt>reverse_nonempty_iterator nonempty_rbegin()</tt>
521</TD>
522<TD VAlign=top>
523   <tt>sparsetable</tt>
524</TD>
525<TD VAlign=top>
526   Returns a <tt>reverse_nonempty_iterator</tt> pointing to the first
527   <A HREF="#assigned">assigned</A> element of the reversed
528   <tt>sparsetable</tt>.
529</TD>
530</TR>
531
532<TR>
533<TD VAlign=top>
534   <tt>reverse_nonempty_iterator nonempty_rend()</tt>
535</TD>
536<TD VAlign=top>
537   <tt>sparsetable</tt>
538</TD>
539<TD VAlign=top>
540   Returns a <tt>reverse_nonempty_iterator</tt> pointing to the end of
541   the reversed <tt>sparsetable</tt>.
542</TD>
543</TR>
544
545<TR>
546<TD VAlign=top>
547   <tt>const_reverse_nonempty_iterator nonempty_rbegin() const</tt>
548</TD>
549<TD VAlign=top>
550   <tt>sparsetable</tt>
551</TD>
552<TD VAlign=top>
553   Returns a <tt>const_reverse_nonempty_iterator</tt> pointing to the
554   first <A HREF="#assigned">assigned</A> element of the reversed
555   <tt>sparsetable</tt>.
556</TD>
557</TR>
558
559<TR>
560<TD VAlign=top>
561   <tt>const_reverse_nonempty_iterator nonempty_rend() const</tt>
562</TD>
563<TD VAlign=top>
564   <tt>sparsetable</tt>
565</TD>
566<TD VAlign=top>
567   Returns a <tt>const_reverse_nonempty_iterator</tt> pointing to the
568   end of the reversed <tt>sparsetable</tt>.
569</TD>
570</TR>
571
572<TR>
573<TD VAlign=top>
574   <tt>destructive_iterator destructive_begin()</tt>
575</TD>
576<TD VAlign=top>
577   <tt>sparsetable</tt>
578</TD>
579<TD VAlign=top>
580   Returns a <tt>destructive_iterator</tt> pointing to the first
581   <A HREF="#assigned">assigned</A> element of the
582   <tt>sparsetable</tt>.
583</TD>
584</TR>
585
586<TR>
587<TD VAlign=top>
588   <tt>destructive_iterator destructive_end()</tt>
589</TD>
590<TD VAlign=top>
591   <tt>sparsetable</tt>
592</TD>
593<TD VAlign=top>
594   Returns a <tt>destructive_iterator</tt> pointing to the end of
595   the <tt>sparsetable</tt>.
596</TD>
597</TR>
598
599<TR>
600<TD VAlign=top>
601   <tt>size_type size() const</tt>
602</TD>
603<TD VAlign=top>
604    <A href="http://www.sgi.com/tech/stl/Container.html">Container</A>
605</TD>
606<TD VAlign=top>
607   Returns the size of the <tt>sparsetable</tt>.
608</TD>
609</TR>
610
611<TR>
612<TD VAlign=top>
613   <tt>size_type max_size() const</tt>
614</TD>
615<TD VAlign=top>
616    <A href="http://www.sgi.com/tech/stl/Container.html">Container</A>
617</TD>
618<TD VAlign=top>
619   Returns the largest possible size of the <tt>sparsetable</tt>.
620</TD>
621</TR>
622
623<TR>
624<TD VAlign=top>
625   <tt>bool empty() const</tt>
626</TD>
627<TD VAlign=top>
628    <A href="http://www.sgi.com/tech/stl/Container.html">Container</A>
629</TD>
630<TD VAlign=top>
631   <tt>true</tt> if the <tt>sparsetable</tt>'s size is <tt>0</tt>.
632</TD>
633</TR>
634
635<TR>
636<TD VAlign=top>
637   <tt>size_type num_nonempty() const</tt>
638</TD>
639<TD VAlign=top>
640   <tt>sparsetable</tt>
641</TD>
642<TD VAlign=top>
643   Returns the number of sparsetable elements that are currently <A
644   HREF="#assigned">assigned</A>.
645</TD>
646</TR>
647
648<TR>
649<TD VAlign=top>
650   <tt>sparsetable(size_type n)</tt>
651</TD>
652<TD VAlign=top>
653    <A href="http://www.sgi.com/tech/stl/Container.html">Container</A>
654</TD>
655<TD VAlign=top>
656   Creates a <tt>sparsetable</tt> with <tt>n</tt> elements.
657</TD>
658</TR>
659
660<TR>
661<TD VAlign=top>
662   <tt>sparsetable(const sparsetable&amp;)</tt>
663</TD>
664<TD VAlign=top>
665    <A href="http://www.sgi.com/tech/stl/Container.html">Container</A>
666</TD>
667<TD VAlign=top>
668   The copy constructor.
669</TD>
670</TR>
671
672<TR>
673<TD VAlign=top>
674   <tt>~sparsetable()</tt>
675</TD>
676<TD VAlign=top>
677    <A href="http://www.sgi.com/tech/stl/Container.html">Container</A>
678</TD>
679<TD VAlign=top>
680   The destructor.
681</TD>
682</TR>
683
684<TR>
685<TD VAlign=top>
686   <tt>sparsetable&amp; operator=(const sparsetable&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 assignment operator
693</TD>
694</TR>
695
696<TR>
697<TD VAlign=top>
698   <tt>void swap(sparsetable&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   Swaps the contents of two sparsetables.
705</TD>
706</TR>
707
708<TR>
709<TD VAlign=top>
710   <tt>reference operator[](size_type n)</tt>
711</TD>
712<TD VAlign=top>
713    <A
714    href="http://www.sgi.com/tech/stl/RandomAccessContainer.html">Random
715    Access Container</A>
716</TD>
717<TD VAlign=top>
718   Returns the <tt>n</tt>'th element.  <A href="#3">[2]</A>
719</TD>
720</TR>
721
722<TR>
723<TD VAlign=top>
724   <tt>const_reference operator[](size_type n) const</tt>
725</TD>
726<TD VAlign=top>
727    <A
728    href="http://www.sgi.com/tech/stl/RandomAccessContainer.html">Random
729    Access Container</A>
730</TD>
731<TD VAlign=top>
732   Returns the <tt>n</tt>'th element.
733</TD>
734</TR>
735
736<TR>
737<TD VAlign=top>
738   <tt>bool test(size_type i) const</tt>
739</TD>
740<TD VAlign=top>
741   <tt>sparsetable</tt>
742</TD>
743<TD VAlign=top>
744   true if the <tt>i</tt>'th element of the <tt>sparsetable</tt> is <A
745   HREF="#assigned">assigned</A>.
746</TD>
747</TR>
748
749<TR>
750<TD VAlign=top>
751   <tt>bool test(iterator pos) const</tt>
752</TD>
753<TD VAlign=top>
754   <tt>sparsetable</tt>
755</TD>
756<TD VAlign=top>
757   true if the <tt>sparsetable</tt> element pointed to by <tt>pos</tt>
758   is <A HREF="#assigned">assigned</A>.
759</TD>
760</TR>
761
762<TR>
763<TD VAlign=top>
764   <tt>bool test(const_iterator pos) const</tt>
765</TD>
766<TD VAlign=top>
767   <tt>sparsetable</tt>
768</TD>
769<TD VAlign=top>
770   true if the <tt>sparsetable</tt> element pointed to by <tt>pos</tt>
771   is <A HREF="#assigned">assigned</A>.
772</TD>
773</TR>
774
775<TR>
776<TD VAlign=top>
777   <tt>const_reference get(size_type i) const</tt>
778</TD>
779<TD VAlign=top>
780   <tt>sparsetable</tt>
781</TD>
782<TD VAlign=top>
783   returns the <tt>i</tt>'th element of the <tt>sparsetable</tt>.
784</TD>
785</TR>
786
787<TR>
788<TD VAlign=top>
789   <tt>reference set(size_type i, const_reference val)</tt>
790</TD>
791<TD VAlign=top>
792   <tt>sparsetable</tt>
793</TD>
794<TD VAlign=top>
795   Sets the <tt>i</tt>'th element of the <tt>sparsetable</tt> to value
796   <tt>val</tt>.
797</TD>
798</TR>
799
800<TR>
801<TD VAlign=top>
802   <tt>void erase(size_type i)</tt>
803</TD>
804<TD VAlign=top>
805   <tt>sparsetable</tt>
806</TD>
807<TD VAlign=top>
808   Erases the <tt>i</tt>'th element of the <tt>sparsetable</tt>.
809</TD>
810</TR>
811
812<TR>
813<TD VAlign=top>
814   <tt>void erase(iterator pos)</tt>
815</TD>
816<TD VAlign=top>
817   <tt>sparsetable</tt>
818</TD>
819<TD VAlign=top>
820   Erases the element of the <tt>sparsetable</tt> pointed to by
821   <tt>pos</tt>.
822</TD>
823</TR>
824
825<TR>
826<TD VAlign=top>
827   <tt>void erase(iterator first, iterator last)</tt>
828</TD>
829<TD VAlign=top>
830   <tt>sparsetable</tt>
831</TD>
832<TD VAlign=top>
833   Erases the elements of the <tt>sparsetable</tt> in the range
834   <tt>[first, last)</tt>.
835</TD>
836</TR>
837
838<TR>
839<TD VAlign=top>
840   <tt>void clear()</tt>
841</TD>
842<TD VAlign=top>
843   <tt>sparsetable</tt>
844</TD>
845<TD VAlign=top>
846   Erases all of the elements.
847</TD>
848</TR>
849
850<TR>
851<TD VAlign=top>
852   <tt>void resize(size_type n)</tt>
853</TD>
854<TD VAlign=top>
855   <tt>sparsetable</tt>
856</TD>
857<TD VAlign=top>
858   Changes the size of sparsetable to <tt>n</tt>.
859   <A HREF="#1">[1]</A>
860</TD>
861</TR>
862
863<TR>
864<TD VAlign=top>
865   <tt>bool write_metadata(FILE *fp)</tt>
866</TD>
867<TD VAlign=top>
868   <tt>sparsetable</tt>
869</TD>
870<TD VAlign=top>
871   See below.
872</TD>
873</TR>
874
875<TR>
876<TD VAlign=top>
877   <tt>bool read_metadata(FILE *fp)</tt>
878</TD>
879<TD VAlign=top>
880   <tt>sparsetable</tt>
881</TD>
882<TD VAlign=top>
883   See below.
884</TD>
885</TR>
886
887<TR>
888<TD VAlign=top>
889   <tt>bool write_nopointer_data(FILE *fp)</tt>
890</TD>
891<TD VAlign=top>
892   <tt>sparsetable</tt>
893</TD>
894<TD VAlign=top>
895   See below.
896</TD>
897</TR>
898
899<TR>
900<TD VAlign=top>
901   <tt>bool read_nopointer_data(FILE *fp)</tt>
902</TD>
903<TD VAlign=top>
904   <tt>sparsetable</tt>
905</TD>
906<TD VAlign=top>
907   See below.
908</TD>
909</TR>
910
911<TR>
912<TD VAlign=top>
913   <pre>bool operator==(const sparsetable&amp;, const sparsetable&amp;)
914</pre>
915</TD>
916<TD VAlign=top>
917    <A
918    href="http://www.sgi.com/tech/stl/ForwardContainer.html">Forward
919    Container</A>
920</TD>
921<TD VAlign=top>
922   Tests two sparsetables for equality.  This is a global function,
923   not a member function.
924</TD>
925</TR>
926
927<TR>
928<TD VAlign=top>
929   <pre>bool operator&lt;(const sparsetable&amp;, const sparsetable&amp;)
930</pre>
931</TD>
932<TD VAlign=top>
933    <A
934    href="http://www.sgi.com/tech/stl/ForwardContainer.html">Forward
935    Container</A>
936</TD>
937<TD VAlign=top>
938   Lexicographical comparison.  This is a global function,
939   not a member function.
940</TD>
941</TR>
942
943</table>
944
945
946<h3>New members</h3>
947
948These members are not defined in the <A
949href="http://www.sgi.com/tech/stl/RandomAccessContainer.html">Random
950Access Container</A> requirement, but are specific to
951<tt>sparsetable</tt>.
952
953<table border>
954<TR><TH>Member</TH><TH>Description</TH></TR>
955
956<TR>
957<TD VAlign=top>
958   <tt>nonempty_iterator</tt>
959</TD>
960<TD VAlign=top>
961   Iterator used to iterate through the
962   <A HREF="#assigned">assigned</A> elements of the
963   <tt>sparsetable</tt>.
964</TD>
965</TR>
966
967<TR>
968<TD VAlign=top>
969   <tt>const_nonempty_iterator</tt>
970</TD>
971<TD VAlign=top>
972   Const iterator used to iterate through the
973   <A HREF="#assigned">assigned</A> elements of the
974   <tt>sparsetable</tt>.
975</TD>
976</TR>
977
978<TR>
979<TD VAlign=top>
980   <tt>reverse_nonempty_iterator</tt>
981</TD>
982<TD VAlign=top>
983   Iterator used to iterate backwards through the
984   <A HREF="#assigned">assigned</A> elements of the
985   <tt>sparsetable</tt>.
986</TD>
987</TR>
988
989<TR>
990<TD VAlign=top>
991   <tt>const_reverse_nonempty_iterator</tt>
992</TD>
993<TD VAlign=top>
994   Const iterator used to iterate backwards through the
995   <A HREF="#assigned">assigned</A> elements of the
996   <tt>sparsetable</tt>.
997</TD>
998</TR>
999
1000<TR>
1001<TD VAlign=top>
1002   <tt>destructive_iterator</tt>
1003</TD>
1004<TD VAlign=top>
1005   Iterator used to iterate through the
1006   <A HREF="#assigned">assigned</A> elements of the
1007   <tt>sparsetable</tt>, erasing elements as it iterates.
1008   <A href="#2">[2]</A>
1009</TD>
1010</TR>
1011
1012<TR>
1013<TD VAlign=top>
1014   <tt>nonempty_iterator nonempty_begin()</tt>
1015</TD>
1016<TD VAlign=top>
1017   Returns a <tt>nonempty_iterator</tt> pointing to the first
1018   <A HREF="#assigned">assigned</A> element of the
1019   <tt>sparsetable</tt>.
1020</TD>
1021</TR>
1022
1023<TR>
1024<TD VAlign=top>
1025   <tt>nonempty_iterator nonempty_end()</tt>
1026</TD>
1027<TD VAlign=top>
1028   Returns a <tt>nonempty_iterator</tt> pointing to the end of the
1029   <tt>sparsetable</tt>.
1030</TD>
1031</TR>
1032
1033<TR>
1034<TD VAlign=top>
1035   <tt>const_nonempty_iterator nonempty_begin() const</tt>
1036</TD>
1037<TD VAlign=top>
1038   Returns a <tt>const_nonempty_iterator</tt> pointing to the first
1039   <A HREF="#assigned">assigned</A> element of the
1040   <tt>sparsetable</tt>.
1041</TD>
1042</TR>
1043
1044<TR>
1045<TD VAlign=top>
1046   <tt>const_nonempty_iterator nonempty_end() const</tt>
1047</TD>
1048<TD VAlign=top>
1049   Returns a <tt>const_nonempty_iterator</tt> pointing to the end of
1050   the <tt>sparsetable</tt>.
1051</TD>
1052</TR>
1053
1054<TR>
1055<TD VAlign=top>
1056   <tt>reverse_nonempty_iterator nonempty_rbegin()</tt>
1057</TD>
1058<TD VAlign=top>
1059   Returns a <tt>reverse_nonempty_iterator</tt> pointing to the first
1060   <A HREF="#assigned">assigned</A> element of the reversed
1061   <tt>sparsetable</tt>.
1062</TD>
1063</TR>
1064
1065<TR>
1066<TD VAlign=top>
1067   <tt>reverse_nonempty_iterator nonempty_rend()</tt>
1068</TD>
1069<TD VAlign=top>
1070   Returns a <tt>reverse_nonempty_iterator</tt> pointing to the end of
1071   the reversed <tt>sparsetable</tt>.
1072</TD>
1073</TR>
1074
1075<TR>
1076<TD VAlign=top>
1077   <tt>const_reverse_nonempty_iterator nonempty_rbegin() const</tt>
1078</TD>
1079<TD VAlign=top>
1080   Returns a <tt>const_reverse_nonempty_iterator</tt> pointing to the
1081   first <A HREF="#assigned">assigned</A> element of the reversed
1082   <tt>sparsetable</tt>.
1083</TD>
1084</TR>
1085
1086<TR>
1087<TD VAlign=top>
1088   <tt>const_reverse_nonempty_iterator nonempty_rend() const</tt>
1089</TD>
1090<TD VAlign=top>
1091   Returns a <tt>const_reverse_nonempty_iterator</tt> pointing to the
1092   end of the reversed <tt>sparsetable</tt>.
1093</TD>
1094</TR>
1095
1096<TR>
1097<TD VAlign=top>
1098   <tt>destructive_iterator destructive_begin()</tt>
1099</TD>
1100<TD VAlign=top>
1101   Returns a <tt>destructive_iterator</tt> pointing to the first
1102   <A HREF="#assigned">assigned</A> element of the
1103   <tt>sparsetable</tt>.
1104</TD>
1105</TR>
1106
1107<TR>
1108<TD VAlign=top>
1109   <tt>destructive_iterator destructive_end()</tt>
1110</TD>
1111<TD VAlign=top>
1112   Returns a <tt>destructive_iterator</tt> pointing to the end of
1113   the <tt>sparsetable</tt>.
1114</TD>
1115</TR>
1116
1117<TR>
1118<TD VAlign=top>
1119   <tt>size_type num_nonempty() const</tt>
1120</TD>
1121<TD VAlign=top>
1122   Returns the number of sparsetable elements that are currently <A
1123   HREF="#assigned">assigned</A>.
1124</TD>
1125</TR>
1126
1127<TR>
1128<TD VAlign=top>
1129   <tt>bool test(size_type i) const</tt>
1130</TD>
1131<TD VAlign=top>
1132   true if the <tt>i</tt>'th element of the <tt>sparsetable</tt> is <A
1133   HREF="#assigned">assigned</A>.
1134</TD>
1135</TR>
1136
1137<TR>
1138<TD VAlign=top>
1139   <tt>bool test(iterator pos) const</tt>
1140</TD>
1141<TD VAlign=top>
1142   true if the <tt>sparsetable</tt> element pointed to by <tt>pos</tt>
1143   is <A HREF="#assigned">assigned</A>.
1144</TD>
1145</TR>
1146
1147<TR>
1148<TD VAlign=top>
1149   <tt>bool test(const_iterator pos) const</tt>
1150</TD>
1151<TD VAlign=top>
1152   true if the <tt>sparsetable</tt> element pointed to by <tt>pos</tt>
1153   is <A HREF="#assigned">assigned</A>.
1154</TD>
1155</TR>
1156
1157<TR>
1158<TD VAlign=top>
1159   <tt>const_reference get(size_type i) const</tt>
1160</TD>
1161<TD VAlign=top>
1162   returns the <tt>i</tt>'th element of the <tt>sparsetable</tt>.  If
1163   the <tt>i</tt>'th element is <A HREF="#assigned">assigned</A>, the
1164   assigned value is returned, otherwise, the default value
1165   <tt>T()</tt> is returned.
1166</TD>
1167</TR>
1168
1169<TR>
1170<TD VAlign=top>
1171   <tt>reference set(size_type i, const_reference val)</tt>
1172</TD>
1173<TD VAlign=top>
1174   Sets the <tt>i</tt>'th element of the <tt>sparsetable</tt> to value
1175   <tt>val</tt>, and returns a reference to the <tt>i</tt>'th element
1176   of the table.  This operation causes the <tt>i</tt>'th element to
1177   be <A HREF="#assigned">assigned</A>.
1178</TD>
1179</TR>
1180
1181<TR>
1182<TD VAlign=top>
1183   <tt>void erase(size_type i)</tt>
1184</TD>
1185<TD VAlign=top>
1186   Erases the <tt>i</tt>'th element of the <tt>sparsetable</tt>.  This
1187   operation causes the <tt>i</tt>'th element to be <A
1188   HREF="#assigned">unassigned</A>.
1189</TD>
1190</TR>
1191
1192<TR>
1193<TD VAlign=top>
1194   <tt>void erase(iterator pos)</tt>
1195</TD>
1196<TD VAlign=top>
1197   Erases the element of the <tt>sparsetable</tt> pointed to by
1198   <tt>pos</tt>.  This operation causes the <tt>i</tt>'th element to
1199   be <A HREF="#assigned">unassigned</A>.
1200</TD>
1201</TR>
1202
1203<TR>
1204<TD VAlign=top>
1205   <tt>void erase(iterator first, iterator last)</tt>
1206</TD>
1207<TD VAlign=top>
1208   Erases the elements of the <tt>sparsetable</tt> in the range
1209   <tt>[first, last)</tt>.  This operation causes these elements to
1210   be <A HREF="#assigned">unassigned</A>.
1211</TD>
1212</TR>
1213
1214<TR>
1215<TD VAlign=top>
1216   <tt>void clear()</tt>
1217</TD>
1218<TD VAlign=top>
1219   Erases all of the elements.  This causes all elements to be
1220   <A HREF="#assigned">unassigned</A>.
1221</TD>
1222</TR>
1223
1224<TR>
1225<TD VAlign=top>
1226   <tt>void resize(size_type n)</tt>
1227</TD>
1228<TD VAlign=top>
1229   Changes the size of sparsetable to <tt>n</tt>.  If <tt>n</tt> is
1230   greater than the old size, new, <A HREF="#assigned">unassigned</A>
1231   elements are appended.  If <tt>n</tt> is less than the old size,
1232   all elements in position &gt;<tt>n</tt> are deleted.
1233   <A HREF="#1">[1]</A>
1234</TD>
1235</TR>
1236
1237<TR>
1238<TD VAlign=top>
1239   <tt>bool write_metadata(FILE *fp)</tt>
1240</TD>
1241<TD VAlign=top>
1242   Write hashtable metadata to <tt>fp</tt>.  See <A HREF="#io">below</A>.
1243</TD>
1244</TR>
1245
1246<TR>
1247<TD VAlign=top>
1248   <tt>bool read_metadata(FILE *fp)</tt>
1249</TD>
1250<TD VAlign=top>
1251   Read hashtable metadata from <tt>fp</tt>.  See <A HREF="#io">below</A>.
1252</TD>
1253</TR>
1254
1255<TR>
1256<TD VAlign=top>
1257   <tt>bool write_nopointer_data(FILE *fp)</tt>
1258</TD>
1259<TD VAlign=top>
1260   Write hashtable contents to <tt>fp</tt>.  This is valid only if the
1261   hashtable key and value are "plain" data.  See <A HREF="#io">below</A>.
1262</TD>
1263</TR>
1264
1265<TR>
1266<TD VAlign=top>
1267   <tt>bool read_nopointer_data(FILE *fp)</tt>
1268</TD>
1269<TD VAlign=top>
1270   Read hashtable contents to <tt>fp</tt>.  This is valid only if the
1271   hashtable key and value are "plain" data.  See <A HREF="#io">below</A>.
1272</TD>
1273</TR>
1274
1275</table>
1276
1277
1278<h3>Notes</h3>
1279
1280<P><A name="1">[1]</A>
1281
1282<tt>value_type</tt> must be <A
1283HREF="http://c2.com/cgi/wiki?PlainOldData">plain old data</A> (see <A
1284HREF="implementation.html">implementation.html</A> for why this is necessary).
1285In addition, there should be no data structures that point directly
1286into parts of value, including the value itself (for instance, you
1287cannot have a value like <tt>struct {int a = 1, *b = &a}</tt>.  This
1288is because <tt>sparsetable</tt> uses <tt>malloc()</tt> and
1289<tt>free</tt> to allocate space for the key and value, and
1290<tt>memmove()</tt> to reorganize the key and value in memory.</p>
1291
1292<p>Almost all common uses fit this criterion: <tt>value_type</tt> can
1293be a basic C type or an STL type like <tt>string</tt>, for instance.
1294
1295<P><A name="2">[2]</A>
1296
1297<tt>sparsetable::destructive_iterator</tt> iterates through a
1298sparsetable like a normal iterator, but <tt>++it</tt> may delete the
1299element being iterated past.  Obviously, this iterator can only be
1300used once on a given table!  One application of this iterator is to
1301copy data from a sparsetable to some other data structure without
1302using extra memory to store the data in both places during the
1303copy.</p>
1304
1305<P><A name="3">[3]</A>
1306
1307Since <tt>operator[]</tt> might insert a new element into the
1308<tt>sparsetable</tt>, it can't possibly be a <tt>const</tt> member
1309function.  In theory, since it might insert a new element, it should
1310cause the element it refers to to become <A
1311HREF="#assigned">assigned</A>.  However, this is undesirable when
1312<tt>operator[]</tt> is used to examine elements, rather than assign
1313them.   Thus, as an implementation trick, <tt>operator[]</tt> does not
1314really return a <tt>reference</tt>.  Instead it returns an object that
1315behaves almost exactly like a <tt>reference</tt>.  This object,
1316however, delays setting the appropriate sparsetable element to <A
1317HREF="#assigned">assigned</A> to when it is actually assigned to.</p>
1318
1319<p>For a bit more detail: the object returned by <tt>operator[]</tt>
1320is an opaque type which defines <tt>operator=</tt>, <tt>operator
1321reference()</tt>, and <tt>operator&</tt>.  The first operator controls
1322assigning to the value.  The second controls examining the value.  The
1323third controls pointing to the value.</p>
1324
1325<p>All three operators perform exactly as an object of type
1326<tt>reference</tt> would perform.  The only problems that arise is
1327when this object is accessed in situations where C++ cannot do the
1328conversion by default.  By far the most common situation is with
1329variadic functions such as <tt>printf</tt>.  In such situations, you
1330may need to manually cast the object to the right type:</p>
1331<pre>
1332   printf("%d", static_cast&lt;typename table::reference&gt;(table[i]));
1333</pre>
1334
1335
1336<h3><A NAME=io>Input/Output</A></h3>
1337
1338<p>It is possible to save and restore <tt>sparsetable</tt> objects
1339to disk.  Storage takes place in two steps.  The first writes the
1340table metadata.  The second writes the actual data.</p>
1341
1342<p>To write a sparsetable to disk, first call <tt>write_metadata()</tt>
1343on an open file pointer.  This saves the sparsetable information in a
1344byte-order-independent format.  However, currently information written
1345by a 32-bit system cannot be read by a 64-bit system, and vice
1346versa.</p>
1347
1348<p>After the metadata has been written to disk, you must write the
1349actual data stored in the sparsetable to disk.  If the value is
1350"simple" enough, you can do this by calling
1351<tt>write_nopointer_data()</tt>.  "Simple" data is data that can be
1352safely copied to disk via <tt>fwrite()</tt>.  Native C data types fall
1353into this category, as do structs of native C data types.  Pointers
1354and STL objects do not.</p>
1355
1356<p>Note that <tt>write_nopointer_data()</tt> does not do any endian
1357conversion.  Thus, it is only appropriate when you intend to read the
1358data on the same endian architecture as you write the data.</p>
1359
1360<p>If you cannot use <tt>write_nopointer_data()</tt> for any reason,
1361you can write the data yourself by iterating over the
1362<tt>sparsetable</tt> with a <tt>const_nonempty_iterator</tt> and
1363writing the key and data in any manner you wish.</p>
1364
1365<p>To read the hashtable information from disk, first you must create
1366a <tt>sparsetable</tt> object.  Then open a file pointer to point
1367to the saved sparsetable, and call <tt>read_metadata()</tt>.  If you
1368saved the data via <tt>write_nopointer_data()</tt>, you can follow the
1369<tt>read_metadata()</tt> call with a call to
1370<tt>read_nopointer_data()</tt>.  This is all that is needed.</p>
1371
1372<p>If you saved the data through a custom write routine, you must call
1373a custom read routine to read in the data.  To do this, iterate over
1374the <tt>sparsetable</tt> with a <tt>nonempty_iterator</tt>; this
1375operation is sensical because the metadata has already been set up.
1376For each iterator item, you can read the key and value from disk, and
1377set it appropriately.  The code might look like this:</p>
1378<pre>
1379   for (sparsetable&lt;int*&gt;::nonempty_iterator it = t.nonempty_begin();
1380        it != t.nonempty_end(); ++it) {
1381       *it = new int;
1382       fread(*it, sizeof(int), 1, fp);
1383   }
1384</pre>
1385
1386
1387<h3>See also</h3>
1388
1389<p>The following are SGI STL concepts and classes related to
1390<tt>sparsetable</tt>.</p>
1391
1392<A href="http://www.sgi.com/tech/stl/Container.html">Container</A>,
1393<A href="http://www.sgi.com/tech/stl/RandomAccessContainer.html">Random Access Container</A>,
1394<tt><A href="sparse_hash_set.html">sparse_hash_set</A></tt>,
1395<tt><A href="sparse_hash_map.html">sparse_hash_map</A></tt>
1396
1397</BODY>
1398</HTML>
Note: See TracBrowser for help on using the repository browser.