[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_set<Key, HashFcn, EqualKey, Alloc>

sparse_hash_set is a Hashed Associative Container that stores objects of type Key. sparse_hash_set is a Simple Associative Container, meaning that its value type, as well as its key type, is key. 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_set by its key is efficient, so sparse_hash_set 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_set is distinguished from other hash-set implementations by its stingy use of memory and by the ability to save and restore contents to disk. On the other hand, this hash-set implementation, while still efficient, is slower than other hash-set 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_set>

using google::sparse_hash_set;      // 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);
  }
};

void lookup(const hash_set<const char*, hash<const char*>, eqstr>& Set,
            const char* word)
{
  sparse_hash_set<const char*, hash<const char*>, eqstr>::const_iterator it
    = Set.find(word);
  cout << word << ": "
       << (it != Set.end() ? "present" : "not present")
       << endl;
}

int main()
{
  sparse_hash_set<const char*, hash<const char*>, eqstr> Set;
  Set.insert("kiwi");
  Set.insert("plum");
  Set.insert("apple");
  Set.insert("mango");
  Set.insert("apricot");
  Set.insert("banana");

  lookup(Set, "mango");
  lookup(Set, "apple");
  lookup(Set, "durian");
}

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

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

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

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

template <class InputIterator>
sparse_hash_set(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<iterator, iterator> equal_range(const
key_type& k) const

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

New members

Notes

[1] 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_set::const_iterator.

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

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

[4] sparse_hash_set requires you call set_deleted_key() before calling erase(). (This is the largest difference between the sparse_hash_set API and other hash-set 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-set 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-set.

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.

Input/Output

It is possible to save and restore sparse_hash_set 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-set 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_set 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_set 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_set 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 is always const. The code might look like this:

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

Here's another example, where the item stored in the hash-set is a C++ object with a non-trivial constructor. In this case, you must use "placement new" to construct the object at the correct memory location.

   for (sparse_hash_set<ComplicatedClass>::iterator it = ht.begin();
        it != ht.end(); ++it) {
       int ctor_arg;  // ComplicatedClass takes an int as its constructor arg
       fread(&ctor_arg, sizeof(int), 1, fp);
       new (const_cast<ComplicatedClass*>(&(*it))) ComplicatedClass(ctor_arg);
   }

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_set, either do so after finishing hashtable inserts, or store the object on the heap and a pointer to it in the sparse_hash_set.

See also

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