[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.]

dense_hash_map<Key, Data, HashFcn, EqualKey, Alloc>

dense_hash_map is a Hashed Associative Container that associates objects of type Key with objects of type Data. dense_hash_map is a Pair Associative Container, meaning that its value type is pair<const Key, Data>. It is also a Unique Associative Container, meaning that no two elements have keys that compare equal using EqualKey.

Looking up an element in a dense_hash_map by its key is efficient, so dense_hash_map 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 map is more appropriate.

dense_hash_map 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.

This class is appropriate for applications that need speedy access to relatively small "dictionaries" stored in memory, and for applications that need these dictionaries to be persistent. [implementation note])

Example

#include <google/dense_hash_map>

using std::dense_hash_map;      // namespace where class lives by default

struct eqstr
{
  bool operator()(const char* s1, const char* s2) const
  {
    return 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;
}

Definition

Template parameters

Model of

Type requirements

• Key is Assignable.
• EqualKey is a Binary Predicate whose argument type is Key.
• EqualKey is an equivalence relation.
• Alloc is an Allocator.

Public base classes

Members

template <class InputIterator>
dense_hash_map(InputIterator f, InputIterator l) 

template <class InputIterator>
dense_hash_map(InputIterator f, InputIterator l, size_type n) 

template <class InputIterator>
dense_hash_map(InputIterator f, InputIterator l, size_type n, const
hasher& h) 

template <class InputIterator>
dense_hash_map(InputIterator f, InputIterator l, size_type n, const
hasher& h, const key_equal& k) 

pair<iterator, bool> insert(const value_type& x)

template <class InputIterator>
void insert(InputIterator f, InputIterator l) 

pair<const_iterator, const_iterator> equal_range(const
key_type& k) const 

pair<iterator, iterator> equal_range(const
key_type& k) 

data_type& operator[](const key_type& k) [3] 

bool operator==(const hash_map&, const hash_map&)

New members

   data_type& 
   operator[](const key_type& k) [3]

Notes

[1] dense_hash_map::iterator is not a mutable iterator, because dense_hash_map::value_type is not Assignable. That is, if i is of type dense_hash_map::iterator and p is of type dense_hash_map::value_type, then *i = p is not a valid expression. However, dense_hash_map::iterator 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, (*i).second = p is a valid expression.

[2] This member function relies on member template functions, which may not be supported by all compilers. If your compiler supports member templates, you can call this function with any type of input iterator. If your compiler does not yet support member templates, though, then the arguments must either be of type const value_type* or of type dense_hash_map::const_iterator.

[3] Since operator[] might insert a new element into the dense_hash_map, it can't possibly be a const member function. Note that the definition of operator[] is extremely simple: m[k] is equivalent to (*((m.insert(value_type(k, data_type()))).first)).second. Strictly speaking, this member function is unnecessary: it exists only for convenience.

[4] In order to preserve iterators, erasing hashtable elements does not cause a hashtable to resize. This means that after a string of erase() calls, the hashtable will use more space than is required. At a cost of invalidating all current iterators, you can call resize() to manually compact the hashtable. The hashtable promotes too-small resize() arguments to the smallest legal value, so to compact a hashtable, it's sufficient to call resize(0).

[5] Unlike some other hashtable implementations, the optional n in the constructor size 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 close to n.

[6] dense_hash_map requires you call set_empty_key() immediately after constructing the hash-map, and before calling any other dense_hash_map method. (This is the largest difference between the dense_hash_map API and other hash-map APIs. See implementation.html for why this is necessary.) The argument to set_empty_key() 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 dense_hash_map. It is an error to call insert() with an item whose key is the "empty key."

There is no need to call set_deleted_key if you do not wish to call erase() on the hash-map.

It is acceptable to change the deleted-key at any time by calling set_deleted_key() with a new argument. You can also call clear_deleted_key(), at which point all keys become valid for insertion but no hashtable entries can be deleted until set_deleted_key() is called again.

[7] Both key_type and data_type must be plain old data (see implementation.html for why this is necessary). In addition, there should be no data structures that point directly into parts of key or value, including the key or value itself (for instance, you cannot have a value like struct {int a = 1, *b = &a}. This is because dense_hash_map uses malloc() and free() to allocate space for the key and value, and memmove() to reorganize the key and value in memory.

Almost all common uses fit this criterion: key_type can be a basic C type or an STL type like string, for instance. If value_type is complex, consider storing only the pointer to the data in the dense_hash_map. This will speed up the hashtable as well, since hashtable resizes will have to manipulate less memory.

Input/Output

It is possible to save and restore dense_hash_map objects to disk. Storage takes place in two steps. The first writes the hashtable metadata. The second writes the actual data.

To write a hashtable to disk, first call write_metadata() on an open file pointer. This saves the hashtable information in a byte-order-independent format.

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 write_nopointer_data(). "Simple" data is data that can be safely copied to disk via fwrite(). Native C data types fall into this category, as do structs of native C data types. Pointers and STL objects do not.

Note that write_nopointer_data() 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.

If you cannot use write_nopointer_data() for any reason, you can write the data yourself by iterating over the dense_hash_map with a const_iterator and writing the key and data in any manner you wish.

To read the hashtable information from disk, first you must create a dense_hash_map object. Then open a file pointer to point to the saved hashtable, and call read_metadata(). If you saved the data via write_nopointer_data(), you can follow the read_metadata() call with a call to read_nopointer_data(). This is all that is needed.

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 dense_hash_map with an iterator; 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 const_cast on the iterator, since it->first is always const. The code might look like this:

   for (dense_hash_map<int*, int>::iterator it = ht.begin();
        it != ht.end(); ++it) {
       const_cast<int*>(it->first) = new int;
       fread(const_cast<int*>(it->first), sizeof(int), 1, fp);
       fread(&it->second, sizeof(int), 1, fp);
   }

Validity of Iterators

insert() invalidates all iterators, as does resize(). erase() is guaranteed not to invalidate any iterators.

This is implemented by making erase() not resize the hashtable. If you desire maximum space efficiency, you can call resize(0) after a string of erase() calls, to force the hashtable to resize to the smallest possible size.

See also

The following are SGI STL concepts and classes related to dense_hash_map.