Permalink
Cannot retrieve contributors at this time
Fetching contributors…
Cannot retrieve contributors at this time
| <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 <sparsehash/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. This is also defined as | |
| <tt>dense_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>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>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>dense_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>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> | |
| <tt>dense_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>dense_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>> | |
| 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> | |
| <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, 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>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>template <ValueSerializer, OUTPUT> | |
| bool serialize(ValueSerializer serializer, OUTPUT *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>template <ValueSerializer, INPUT> | |
| bool unserialize(ValueSerializer serializer, INPUT *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>NopointerSerializer</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_metadata(FILE *fp)</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>bool read_metadata(FILE *fp)</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>bool write_nopointer_data(FILE *fp)</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>bool read_nopointer_data(FILE *fp)</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> | |
| <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>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>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> | |
| <p>It is possible to save and restore <tt>dense_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; | |
| } | |
| value->second.assign(buf, size); | |
| delete[] buf; | |
| return true; | |
| } | |
| }; | |
| </pre> | |
| <p>Here is the functor being used in code (error checking omitted):</p> | |
| <pre> | |
| dense_hash_map<string, int> mymap = CreateMap(); | |
| FILE* fp = fopen("hashtable.data", "w"); | |
| mymap.serialize(StringToIntSerializer(), fp); | |
| fclose(fp); | |
| dense_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>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>dense_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>dense_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>. These methods were never implemented | |
| and always did nothing but return <tt>false</tt>. You should | |
| exclusively use the new API for serialization.</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 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> |