[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 <sparsehash/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 an arbitrary stream (such as a disk file) using the serialize() and unserialize() methods.

Each of these methods takes two arguments: a serializer, which says how to write hashtable items to disk, and a stream, which can be a C++ stream (istream or its subclasses for input, ostream or its subclasses for output), a FILE*, or a user-defined type (as described below).

The serializer is a functor that takes a stream and a single hashtable element (a value_type) and copies the hashtable element to the stream (for serialize()) or fills the hashtable element contents from the stream (for unserialize()), 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 a string hash_set to a FILE*:

struct StringSerializer {
  bool operator()(FILE* fp, const std::string& value) const {
    assert(value.length() <= 255);   // we only support writing small strings
    const unsigned char size = value.length();
    if (fwrite(&size, 1, 1, fp) != 1)
      return false;
    if (fwrite(value.data(), size, 1, fp) != 1)
      return false;
    return true;
  }
  bool operator()(FILE* fp, std::string* value) const {
    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;
    }
    new(value) string(buf, size);
    delete[] buf;
    return true;
  }
};

Here is the functor being used in code (error checking omitted):

   sparse_hash_set<string> myset = CreateSet();
   FILE* fp = fopen("hashtable.data", "w");
   myset.serialize(StringSerializer(), fp);
   fclose(fp);

   sparse_hash_set<string> myset2;
   FILE* fp_in = fopen("hashtable.data", "r");
   myset2.unserialize(StringSerializer(), fp_in);
   fclose(fp_in);
   assert(myset == myset2);

Important note: the code above uses placement-new to instantiate the string. This is required for any non-POD type. The value_type passed in to the unserializer points to garbage memory, so it is not safe to assign to it directly if doing so causes a destructor to be called.

Also 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 operator()'s, one that reads from an istream, and one that writes to an ostream. Likewise if you want to support serializing to a custom class.

If the key is "simple" enough, you can use the pre-supplied functor NopointerSerializer. This copies the hashtable data using the equivalent of a memcpy<>. Native C data types can be serialized this way, as can structs of native C data types. Pointers and STL objects cannot.

Note that NopointerSerializer() 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 wish to serialize to your own stream type, you can do so by creating an object which supports two methods:

   bool Write(const void* data, size_t length);
   bool Read(void* data, size_t length);

Write() writes length bytes of data to a stream (presumably a stream owned by the object), while Read() reads data bytes from the stream into data. Both return true on success or false on error.

To unserialize a hashtable from a stream, you wil typically create a new sparse_hash_set object, then call unserialize() on it. unserialize() destroys the old contents of the object. You must pass in the appropriate ValueSerializer for the data being read in.

Both serialize() and unserialize() return true on success, or false if there was an error streaming the data.

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

NOTE: older versions of sparse_hash_set provided a different API, consisting of read_metadata(), read_nopointer_data(), write_metadata(), write_nopointer_data(). Writing to disk consisted of a call to write_metadata() followed by write_nopointer_data() (if the hash data was POD) or a custom loop over the hashtable buckets to write the data (otherwise). Reading from disk was similar. Prefer the new API for new code.

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.