<HTML>
<!-- The API of this class and the documentation -- but not the
implementation! -- are based on that for SGI's hash_map class,
augmented with tr1 support.
-->
<!--
-- 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>sparse_hash_map<Key, Data, HashFcn, EqualKey, Alloc></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>sparse_hash_map<Key, Data, HashFcn, EqualKey, Alloc></H1>
<p><tt>sparse_hash_map</tt> is a <A
href="http://www.sgi.com/tech/stl/HashedAssociativeContainer.html">Hashed
Associative Container</A> that associates objects of type <tt>Key</tt>
with objects of type <tt>Data</tt>. <tt>sparse_hash_map</tt> is a <A
href="http://www.sgi.com/tech/stl/PairAssociativeContainer.html">Pair
Associative Container</A>, meaning that its value type is <tt><A
href="pair.html">pair</A><const Key, Data></tt>. It is also a
<A
href="http://www.sgi.com/tech/stl/UniqueAssociativeContainer.html">Unique
Associative Container</A>, meaning that no two elements have keys that
compare equal using <tt>EqualKey</tt>.</p>
<p>Looking up an element in a <tt>sparse_hash_map</tt> by its key is
efficient, so <tt>sparse_hash_map</tt> is useful for "dictionaries"
where the order of elements is irrelevant. If it is important for the
elements to be in a particular order, however, then <tt><A
href="http://www.sgi.com/tech/stl/Map.html">map</A></tt> is more appropriate.</p>
<p><tt>sparse_hash_map</tt> is distinguished from other hash-map
implementations by its stingy use of memory and by the ability to save
and restore contents to disk. On the other hand, this hash-map
implementation, while still efficient, is slower than other hash-map
implementations, and it also has requirements -- for instance, for a
distinguished "deleted key" -- that may not be easy for all
applications to satisfy.</p>
<p>This class is appropriate for applications that need to store
large "dictionaries" in memory, or for applications that need these
dictionaries to be persistent.</p>
<h3>Example</h3>
(Note: this example uses SGI semantics for <code>hash<></code>
-- the kind used by gcc and most Unix compiler suites -- and not
Dinkumware semantics -- the kind used by Microsoft Visual Studio. If
you are using MSVC, this example will not compile as-is: you'll need
to change <code>hash</code> to <code>hash_compare</code>, and you
won't use <code>eqstr</code> at all. See the MSVC documentation for
<code>hash_map</code> and <code>hash_compare</code>, for more
details.)
<pre>
#include <iostream>
#include <sparsehash/sparse_hash_map>
using google::sparse_hash_map; // namespace where class lives by default
using std::cout;
using std::endl;
using ext::hash; // or __gnu_cxx::hash, or maybe tr1::hash, depending on your OS
struct eqstr
{
bool operator()(const char* s1, const char* s2) const
{
return (s1 == s2) || (s1 && s2 && strcmp(s1, s2) == 0);
}
};
int main()
{
sparse_hash_map<const char*, int, hash<const char*>, eqstr> months;
months["january"] = 31;
months["february"] = 28;
months["march"] = 31;
months["april"] = 30;
months["may"] = 31;
months["june"] = 30;
months["july"] = 31;
months["august"] = 31;
months["september"] = 30;
months["october"] = 31;
months["november"] = 30;
months["december"] = 31;
cout << "september -> " << months["september"] << endl;
cout << "april -> " << months["april"] << endl;
cout << "june -> " << months["june"] << endl;
cout << "november -> " << months["november"] << endl;
}
</pre>
<h3>Definition</h3>
Defined in the header <A href="sparse_hash_map">sparse_hash_map</A>.
This class is not part of the C++ standard, though it is mostly
compatible with the tr1 class <code>unordered_map</code>.
<h3>Template parameters</h3>
<table border>
<TR><TH>Parameter</TH><TH>Description</TH><TH>Default</TH></TR>
<TR>
<TD VAlign=top>
<tt>Key</tt>
</TD>
<TD VAlign=top>
The hash_map's key type. This is also defined as
<tt>sparse_hash_map::key_type</tt>.
</TD>
<TD VAlign=top>
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>Data</tt>
</TD>
<TD VAlign=top>
The hash_map's data type. This is also defined as
<tt>sparse_hash_map::data_type</tt>.
</TD>
<TD VAlign=top>
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>HashFcn</tt>
</TD>
<TD VAlign=top>
The <A href="http://www.sgi.com/tech/stl/HashFunction.html">hash function</A> used by the
hash_map. This is also defined as <tt>sparse_hash_map::hasher</tt>.
<br><b>Note:</b> Hashtable performance depends heavily on the choice of
hash function. See <A HREF="performance.html#hashfn">the performance
page</A> for more information.
</TD>
<TD VAlign=top>
<tt><A href="http://www.sgi.com/tech/stl/hash.html">hash</A><Key></tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>EqualKey</tt>
</TD>
<TD VAlign=top>
The hash_map key equality function: a <A
href="http://www.sgi.com/tech/stl/BinaryPredicate.html">binary predicate</A> that determines
whether two keys are equal. This is also defined as
<tt>sparse_hash_map::key_equal</tt>.
</TD>
<TD VAlign=top>
<tt><A href="http://www.sgi.com/tech/stl/equal_to.html">equal_to</A><Key></tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>Alloc</tt>
</TD>
<TD VAlign=top>
The STL allocator to use. By default, uses the provided allocator
<code>libc_allocator_with_realloc</code>, which likely gives better
performance than other STL allocators due to its built-in support
for <code>realloc</code>, which this container takes advantage of.
If you use an allocator other than the default, note that this
container imposes an additional requirement on the STL allocator
type beyond those in [lib.allocator.requirements]: it does not
support allocators that define alternate memory models. That is,
it assumes that <code>pointer</code>, <code>const_pointer</code>,
<code>size_type</code>, and <code>difference_type</code> are just
<code>T*</code>, <code>const T*</code>, <code>size_t</code>, and
<code>ptrdiff_t</code>, respectively. This is also defined as
<tt>sparse_hash_map::allocator_type</tt>.
</TD>
<TD VAlign=top>
</TD>
</TR>
</table>
<h3>Model of</h3>
<A href="http://www.sgi.com/tech/stl/UniqueHashedAssociativeContainer.html">Unique Hashed Associative Container</A>,
<A href="http://www.sgi.com/tech/stl/PairAssociativeContainer.html">Pair Associative Container</A>
<h3>Type requirements</h3>
<UL>
<LI>
<tt>Key</tt> is Assignable.
<LI>
<tt>EqualKey</tt> is a Binary Predicate whose argument type is Key.
<LI>
<tt>EqualKey</tt> is an equivalence relation.
<LI>
<tt>Alloc</tt> is an Allocator.
</UL>
<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>key_type</tt>
</TD>
<TD VAlign=top>
<A
href="http://www.sgi.com/tech/stl/AssociativeContainer.html">Associative
Container</A>
</TD>
<TD VAlign=top>
The <tt>sparse_hash_map</tt>'s key type, <tt>Key</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>data_type</tt>
</TD>
<TD VAlign=top>
<A
href="http://www.sgi.com/tech/stl/PairAssociativeContainer.html">Pair
Associative Container</A>
</TD>
<TD VAlign=top>
The type of object associated with the keys.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>value_type</tt>
</TD>
<TD VAlign=top>
<A
href="http://www.sgi.com/tech/stl/PairAssociativeContainer.html">Pair
Associative Container</A>
</TD>
<TD VAlign=top>
The type of object, <tt>pair<const key_type, data_type></tt>,
stored in the hash_map.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>hasher</tt>
</TD>
<TD VAlign=top>
<A
href="http://www.sgi.com/tech/stl/HashedAssociativeContainer.html">Hashed
Associative Container</A>
</TD>
<TD VAlign=top>
The <tt>sparse_hash_map</tt>'s <A
href="http://www.sgi.com/tech/stl/HashFunction.html">hash
function</A>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>key_equal</tt>
</TD>
<TD VAlign=top>
<A
href="http://www.sgi.com/tech/stl/HashedAssociativeContainer.html">Hashed
Associative Container</A>
</TD>
<TD VAlign=top>
<A href="http://www.sgi.com/tech/stl/functors.html">Function
object</A> that compares keys for equality.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>allocator_type</tt>
</TD>
<TD VAlign=top>
<tt>Unordered Associative Container</tt> (tr1)
</TD>
<TD VAlign=top>
The type of the Allocator given as a template parameter.
</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>sparse_hash_map</tt>. <A
href="#1">[1]</A>
</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>sparse_hash_map</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>local_iterator</tt>
</TD>
<TD VAlign=top>
<tt>Unordered Associative Container</tt> (tr1)
</TD>
<TD VAlign=top>
Iterator used to iterate through a subset of
<tt>sparse_hash_map</tt>. <A href="#1">[1]</A>
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>const_local_iterator</tt>
</TD>
<TD VAlign=top>
<tt>Unordered Associative Container</tt> (tr1)
</TD>
<TD VAlign=top>
Const iterator used to iterate through a subset of
<tt>sparse_hash_map</tt>.
</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>sparse_hash_map</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>sparse_hash_map</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>sparse_hash_map</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>sparse_hash_map</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>local_iterator begin(size_type i)</tt>
</TD>
<TD VAlign=top>
<tt>Unordered Associative Container</tt> (tr1)
</TD>
<TD VAlign=top>
Returns a <tt>local_iterator</tt> pointing to the beginning of bucket
<tt>i</tt> in the <tt>sparse_hash_map</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>local_iterator end(size_type i)</tt>
</TD>
<TD VAlign=top>
<tt>Unordered Associative Container</tt> (tr1)
</TD>
<TD VAlign=top>
Returns a <tt>local_iterator</tt> pointing to the end of bucket
<tt>i</tt> in the <tt>sparse_hash_map</tt>. For
<tt>sparse_hash_map</tt>, each bucket contains either 0 or 1 item.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>const_local_iterator begin(size_type i) const</tt>
</TD>
<TD VAlign=top>
<tt>Unordered Associative Container</tt> (tr1)
</TD>
<TD VAlign=top>
Returns a <tt>const_local_iterator</tt> pointing to the beginning of bucket
<tt>i</tt> in the <tt>sparse_hash_map</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>const_local_iterator end(size_type i) const</tt>
</TD>
<TD VAlign=top>
<tt>Unordered Associative Container</tt> (tr1)
</TD>
<TD VAlign=top>
Returns a <tt>const_local_iterator</tt> pointing to the end of bucket
<tt>i</tt> in the <tt>sparse_hash_map</tt>. For
<tt>sparse_hash_map</tt>, each bucket contains either 0 or 1 item.
</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>sparse_hash_map</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>sparse_hash_map</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>sparse_hash_map</tt>'s size is <tt>0</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>size_type bucket_count() const</tt>
</TD>
<TD VAlign=top>
<A
href="http://www.sgi.com/tech/stl/HashedAssociativeContainer.html">Hashed
Associative Container</A>
</TD>
<TD VAlign=top>
Returns the number of buckets used by the <tt>sparse_hash_map</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>size_type max_bucket_count() const</tt>
</TD>
<TD VAlign=top>
<A
href="http://www.sgi.com/tech/stl/HashedAssociativeContainer.html">Hashed
Associative Container</A>
</TD>
<TD VAlign=top>
Returns the largest possible number of buckets used by the <tt>sparse_hash_map</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>size_type bucket_size(size_type i) const</tt>
</TD>
<TD VAlign=top>
<tt>Unordered Associative Container</tt> (tr1)
</TD>
<TD VAlign=top>
Returns the number of elements in bucket <tt>i</tt>. For
<tt>sparse_hash_map</tt>, this will be either 0 or 1.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>size_type bucket(const key_type& key) const</tt>
</TD>
<TD VAlign=top>
<tt>Unordered Associative Container</tt> (tr1)
</TD>
<TD VAlign=top>
If the key exists in the map, returns the index of the bucket
containing the given key, otherwise, return the bucket the key
would be inserted into.
This value may be passed to <tt>begin(size_type)</tt> and
<tt>end(size_type)</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>float load_factor() const</tt>
</TD>
<TD VAlign=top>
<tt>Unordered Associative Container</tt> (tr1)
</TD>
<TD VAlign=top>
The number of elements in the <tt>sparse_hash_map</tt> divided by
the number of buckets.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>float max_load_factor() const</tt>
</TD>
<TD VAlign=top>
<tt>Unordered Associative Container</tt> (tr1)
</TD>
<TD VAlign=top>
The maximum load factor before increasing the number of buckets in
the <tt>sparse_hash_map</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void max_load_factor(float new_grow)</tt>
</TD>
<TD VAlign=top>
<tt>Unordered Associative Container</tt> (tr1)
</TD>
<TD VAlign=top>
Sets the maximum load factor before increasing the number of
buckets in the <tt>sparse_hash_map</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>float min_load_factor() const</tt>
</TD>
<TD VAlign=top>
<tt>sparse_hash_map</tt>
</TD>
<TD VAlign=top>
The minimum load factor before decreasing the number of buckets in
the <tt>sparse_hash_map</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void min_load_factor(float new_grow)</tt>
</TD>
<TD VAlign=top>
<tt>sparse_hash_map</tt>
</TD>
<TD VAlign=top>
Sets the minimum load factor before decreasing the number of
buckets in the <tt>sparse_hash_map</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void set_resizing_parameters(float shrink, float grow)</tt>
</TD>
<TD VAlign=top>
<tt>sparse_hash_map</tt>
</TD>
<TD VAlign=top>
DEPRECATED. <A HREF="#new">See below</A>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void resize(size_type n)</tt>
</TD>
<TD VAlign=top>
<A
href="http://www.sgi.com/tech/stl/HashedAssociativeContainer.html">Hashed
Associative Container</A>
</TD>
<TD VAlign=top>
Increases the bucket count to hold at least <tt>n</tt> items.
<A href="#4">[4]</A> <A href="#5">[5]</A>
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void rehash(size_type n)</tt>
</TD>
<TD VAlign=top>
<tt>Unordered Associative Container</tt> (tr1)
</TD>
<TD VAlign=top>
Increases the bucket count to hold at least <tt>n</tt> items.
This is identical to <tt>resize</tt>.
<A href="#4">[4]</A> <A href="#5">[5]</A>
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>hasher hash_funct() const</tt>
</TD>
<TD VAlign=top>
<A
href="http://www.sgi.com/tech/stl/HashedAssociativeContainer.html">Hashed
Associative Container</A>
</TD>
<TD VAlign=top>
Returns the <tt>hasher</tt> object used by the <tt>sparse_hash_map</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>hasher hash_function() const</tt>
</TD>
<TD VAlign=top>
<tt>Unordered Associative Container</tt> (tr1)
</TD>
<TD VAlign=top>
Returns the <tt>hasher</tt> object used by the <tt>sparse_hash_map</tt>.
This is idential to <tt>hash_funct</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>key_equal key_eq() const</tt>
</TD>
<TD VAlign=top>
<A
href="http://www.sgi.com/tech/stl/HashedAssociativeContainer.html">Hashed
Associative Container</A>
</TD>
<TD VAlign=top>
Returns the <tt>key_equal</tt> object used by the
<tt>sparse_hash_map</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>allocator_type get_allocator() const</tt>
</TD>
<TD VAlign=top>
<tt>Unordered Associative Container</tt> (tr1)
</TD>
<TD VAlign=top>
Returns the <tt>allocator_type</tt> object used by the
<tt>sparse_hash_map</tt>: either the one passed in to the
constructor, or a default <tt>Alloc</tt> instance.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>sparse_hash_map()</tt>
</TD>
<TD VAlign=top>
<A href="http://www.sgi.com/tech/stl/Container.html">Container</A>
</TD>
<TD VAlign=top>
Creates an empty <tt>sparse_hash_map</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>sparse_hash_map(size_type n)</tt>
</TD>
<TD VAlign=top>
<A
href="http://www.sgi.com/tech/stl/HashedAssociativeContainer.html">Hashed
Associative Container</A>
</TD>
<TD VAlign=top>
Creates an empty <tt>sparse_hash_map</tt> that's optimized for holding
up to <tt>n</tt> items.
<A href="#5">[5]</A>
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>sparse_hash_map(size_type n, const hasher& h)</tt>
</TD>
<TD VAlign=top>
<A
href="http://www.sgi.com/tech/stl/HashedAssociativeContainer.html">Hashed
Associative Container</A>
</TD>
<TD VAlign=top>
Creates an empty <tt>sparse_hash_map</tt> that's optimized for up
to <tt>n</tt> items, using <tt>h</tt> as the hash function.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>sparse_hash_map(size_type n, const hasher& h, const
key_equal& k)</tt>
</TD>
<TD VAlign=top>
<A
href="http://www.sgi.com/tech/stl/HashedAssociativeContainer.html">Hashed
Associative Container</A>
</TD>
<TD VAlign=top>
Creates an empty <tt>sparse_hash_map</tt> that's optimized for up
to <tt>n</tt> items, using <tt>h</tt> as the hash function and
<tt>k</tt> as the key equal function.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>sparse_hash_map(size_type n, const hasher& h, const
key_equal& k, const allocator_type& a)</tt>
</TD>
<TD VAlign=top>
<tt>Unordered Associative Container</tt> (tr1)
</TD>
<TD VAlign=top>
Creates an empty <tt>sparse_hash_map</tt> that's optimized for up
to <tt>n</tt> items, using <tt>h</tt> as the hash function,
<tt>k</tt> as the key equal function, and <tt>a</tt> as the
allocator object.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>template <class <A
href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</A>>
sparse_hash_map(InputIterator f, InputIterator l) </pre>
<A href="#2">[2]</A>
</TD>
<TD VAlign=top>
<A
href="http://www.sgi.com/tech/stl/UniqueHashedAssociativeContainer.html">Unique
Hashed Associative Container</A>
</TD>
<TD VAlign=top>
Creates a sparse_hash_map with a copy of a range.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>template <class <A
href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</A>>
sparse_hash_map(InputIterator f, InputIterator l, size_type n) </pre>
<A href="#2">[2]</A>
</TD>
<TD VAlign=top>
<A
href="http://www.sgi.com/tech/stl/UniqueHashedAssociativeContainer.html">Unique
Hashed Associative Container</A>
</TD>
<TD VAlign=top>
Creates a hash_map with a copy of a range that's optimized to
hold up to <tt>n</tt> items.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>template <class <A
href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</A>>
sparse_hash_map(InputIterator f, InputIterator l, size_type n, const
hasher& h) </pre> <A href="#2">[2]</A>
</TD>
<TD VAlign=top>
<A
href="http://www.sgi.com/tech/stl/UniqueHashedAssociativeContainer.html">Unique
Hashed Associative Container</A>
</TD>
<TD VAlign=top>
Creates a hash_map with a copy of a range that's optimized to hold
up to <tt>n</tt> items, using <tt>h</tt> as the hash function.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>template <class <A
href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</A>>
sparse_hash_map(InputIterator f, InputIterator l, size_type n, const
hasher& h, const key_equal& k) </pre> <A href="#2">[2]</A>
</TD>
<TD VAlign=top>
<A
href="http://www.sgi.com/tech/stl/UniqueHashedAssociativeContainer.html">Unique
Hashed Associative Container</A>
</TD>
<TD VAlign=top>
Creates a hash_map with a copy of a range that's optimized for
holding up to <tt>n</tt> items, using <tt>h</tt> as the hash
function and <tt>k</tt> as the key equal function.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>template <class <A
href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</A>>
sparse_hash_map(InputIterator f, InputIterator l, size_type n, const
hasher& h, const key_equal& k, const allocator_type& a) </pre>
<A href="#2">[2]</A>
</TD>
<TD VAlign=top>
<tt>Unordered Associative Container</tt> (tr1)
</TD>
<TD VAlign=top>
Creates a hash_map with a copy of a range that's optimized for
holding up to <tt>n</tt> items, using <tt>h</tt> as the hash
function, <tt>k</tt> as the key equal function, and <tt>a</tt> as
the allocator object.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>sparse_hash_map(const hash_map&)</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>sparse_hash_map& operator=(const hash_map&)</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(hash_map&)</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 hash_maps.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>pair<iterator, bool> insert(const value_type& x)
</pre>
</TD>
<TD VAlign=top>
<A
href="http://www.sgi.com/tech/stl/UniqueAssociativeContainer.html">Unique
Associative Container</A>
</TD>
<TD VAlign=top>
Inserts <tt>x</tt> into the <tt>sparse_hash_map</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>template <class <A
href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</A>>
void insert(InputIterator f, InputIterator l) </pre> <A href="#2">[2]</A>
</TD>
<TD VAlign=top>
<A
href="http://www.sgi.com/tech/stl/UniqueAssociativeContainer.html">Unique
Associative Container</A>
</TD>
<TD VAlign=top>
Inserts a range into the <tt>sparse_hash_map</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void set_deleted_key(const key_type& key)</tt> <A href="#6">[6]</A>
</TD>
<TD VAlign=top>
<tt>sparse_hash_map</tt>
</TD>
<TD VAlign=top>
<A HREF="#new">See below</A>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void clear_deleted_key()</tt> <A href="#6">[6]</A>
</TD>
<TD VAlign=top>
<tt>sparse_hash_map</tt>
</TD>
<TD VAlign=top>
<A HREF="#new">See below</A>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void erase(iterator pos)</tt>
</TD>
<TD VAlign=top>
<A
href="http://www.sgi.com/tech/stl/AssociativeContainer.html">Associative
Container</A>
</TD>
<TD VAlign=top>
Erases the element pointed to by <tt>pos</tt>.
<A href="#6">[6]</A>
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>size_type erase(const key_type& k)</tt>
</TD>
<TD VAlign=top>
<A
href="http://www.sgi.com/tech/stl/AssociativeContainer.html">Associative
Container</A>
</TD>
<TD VAlign=top>
Erases the element whose key is <tt>k</tt>.
<A href="#6">[6]</A>
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void erase(iterator first, iterator last)</tt>
</TD>
<TD VAlign=top>
<A
href="http://www.sgi.com/tech/stl/AssociativeContainer.html">Associative
Container</A>
</TD>
<TD VAlign=top>
Erases all elements in a range.
<A href="#6">[6]</A>
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void clear()</tt>
</TD>
<TD VAlign=top>
<A
href="http://www.sgi.com/tech/stl/AssociativeContainer.html">Associative
Container</A>
</TD>
<TD VAlign=top>
Erases all of the elements.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>const_iterator find(const key_type& k) const</tt>
</TD>
<TD VAlign=top>
<A
href="http://www.sgi.com/tech/stl/AssociativeContainer.html">Associative
Container</A>
</TD>
<TD VAlign=top>
Finds an element whose key is <tt>k</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>iterator find(const key_type& k)</tt>
</TD>
<TD VAlign=top>
<A
href="http://www.sgi.com/tech/stl/AssociativeContainer.html">Associative
Container</A>
</TD>
<TD VAlign=top>
Finds an element whose key is <tt>k</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>size_type count(const key_type& k) const</tt>
</TD>
<TD VAlign=top>
<A
href="http://www.sgi.com/tech/stl/UniqueAssociativeContainer.html">Unique
Associative Container</A>
</TD>
<TD VAlign=top>
Counts the number of elements whose key is <tt>k</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>pair<const_iterator, const_iterator> equal_range(const
key_type& k) const </pre>
</TD>
<TD VAlign=top>
<A
href="http://www.sgi.com/tech/stl/AssociativeContainer.html">Associative
Container</A>
</TD>
<TD VAlign=top>
Finds a range containing all elements whose key is <tt>k</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>pair<iterator, iterator> equal_range(const
key_type& k) </pre>
</TD>
<TD VAlign=top>
<A
href="http://www.sgi.com/tech/stl/AssociativeContainer.html">Associative
Container</A>
</TD>
<TD VAlign=top>
Finds a range containing all elements whose key is <tt>k</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>data_type& operator[](const key_type& k) <A
href="http://www.sgi.com/tech/stl/#3">[3]</A> </pre>
</TD>
<TD VAlign=top>
<tt>sparse_hash_map</tt>
</TD>
<TD VAlign=top>
<A HREF="#new">See below</A>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>template <ValueSerializer, OUTPUT>
bool serialize(ValueSerializer serializer, OUTPUT *fp)</tt>
</TD>
<TD VAlign=top>
<tt>sparse_hash_map</tt>
</TD>
<TD VAlign=top>
<A HREF="#new">See below</A>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>template <ValueSerializer, INPUT>
bool unserialize(ValueSerializer serializer, INPUT *fp)</tt>
</TD>
<TD VAlign=top>
<tt>sparse_hash_map</tt>
</TD>
<TD VAlign=top>
<A HREF="#new">See below</A>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>NopointerSerializer</tt>
</TD>
<TD VAlign=top>
<tt>sparse_hash_map</tt>
</TD>
<TD VAlign=top>
<A HREF="#new">See below</A>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>bool write_metadata(FILE *fp)</tt>
</TD>
<TD VAlign=top>
<tt>sparse_hash_map</tt>
</TD>
<TD VAlign=top>
DEPRECATED. <A HREF="#new">See below</A>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>bool read_metadata(FILE *fp)</tt>
</TD>
<TD VAlign=top>
<tt>sparse_hash_map</tt>
</TD>
<TD VAlign=top>
DEPRECATED. <A HREF="#new">See below</A>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>bool write_nopointer_data(FILE *fp)</tt>
</TD>
<TD VAlign=top>
<tt>sparse_hash_map</tt>
</TD>
<TD VAlign=top>
DEPRECATED. <A HREF="#new">See below</A>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>bool read_nopointer_data(FILE *fp)</tt>
</TD>
<TD VAlign=top>
<tt>sparse_hash_map</tt>
</TD>
<TD VAlign=top>
DEPRECATED. <A HREF="#new">See below</A>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>bool operator==(const hash_map&, const hash_map&)
</pre>
</TD>
<TD VAlign=top>
<A
href="http://www.sgi.com/tech/stl/HashedAssociativeContainer.html">Hashed
Associative Container</A>
</TD>
<TD VAlign=top>
Tests two hash_maps for equality. This is a global function, not a
member function.
</TD>
</TR>
</table>
<h3><A NAME="new">New members</A></h3>
These members are not defined in the <A
href="http://www.sgi.com/tech/stl/UniqueHashedAssociativeContainer.html">Unique
Hashed Associative Container</A>, <A
href="http://www.sgi.com/tech/stl/PairAssociativeContainer.html">Pair
Associative Container</A>, or tr1's
<tt>Unordered Associative Container</tt> requirements,
but are specific to <tt>sparse_hash_map</tt>.
<table border>
<TR><TH>Member</TH><TH>Description</TH></TR>
<TR>
<TR>
<TD VAlign=top>
<tt>void set_deleted_key(const key_type& key)</tt>
</TD>
<TD VAlign=top>
Sets the distinguished "deleted" key to <tt>key</tt>. This must be
called before any calls to <tt>erase()</tt>. <A href="#6">[6]</A>
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void clear_deleted_key()</tt>
</TD>
<TD VAlign=top>
Clears the distinguished "deleted" key. After this is called,
calls to <tt>erase()</tt> are not valid on this object.
<A href="#6">[6]</A>
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>
data_type&
operator[](const key_type& k) <A
href="http://www.sgi.com/tech/stl/#3">[3]</A>
</pre>
</TD>
<TD VAlign=top>
Returns a reference to the object that is associated with
a particular key. If the <tt>sparse_hash_map</tt> does not already
contain such an object, <tt>operator[]</tt> inserts the default
object <tt>data_type()</tt>. <A
href="http://www.sgi.com/tech/stl/#3">[3]</A>
</TD>
</TR>
<TD VAlign=top>
<tt>void set_resizing_parameters(float shrink, float grow)</tt>
</TD>
<TD VAlign=top>
This function is DEPRECATED. It is equivalent to calling
<tt>min_load_factor(shrink); max_load_factor(grow)</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>template <ValueSerializer, OUTPUT>
bool serialize(ValueSerializer serializer, OUTPUT *fp)</tt>
</TD>
<TD VAlign=top>
Emit a serialization of the hash_map to a stream.
See <A HREF="#io">below</A>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>template <ValueSerializer, INPUT>
bool unserialize(ValueSerializer serializer, INPUT *fp)</tt>
</TD>
<TD VAlign=top>
Read in a serialization of a hash_map from a stream, replacing the
existing hash_map contents with the serialized contents.
See <A HREF="#io">below</A>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>bool write_metadata(FILE *fp)</tt>
</TD>
<TD VAlign=top>
This function is DEPRECATED. See <A HREF="#io">below</A>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>bool read_metadata(FILE *fp)</tt>
</TD>
<TD VAlign=top>
This function is DEPRECATED. See <A HREF="#io">below</A>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>bool write_nopointer_data(FILE *fp)</tt>
</TD>
<TD VAlign=top>
This function is DEPRECATED. See <A HREF="#io">below</A>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>bool read_nopointer_data(FILE *fp)</tt>
</TD>
<TD VAlign=top>
This function is DEPRECATED. See <A HREF="#io">below</A>.
</TD>
</TR>
</table>
<h3>Notes</h3>
<P><A name="1">[1]</A>
<tt>sparse_hash_map::iterator</tt> is not a mutable iterator, because
<tt>sparse_hash_map::value_type</tt> is not <A
href="http://www.sgi.com/tech/stl/Assignable.html">Assignable</A>.
That is, if <tt>i</tt> is of type <tt>sparse_hash_map::iterator</tt>
and <tt>p</tt> is of type <tt>sparse_hash_map::value_type</tt>, then
<tt>*i = p</tt> is not a valid expression. However,
<tt>sparse_hash_map::iterator</tt> isn't a constant iterator either,
because it can be used to modify the object that it points to. Using
the same notation as above, <tt>(*i).second = p</tt> is a valid
expression.</p>
<P><A name="2">[2]</A>
This member function relies on <i>member template</i> functions, which
may not be supported by all compilers. If your compiler supports
member templates, you can call this function with any type of <A
href="http://www.sgi.com/tech/stl/InputIterator.html">input
iterator</A>. If your compiler does not yet support member templates,
though, then the arguments must either be of type <tt>const
value_type*</tt> or of type <tt>sparse_hash_map::const_iterator</tt>.</p>
<P><A name="3">[3]</A>
Since <tt>operator[]</tt> might insert a new element into the
<tt>sparse_hash_map</tt>, it can't possibly be a <tt>const</tt> member
function. Note that the definition of <tt>operator[]</tt> is
extremely simple: <tt>m[k]</tt> is equivalent to
<tt>(*((m.insert(value_type(k, data_type()))).first)).second</tt>.
Strictly speaking, this member function is unnecessary: it exists only
for convenience.</p>
<P><A name="4">[4]</A>
In order to preserve iterators, erasing hashtable elements does not
cause a hashtable to resize. This means that after a string of
<tt>erase()</tt> calls, the hashtable will use more space than is
required. At a cost of invalidating all current iterators, you can
call <tt>resize()</tt> to manually compact the hashtable. The
hashtable promotes too-small <tt>resize()</tt> arguments to the
smallest legal value, so to compact a hashtable, it's sufficient to
call <tt>resize(0)</tt>.
<P><A name="5">[5]</A>
Unlike some other hashtable implementations, the optional <i>n</i> in
the calls to the constructor, <tt>resize</tt>, and <tt>rehash</tt>
indicates not the desired number of buckets that
should be allocated, but instead the expected number of items to be
inserted. The class then sizes the hash-map appropriately for the
number of items specified. It's not an error to actually insert more
or fewer items into the hashtable, but the implementation is most
efficient -- does the fewest hashtable resizes -- if the number of
inserted items is <i>n</i> or slightly less.</p>
<P><A name="6">[6]</A>
<tt>sparse_hash_map</tt> <b>requires</b> you call
<tt>set_deleted_key()</tt> before calling <tt>erase()</tt>. (This is
the largest difference between the <tt>sparse_hash_map</tt> API and
other hash-map APIs. See <A HREF="implementation.html">implementation.html</A>
for why this is necessary.)
The argument to <tt>set_deleted_key()</tt> should be a key-value that
is never used for legitimate hash-map entries. It is an error to call
<tt>erase()</tt> without first calling <tt>set_deleted_key()</tt>, and
it is also an error to call <tt>insert()</tt> with an item whose key
is the "deleted key."</p>
<p>There is no need to call <tt>set_deleted_key</tt> if you do not
wish to call <tt>erase()</tt> on the hash-map.</p>
<p>It is acceptable to change the deleted-key at any time by calling
<tt>set_deleted_key()</tt> with a new argument. You can also call
<tt>clear_deleted_key()</tt>, at which point all keys become valid for
insertion but no hashtable entries can be deleted until
<tt>set_deleted_key()</tt> is called again.</p>
<p><b>Note:</b> If you use <tt>set_deleted_key</tt>, it is also
necessary that <tt>data_type</tt> has a zero-argument default
constructor. This is because <tt>sparse_hash_map</tt> uses the
special value <tt>pair(deleted_key, data_type())</tt> to denote
deleted buckets, and thus needs to be able to create
<tt>data_type</tt> using a zero-argument constructor.</p>
<p>If your <tt>data_type</tt> does not have a zero-argument default
constructor, there are several workarounds:</p>
<ul>
<li> Store a pointer to <tt>data_type</tt> in the map, instead of
<tt>data_type</tt> directly. This may yield faster code as
well, since hashtable-resizes will just have to move pointers
around, rather than copying the entire <tt>data_type</tt>.
<li> Add a zero-argument default constructor to <tt>data_type</tt>.
<li> Subclass <tt>data_type</tt> and add a zero-argument default
constructor to the subclass.
</ul>
<p>If you do not use <tt>set_deleted_key</tt>, then there is no
requirement that <tt>data_type</tt> havea zero-argument default
constructor.
<h3><A NAME=io>Input/Output</A></h3>
<p>It is possible to save and restore <tt>sparse_hash_map</tt> objects
to an arbitrary stream (such as a disk file) using the
<tt>serialize()</tt> and <tt>unserialize()</tt> methods.</p>
<p>Each of these methods takes two arguments: a <i>serializer</i>,
which says how to write hashtable items to disk, and a <i>stream</i>,
which can be a C++ stream (<tt>istream</tt> or its subclasses for
input, <tt>ostream</tt> or its subclasses for output), a
<tt>FILE*</tt>, or a user-defined type (as described below).</p>
<p>The <it>serializer</i> is a functor that takes a stream and a
single hashtable element (a <tt>value_type</tt>, which is a pair of
the key and data) and copies the hashtable element to the stream (for
<tt>serialize()</tt>) or fills the hashtable element contents from the
stream (for <tt>unserialize()</tt>), and returns true on success or
false on error. The copy-in and copy-out functions can be provided in
a single functor. Here is a sample serializer that read/writes a hashtable
element for an int-to-string hash_map to a <tt>FILE*</tt>:</p>
<pre>
struct StringToIntSerializer {
bool operator()(FILE* fp, const std::pair<const int, std::string>& value) const {
// Write the key. We ignore endianness for this example.
if (fwrite(&value.first, sizeof(value.first), 1, fp) != 1)
return false;
// Write the value.
assert(value.second.length() <= 255); // we only support writing small strings
const unsigned char size = value.second.length();
if (fwrite(&size, 1, 1, fp) != 1)
return false;
if (fwrite(value.second.data(), size, 1, fp) != 1)
return false;
return true;
}
bool operator()(FILE* fp, std::pair<const int, std::string>* value) const {
// Read the key. Note the need for const_cast to get around
// the fact hash_map keys are always const.
if (fread(const_cast<int*>(&value->first), sizeof(value->first), 1, fp) != 1)
return false;
// Read the value.
unsigned char size; // all strings are <= 255 chars long
if (fread(&size, 1, 1, fp) != 1)
return false;
char* buf = new char[size];
if (fread(buf, size, 1, fp) != 1) {
delete[] buf;
return false;
}
new(&value->second) string(buf, size);
delete[] buf;
return true;
}
};
</pre>
<p>Here is the functor being used in code (error checking omitted):</p>
<pre>
sparse_hash_map<string, int> mymap = CreateMap();
FILE* fp = fopen("hashtable.data", "w");
mymap.serialize(StringToIntSerializer(), fp);
fclose(fp);
sparse_hash_map<string, int> mymap2;
FILE* fp_in = fopen("hashtable.data", "r");
mymap2.unserialize(StringToIntSerializer(), fp_in);
fclose(fp_in);
assert(mymap == mymap2);
</pre>
<p><b>Important note:</b> the code above uses placement-new to
instantiate the <tt>string</tt>. This is <i>required</i> for any
non-POD type (which is why we didn't need to worry about this to read
in the integer key). The value_type passed in to the unserializer
points to garbage memory, so it is not safe to assign to it directly
if doing so causes a destructor to be called.</p>
<p>Also note that this example serializer can only serialize to a
FILE*. If you want to also be able to use this serializer with C++
streams, you will need to write two more overloads of
<tt>operator()</tt>'s, one that reads from an <tt>istream</tt>, and
one that writes to an <tt>ostream</tt>. Likewise if you want to
support serializing to a custom class.</p>
<p>If both the key and data are "simple" enough, you can use the
pre-supplied functor <tt>NopointerSerializer</tt>. This copies the
hashtable data using the equivalent of a <tt>memcpy<></tt>. Native C
data types can be serialized this way, as can structs of native C data
types. Pointers and STL objects cannot.</p>
<p>Note that <tt>NopointerSerializer()</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 wish to serialize to your own stream type, you can do so by
creating an object which supports two methods:</p>
<pre>
bool Write(const void* data, size_t length);
bool Read(void* data, size_t length);
</pre>
<p><tt>Write()</tt> writes <tt>length</tt> bytes of <tt>data</tt> to a
stream (presumably a stream owned by the object), while
<tt>Read()</tt> reads <tt>data</tt> bytes from the stream into
<tt>data</tt>. Both return true on success or false on error.</p>
<p>To unserialize a hashtable from a stream, you wil typically create
a new <tt>sparse_hash_map</tt> object, then call <tt>unserialize()</tt>
on it. <tt>unserialize()</tt> destroys the old contents of the
object. You must pass in the appropriate <tt>ValueSerializer</tt> for
the data being read in.</p>
<p>Both <tt>serialize()</tt> and <tt>unserialize()</tt> return
<tt>true</tt> on success, or <tt>false</tt> if there was an error
streaming the data.</p>
<p>Note that <tt>serialize()</tt> is not a const method, since it
purges deleted elements before serializing. It is not safe to
serialize from two threads at once, without synchronization.</p>
<p>NOTE: older versions of <tt>sparse_hash_map</tt> provided a
different API, consisting of <tt>read_metadata()</tt>,
<tt>read_nopointer_data()</tt>, <tt>write_metadata()</tt>,
<tt>write_nopointer_data()</tt>. Writing to disk consisted of a call
to <tt>write_metadata()</tt> followed by
<tt>write_nopointer_data()</tt> (if the hash data was POD) or a custom
loop over the hashtable buckets to write the data (otherwise).
Reading from disk was similar. Prefer the new API for new code.</p>
<h3><A NAME=iter>Validity of Iterators</A></h3>
<p><tt>erase()</tt> is guaranteed not to invalidate any iterators --
except for any iterators pointing to the item being erased, of course.
<tt>insert()</tt> invalidates all iterators, as does
<tt>resize()</tt>. </p>
<p>This is implemented by making <tt>erase()</tt> not resize the
hashtable. If you desire maximum space efficiency, you can call
<tt>resize(0)</tt> after a string of <tt>erase()</tt> calls, to force
the hashtable to resize to the smallest possible size.</p>
<p>In addition to invalidating iterators, <tt>insert()</tt>
and <tt>resize()</tt> invalidate all pointers into the hashtable. If
you want to store a pointer to an object held in a sparse_hash_map,
either do so after finishing hashtable inserts, or store the object on
the heap and a pointer to it in the sparse_hash_map.</p>
<h3>See also</h3>
<p>The following are SGI STL, and some Google STL, concepts and
classes related to <tt>sparse_hash_map</tt>.</p>
<tt><A href="http://www.sgi.com/tech/stl/hash_map.html">hash_map</A></tt>,
<A href="http://www.sgi.com/tech/stl/AssociativeContainer.html">Associative Container</A>,
<A href="http://www.sgi.com/tech/stl/HashedAssociativeContainer.html">Hashed Associative Container</A>,
<A href="http://www.sgi.com/tech/stl/PairAssociativeContainer.html">Pair Associative Container</A>,
<A href="http://www.sgi.com/tech/stl/UniqueHashedAssociativeContainer.html">Unique Hashed Associative Container</A>,
<tt><A href="http://www.sgi.com/tech/stl/set.html">set</A></tt>,
<tt><A href="http://www.sgi.com/tech/stl/Map.html">map</A></tt>
<tt><A href="http://www.sgi.com/tech/stl/multiset.html">multiset</A></tt>,
<tt><A href="http://www.sgi.com/tech/stl/Multimap.html">multimap</A></tt>,
<tt><A href="http://www.sgi.com/tech/stl/hash_set.html">hash_set</A></tt>,
<tt><A href="http://www.sgi.com/tech/stl/hash_multiset.html">hash_multiset</A></tt>,
<tt><A href="http://www.sgi.com/tech/stl/hash_multimap.html">hash_multimap</A></tt>,
<tt><A href="sparsetable.html">sparsetable</A></tt>,
<tt><A href="sparse_hash_set.html">sparse_hash_set</A></tt>,
<tt><A href="dense_hash_set.html">dense_hash_set</A></tt>,
<tt><A href="dense_hash_map.html">dense_hash_map</A></tt>
</BODY>
</HTML>