| <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>dense_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>dense_hash_map<Key, Data, HashFcn, EqualKey, Alloc></H1> |
| |
| <p><tt>dense_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>dense_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>dense_hash_map</tt> by its key is |
| efficient, so <tt>dense_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>dense_hash_map</tt> is distinguished from other hash-map |
| implementations by its speed and by the ability to save |
| and restore contents to disk. On the other hand, this hash-map |
| implementation can use significantly more space than other hash-map |
| implementations, and it also has requirements -- for instance, for a |
| distinguished "empty key" -- that may not be easy for all |
| applications to satisfy.</p> |
| |
| <p>This class is appropriate for applications that need speedy access |
| to relatively small "dictionaries" stored in memory, or for |
| applications that need these dictionaries to be persistent. <A |
| HREF="#io">[implementation note]</A>)</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 <google/dense_hash_map> |
| |
| using google::dense_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() |
| { |
| dense_hash_map<const char*, int, hash<const char*>, eqstr> months; |
| |
| months.set_empty_key(NULL); |
| 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="dense_hash_map">dense_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>dense_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>dense_hash_map::data_type</tt>. <A href="#1">[7]</A> |
| </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>dense_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>dense_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. |
| </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>dense_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>dense_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>dense_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>dense_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>dense_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>dense_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>dense_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>dense_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>dense_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>dense_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>dense_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>dense_hash_map</tt>. For |
| <tt>dense_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>dense_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>dense_hash_map</tt>. For |
| <tt>dense_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>dense_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>dense_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>dense_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>dense_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>dense_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>dense_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>dense_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>dense_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>dense_hash_map</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>float min_load_factor() const</tt> |
| </TD> |
| <TD VAlign=top> |
| <tt>dense_hash_map</tt> |
| </TD> |
| <TD VAlign=top> |
| The minimum load factor before decreasing the number of buckets in |
| the <tt>dense_hash_map</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>void min_load_factor(float new_grow)</tt> |
| </TD> |
| <TD VAlign=top> |
| <tt>dense_hash_map</tt> |
| </TD> |
| <TD VAlign=top> |
| Sets the minimum load factor before decreasing the number of |
| buckets in the <tt>dense_hash_map</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>void set_resizing_parameters(float shrink, float grow)</tt> |
| </TD> |
| <TD VAlign=top> |
| <tt>dense_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>dense_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>dense_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>dense_hash_map</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>dense_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>dense_hash_map</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>dense_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>dense_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>dense_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>dense_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>dense_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>dense_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> |
| <pre>template <class <A |
| href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</A>> |
| dense_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 dense_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>> |
| dense_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>> |
| dense_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>> |
| dense_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> |
| <tt>dense_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>dense_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>dense_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>dense_hash_map</tt>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>void set_empty_key(const key_type& key)</tt> <A href="#6">[6]</A> |
| </TD> |
| <TD VAlign=top> |
| <tt>dense_hash_map</tt> |
| </TD> |
| <TD VAlign=top> |
| <A HREF="#new">See below</A>. |
| </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>dense_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>dense_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>void clear_no_resize()</tt> |
| </TD> |
| <TD VAlign=top> |
| <tt>dense_hash_map</tt> |
| </TD> |
| <TD VAlign=top> |
| <A HREF="#new">See below</A>. |
| </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>dense_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>dense_hash_map</tt> |
| </TD> |
| <TD VAlign=top> |
| <A HREF="#new">See below</A>. |
| </TD> |
| </TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>bool read_metadata(FILE *fp)</tt> |
| </TD> |
| <TD VAlign=top> |
| <tt>dense_hash_map</tt> |
| </TD> |
| <TD VAlign=top> |
| <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>dense_hash_map</tt> |
| </TD> |
| <TD VAlign=top> |
| <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>dense_hash_map</tt> |
| </TD> |
| <TD VAlign=top> |
| <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>dense_hash_map</tt>. |
| |
| <table border> |
| <TR><TH>Member</TH><TH>Description</TH></TR> |
| |
| <TR> |
| <TD VAlign=top> |
| <tt>void set_empty_key(const key_type& key)</tt> |
| </TD> |
| <TD VAlign=top> |
| Sets the distinguished "empty" key to <tt>key</tt>. This must be |
| called immediately after construct time, before calls to another |
| other <tt>dense_hash_map</tt> operation. <A href="#6">[6]</A> |
| </TD> |
| </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> |
| <tt>void clear_no_resize()</tt> |
| </TD> |
| <TD VAlign=top> |
| Clears the hashtable like <tt>clear()</tt> does, but does not |
| recover the memory used for hashtable buckets. (The memory |
| used by the <i>items</i> in the hashtable is still recovered.) |
| This can save time for applications that want to reuse a |
| <tt>dense_hash_map</tt> many times, each time with a similar number |
| of objects. |
| </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>dense_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>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>dense_hash_map::iterator</tt> is not a mutable iterator, because |
| <tt>dense_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>dense_hash_map::iterator</tt> |
| and <tt>p</tt> is of type <tt>dense_hash_map::value_type</tt>, then |
| <tt>*i = p</tt> is not a valid expression. However, |
| <tt>dense_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>dense_hash_map::const_iterator</tt>.</p> |
| |
| <P><A name="3">[3]</A> |
| |
| Since <tt>operator[]</tt> might insert a new element into the |
| <tt>dense_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> |
| |
| <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>dense_hash_map</tt> <b>requires</b> you call |
| <tt>set_empty_key()</tt> immediately after constructing the hash-map, |
| and before calling any other <tt>dense_hash_map</tt> method. (This is |
| the largest difference between the <tt>dense_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_empty_key()</tt> should be a key-value that |
| is never used for legitimate hash-map entries. If you have no such |
| key value, you will be unable to use <tt>dense_hash_map</tt>. It is |
| an error to call <tt>insert()</tt> with an item whose key is the |
| "empty key."</p> |
| |
| <tt>dense_hash_map</tt> also requires you call |
| <tt>set_deleted_key()</tt> before calling <tt>erase()</tt>. |
| The argument to <tt>set_deleted_key()</tt> should be a key-value that |
| is never used for legitimate hash-map entries. It must be different |
| from the key-value used for <tt>set_empty_key()</tt>. 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><A name="7">[7]</A> |
| |
| <tt>dense_hash_map</tt> <b>requires</b> that <tt>data_type</tt> has a |
| zero-argument default constructor. This is because |
| <tt>dense_hash_map</tt> uses the special value <tt>pair(empty_key, |
| data_type())</tt> to denote empty 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> |
| |
| |
| <h3><A NAME=io>Input/Output</A></h3> |
| |
| <table border=1 cellpadding=5><tr><td> |
| <p><b>IMPORTANT IMPLEMENTATION NOTE:</b> In the current version of |
| this code, the input/output routines for <tt>dense_hash_map</tt> have |
| <b>not yet been implemented</b>. This section explains the API, but |
| note that all calls to these routines will fail (return |
| <tt>false</tt>). It is a TODO to remedy this situation.</p> |
| </td></tr></table> |
| |
| <p>It is possible to save and restore <tt>dense_hash_map</tt> objects |
| to disk. Storage takes place in two steps. The first writes the |
| hashtable metadata. The second writes the actual data.</p> |
| |
| <p>To write a hashtable to disk, first call <tt>write_metadata()</tt> |
| on an open file pointer. This saves the hashtable 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 hash-map to disk. If both the key and data |
| are "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>dense_hash_map</tt> with a <tt>const_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>dense_hash_map</tt> object. Then open a file pointer to point |
| to the saved hashtable, 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>dense_hash_map</tt> with an <tt>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. You will need to do a <tt>const_cast</tt> on the |
| iterator, since <tt>it->first</tt> is always <tt>const</tt>. You |
| will also need to use placement-new if the key or value is a C++ |
| object. The code might look like this:</p> |
| <pre> |
| for (dense_hash_map<int*, ComplicatedClass>::iterator it = ht.begin(); |
| it != ht.end(); ++it) { |
| // The key is stored in the dense_hash_map as a pointer |
| const_cast<int*>(it->first) = new int; |
| fread(const_cast<int*>(it->first), sizeof(int), 1, fp); |
| // The value is a complicated C++ class that takes an int to construct |
| int ctor_arg; |
| fread(&ctor_arg, sizeof(int), 1, fp); |
| new (&it->second) ComplicatedClass(ctor_arg); // "placement new" |
| } |
| </pre> |
| |
| |
| <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 dense_hash_map, |
| either do so after finishing hashtable inserts, or store the object on |
| the heap and a pointer to it in the dense_hash_map.</p> |
| |
| |
| <h3>See also</h3> |
| |
| <p>The following are SGI STL, and some Google STL, concepts and |
| classes related to <tt>dense_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="sparse_hash_map.html">sparse_hash_map</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> |
| |
| </BODY> |
| </HTML> |