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

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

sparse_hash_map is a Hashed Associative Container that associates objects of type Key with objects of type Data. sparse_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 sparse_hash_map by its key is efficient, so sparse_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.

sparse_hash_map is distinguished from other hash-map implementations by its stingy use of memory and by the ability to save and restore contents to disk. On the other hand, this hash-map implementation, while still efficient, is slower than other hash-map implementations, and it also has requirements -- for instance, for a distinguished "deleted key" -- that may not be easy for all applications to satisfy.

This class is appropriate for applications that need to store large "dictionaries" in memory, or for applications that need these dictionaries to be persistent.

Example

#include <iostream>
#include <google/sparse_hash_map>

using google::sparse_hash_map;      // namespace where class lives by default
using std::cout;
using std::endl;
using ext::hash;  // or __gnu_cxx::hash, or maybe tr1::hash, depending on your OS

struct eqstr
{
  bool operator()(const char* s1, const char* s2) const
  {
    return (s1 == s2) || (s1 && s2 && strcmp(s1, s2) == 0);
  }
};

int main()
{
  sparse_hash_map<const char*, int, hash<const char*>, eqstr> months;
  
  months["january"] = 31;
  months["february"] = 28;
  months["march"] = 31;
  months["april"] = 30;
  months["may"] = 31;
  months["june"] = 30;
  months["july"] = 31;
  months["august"] = 31;
  months["september"] = 30;
  months["october"] = 31;
  months["november"] = 30;
  months["december"] = 31;
  
  cout << "september -> " << months["september"] << endl;
  cout << "april     -> " << months["april"] << endl;
  cout << "june      -> " << months["june"] << endl;
  cout << "november  -> " << months["november"] << endl;
}

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>
sparse_hash_map(InputIterator f, InputIterator l) 

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

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

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

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

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] sparse_hash_map::iterator is not a mutable iterator, because sparse_hash_map::value_type is not Assignable. That is, if i is of type sparse_hash_map::iterator and p is of type sparse_hash_map::value_type, then *i = p is not a valid expression. However, sparse_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 sparse_hash_map::const_iterator.

[3] Since operator[] might insert a new element into the sparse_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 calls to the constructor, resize, and rehash 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 n or slightly less.

[6] sparse_hash_map requires you call set_deleted_key() before calling erase(). (This is the largest difference between the sparse_hash_map API and other hash-map APIs. See implementation.html for why this is necessary.) The argument to set_deleted_key() should be a key-value that is never used for legitimate hash-map entries. It is an error to call erase() without first calling set_deleted_key(), and it is also an error to call insert() with an item whose key is the "deleted 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.

Note: If you use set_deleted_key, it is also necessary that data_type has a zero-argument default constructor. This is because sparse_hash_map uses the special value pair(deleted_key, data_type()) to denote deleted buckets, and thus needs to be able to create data_type using a zero-argument constructor.

If your data_type does not have a zero-argument default constructor, there are several workarounds:

• Store a pointer to data_type in the map, instead of data_type directly. This may yield faster code as well, since hashtable-resizes will just have to move pointers around, rather than copying the entire data_type.
• Add a zero-argument default constructor to data_type.
• Subclass data_type and add a zero-argument default constructor to the subclass.

If you do not use set_deleted_key, then there is no requirement that data_type havea zero-argument default constructor.

Input/Output

It is possible to save and restore sparse_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 sparse_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 sparse_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 sparse_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. You will also need to use placement-new if the key or value is a C++ object. The code might look like this:

   for (sparse_hash_map<int*, ComplicatedClass>::iterator it = ht.begin();
        it != ht.end(); ++it) {
       // The key is stored in the sparse_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"
   }

Validity of Iterators

erase() is guaranteed not to invalidate any iterators -- except for any iterators pointing to the item being erased, of course. insert() invalidates all iterators, as does resize().

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.

In addition to invalidating iterators, insert() and resize() invalidate all pointers into the hashtable. If you want to store a pointer to an object held in a sparse_hash_map, either do so after finishing hashtable inserts, or store the object on the heap and a pointer to it in the sparse_hash_map.

See also

The following are SGI STL, and some Google STL, concepts and classes related to sparse_hash_map.