Pair Associative Container with 'ex' objects as keys, that is implemented with a hash table and can be used as a replacement for map<> in many cases. More...

#include <hash_map.h>

Classes
class	exhashmap_iterator
class	value_compare
Public Types
typedef ex	key_type
typedef T	mapped_type
typedef std::pair< key_type, T >	value_type
typedef ex_is_less	key_compare
typedef ex_is_equal	key_equal
typedef value_type &	reference
typedef const value_type &	const_reference
typedef value_type *	pointer
typedef const value_type *	const_pointer
typedef A< Bucket >	allocator_type
typedef exhashmap_iterator < value_type *, value_type &, table_iterator >	iterator
typedef exhashmap_iterator < const value_type *, const value_type &, table_const_iterator >	const_iterator
typedef Table::size_type	size_type
typedef Table::difference_type	difference_type
Public Member Functions
	exhashmap ()
	exhashmap (size_type nbuckets)
template<class InputIterator >
	exhashmap (InputIterator first, InputIterator last)
exhashmap &	operator= (const exhashmap &other)
iterator	begin ()
const_iterator	begin () const
iterator	end ()
const_iterator	end () const
bool	empty () const
size_type	size () const
size_type	max_size () const
size_type	bucket_count () const
T &	operator[] (const key_type &x)
std::pair< iterator, bool >	insert (const value_type &x)
iterator	insert (iterator pos, const value_type &x)
template<class InputIterator >
void	insert (InputIterator first, InputIterator last)
void	erase (iterator position)
size_type	erase (const key_type &x)
void	swap (exhashmap &other)
void	clear ()
key_compare	key_comp () const
value_compare	value_comp () const
iterator	find (const key_type &x)
const_iterator	find (const key_type &x) const
size_type	count (const key_type &x) const
std::pair< iterator, iterator >	equal_range (const key_type &x)
std::pair< const_iterator, const_iterator >	equal_range (const key_type &x) const
Static Public Attributes
static const unsigned	min_num_buckets = 31
Protected Types
enum	bucket_state { EMPTY, USED, ERASED }
typedef std::pair < bucket_state, value_type >	Bucket
typedef std::vector< Bucket, allocator_type >	Table
typedef Table::iterator	table_iterator
typedef Table::const_iterator	table_const_iterator
Protected Member Functions
table_iterator	find_bucket (const key_type &x)
	Return pointer to bucket corresponding to key (or first empty bucket).
table_const_iterator	find_bucket (const key_type &x) const
	Return pointer to bucket corresponding to key (or first empty bucket).
table_iterator	find_bucket_for_insertion (const key_type &x)
	Return pointer to bucket corresponding to key (or first empty or erased bucket).
size_type	hwm () const
	Return number of entries above which the table will grow.
void	grow ()
	Grow hash table.
Static Protected Member Functions
static size_type	hash_index (const key_type &x, size_type nbuckets)
	Return index of key in hash table.
static table_iterator	find_bucket (const key_type &x, table_iterator tab, size_type nbuckets)
	Return pointer to bucket corresponding to key (or first empty bucket).
static table_const_iterator	find_bucket (const key_type &x, table_const_iterator tab, size_type nbuckets)
	Return pointer to bucket corresponding to key (or first empty bucket).
static table_iterator	find_bucket_for_insertion (const key_type &x, table_iterator tab, size_type nbuckets)
	Return pointer to bucket corresponding to key (or first empty or erased bucket).
Protected Attributes
size_type	num_entries
	Number of values stored in container (cached for faster operation of size())
size_type	num_buckets
	Number of buckets (= hashtab.size())
Table	hashtab
	Vector of buckets, each bucket is kept sorted.
Friends
bool	operator== (const exhashmap &lhs, const exhashmap &rhs)
bool	operator!= (const exhashmap &lhs, const exhashmap &rhs)

Detailed Description

template<typename T, template< class > class A>
class GiNaC::exhashmap< T, A >

Pair Associative Container with 'ex' objects as keys, that is implemented with a hash table and can be used as a replacement for map<> in many cases.

Differences to map<>:

no lower_bound()/upper_bound()
no reverse iterators, no rbegin()/rend()
no operator<()
comparison functor is hardcoded to ex_is_less
bucket_count() returns the number of buckets allocated in the hash table
insert() and erase() invalidate all iterators
average complexity of find() is constant time, worst case is O(n)

Definition at line 82 of file hash_map.h.

Member Typedef Documentation

template<typename T, template< class > class A>

typedef ex GiNaC::exhashmap< T, A >::key_type

Definition at line 87 of file hash_map.h.

template<typename T, template< class > class A>

typedef T GiNaC::exhashmap< T, A >::mapped_type

Definition at line 88 of file hash_map.h.

template<typename T, template< class > class A>

typedef std::pair<key_type, T> GiNaC::exhashmap< T, A >::value_type

Definition at line 89 of file hash_map.h.

template<typename T, template< class > class A>

typedef ex_is_less GiNaC::exhashmap< T, A >::key_compare

Definition at line 90 of file hash_map.h.

template<typename T, template< class > class A>

typedef ex_is_equal GiNaC::exhashmap< T, A >::key_equal

Definition at line 91 of file hash_map.h.

template<typename T, template< class > class A>

typedef value_type& GiNaC::exhashmap< T, A >::reference

Definition at line 92 of file hash_map.h.

template<typename T, template< class > class A>

typedef const value_type& GiNaC::exhashmap< T, A >::const_reference

Definition at line 93 of file hash_map.h.

template<typename T, template< class > class A>

typedef value_type* GiNaC::exhashmap< T, A >::pointer

Definition at line 94 of file hash_map.h.

template<typename T, template< class > class A>

typedef const value_type* GiNaC::exhashmap< T, A >::const_pointer

Definition at line 95 of file hash_map.h.

template<typename T, template< class > class A>

typedef std::pair<bucket_state, value_type> GiNaC::exhashmap< T, A >::Bucket [protected]

Definition at line 104 of file hash_map.h.

template<typename T, template< class > class A>

typedef A<Bucket> GiNaC::exhashmap< T, A >::allocator_type

Definition at line 108 of file hash_map.h.

template<typename T, template< class > class A>

typedef std::vector<Bucket, allocator_type> GiNaC::exhashmap< T, A >::Table [protected]

Definition at line 112 of file hash_map.h.

template<typename T, template< class > class A>

typedef Table::iterator GiNaC::exhashmap< T, A >::table_iterator [protected]

Definition at line 114 of file hash_map.h.

template<typename T, template< class > class A>

typedef Table::const_iterator GiNaC::exhashmap< T, A >::table_const_iterator [protected]

Definition at line 115 of file hash_map.h.

template<typename T, template< class > class A>

typedef exhashmap_iterator<value_type*, value_type&, table_iterator> GiNaC::exhashmap< T, A >::iterator

Definition at line 188 of file hash_map.h.

template<typename T, template< class > class A>

typedef exhashmap_iterator<const value_type*, const value_type&, table_const_iterator> GiNaC::exhashmap< T, A >::const_iterator

Definition at line 189 of file hash_map.h.

template<typename T, template< class > class A>

typedef Table::size_type GiNaC::exhashmap< T, A >::size_type

Definition at line 192 of file hash_map.h.

template<typename T, template< class > class A>

typedef Table::difference_type GiNaC::exhashmap< T, A >::difference_type

Definition at line 193 of file hash_map.h.

Member Enumeration Documentation

template<typename T, template< class > class A>

enum GiNaC::exhashmap::bucket_state [protected]

Enumerator:

EMPTY	bucket empty (never used)
USED	bucket in use
ERASED	bucket empty (element deleted), but may be part of a search chain

Definition at line 99 of file hash_map.h.

Constructor & Destructor Documentation

template<typename T, template< class > class A>

GiNaC::exhashmap< T, A >::exhashmap ( ) [inline]

Definition at line 259 of file hash_map.h.

Referenced by GiNaC::exhashmap< T, A >::operator=().

template<typename T, template< class > class A>

GiNaC::exhashmap< T, A >::exhashmap ( size_type nbuckets ) [inline, explicit]

Definition at line 262 of file hash_map.h.

template<typename T, template< class > class A>

template<class InputIterator >

GiNaC::exhashmap< T, A >::exhashmap	(	InputIterator	first,
		InputIterator	last
	)		`[inline]`

Definition at line 266 of file hash_map.h.

References GiNaC::exhashmap< T, A >::insert().

Member Function Documentation

template<typename T, template< class > class A>

static size_type GiNaC::exhashmap< T, A >::hash_index	(	const key_type &	x,
		size_type	nbuckets
	)		`[inline, static, protected]`

Return index of key in hash table.

Definition at line 221 of file hash_map.h.

References GiNaC::ex::gethash().

template<typename T , template< class > class A>

exhashmap< T, A >::table_iterator GiNaC::exhashmap< T, A >::find_bucket	(	const key_type &	x,
		table_iterator	tab,
		size_type	nbuckets
	)		`[inline, static, protected]`

Return pointer to bucket corresponding to key (or first empty bucket).

Definition at line 449 of file hash_map.h.

Referenced by GiNaC::exhashmap< T, A >::find_bucket().

template<typename T , template< class > class A>

exhashmap< T, A >::table_const_iterator GiNaC::exhashmap< T, A >::find_bucket	(	const key_type &	x,
		table_const_iterator	tab,
		size_type	nbuckets
	)		`[inline, static, protected]`

Return pointer to bucket corresponding to key (or first empty bucket).

Definition at line 465 of file hash_map.h.

template<typename T , template< class > class A>

exhashmap< T, A >::table_iterator GiNaC::exhashmap< T, A >::find_bucket_for_insertion	(	const key_type &	x,
		table_iterator	tab,
		size_type	nbuckets
	)		`[inline, static, protected]`

Return pointer to bucket corresponding to key (or first empty or erased bucket).

Definition at line 481 of file hash_map.h.

Referenced by GiNaC::exhashmap< T, A >::find_bucket_for_insertion().

template<typename T, template< class > class A>

table_iterator GiNaC::exhashmap< T, A >::find_bucket ( const key_type & x ) [inline, protected]

Return pointer to bucket corresponding to key (or first empty bucket).

Definition at line 231 of file hash_map.h.

References GiNaC::exhashmap< T, A >::find_bucket(), GiNaC::exhashmap< T, A >::hashtab, and GiNaC::exhashmap< T, A >::num_buckets.

template<typename T, template< class > class A>

table_const_iterator GiNaC::exhashmap< T, A >::find_bucket ( const key_type & x ) const [inline, protected]

Return pointer to bucket corresponding to key (or first empty bucket).

Definition at line 237 of file hash_map.h.

References GiNaC::exhashmap< T, A >::find_bucket(), GiNaC::exhashmap< T, A >::hashtab, and GiNaC::exhashmap< T, A >::num_buckets.

template<typename T, template< class > class A>

table_iterator GiNaC::exhashmap< T, A >::find_bucket_for_insertion ( const key_type & x ) [inline, protected]

Return pointer to bucket corresponding to key (or first empty or erased bucket).

Definition at line 243 of file hash_map.h.

References GiNaC::exhashmap< T, A >::find_bucket_for_insertion(), GiNaC::exhashmap< T, A >::hashtab, and GiNaC::exhashmap< T, A >::num_buckets.

template<typename T, template< class > class A>

size_type GiNaC::exhashmap< T, A >::hwm ( ) const [inline, protected]

Return number of entries above which the table will grow.

Definition at line 249 of file hash_map.h.

References GiNaC::exhashmap< T, A >::num_buckets.

template<typename T , template< class > class A>

void GiNaC::exhashmap< T, A >::grow ( ) [protected]

Grow hash table.

Definition at line 497 of file hash_map.h.

References GiNaC::internal::next_prime().

template<typename T, template< class > class A>

exhashmap& GiNaC::exhashmap< T, A >::operator= ( const exhashmap< T, A > & other ) [inline]

Definition at line 272 of file hash_map.h.

References GiNaC::exhashmap< T, A >::exhashmap().

template<typename T, template< class > class A>

iterator GiNaC::exhashmap< T, A >::begin ( ) [inline]

Definition at line 279 of file hash_map.h.

References GiNaC::exhashmap< T, A >::hashtab, and GiNaC::exhashmap< T, A >::USED.

template<typename T, template< class > class A>

const_iterator GiNaC::exhashmap< T, A >::begin ( ) const [inline]

Definition at line 288 of file hash_map.h.

References GiNaC::exhashmap< T, A >::hashtab, and GiNaC::exhashmap< T, A >::USED.

template<typename T, template< class > class A>

iterator GiNaC::exhashmap< T, A >::end ( ) [inline]

Definition at line 297 of file hash_map.h.

References GiNaC::exhashmap< T, A >::hashtab.

Referenced by GiNaC::exhashmap< T, A >::count(), and GiNaC::exhashmap< T, A >::equal_range().

template<typename T, template< class > class A>

const_iterator GiNaC::exhashmap< T, A >::end ( ) const [inline]

Definition at line 302 of file hash_map.h.

References GiNaC::exhashmap< T, A >::hashtab.

template<typename T, template< class > class A>

bool GiNaC::exhashmap< T, A >::empty ( ) const [inline]

Definition at line 308 of file hash_map.h.

References GiNaC::exhashmap< T, A >::num_entries.

template<typename T, template< class > class A>

size_type GiNaC::exhashmap< T, A >::size ( ) const [inline]

Definition at line 313 of file hash_map.h.

References GiNaC::exhashmap< T, A >::num_entries.

template<typename T, template< class > class A>

size_type GiNaC::exhashmap< T, A >::max_size ( ) const [inline]

Definition at line 318 of file hash_map.h.

References GiNaC::exhashmap< T, A >::hashtab.

template<typename T, template< class > class A>

size_type GiNaC::exhashmap< T, A >::bucket_count ( ) const [inline]

Definition at line 323 of file hash_map.h.

References GiNaC::exhashmap< T, A >::num_buckets.

template<typename T, template< class > class A>

T& GiNaC::exhashmap< T, A >::operator[] ( const key_type & x ) [inline]

Definition at line 329 of file hash_map.h.

References GiNaC::exhashmap< T, A >::insert().

template<typename T , template< class > class A>

std::pair< typename exhashmap< T, A >::iterator, bool > GiNaC::exhashmap< T, A >::insert ( const value_type & x )

Definition at line 520 of file hash_map.h.

References x.

Referenced by GiNaC::exhashmap< T, A >::exhashmap(), GiNaC::exhashmap< T, A >::insert(), and GiNaC::exhashmap< T, A >::operator[]().

template<typename T, template< class > class A>

iterator GiNaC::exhashmap< T, A >::insert	(	iterator	pos,
		const value_type &	x
	)		`[inline]`

Definition at line 337 of file hash_map.h.

References GiNaC::exhashmap< T, A >::insert().

template<typename T, template< class > class A>

template<class InputIterator >

void GiNaC::exhashmap< T, A >::insert	(	InputIterator	first,
		InputIterator	last
	)		`[inline]`

Definition at line 343 of file hash_map.h.

References GiNaC::exhashmap< T, A >::insert(), and last.

template<typename T, template< class > class A>

void GiNaC::exhashmap< T, A >::erase ( iterator position ) [inline]

Definition at line 349 of file hash_map.h.

References GiNaC::exhashmap< T, A >::ERASED, GiNaC::exhashmap< T, A >::exhashmap_iterator< Pointer, Reference, TableIterator >::get_it_(), and GiNaC::exhashmap< T, A >::num_entries.

template<typename T , template< class > class A>

exhashmap< T, A >::size_type GiNaC::exhashmap< T, A >::erase ( const key_type & x )

Definition at line 540 of file hash_map.h.

References GiNaC::find().

template<typename T, template< class > class A>

void GiNaC::exhashmap< T, A >::swap ( exhashmap< T, A > & other ) [inline]

Definition at line 359 of file hash_map.h.

References GiNaC::exhashmap< T, A >::hashtab, GiNaC::exhashmap< T, A >::num_buckets, and GiNaC::exhashmap< T, A >::num_entries.

Referenced by std::swap().

template<typename T , template< class > class A>

void GiNaC::exhashmap< T, A >::clear ( )

Definition at line 571 of file hash_map.h.

template<typename T, template< class > class A>

key_compare GiNaC::exhashmap< T, A >::key_comp ( ) const [inline]

Definition at line 369 of file hash_map.h.

template<typename T, template< class > class A>

value_compare GiNaC::exhashmap< T, A >::value_comp ( ) const [inline]

Definition at line 374 of file hash_map.h.

template<typename T , template< class > class A>

exhashmap< T, A >::iterator GiNaC::exhashmap< T, A >::find ( const key_type & x )

Definition at line 551 of file hash_map.h.

Referenced by GiNaC::exhashmap< T, A >::count(), and GiNaC::exhashmap< T, A >::equal_range().

template<typename T , template< class > class A>

exhashmap< T, A >::const_iterator GiNaC::exhashmap< T, A >::find ( const key_type & x ) const

Definition at line 561 of file hash_map.h.

template<typename T, template< class > class A>

size_type GiNaC::exhashmap< T, A >::count ( const key_type & x ) const [inline]

Definition at line 383 of file hash_map.h.

References GiNaC::exhashmap< T, A >::end(), and GiNaC::exhashmap< T, A >::find().

template<typename T, template< class > class A>

std::pair<iterator, iterator> GiNaC::exhashmap< T, A >::equal_range ( const key_type & x ) [inline]

Definition at line 388 of file hash_map.h.

References GiNaC::exhashmap< T, A >::end(), and GiNaC::exhashmap< T, A >::find().

template<typename T, template< class > class A>

std::pair<const_iterator, const_iterator> GiNaC::exhashmap< T, A >::equal_range ( const key_type & x ) const [inline]

Definition at line 399 of file hash_map.h.

References GiNaC::exhashmap< T, A >::end(), and GiNaC::exhashmap< T, A >::find().

Friends And Related Function Documentation

template<typename T, template< class > class A>

bool operator==	(	const exhashmap< T, A > &	lhs,
		const exhashmap< T, A > &	rhs
	)		`[friend]`

Definition at line 410 of file hash_map.h.

template<typename T, template< class > class A>

bool operator!=	(	const exhashmap< T, A > &	lhs,
		const exhashmap< T, A > &	rhs
	)		`[friend]`

Definition at line 428 of file hash_map.h.

Member Data Documentation

template<typename T, template< class > class A>

const unsigned GiNaC::exhashmap< T, A >::min_num_buckets = 31 [static]

Definition at line 84 of file hash_map.h.

template<typename T, template< class > class A>

size_type GiNaC::exhashmap< T, A >::num_entries [protected]

Number of values stored in container (cached for faster operation of size())

Definition at line 216 of file hash_map.h.

Referenced by GiNaC::exhashmap< T, A >::empty(), GiNaC::exhashmap< T, A >::erase(), GiNaC::exhashmap< T, A >::size(), and GiNaC::exhashmap< T, A >::swap().

template<typename T, template< class > class A>

size_type GiNaC::exhashmap< T, A >::num_buckets [protected]

Number of buckets (= hashtab.size())

Definition at line 217 of file hash_map.h.

Referenced by GiNaC::exhashmap< T, A >::bucket_count(), GiNaC::exhashmap< T, A >::find_bucket(), GiNaC::exhashmap< T, A >::find_bucket_for_insertion(), GiNaC::exhashmap< T, A >::hwm(), and GiNaC::exhashmap< T, A >::swap().

template<typename T, template< class > class A>

Table GiNaC::exhashmap< T, A >::hashtab [protected]

Vector of buckets, each bucket is kept sorted.

Definition at line 218 of file hash_map.h.

Referenced by GiNaC::exhashmap< T, A >::begin(), GiNaC::exhashmap< T, A >::end(), GiNaC::exhashmap< T, A >::find_bucket(), GiNaC::exhashmap< T, A >::find_bucket_for_insertion(), GiNaC::exhashmap< T, A >::max_size(), and GiNaC::exhashmap< T, A >::swap().

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

hash_map.h

Classes

Public Types

Public Member Functions

Static Public Attributes

Protected Types

Protected Member Functions

Static Protected Member Functions

Protected Attributes

Friends

Detailed Description

template<typename T, template< class > class A> class GiNaC::exhashmap< T, A >

Member Typedef Documentation

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation

template<typename T, template< class > class A>
class GiNaC::exhashmap< T, A >