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

dense_hash_set is a Hashed Associative Container that stores objects of type Key. dense_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 dense_hash_set by its key is efficient, so dense_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.

dense_hash_set is distinguished from other hash-set implementations by its speed and by the ability to save and restore contents to disk. On the other hand, this hash-set implementation can use significantly more space than other hash-set 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, or for applications that need these dictionaries to be persistent. [implementation note])

Example

#include <iostream>
#include <google/dense_hash_set>

using google::dense_hash_set;      // namespace where class lives by default
using std::cout;
using std::endl;

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)
{
  dense_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()
{
  dense_hash_set<const char*, hash<const char*>, eqstr> Set;
  Set.set_empty_key(NULL);
  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

Defined in the header dense_hash_set. This class is not part of the C++ standard.

Template parameters

Parameter	Description	Default
`Key`	The hash_set's key and value type. This is also defined as `dense_hash_set::key_type` and `dense_hash_set::value_type`.
`HashFcn`	The hash function used by the hash_set. This is also defined as `dense_hash_set::hasher`. Note: Hashtable performance depends heavliy on the choice of hash function. See the performance page for more information.	`hash<Key>`
`EqualKey`	The hash_set key equality function: a binary predicate that determines whether two keys are equal. This is also defined as `dense_hash_set::key_equal`.	`equal_to<Key>`
`Alloc`	Ignored; this is included only for API-compatibility with SGI's STL implementation.	`alloc`

Model of

Unique Hashed Associative Container, Simple Associative Container

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

None.

Members

Member	Where defined	Description
`value_type`	Container	The type of object, `T`, stored in the hash_set.
`key_type`	Associative Container	The key type associated with `value_type`.
`hasher`	Hashed Associative Container	The `dense_hash_set`'s hash function.
`key_equal`	Hashed Associative Container	Function object that compares keys for equality.
`pointer`	Container	Pointer to `T`.
`reference`	Container	Reference to `T`
`const_reference`	Container	Const reference to `T`
`size_type`	Container	An unsigned integral type.
`difference_type`	Container	A signed integral type.
`iterator`	Container	Iterator used to iterate through a `dense_hash_set`.
`const_iterator`	Container	Const iterator used to iterate through a `dense_hash_set`. (`iterator` and `const_iterator` are the same type.)
`iterator begin() const`	Container	Returns an `iterator` pointing to the beginning of the `dense_hash_set`.
`iterator end() const`	Container	Returns an `iterator` pointing to the end of the `dense_hash_set`.
`size_type size() const`	Container	Returns the size of the `dense_hash_set`.
`size_type max_size() const`	Container	Returns the largest possible size of the `dense_hash_set`.
`bool empty() const`	Container	`true` if the `dense_hash_set`'s size is `0`.
`size_type bucket_count() const`	Hashed Associative Container	Returns the number of buckets used by the `dense_hash_set`.
`size_type max_bucket_count() const`	Hashed Associative Container	Returns the largest possible number of buckets used by the `dense_hash_set`.
`void resize(size_type n)`	Hashed Associative Container	Increases the bucket count to at least `n`. [2]
`hasher hash_funct() const`	Hashed Associative Container	Returns the `hasher` object used by the `dense_hash_set`.
`key_equal key_eq() const`	Hashed Associative Container	Returns the `key_equal` object used by the `dense_hash_set`.
`dense_hash_set()`	Container	Creates an empty `dense_hash_set`.
`dense_hash_set(size_type n)`	Hashed Associative Container	Creates an empty `dense_hash_set` that's optimized for holding up to `n` items. [3]
`dense_hash_set(size_type n, const hasher& h)`	Hashed Associative Container	Creates an empty `dense_hash_set` that's optimized for up to `n` items, using `h` as the hash function.
`dense_hash_set(size_type n, const hasher& h, const key_equal& k)`	Hashed Associative Container	Creates an empty `dense_hash_set` that's optimized for up to `n` items, using `h` as the hash function and `k` as the key equal function.
template <class InputIterator> dense_hash_set(InputIterator f, InputIterator l) [2]	Unique Hashed Associative Container	Creates a dense_hash_set with a copy of a range.
template <class InputIterator> dense_hash_set(InputIterator f, InputIterator l, size_type n) [2]	Unique Hashed Associative Container	Creates a hash_set with a copy of a range that's optimized to hold up to `n` items.
template <class InputIterator> dense_hash_set(InputIterator f, InputIterator l, size_type n, const hasher& h) [2]	Unique Hashed Associative Container	Creates a hash_set with a copy of a range that's optimized to hold up to `n` items, using `h` as the hash function.
template <class InputIterator> dense_hash_set(InputIterator f, InputIterator l, size_type n, const hasher& h, const key_equal& k) [2]	Unique Hashed Associative Container	Creates a hash_set with a copy of a range that's optimized for holding up to `n` items, using `h` as the hash function and `k` as the key equal function.
`dense_hash_set(const hash_set&)`	Container	The copy constructor.
`dense_hash_set& operator=(const hash_set&)`	Container	The assignment operator
`void swap(hash_set&)`	Container	Swaps the contents of two hash_sets.
pair<iterator, bool> insert(const value_type& x)	Unique Associative Container	Inserts `x` into the `dense_hash_set`.
template <class InputIterator> void insert(InputIterator f, InputIterator l) [2]	Unique Associative Container	Inserts a range into the `dense_hash_set`.
`void set_empty_key(const key_type& key)` [4]	`dense_hash_set`	See below.
`void set_deleted_key(const key_type& key)` [4]	`dense_hash_set`	See below.
`void clear_deleted_key()` [4]	`dense_hash_set`	See below.
`void erase(iterator pos)`	Associative Container	Erases the element pointed to by `pos`. [4]
`size_type erase(const key_type& k)`	Associative Container	Erases the element whose key is `k`. [4]
`void erase(iterator first, iterator last)`	Associative Container	Erases all elements in a range. [4]
`void clear()`	Associative Container	Erases all of the elements.
`void clear_no_resize()`	`dense_hash_map`	See below.
`iterator find(const key_type& k) const`	Associative Container	Finds an element whose key is `k`.
`size_type count(const key_type& k) const`	Unique Associative Container	Counts the number of elements whose key is `k`.
pair<iterator, iterator> equal_range(const key_type& k) const	Associative Container	Finds a range containing all elements whose key is `k`.
`bool write_metadata(FILE *fp)`	`dense_hash_set`	See below.
`bool read_metadata(FILE *fp)`	`dense_hash_set`	See below.
`bool write_nopointer_data(FILE *fp)`	`dense_hash_set`	See below.
`bool read_nopointer_data(FILE *fp)`	`dense_hash_set`	See below.
bool operator==(const hash_set&, const hash_set&)	Hashed Associative Container	Tests two hash_sets for equality. This is a global function, not a member function.

New members

These members are not defined in the Unique Hashed Associative Container and Simple Associative Container requirements, but are specific to dense_hash_set.

Member	Description
`void set_empty_key(const key_type& key)`	Sets the distinguished "empty" key to `key`. This must be called immediately after construct time, before calls to another other `dense_hash_set` operation. [4]
`void set_deleted_key(const key_type& key)`	Sets the distinguished "deleted" key to `key`. This must be called before any calls to `erase()`. [4]
`void clear_deleted_key()`	Clears the distinguished "deleted" key. After this is called, calls to `erase()` are not valid on this object. [4]
`void clear_no_resize()`	Clears the hashtable like `clear()` does, but does not recover the memory used for hashtable buckets. (The memory used by the items in the hashtable is still recovered.) This can save time for applications that want to reuse a `dense_hash_set` many times, each time with a similar number of objects.
`bool write_metadata(FILE *fp)`	Write hashtable metadata to `fp`. See below.
`bool read_metadata(FILE *fp)`	Read hashtable metadata from `fp`. See below.
`bool write_nopointer_data(FILE *fp)`	Write hashtable contents to `fp`. This is valid only if the hashtable key and value are "plain" data. See below.
`bool read_nopointer_data(FILE *fp)`	Read hashtable contents to `fp`. This is valid only if the hashtable key and value are "plain" data. See below.

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 dense_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 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-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 close to n.

[4] dense_hash_set requires you call set_empty_key() immediately after constructing the hash-set, and before calling any other dense_hash_set method. (This is the largest difference between the dense_hash_set API and other hash-set 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-set entries. If you have no such key value, you will be unable to use dense_hash_set. It is an error to call insert() with an item whose key is the "empty key."

dense_hash_set also requires you call set_deleted_key() before calling erase(). The argument to set_deleted_key() should be a key-value that is never used for legitimate hash-set entries. It must be different from the key-value used for set_empty_key(). 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

IMPORTANT IMPLEMENTATION NOTE: In the current version of this code, the input/output routines for dense_hash_set have not yet been implemented. This section explains the API, but note that all calls to these routines will fail (return false). It is a TODO to remedy this situation.

It is possible to save and restore dense_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 dense_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 dense_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 dense_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 (dense_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 (dense_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 dense_hash_set, either do so after finishing hashtable inserts, or store the object on the heap and a pointer to it in the dense_hash_set.