hash_list< Key, Value, Hash > Class Template Reference

A hash_list<Key,Value,Hash> is a list of pair<Key,Value> which can be quickly searched for a given K. Most operations are of fixed cost. Memory consumed is approximately 3 * sizeof(void*) + sizeof(K) + sizeof(V). The primary storage mechanism is a list of Key,Value,bucket_next objects. This gives O(1) insert, erase, iteration, etc. The 'bucket_next' member kept with the Key,Value pair lets us have a fixed time cost to find a given K -- there is a hash table containing all Keys -- this table's buckets thread through the individual objects stored in the linked list. More...

#include <hash_list.h>

Inheritance diagram for hash_list< Key, Value, Hash >:

[legend]

Collaboration diagram for hash_list< Key, Value, Hash >:

[legend]

List of all members.

Classes
struct	index_helper
	When using a non-const hash_list, and invoking the array index operator, [], you get back an index_helper object rather than a reference to the Value object you would expect to be gettting. This is because the behaviour of the array index operation requires that if the object isn't there already that it be inserted. You could insert a 'default' Value object into the container, only to have it deleted if you are writing code like this: More...
struct	value_type
	The objects actually stored in a hash_list are 'value_type' objects. The member, data_, contains the pair<Key,Value> that is the user data provided by an insert operation. More...
Public Types
typedef List::const_iterator	const_iterator
	std STL style const_iterator
typedef List::iterator	iterator
	std STL style iterator
typedef std::list< value_type >	List
	the primary storage representationt ype
typedef std::pair< Key, Value >	mapped_type
	Data you should think about as being in the hash_list. Actually, this is only part of the real 'value_type'.
typedef hash_list< Key, Value, Hash >	self
typedef std::vector< value_type * >	Vector
	the collection of buckets
Public Member Functions
const_iterator	begin () const
	iterator to first element in the list
iterator	begin ()
	iterator to first element in the list
const_iterator	end () const
	iterator to end element of the list
iterator	end ()
	iterator to the end element of the list
void	erase (iterator location)
	Remove one element from the list at the specified location. Used like this:
const_iterator	find (Key const &index) const
iterator	find (Key const &key)
	given a Key value, get an interator to the hash_list::value_type object that contains that key.
	hash_list (int chain_length=10)
iterator	insert (mapped_type const &data)
	Insert a Key/Value pair. When inserting, you must supply a hash_list::mapped_type object. Used like this:
index_helper	operator[] (Key const &index)
	Array index operator. returns a Value given its Key.
Value const &	operator[] (Key const &index) const
	Array index operator. returns a Value given its Key. When the hash_list is const, then this function just returns a const& to either the object in the list or to the empty_value_ object for this hash_list.
size_t	size () const
	number of items in the container
	~hash_list ()
	destructor
Private Member Functions
void	resize ()
Private Attributes
size_t	average_chain_length_
	when size_/ht_.size() > acl, resize vector_
Value	empty_value_
	returned by the const array index operator when no object with a given key is specified
Hash	hash
	function which gives you hashes of the Key
Vector	ht_
	hash buckets
List	list_
	primary storage
size_t	size_
	cache length of list_
Friends
class	index_helper

Detailed Description

template<class Key, class Value, class Hash = Hasher<Key>>
class cxxtls::hash_list< Key, Value, Hash >

A hash_list<Key,Value,Hash> is a list of pair<Key,Value> which can be quickly searched for a given K. Most operations are of fixed cost. Memory consumed is approximately 3 * sizeof(void*) + sizeof(K) + sizeof(V). The primary storage mechanism is a list of Key,Value,bucket_next objects. This gives O(1) insert, erase, iteration, etc. The 'bucket_next' member kept with the Key,Value pair lets us have a fixed time cost to find a given K -- there is a hash table containing all Keys -- this table's buckets thread through the individual objects stored in the linked list.

There can be only element in the container with a given Key value.

The template parameters are as follows:

Key -- an object which is the search key into the list.
Value -- an object which is assumed to be associated with the key.
Hash -- a functor object with a function call operator method which will give an 'int' given a 'Key'. The performance of the container is directly proportional to the uniqueness of the mapping between keys and values. If lots of Keys give the same 'int' value, then performance of this class will be poor. You probably want to user the template found in <Hashs> for built in types, and follow the implementation examples their for your own classes.

Here is an example use:

     struct IntHash  // or use Hasher<int> from file <hashers>
     {
        int operator() (int value ) { return value; }
     };
 
     typedef hash_list<int,string,IntHash> Container;
 
     Container hl;
 
     hl.insert(Container::mapped_data(9, "stuff"));
 
     Container::iterator nine = hl.find(9);
 
     string stuff = nine->second;

Be careful when writing Hash's. It is tempting to write a generic Hash algorithm that simply takes any kind of object and adds up the bytes in it. This won't work because of alignment holes put into the structure by the compiler -- and for other reasons. You should make the Hash's return value be dependent ONLY on the actual usuable fields in a structure -- and it should be written to run very quickly. A Hash's function call operator can not be a static method If you have data in the Hash, remember to make its copy constructor and destructor work correctly.

Here is a trivial example of hashing a string:

/ 
    struct StringHash  // or use Hasher<std::string> from file <hashers>
    {
      int operator() (string s)
      {
        int rv = 0;
 
        string::const_iterator f = s.begin();
        string::const_iterator l = s.end();
 
        while(f != l) rv += *f++;
 
        return ( (rv << 8) | s.size() );
 
      }
    };

Definition at line 47 of file hash_list.h.

Member Typedef Documentation

typedef List::const_iterator const_iterator

std STL style const_iterator

Definition at line 164 of file hash_list.h.

typedef List::iterator iterator

std STL style iterator

Definition at line 163 of file hash_list.h.

typedef std::list<value_type> List

the primary storage representationt ype

Definition at line 160 of file hash_list.h.

typedef std::pair<Key,Value> mapped_type

Data you should think about as being in the hash_list. Actually, this is only part of the real 'value_type'.

Definition at line 131 of file hash_list.h.

typedef hash_list<Key,Value,Hash> self

Definition at line 128 of file hash_list.h.

typedef std::vector<value_type*> Vector

the collection of buckets

Definition at line 161 of file hash_list.h.

Constructor & Destructor Documentation

hash_list ( int chain_length = 10 )

Definition at line 176 of file hash_list.h.

~hash_list ( )

destructor

Definition at line 195 of file hash_list.h.

Member Function Documentation

const_iterator begin ( ) const

iterator to first element in the list

Definition at line 205 of file hash_list.h.

iterator begin ( )

iterator to first element in the list

Definition at line 202 of file hash_list.h.

Here is the caller graph for this function:

const_iterator end ( ) const

iterator to end element of the list

Definition at line 206 of file hash_list.h.

iterator end ( )

iterator to the end element of the list

Definition at line 203 of file hash_list.h.

Here is the caller graph for this function:

void erase ( iterator location )

Remove one element from the list at the specified location. Used like this:

       hash_list<t>::iterator location = hl.find(some_key);
    
       hl.erase(location);

Definition at line 246 of file hash_list.h.

Here is the caller graph for this function:

const_iterator find ( Key const & index ) const

Returns:: an iterator to the entry with the specified key

Parameters:

index

the entry being searched for

Definition at line 347 of file hash_list.h.

iterator find ( Key const & key )

given a Key value, get an interator to the hash_list::value_type object that contains that key.

Definition at line 293 of file hash_list.h.

Here is the caller graph for this function:

iterator insert ( mapped_type const & data )

Insert a Key/Value pair. When inserting, you must supply a hash_list::mapped_type object. Used like this:

      hl->insert( hash_list::mapped_type(key,value) );

Definition at line 208 of file hash_list.h.

Here is the caller graph for this function:

index_helper operator[] ( Key const & index )

Array index operator. returns a Value given its Key.

Definition at line 497 of file hash_list.h.

Value const& operator[] ( Key const & index ) const

Array index operator. returns a Value given its Key. When the hash_list is const, then this function just returns a const& to either the object in the list or to the empty_value_ object for this hash_list.

Returns:: a reference to the desired object

Parameters:

index

the key value of the desired object

Definition at line 358 of file hash_list.h.

void resize ( ) [private]

Increases the size of the hash table to speed up find operations. This recreates the mapping between items in the list and hash buckets to preserver the hashtable logic.

Definition at line 511 of file hash_list.h.

Here is the caller graph for this function:

size_t size ( ) const

number of items in the container

Definition at line 200 of file hash_list.h.

Here is the caller graph for this function:

Friends And Related Function Documentation

friend class index_helper [friend]

Definition at line 494 of file hash_list.h.

Member Data Documentation

size_t average_chain_length_ [private]

when size_/ht_.size() > acl, resize vector_

Definition at line 169 of file hash_list.h.

Value empty_value_ [private]

returned by the const array index operator when no object with a given key is specified

Definition at line 123 of file hash_list.h.

Hash hash [private]

function which gives you hashes of the Key

Definition at line 172 of file hash_list.h.

Vector ht_ [private]

hash buckets

Definition at line 171 of file hash_list.h.

List list_ [private]

primary storage

Definition at line 170 of file hash_list.h.

size_t size_ [private]

cache length of list_

Definition at line 168 of file hash_list.h.

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

include/cxxtls/hash_list.h

hash_list< Key, Value, Hash > Class Template Reference

Classes

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Friends

Detailed Description

template<class Key, class Value, class Hash = Hasher<Key>> class cxxtls::hash_list< Key, Value, Hash >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation

template<class Key, class Value, class Hash = Hasher<Key>>
class cxxtls::hash_list< Key, Value, Hash >