hudson::OrderedHashSet< Item, Hasher > Class Template Reference

#include <OrderedHash.h>

List of all members.

Public Types
typedef iterator	const_iterator
Public Member Functions
	OrderedHashSet ()
iterator	begin () const
iterator	end () const
size_t	size () const
bool	empty () const
const Item &	front () const
iterator	find (const Item &item) const
bool	has (const Item &item) const
pair< iterator, bool >	insert (const Item &item)
template<class item_iterator>
void	insert (item_iterator begin, const item_iterator &end)
bool	erase (const Item &item)
Classes
class	iterator
struct	Node

---

Detailed Description

template<class Item, class Hasher = hashers::hash<Item>>
class hudson::OrderedHashSet< Item, Hasher >

A set that can be iterated over, with constant-time search and erase. This is intended to be a drop-in replacement for hash_set.

We use a hash function for the fast search. The hash function must be good mod powers of two (use jenkin's hash for instance).

The advantage of this class over FastHashSet is that we can iterate. The advantages of this class over hash_set are two:

• Iteration order is independent of hash values (and it thus more stable across platforms and across minor changes in the code)
• hash_set has a stupidly large minimum size, totally inappropriate for small sets. The disadvantage is that the hash function we require can be more expensive than that required by hash_set.

Internally, we use a FastHashSet with entries arranged in a doubly-linked list.

---

Member Typedef Documentation

template<class Item, class Hasher = hashers::hash<Item>> typedef iterator hudson::OrderedHashSet< Item, Hasher >::const_iterator

---

Constructor & Destructor Documentation

template<class Item, class Hasher = hashers::hash<Item>> hudson::OrderedHashSet< Item, Hasher >::OrderedHashSet (   )  [inline]

---

Member Function Documentation

template<class Item, class Hasher = hashers::hash<Item>> iterator hudson::OrderedHashSet< Item, Hasher >::begin (   )  const [inline]

template<class Item, class Hasher = hashers::hash<Item>> bool hudson::OrderedHashSet< Item, Hasher >::empty (   )  const [inline]

template<class Item, class Hasher = hashers::hash<Item>> iterator hudson::OrderedHashSet< Item, Hasher >::end (   )  const [inline]

template<class Item, class Hasher = hashers::hash<Item>> bool hudson::OrderedHashSet< Item, Hasher >::erase (  const Item &  item  )  [inline]

template<class Item, class Hasher = hashers::hash<Item>> iterator hudson::OrderedHashSet< Item, Hasher >::find (  const Item &  item  )  const [inline]

template<class Item, class Hasher = hashers::hash<Item>> const Item& hudson::OrderedHashSet< Item, Hasher >::front (   )  const [inline]

template<class Item, class Hasher = hashers::hash<Item>> bool hudson::OrderedHashSet< Item, Hasher >::has (  const Item &  item  )  const [inline]

template<class Item, class Hasher = hashers::hash<Item>> template<class item_iterator> void hudson::OrderedHashSet< Item, Hasher >::insert (  item_iterator  begin, const item_iterator &  end )  [inline]

template<class Item, class Hasher = hashers::hash<Item>> pair<iterator, bool> hudson::OrderedHashSet< Item, Hasher >::insert (  const Item &  item  )  [inline]

template<class Item, class Hasher = hashers::hash<Item>> size_t hudson::OrderedHashSet< Item, Hasher >::size (   )  const [inline]

---

The documentation for this class was generated from the following file:

• utilities/OrderedHash.h

---