| <HTML> |
| <!-- The API of this class and the documentation -- but not the |
| implementation! -- are based on that for SGI's hash_set class: |
| --> |
| <!-- |
| -- Copyright (c) 1996-1999 |
| -- Silicon Graphics Computer Systems, Inc. |
| -- |
| -- Permission to use, copy, modify, distribute and sell this software |
| -- and its documentation for any purpose is hereby granted without fee, |
| -- provided that the above copyright notice appears in all copies and |
| -- that both that copyright notice and this permission notice appear |
| -- in supporting documentation. Silicon Graphics makes no |
| -- representations about the suitability of this software for any |
| -- purpose. It is provided "as is" without express or implied warranty. |
| -- |
| -- Copyright (c) 1994 |
| -- Hewlett-Packard Company |
| -- |
| -- Permission to use, copy, modify, distribute and sell this software |
| -- and its documentation for any purpose is hereby granted without fee, |
| -- provided that the above copyright notice appears in all copies and |
| -- that both that copyright notice and this permission notice appear |
| -- in supporting documentation. Hewlett-Packard Company makes no |
| -- representations about the suitability of this software for any |
| -- purpose. It is provided "as is" without express or implied warranty. |
| -- |
| --> |
| |
| <HEAD> |
| <Title>sparsetable<T, GROUP_SIZE></Title> |
| </HEAD> |
| |
| <BODY> |
| |
| <p><i>[Note: this document is formatted similarly to the SGI STL |
| implementation documentation pages, and refers to concepts and classes |
| defined there. However, neither this document nor the code it |
| describes is associated with SGI, nor is it necessary to have SGI's |
| STL implementation installed in order to use this class.]</i></p> |
| |
| <H1>sparsetable<T, GROUP_SIZE></H1> |
| |
| <p>A <tt>sparsetable</tt> is a <A |
| href="http://www.sgi.com/tech/stl/RandomAccessContainer.html">Random |
| Access Container</A> that supports constant time random access to |
| elements, and constant time insertion and removal of elements. It |
| implements the "array" or "table" abstract data type. The number of |
| elements in a <tt>sparsetable</tt> is set at constructor time, though |
| you can change it at any time by calling <tt>resize()</tt>.</p> |
| |
| <p><tt>sparsetable</tt> is distinguished from other array |
| implementations, including the default C implementation, in its stingy |
| use of memory -- in particular, unused array elements require only 1 bit |
| of disk space to store, rather than <tt>sizeof(T)</tt> bytes -- and by |
| the ability to save and restore contents to disk. On the other hand, |
| this array implementation, while still efficient, is slower than other |
| array implementations.</p> |
| |
| <A NAME="assigned"> |
| <p>A <tt>sparsetable</tt> distinguishes between table elements that |
| have been <i>assigned</i> and those that are <i>unassigned</i>. |
| Assigned table elements are those that have had a value set via |
| <tt>set()</tt>, <tt>operator()</tt>, assignment via an iterator, and |
| so forth. Unassigned table elements are those that have not had a |
| value set in one of these ways, or that have been explicitly |
| unassigned via a call to <tt>erase()</tt> or <tt>clear()</tt>. Lookup |
| is valid on both assigned and unassigned table elements; for |
| unassigned elements, lookup returns the default value |
| <tt>T()</tt>.</p> |
| </A> |
| |
| <p>This class is appropriate for applications that need to store large |
| arrays in memory, or for applications that need these arrays to be |
| persistent.</p> |
| |
| |
| <h3>Example</h3> |
| |
| <pre> |
| #include <google/sparsetable> |
| |
| using google::sparsetable; // namespace where class lives by default |
| |
| sparsetable<int> t(100); |
| t[5] = 6; |
| cout << "t[5] = " << t[5]; |
| cout << "Default value = " << t[99]; |
| </pre> |
| |
| |
| <h3>Definition</h3> |
| |
| Defined in the header <A href="sparsetable">sparsetable</A>. This |
| class is not part of the C++ standard. |
| |
| |
| <h3>Template parameters</h3> |
| |
| <table border> |
| <TR><TH>Parameter</TH><TH>Description</TH><TH>Default</TH></TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>T</tt> |
| </TD> |
| <TD VAlign=top> |
| The sparsetable's value type: the type of object that is stored in |
| the table. |
| </TD> |
| <TD VAlign=top> |
| |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>GROUP_SIZE</tt> |
| </TD> |
| <TD VAlign=top> |
| The number of elements in each sparsetable group (see <A |
| HREF="implementation.html">the implementation doc</A> for more details |
| on this value). This almost never need be specified; the default |
| template parameter value works well in all situations. |
| </TD> |
| <TD VAlign=top> |
| |
| </TD> |
| </TR> |
| |
| </table> |
| |
| |
| <h3>Model of</h3> |
| |
| <A href="http://www.sgi.com/tech/stl/RandomAccessContainer.html">Random Access Container</A> |
| |
| |
| <h3>Type requirements</h3> |
| |
| None, except for those imposed by the requirements of |
| <A |
| href="http://www.sgi.com/tech/stl/RandomAccessContainer.html">Random |
| Access Container</A> |
| |
| |
| <h3>Public base classes</h3> |
| |
| None. |
| |
| |
| <h3>Members</h3> |
| |
| <table border> |
| <TR><TH>Member</TH><TH>Where defined</TH><TH>Description</TH></TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>value_type</tt> |
| </TD> |
| <TD VAlign=top> |
| <A href="http://www.sgi.com/tech/stl/Container.html">Container</A> |
| </TD> |
| <TD VAlign=top> |
| The type of object, <tt>T</tt>, stored in the table. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>pointer</tt> |
| </TD> |
| <TD VAlign=top> |
| <A href="http://www.sgi.com/tech/stl/Container.html">Container</A> |
| </TD> |
| <TD VAlign=top> |
| Pointer to <tt>T</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>reference</tt> |
| </TD> |
| <TD VAlign=top> |
| <A href="http://www.sgi.com/tech/stl/Container.html">Container</A> |
| </TD> |
| <TD VAlign=top> |
| Reference to <tt>T</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>const_reference</tt> |
| </TD> |
| <TD VAlign=top> |
| <A href="http://www.sgi.com/tech/stl/Container.html">Container</A> |
| </TD> |
| <TD VAlign=top> |
| Const reference to <tt>T</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>size_type</tt> |
| </TD> |
| <TD VAlign=top> |
| <A href="http://www.sgi.com/tech/stl/Container.html">Container</A> |
| </TD> |
| <TD VAlign=top> |
| An unsigned integral type. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>difference_type</tt> |
| </TD> |
| <TD VAlign=top> |
| <A href="http://www.sgi.com/tech/stl/Container.html">Container</A> |
| </TD> |
| <TD VAlign=top> |
| A signed integral type. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>iterator</tt> |
| </TD> |
| <TD VAlign=top> |
| <A href="http://www.sgi.com/tech/stl/Container.html">Container</A> |
| </TD> |
| <TD VAlign=top> |
| Iterator used to iterate through a <tt>sparsetable</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>const_iterator</tt> |
| </TD> |
| <TD VAlign=top> |
| <A href="http://www.sgi.com/tech/stl/Container.html">Container</A> |
| </TD> |
| <TD VAlign=top> |
| Const iterator used to iterate through a <tt>sparsetable</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>reverse_iterator</tt> |
| </TD> |
| <TD VAlign=top> |
| <A |
| href="http://www.sgi.com/tech/stl/ReversibleContainer.html">Reversible |
| Container</A> |
| </TD> |
| <TD VAlign=top> |
| Iterator used to iterate backwards through a <tt>sparsetable</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>const_reverse_iterator</tt> |
| </TD> |
| <TD VAlign=top> |
| <A |
| href="http://www.sgi.com/tech/stl/ReversibleContainer.html">Reversible |
| Container</A> |
| </TD> |
| <TD VAlign=top> |
| Const iterator used to iterate backwards through a |
| <tt>sparsetable</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>nonempty_iterator</tt> |
| </TD> |
| <TD VAlign=top> |
| <tt>sparsetable</tt> |
| </TD> |
| <TD VAlign=top> |
| Iterator used to iterate through the |
| <A HREF="#assigned">assigned</A> elements of the |
| <tt>sparsetable</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>const_nonempty_iterator</tt> |
| </TD> |
| <TD VAlign=top> |
| <tt>sparsetable</tt> |
| </TD> |
| <TD VAlign=top> |
| Const iterator used to iterate through the |
| <A HREF="#assigned">assigned</A> elements of the |
| <tt>sparsetable</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>reverse_nonempty_iterator</tt> |
| </TD> |
| <TD VAlign=top> |
| <tt>sparsetable</tt> |
| </TD> |
| <TD VAlign=top> |
| Iterator used to iterate backwards through the |
| <A HREF="#assigned">assigned</A> elements of the |
| <tt>sparsetable</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>const_reverse_nonempty_iterator</tt> |
| </TD> |
| <TD VAlign=top> |
| <tt>sparsetable</tt> |
| </TD> |
| <TD VAlign=top> |
| Const iterator used to iterate backwards through the |
| <A HREF="#assigned">assigned</A> elements of the |
| <tt>sparsetable</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>destructive_iterator</tt> |
| </TD> |
| <TD VAlign=top> |
| <tt>sparsetable</tt> |
| </TD> |
| <TD VAlign=top> |
| Iterator used to iterate through the |
| <A HREF="#assigned">assigned</A> elements of the |
| <tt>sparsetable</tt>, erasing elements as it iterates. |
| <A href="#1">[1]</A> |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>iterator begin()</tt> |
| </TD> |
| <TD VAlign=top> |
| <A href="http://www.sgi.com/tech/stl/Container.html">Container</A> |
| </TD> |
| <TD VAlign=top> |
| Returns an <tt>iterator</tt> pointing to the beginning of the |
| <tt>sparsetable</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>iterator end()</tt> |
| </TD> |
| <TD VAlign=top> |
| <A href="http://www.sgi.com/tech/stl/Container.html">Container</A> |
| </TD> |
| <TD VAlign=top> |
| Returns an <tt>iterator</tt> pointing to the end of the |
| <tt>sparsetable</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>const_iterator begin() const</tt> |
| </TD> |
| <TD VAlign=top> |
| <A href="http://www.sgi.com/tech/stl/Container.html">Container</A> |
| </TD> |
| <TD VAlign=top> |
| Returns an <tt>const_iterator</tt> pointing to the beginning of the |
| <tt>sparsetable</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>const_iterator end() const</tt> |
| </TD> |
| <TD VAlign=top> |
| <A href="http://www.sgi.com/tech/stl/Container.html">Container</A> |
| </TD> |
| <TD VAlign=top> |
| Returns an <tt>const_iterator</tt> pointing to the end of the |
| <tt>sparsetable</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>reverse_iterator rbegin()</tt> |
| </TD> |
| <TD VAlign=top> |
| <A |
| href="http://www.sgi.com/tech/stl/ReversibleContainer.html">Reversible |
| Container</A> |
| </TD> |
| <TD VAlign=top> |
| Returns a <tt>reverse_iterator</tt> pointing to the beginning of the |
| reversed <tt>sparsetable</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>reverse_iterator rend()</tt> |
| </TD> |
| <TD VAlign=top> |
| <A |
| href="http://www.sgi.com/tech/stl/ReversibleContainer.html">Reversible |
| Container</A> |
| </TD> |
| <TD VAlign=top> |
| Returns a <tt>reverse_iterator</tt> pointing to the end of the |
| reversed <tt>sparsetable</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>const_reverse_iterator rbegin() const</tt> |
| </TD> |
| <TD VAlign=top> |
| <A |
| href="http://www.sgi.com/tech/stl/ReversibleContainer.html">Reversible |
| Container</A> |
| </TD> |
| <TD VAlign=top> |
| Returns a <tt>const_reverse_iterator</tt> pointing to the beginning |
| of the reversed <tt>sparsetable</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>const_reverse_iterator rend() const</tt> |
| </TD> |
| <TD VAlign=top> |
| <A |
| href="http://www.sgi.com/tech/stl/ReversibleContainer.html">Reversible |
| Container</A> |
| </TD> |
| <TD VAlign=top> |
| Returns a <tt>const_reverse_iterator</tt> pointing to the end of |
| the reversed <tt>sparsetable</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>nonempty_iterator nonempty_begin()</tt> |
| </TD> |
| <TD VAlign=top> |
| <tt>sparsetable</tt> |
| </TD> |
| <TD VAlign=top> |
| Returns a <tt>nonempty_iterator</tt> pointing to the first |
| <A HREF="#assigned">assigned</A> element of the |
| <tt>sparsetable</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>nonempty_iterator nonempty_end()</tt> |
| </TD> |
| <TD VAlign=top> |
| <tt>sparsetable</tt> |
| </TD> |
| <TD VAlign=top> |
| Returns a <tt>nonempty_iterator</tt> pointing to the end of the |
| <tt>sparsetable</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>const_nonempty_iterator nonempty_begin() const</tt> |
| </TD> |
| <TD VAlign=top> |
| <tt>sparsetable</tt> |
| </TD> |
| <TD VAlign=top> |
| Returns a <tt>const_nonempty_iterator</tt> pointing to the first |
| <A HREF="#assigned">assigned</A> element of the |
| <tt>sparsetable</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>const_nonempty_iterator nonempty_end() const</tt> |
| </TD> |
| <TD VAlign=top> |
| <tt>sparsetable</tt> |
| </TD> |
| <TD VAlign=top> |
| Returns a <tt>const_nonempty_iterator</tt> pointing to the end of |
| the <tt>sparsetable</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>reverse_nonempty_iterator nonempty_rbegin()</tt> |
| </TD> |
| <TD VAlign=top> |
| <tt>sparsetable</tt> |
| </TD> |
| <TD VAlign=top> |
| Returns a <tt>reverse_nonempty_iterator</tt> pointing to the first |
| <A HREF="#assigned">assigned</A> element of the reversed |
| <tt>sparsetable</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>reverse_nonempty_iterator nonempty_rend()</tt> |
| </TD> |
| <TD VAlign=top> |
| <tt>sparsetable</tt> |
| </TD> |
| <TD VAlign=top> |
| Returns a <tt>reverse_nonempty_iterator</tt> pointing to the end of |
| the reversed <tt>sparsetable</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>const_reverse_nonempty_iterator nonempty_rbegin() const</tt> |
| </TD> |
| <TD VAlign=top> |
| <tt>sparsetable</tt> |
| </TD> |
| <TD VAlign=top> |
| Returns a <tt>const_reverse_nonempty_iterator</tt> pointing to the |
| first <A HREF="#assigned">assigned</A> element of the reversed |
| <tt>sparsetable</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>const_reverse_nonempty_iterator nonempty_rend() const</tt> |
| </TD> |
| <TD VAlign=top> |
| <tt>sparsetable</tt> |
| </TD> |
| <TD VAlign=top> |
| Returns a <tt>const_reverse_nonempty_iterator</tt> pointing to the |
| end of the reversed <tt>sparsetable</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>destructive_iterator destructive_begin()</tt> |
| </TD> |
| <TD VAlign=top> |
| <tt>sparsetable</tt> |
| </TD> |
| <TD VAlign=top> |
| Returns a <tt>destructive_iterator</tt> pointing to the first |
| <A HREF="#assigned">assigned</A> element of the |
| <tt>sparsetable</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>destructive_iterator destructive_end()</tt> |
| </TD> |
| <TD VAlign=top> |
| <tt>sparsetable</tt> |
| </TD> |
| <TD VAlign=top> |
| Returns a <tt>destructive_iterator</tt> pointing to the end of |
| the <tt>sparsetable</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>size_type size() const</tt> |
| </TD> |
| <TD VAlign=top> |
| <A href="http://www.sgi.com/tech/stl/Container.html">Container</A> |
| </TD> |
| <TD VAlign=top> |
| Returns the size of the <tt>sparsetable</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>size_type max_size() const</tt> |
| </TD> |
| <TD VAlign=top> |
| <A href="http://www.sgi.com/tech/stl/Container.html">Container</A> |
| </TD> |
| <TD VAlign=top> |
| Returns the largest possible size of the <tt>sparsetable</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>bool empty() const</tt> |
| </TD> |
| <TD VAlign=top> |
| <A href="http://www.sgi.com/tech/stl/Container.html">Container</A> |
| </TD> |
| <TD VAlign=top> |
| <tt>true</tt> if the <tt>sparsetable</tt>'s size is <tt>0</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>size_type num_nonempty() const</tt> |
| </TD> |
| <TD VAlign=top> |
| <tt>sparsetable</tt> |
| </TD> |
| <TD VAlign=top> |
| Returns the number of sparsetable elements that are currently <A |
| HREF="#assigned">assigned</A>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>sparsetable(size_type n)</tt> |
| </TD> |
| <TD VAlign=top> |
| <A href="http://www.sgi.com/tech/stl/Container.html">Container</A> |
| </TD> |
| <TD VAlign=top> |
| Creates a <tt>sparsetable</tt> with <tt>n</tt> elements. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>sparsetable(const sparsetable&)</tt> |
| </TD> |
| <TD VAlign=top> |
| <A href="http://www.sgi.com/tech/stl/Container.html">Container</A> |
| </TD> |
| <TD VAlign=top> |
| The copy constructor. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>~sparsetable()</tt> |
| </TD> |
| <TD VAlign=top> |
| <A href="http://www.sgi.com/tech/stl/Container.html">Container</A> |
| </TD> |
| <TD VAlign=top> |
| The destructor. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>sparsetable& operator=(const sparsetable&)</tt> |
| </TD> |
| <TD VAlign=top> |
| <A href="http://www.sgi.com/tech/stl/Container.html">Container</A> |
| </TD> |
| <TD VAlign=top> |
| The assignment operator |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>void swap(sparsetable&)</tt> |
| </TD> |
| <TD VAlign=top> |
| <A href="http://www.sgi.com/tech/stl/Container.html">Container</A> |
| </TD> |
| <TD VAlign=top> |
| Swaps the contents of two sparsetables. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>reference operator[](size_type n)</tt> |
| </TD> |
| <TD VAlign=top> |
| <A |
| href="http://www.sgi.com/tech/stl/RandomAccessContainer.html">Random |
| Access Container</A> |
| </TD> |
| <TD VAlign=top> |
| Returns the <tt>n</tt>'th element. <A href="#2">[2]</A> |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>const_reference operator[](size_type n) const</tt> |
| </TD> |
| <TD VAlign=top> |
| <A |
| href="http://www.sgi.com/tech/stl/RandomAccessContainer.html">Random |
| Access Container</A> |
| </TD> |
| <TD VAlign=top> |
| Returns the <tt>n</tt>'th element. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>bool test(size_type i) const</tt> |
| </TD> |
| <TD VAlign=top> |
| <tt>sparsetable</tt> |
| </TD> |
| <TD VAlign=top> |
| true if the <tt>i</tt>'th element of the <tt>sparsetable</tt> is <A |
| HREF="#assigned">assigned</A>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>bool test(iterator pos) const</tt> |
| </TD> |
| <TD VAlign=top> |
| <tt>sparsetable</tt> |
| </TD> |
| <TD VAlign=top> |
| true if the <tt>sparsetable</tt> element pointed to by <tt>pos</tt> |
| is <A HREF="#assigned">assigned</A>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>bool test(const_iterator pos) const</tt> |
| </TD> |
| <TD VAlign=top> |
| <tt>sparsetable</tt> |
| </TD> |
| <TD VAlign=top> |
| true if the <tt>sparsetable</tt> element pointed to by <tt>pos</tt> |
| is <A HREF="#assigned">assigned</A>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>const_reference get(size_type i) const</tt> |
| </TD> |
| <TD VAlign=top> |
| <tt>sparsetable</tt> |
| </TD> |
| <TD VAlign=top> |
| returns the <tt>i</tt>'th element of the <tt>sparsetable</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>reference set(size_type i, const_reference val)</tt> |
| </TD> |
| <TD VAlign=top> |
| <tt>sparsetable</tt> |
| </TD> |
| <TD VAlign=top> |
| Sets the <tt>i</tt>'th element of the <tt>sparsetable</tt> to value |
| <tt>val</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>void erase(size_type i)</tt> |
| </TD> |
| <TD VAlign=top> |
| <tt>sparsetable</tt> |
| </TD> |
| <TD VAlign=top> |
| Erases the <tt>i</tt>'th element of the <tt>sparsetable</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>void erase(iterator pos)</tt> |
| </TD> |
| <TD VAlign=top> |
| <tt>sparsetable</tt> |
| </TD> |
| <TD VAlign=top> |
| Erases the element of the <tt>sparsetable</tt> pointed to by |
| <tt>pos</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>void erase(iterator first, iterator last)</tt> |
| </TD> |
| <TD VAlign=top> |
| <tt>sparsetable</tt> |
| </TD> |
| <TD VAlign=top> |
| Erases the elements of the <tt>sparsetable</tt> in the range |
| <tt>[first, last)</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>void clear()</tt> |
| </TD> |
| <TD VAlign=top> |
| <tt>sparsetable</tt> |
| </TD> |
| <TD VAlign=top> |
| Erases all of the elements. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>void resize(size_type n)</tt> |
| </TD> |
| <TD VAlign=top> |
| <tt>sparsetable</tt> |
| </TD> |
| <TD VAlign=top> |
| Changes the size of sparsetable to <tt>n</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>bool write_metadata(FILE *fp)</tt> |
| </TD> |
| <TD VAlign=top> |
| <tt>sparsetable</tt> |
| </TD> |
| <TD VAlign=top> |
| See below. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>bool read_metadata(FILE *fp)</tt> |
| </TD> |
| <TD VAlign=top> |
| <tt>sparsetable</tt> |
| </TD> |
| <TD VAlign=top> |
| See below. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>bool write_nopointer_data(FILE *fp)</tt> |
| </TD> |
| <TD VAlign=top> |
| <tt>sparsetable</tt> |
| </TD> |
| <TD VAlign=top> |
| See below. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>bool read_nopointer_data(FILE *fp)</tt> |
| </TD> |
| <TD VAlign=top> |
| <tt>sparsetable</tt> |
| </TD> |
| <TD VAlign=top> |
| See below. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <pre>bool operator==(const sparsetable&, const sparsetable&) |
| </pre> |
| </TD> |
| <TD VAlign=top> |
| <A |
| href="http://www.sgi.com/tech/stl/ForwardContainer.html">Forward |
| Container</A> |
| </TD> |
| <TD VAlign=top> |
| Tests two sparsetables for equality. This is a global function, |
| not a member function. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <pre>bool operator<(const sparsetable&, const sparsetable&) |
| </pre> |
| </TD> |
| <TD VAlign=top> |
| <A |
| href="http://www.sgi.com/tech/stl/ForwardContainer.html">Forward |
| Container</A> |
| </TD> |
| <TD VAlign=top> |
| Lexicographical comparison. This is a global function, |
| not a member function. |
| </TD> |
| </TR> |
| |
| </table> |
| |
| |
| <h3>New members</h3> |
| |
| These members are not defined in the <A |
| href="http://www.sgi.com/tech/stl/RandomAccessContainer.html">Random |
| Access Container</A> requirement, but are specific to |
| <tt>sparsetable</tt>. |
| |
| <table border> |
| <TR><TH>Member</TH><TH>Description</TH></TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>nonempty_iterator</tt> |
| </TD> |
| <TD VAlign=top> |
| Iterator used to iterate through the |
| <A HREF="#assigned">assigned</A> elements of the |
| <tt>sparsetable</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>const_nonempty_iterator</tt> |
| </TD> |
| <TD VAlign=top> |
| Const iterator used to iterate through the |
| <A HREF="#assigned">assigned</A> elements of the |
| <tt>sparsetable</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>reverse_nonempty_iterator</tt> |
| </TD> |
| <TD VAlign=top> |
| Iterator used to iterate backwards through the |
| <A HREF="#assigned">assigned</A> elements of the |
| <tt>sparsetable</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>const_reverse_nonempty_iterator</tt> |
| </TD> |
| <TD VAlign=top> |
| Const iterator used to iterate backwards through the |
| <A HREF="#assigned">assigned</A> elements of the |
| <tt>sparsetable</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>destructive_iterator</tt> |
| </TD> |
| <TD VAlign=top> |
| Iterator used to iterate through the |
| <A HREF="#assigned">assigned</A> elements of the |
| <tt>sparsetable</tt>, erasing elements as it iterates. |
| <A href="#1">[1]</A> |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>nonempty_iterator nonempty_begin()</tt> |
| </TD> |
| <TD VAlign=top> |
| Returns a <tt>nonempty_iterator</tt> pointing to the first |
| <A HREF="#assigned">assigned</A> element of the |
| <tt>sparsetable</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>nonempty_iterator nonempty_end()</tt> |
| </TD> |
| <TD VAlign=top> |
| Returns a <tt>nonempty_iterator</tt> pointing to the end of the |
| <tt>sparsetable</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>const_nonempty_iterator nonempty_begin() const</tt> |
| </TD> |
| <TD VAlign=top> |
| Returns a <tt>const_nonempty_iterator</tt> pointing to the first |
| <A HREF="#assigned">assigned</A> element of the |
| <tt>sparsetable</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>const_nonempty_iterator nonempty_end() const</tt> |
| </TD> |
| <TD VAlign=top> |
| Returns a <tt>const_nonempty_iterator</tt> pointing to the end of |
| the <tt>sparsetable</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>reverse_nonempty_iterator nonempty_rbegin()</tt> |
| </TD> |
| <TD VAlign=top> |
| Returns a <tt>reverse_nonempty_iterator</tt> pointing to the first |
| <A HREF="#assigned">assigned</A> element of the reversed |
| <tt>sparsetable</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>reverse_nonempty_iterator nonempty_rend()</tt> |
| </TD> |
| <TD VAlign=top> |
| Returns a <tt>reverse_nonempty_iterator</tt> pointing to the end of |
| the reversed <tt>sparsetable</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>const_reverse_nonempty_iterator nonempty_rbegin() const</tt> |
| </TD> |
| <TD VAlign=top> |
| Returns a <tt>const_reverse_nonempty_iterator</tt> pointing to the |
| first <A HREF="#assigned">assigned</A> element of the reversed |
| <tt>sparsetable</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>const_reverse_nonempty_iterator nonempty_rend() const</tt> |
| </TD> |
| <TD VAlign=top> |
| Returns a <tt>const_reverse_nonempty_iterator</tt> pointing to the |
| end of the reversed <tt>sparsetable</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>destructive_iterator destructive_begin()</tt> |
| </TD> |
| <TD VAlign=top> |
| Returns a <tt>destructive_iterator</tt> pointing to the first |
| <A HREF="#assigned">assigned</A> element of the |
| <tt>sparsetable</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>destructive_iterator destructive_end()</tt> |
| </TD> |
| <TD VAlign=top> |
| Returns a <tt>destructive_iterator</tt> pointing to the end of |
| the <tt>sparsetable</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>size_type num_nonempty() const</tt> |
| </TD> |
| <TD VAlign=top> |
| Returns the number of sparsetable elements that are currently <A |
| HREF="#assigned">assigned</A>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>bool test(size_type i) const</tt> |
| </TD> |
| <TD VAlign=top> |
| true if the <tt>i</tt>'th element of the <tt>sparsetable</tt> is <A |
| HREF="#assigned">assigned</A>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>bool test(iterator pos) const</tt> |
| </TD> |
| <TD VAlign=top> |
| true if the <tt>sparsetable</tt> element pointed to by <tt>pos</tt> |
| is <A HREF="#assigned">assigned</A>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>bool test(const_iterator pos) const</tt> |
| </TD> |
| <TD VAlign=top> |
| true if the <tt>sparsetable</tt> element pointed to by <tt>pos</tt> |
| is <A HREF="#assigned">assigned</A>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>const_reference get(size_type i) const</tt> |
| </TD> |
| <TD VAlign=top> |
| returns the <tt>i</tt>'th element of the <tt>sparsetable</tt>. If |
| the <tt>i</tt>'th element is <A HREF="#assigned">assigned</A>, the |
| assigned value is returned, otherwise, the default value |
| <tt>T()</tt> is returned. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>reference set(size_type i, const_reference val)</tt> |
| </TD> |
| <TD VAlign=top> |
| Sets the <tt>i</tt>'th element of the <tt>sparsetable</tt> to value |
| <tt>val</tt>, and returns a reference to the <tt>i</tt>'th element |
| of the table. This operation causes the <tt>i</tt>'th element to |
| be <A HREF="#assigned">assigned</A>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>void erase(size_type i)</tt> |
| </TD> |
| <TD VAlign=top> |
| Erases the <tt>i</tt>'th element of the <tt>sparsetable</tt>. This |
| operation causes the <tt>i</tt>'th element to be <A |
| HREF="#assigned">unassigned</A>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>void erase(iterator pos)</tt> |
| </TD> |
| <TD VAlign=top> |
| Erases the element of the <tt>sparsetable</tt> pointed to by |
| <tt>pos</tt>. This operation causes the <tt>i</tt>'th element to |
| be <A HREF="#assigned">unassigned</A>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>void erase(iterator first, iterator last)</tt> |
| </TD> |
| <TD VAlign=top> |
| Erases the elements of the <tt>sparsetable</tt> in the range |
| <tt>[first, last)</tt>. This operation causes these elements to |
| be <A HREF="#assigned">unassigned</A>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>void clear()</tt> |
| </TD> |
| <TD VAlign=top> |
| Erases all of the elements. This causes all elements to be |
| <A HREF="#assigned">unassigned</A>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>void resize(size_type n)</tt> |
| </TD> |
| <TD VAlign=top> |
| Changes the size of sparsetable to <tt>n</tt>. If <tt>n</tt> is |
| greater than the old size, new, <A HREF="#assigned">unassigned</A> |
| elements are appended. If <tt>n</tt> is less than the old size, |
| all elements in position ><tt>n</tt> are deleted. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>bool write_metadata(FILE *fp)</tt> |
| </TD> |
| <TD VAlign=top> |
| Write hashtable metadata to <tt>fp</tt>. See <A HREF="#io">below</A>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>bool read_metadata(FILE *fp)</tt> |
| </TD> |
| <TD VAlign=top> |
| Read hashtable metadata from <tt>fp</tt>. See <A HREF="#io">below</A>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>bool write_nopointer_data(FILE *fp)</tt> |
| </TD> |
| <TD VAlign=top> |
| Write hashtable contents to <tt>fp</tt>. This is valid only if the |
| hashtable key and value are "plain" data. See <A HREF="#io">below</A>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>bool read_nopointer_data(FILE *fp)</tt> |
| </TD> |
| <TD VAlign=top> |
| Read hashtable contents to <tt>fp</tt>. This is valid only if the |
| hashtable key and value are "plain" data. See <A HREF="#io">below</A>. |
| </TD> |
| </TR> |
| |
| </table> |
| |
| |
| <h3>Notes</h3> |
| |
| <P><A name="1">[1]</A> |
| |
| <tt>sparsetable::destructive_iterator</tt> iterates through a |
| sparsetable like a normal iterator, but <tt>++it</tt> may delete the |
| element being iterated past. Obviously, this iterator can only be |
| used once on a given table! One application of this iterator is to |
| copy data from a sparsetable to some other data structure without |
| using extra memory to store the data in both places during the |
| copy.</p> |
| |
| <P><A name="2">[2]</A> |
| |
| Since <tt>operator[]</tt> might insert a new element into the |
| <tt>sparsetable</tt>, it can't possibly be a <tt>const</tt> member |
| function. In theory, since it might insert a new element, it should |
| cause the element it refers to to become <A |
| HREF="#assigned">assigned</A>. However, this is undesirable when |
| <tt>operator[]</tt> is used to examine elements, rather than assign |
| them. Thus, as an implementation trick, <tt>operator[]</tt> does not |
| really return a <tt>reference</tt>. Instead it returns an object that |
| behaves almost exactly like a <tt>reference</tt>. This object, |
| however, delays setting the appropriate sparsetable element to <A |
| HREF="#assigned">assigned</A> to when it is actually assigned to.</p> |
| |
| <p>For a bit more detail: the object returned by <tt>operator[]</tt> |
| is an opaque type which defines <tt>operator=</tt>, <tt>operator |
| reference()</tt>, and <tt>operator&</tt>. The first operator controls |
| assigning to the value. The second controls examining the value. The |
| third controls pointing to the value.</p> |
| |
| <p>All three operators perform exactly as an object of type |
| <tt>reference</tt> would perform. The only problems that arise is |
| when this object is accessed in situations where C++ cannot do the |
| conversion by default. By far the most common situation is with |
| variadic functions such as <tt>printf</tt>. In such situations, you |
| may need to manually cast the object to the right type:</p> |
| <pre> |
| printf("%d", static_cast<typename table::reference>(table[i])); |
| </pre> |
| |
| |
| <h3><A NAME=io>Input/Output</A></h3> |
| |
| <p>It is possible to save and restore <tt>sparsetable</tt> objects |
| to disk. Storage takes place in two steps. The first writes the |
| table metadata. The second writes the actual data.</p> |
| |
| <p>To write a sparsetable to disk, first call <tt>write_metadata()</tt> |
| on an open file pointer. This saves the sparsetable information in a |
| byte-order-independent format.</p> |
| |
| <p>After the metadata has been written to disk, you must write the |
| actual data stored in the sparsetable to disk. If the value is |
| "simple" enough, you can do this by calling |
| <tt>write_nopointer_data()</tt>. "Simple" data is data that can be |
| safely copied to disk via <tt>fwrite()</tt>. Native C data types fall |
| into this category, as do structs of native C data types. Pointers |
| and STL objects do not.</p> |
| |
| <p>Note that <tt>write_nopointer_data()</tt> does not do any endian |
| conversion. Thus, it is only appropriate when you intend to read the |
| data on the same endian architecture as you write the data.</p> |
| |
| <p>If you cannot use <tt>write_nopointer_data()</tt> for any reason, |
| you can write the data yourself by iterating over the |
| <tt>sparsetable</tt> with a <tt>const_nonempty_iterator</tt> and |
| writing the key and data in any manner you wish.</p> |
| |
| <p>To read the hashtable information from disk, first you must create |
| a <tt>sparsetable</tt> object. Then open a file pointer to point |
| to the saved sparsetable, and call <tt>read_metadata()</tt>. If you |
| saved the data via <tt>write_nopointer_data()</tt>, you can follow the |
| <tt>read_metadata()</tt> call with a call to |
| <tt>read_nopointer_data()</tt>. This is all that is needed.</p> |
| |
| <p>If you saved the data through a custom write routine, you must call |
| a custom read routine to read in the data. To do this, iterate over |
| the <tt>sparsetable</tt> with a <tt>nonempty_iterator</tt>; this |
| operation is sensical because the metadata has already been set up. |
| For each iterator item, you can read the key and value from disk, and |
| set it appropriately. The code might look like this:</p> |
| <pre> |
| for (sparsetable<int*>::nonempty_iterator it = t.nonempty_begin(); |
| it != t.nonempty_end(); ++it) { |
| *it = new int; |
| fread(*it, sizeof(int), 1, fp); |
| } |
| </pre> |
| |
| <p>Here's another example, where the item stored in the sparsetable is |
| a C++ object with a non-trivial constructor. In this case, you must |
| use "placement new" to construct the object at the correct memory |
| location.</p> |
| <pre> |
| for (sparsetable<ComplicatedCppClass>::nonempty_iterator it = t.nonempty_begin(); |
| it != t.nonempty_end(); ++it) { |
| int constructor_arg; // ComplicatedCppClass takes an int to construct |
| fread(&constructor_arg, sizeof(int), 1, fp); |
| new (&(*it)) ComplicatedCppClass(constructor_arg); // placement new |
| } |
| </pre> |
| |
| |
| <h3>See also</h3> |
| |
| <p>The following are SGI STL concepts and classes related to |
| <tt>sparsetable</tt>.</p> |
| |
| <A href="http://www.sgi.com/tech/stl/Container.html">Container</A>, |
| <A href="http://www.sgi.com/tech/stl/RandomAccessContainer.html">Random Access Container</A>, |
| <tt><A href="sparse_hash_set.html">sparse_hash_set</A></tt>, |
| <tt><A href="sparse_hash_map.html">sparse_hash_map</A></tt> |
| |
| </BODY> |
| </HTML> |