A STL-like hashmap with dense_hashtable as the backend. More...

#include <ash/dense_hashmap.h>

Public Types
typedef ht::key_type	key_type
	The type used to identify elements.
typedef Data	data_type
	The type of object associated with keys.
typedef Data	mapped_type

typedef ht::value_type	value_type
	The type of object stored in the container.
typedef ht::hasher	hasher
	The functor type used to hash keys.
typedef ht::key_equal	key_equal
	The functor used to compare keys for equality.
typedef Alloc	allocator_type

typedef ht::size_type	size_type
	The unsigned type used to represent the size of the container.
typedef ht::difference_type	difference_type
	The signed integral type used to represent the distance between iterators.
typedef ht::pointer	pointer
	The type that serves as a pointer to value_type.
typedef ht::const_pointer	const_pointer
	The type that serves as a const pointer to value_type.
typedef ht::reference	reference
	The type that serves as a reference to value_type.
typedef ht::const_reference	const_reference
	The type that serves as a pointer to value_type.
typedef ht::iterator	iterator
	The type used to iterate through the contents of the container.
typedef ht::const_iterator	const_iterator
	The const type used to iterate through the contents of the container.
typedef ht::local_iterator	local_iterator
	The type used to iterate through a set of elements that share a hash code.
typedef ht::const_local_iterator	const_local_iterator
	The const type used to iterate through a set of elements that share a hash code.
Public Member Functions
key_type	empty_key () const
	Get the key used for empty buckets.
void	set_empty_key (key_type const &key)
	Set the key to use for empty buckets.
key_type	deleted_key () const
	Get the key used for deleted buckets.
void	set_deleted_key (key_type const &key)
	Set the key to use for deleted buckets.
void	clear_deleted_key ()
	Clear the key used for deleted buckets.
bool	operator== (const dense_hashmap &dhm) const
	Equality operator.
Iterator Methods
iterator	begin ()
	Get an iterator to the beginning.
const_iterator	begin () const
	Get an iterator to the beginning.
iterator	end ()
	Get an iterator to the end.
const_iterator	end () const
	Get an iterator to the end.
local_iterator	begin (size_type i)

const_local_iterator	begin (size_type i) const

local_iterator	end (size_type i)

const_local_iterator	end (size_type i) const

Accessor Methods
hasher	hash_funct () const
	Get the hash functor used by the container.
hasher	hash_function () const
	Get the hash functor used by the container.
key_equal	key_eq () const
	Get the key comparison functor used by the container.
Constructors/Destructors
We use the default copy constructor. We use the default destructor.
	dense_hashmap (size_type n=0, hasher const &h=hasher(), key_equal const &k=key_equal())
	Default constructor.
template<class InputIterator >
	dense_hashmap (InputIterator f, InputIterator l, key_type const &empty_key_val, size_type n=0, hasher const &h=hasher(), key_equal const &k=key_equal())
	Iterative constructor.
void	swap (dense_hashmap &c)
	Swap method.
Size Methods
size_type	size () const
	Get the size of the container.
size_type	max_size () const
	Get the maximum size of the container.
bool	empty () const
	Check if the container is empty.
size_type	bucket_count () const
	Get the number of buckets the container has.
size_type	max_bucket_count () const

size_type	bucket_size (size_type i) const

size_type	bucket (key_type const &key) const

float	load_factor () const

float	max_load_factor () const

void	max_load_factor (float new_grow)

float	min_load_factor () const
	Get the min load factor.
void	min_load_factor (float new_shrink)
	Set the min load factor.
void	set_resizing_parameters (float shrink, float grow) __attribute__((__deprecated__))
void	resize (size_type n)
	Resize the container to hold at least n elements.
void	rehash (size_type n)

Lookup Methods
iterator	find (key_type const &key)
	Find an element.
const_iterator	find (key_type const &key) const
	Find an element.
data_type &	operator[] (key_type const &key)
	Element access.
size_type	count (key_type const &key) const
	Count the number of elements with a given key.
pair< iterator, iterator >	equal_range (key_type const &key)
	Find all elements matching a given key.
pair< const_iterator, const_iterator >	equal_range (key_type const &key) const
	Find all elements matching a given key.
Insertion Methods
pair< iterator, bool >	insert (const_reference obj)
	Insert an element into the container.
template<class InputIterator >
void	insert (InputIterator f, InputIterator l)
	Insert a range of elements [f,l) into the container.
void	insert (const_iterator f, const_iterator l)
	Insert a range of elements [f,l) into the container.
iterator	insert (iterator, const_reference obj)
	Insert sematics for std::insert_iterator.
Deletion Methods
void	clear ()
	Erase all elements.
void	clear_no_resize ()
	Clear the container without resizing.
size_type	erase (key_type const &key)
	Erase an element.
void	erase (iterator itr)
	Erase an element.
void	erase (iterator f, iterator l)
	Erase a range of elements.
I/O Methods
bool	write_metadata (FILE *fp)
	Write the container contents to file in a byte-order-independent format.
bool	read_metadata (FILE *fp)
	Read the container contents from a file written by write_metadata().
bool	write_nopointer_data (FILE *fp)
	Write the container contents to file in an architecture-dependent format.
bool	read_nopointer_data (FILE *fp)
	Read the container contents from a file written by write_nopointer_data().
Related Functions
(Note that these are not member functions.)
template<class Key , class T , class HashFx , class EqualKey , class Alloc >
void	swap (dense_hashmap< Key, T, HashFx, EqualKey, Alloc > &x, dense_hashmap< Key, T, HashFx, EqualKey, Alloc > &y)
	Global swap function.

Detailed Description

template<class Key, class Data, class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>
class ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >

A STL-like hashmap with dense_hashtable as the backend.

Concepts:

stl::unique_hashed_associative_container

stl::pair_associative_container

Template Parameters:

Key	The dense_hashmap's key type. Also defined as dense_hashmap::key_type.
Data	The dense_hashmap's data type. Also defined as dense_hashmap::data_type.
HashFx	The hash functor used by the dense_hashmap. Also defined as dense_hashmap::hasher.
EqualKey	The dense_hashmap key equality functor: a binary predicate that determines whether two keys are equal. Also defined as dense_hashmap::key_equal.
Alloc	The allocator to use for internal memory management.

This is just a very thin wrapper over dense_hashtable, just like sgi stl's stl_hash_map is a very thin wrapper over stl_hashtable. The major thing we define is operator[], because we have a concept of a data_type which stl_hashtable doesn't (it only has a key and a value).

NOTE: this is exactly like sparse_hashmap, with the word "sparse" replaced by "dense", except for the addition of set_empty_key().

YOU MUST CALL set_empty_key() IMMEDIATELY AFTER CONSTRUCTION. Otherwise your program will die in mysterious ways. (Note if you use the constructor that takes an InputIterator range, you pass in the empty key in the constructor, rather than after. As a result, this constructor differs from the standard STL version.)

In other respects, we adhere mostly to the STL semantics for hash_map. One important exception is that insert() may invalidate iterators entirely -- STL semantics are that insert() may reorder iterators, but they all still refer to something valid in the hashtable. Not so for us. Likewise, insert() may invalidate pointers into the hashtable. (Whether insert invalidates iterators and pointers depends on whether it results in a hashtable resize). On the plus side, delete() doesn't invalidate iterators or pointers at all, or even change the ordering of elements.

Here are a few "power user" tips:

1) set_deleted_key(): If you want to use erase() you must call set_deleted_key(), in addition to set_empty_key(), after construction. The deleted and empty keys must differ.

2) resize(0): When an item is deleted, its memory isn't freed right away. This allows you to iterate over a hashtable, and call erase(), without invalidating the iterator. To force the memory to be freed, call resize(0). For tr1 compatibility, this can also be called as rehash(0).

3) min_load_factor(0.0) Setting the minimum load factor to 0.0 guarantees that the hash table will never shrink.

Roughly speaking: (1) dense_hashmap: fastest, uses the most memory unless entries are small (2) sparse_hashmap: slowest, uses the least memory (3) hash_map / unordered_map (STL): in the middle

dense_hashmap has, typically, about 78% memory overhead (if your data takes up X bytes, the densehash_map uses .78X more bytes in overhead).
- sparse_hashmap has about 4 bits overhead per entry.
- sparse_hashmap can be 3-7 times slower than the others for lookup and, especially, inserts.

Member Typedef Documentation

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

typedef Alloc ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::allocator_type

Concept: tr1::container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

typedef ht::const_iterator ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::const_iterator

The const type used to iterate through the contents of the container.

Concept: stl::forward_container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

typedef ht::const_local_iterator ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::const_local_iterator

The const type used to iterate through a set of elements that share a hash code.

Concept: tr1::unordered_associative_container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

typedef ht::const_pointer ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::const_pointer

The type that serves as a const pointer to value_type.

Concept: stl::container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

typedef ht::const_reference ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::const_reference

The type that serves as a pointer to value_type.

Concept: stl::container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

typedef Data ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::data_type

The type of object associated with keys.

Concept: stl::pair_associative_container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

typedef ht::difference_type ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::difference_type

The signed integral type used to represent the distance between iterators.

Concept: stl::container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

typedef ht::hasher ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::hasher

The functor type used to hash keys.

Concept: stl::hashed_associative_container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

typedef ht::iterator ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::iterator

The type used to iterate through the contents of the container.

Concept: stl::forward_container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

typedef ht::key_equal ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::key_equal

The functor used to compare keys for equality.

Concept: stl::hashed_associative_container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

typedef ht::key_type ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::key_type

The type used to identify elements.

Concept: stl::associative_container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

typedef ht::local_iterator ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::local_iterator

The type used to iterate through a set of elements that share a hash code.

Concept: tr1::unordered_associative_container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

typedef Data ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::mapped_type

Concept: tr1::unordered_map

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

typedef ht::pointer ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::pointer

The type that serves as a pointer to value_type.

Concept: stl::container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

typedef ht::reference ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::reference

The type that serves as a reference to value_type.

Concept: stl::container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

typedef ht::size_type ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::size_type

The unsigned type used to represent the size of the container.

Concept: stl::container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

typedef ht::value_type ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::value_type

The type of object stored in the container.

Concept: stl::pair_associative_container

Constructor & Destructor Documentation

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::dense_hashmap	(	size_type	n = `0`,
		hasher const &	h = `hasher()`,
		key_equal const &	k = `key_equal()`
	)		`[inline, explicit]`

Default constructor.

Parameters:

n	The number of expected elements.
h	The hasher object to copy, if any.
k	The key_equal object to copy, if any.

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

template<class InputIterator >

ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::dense_hashmap	(	InputIterator	f,
		InputIterator	l,
		key_type const &	empty_key_val,
		size_type	n = `0`,
		hasher const &	h = `hasher()`,
		key_equal const &	k = `key_equal()`
	)		`[inline]`

Iterative constructor.

Parameters:

f	The beginning of the range of elements to insert.
l	The end of the range of elements to insert.
empty_key_val	The key to use for empty buckets.
n	The number of expected elements.
h	The hasher object to copy, if any.
k	The key_equal object to copy, if any.

Member Function Documentation

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

iterator ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::begin ( ) [inline]

Get an iterator to the beginning.

Returns:: An iterator to the beginning of the container.

Concept: stl::container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

const_iterator ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::begin ( ) const [inline]

Get an iterator to the beginning.

Returns:: A const_iterator to the beginning of the container.

Concept: stl::container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

local_iterator ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::begin ( size_type i ) [inline]

Concept: tr1::unordered_associative_container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

const_local_iterator ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::begin ( size_type i ) const [inline]

Concept: tr1::unordered_associative_container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

size_type ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::bucket ( key_type const & key ) const [inline]

Concept: tr1::unordered_associative_container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

size_type ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::bucket_count ( ) const [inline]

Get the number of buckets the container has.

Returns:: The number of currently-allocated buckets.

Concept: stl::hashed_associative_container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

size_type ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::bucket_size ( size_type i ) const [inline]

Concept: tr1::unordered_associative_container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

void ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::clear ( ) [inline]

Erase all elements.

Concept: stl::associative_container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

void ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::clear_deleted_key ( ) [inline]

Clear the key used for deleted buckets.

Attention:: MAKES THE CONTAINER INSERT-ONLY!

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

void ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::clear_no_resize ( ) [inline]

Clear the container without resizing.

This clears the hash map without resizing it down to the minimum bucket count, but rather keeps the number of buckets constant.

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

size_type ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::count ( key_type const & key ) const [inline]

Count the number of elements with a given key.

Parameters:

key	The key to search for.

Returns:: The number of elements matching key. Because this is a Unique Associative Container , the return value will be 0 or 1.

Concept: stl::unique_associative_container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

key_type ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::deleted_key ( ) const [inline]

Get the key used for deleted buckets.

Returns:: A copy of the deleted key.

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

bool ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::empty ( ) const [inline]

Check if the container is empty.

Returns:: True if the container is empty.

Concept: stl::container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

key_type ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::empty_key ( ) const [inline]

Get the key used for empty buckets.

Returns:: A copy of the empty key.

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

iterator ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::end ( ) [inline]

Get an iterator to the end.

Returns:: An iterator to the end of the container.

Concept: stl::container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

const_iterator ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::end ( ) const [inline]

Get an iterator to the end.

Returns:: A const_iterator to the end of the container.

Concept: stl::container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

local_iterator ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::end ( size_type i ) [inline]

Concept: tr1::unordered_associative_container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

const_local_iterator ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::end ( size_type i ) const [inline]

Concept: tr1::unordered_associative_container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

pair<iterator, iterator> ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::equal_range ( key_type const & key ) [inline]

Find all elements matching a given key.

Parameters:

key	The key to search for.

Returns:: A pair of iterators for the range of elements [first,second). Because this is a Unique Associative Container , the first iterator points to the element, or to the end() if not found. The second iterator points to 1 past the first, or to the end().

Concept: stl::unique_associative_container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

pair<const_iterator, const_iterator> ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::equal_range ( key_type const & key ) const [inline]

Find all elements matching a given key.

Parameters:

key	The key to search for.

Returns:: A pair of const_iterators for the range of elements [first,second). Because this is a Unique Associative Container , the first const_iterator points to the element, or to the end() if not found. The second const_iterator points to 1 past the first, or to the end().

Concept: stl::unique_associative_container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

size_type ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::erase ( key_type const & key ) [inline]

Erase an element.

Parameters:

key	The key of the element to erase.

Returns:: The number of erased elements.

Concept: stl::associative_container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

void ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::erase ( iterator itr ) [inline]

Erase an element.

Parameters:

itr	An iterator pointing to the element to erase.

Concept: stl::associative_container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

void ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::erase	(	iterator	f,
		iterator	l
	)		`[inline]`

Erase a range of elements.

Parameters:

f	The beginning of the range to erase.
l	The end of the range to erase.

Concept: stl::associative_container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

iterator ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::find ( key_type const & key ) [inline]

Find an element.

Parameters:

key	The key of the element to search for.

Returns:: A const_iterator to the element, or to the end() if not found.

Concept: stl::associative_container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

const_iterator ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::find ( key_type const & key ) const [inline]

Find an element.

Parameters:

key	The key of the element to search for.

Returns:: A const_iterator to the element, or to the end() if not found.

Concept: stl::associative_container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

hasher ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::hash_funct ( ) const [inline]

Get the hash functor used by the container.

Returns:: A copy of the container's hasher object.

Concept: stl::hashed_associative_container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

hasher ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::hash_function ( ) const [inline]

Get the hash functor used by the container.

Returns:: A copy of the container's hasher object.

Concept: tr1::unordered_associative_container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

pair<iterator, bool> ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::insert ( const_reference obj ) [inline]

Insert an element into the container.

Parameters:

obj	The element to insert.

Returns:: An iterator and a bool. The iterator points to the inserted element, or to another with the same key if one is already in the container. The bool is true if the element was inserted, and false in the case of a duplicate key.

Concept: stl::unique_associative_container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

template<class InputIterator >

void ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::insert	(	InputIterator	f,
		InputIterator	l
	)		`[inline]`

Insert a range of elements [f,l) into the container.

Parameters:

f	The beginning of the range to insert.
l	The end of the range to insert.

Elements with duplicate keys will be ignored.

Concept: stl::unique_associative_container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

void ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::insert	(	const_iterator	f,
		const_iterator	l
	)		`[inline]`

Insert a range of elements [f,l) into the container.

Parameters:

f	The beginning of the range to insert.
l	The end of the range to insert.

Elements with duplicate keys will be ignored.

Concept: stl::unique_associative_container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

iterator ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::insert	(	iterator	,
		const_reference	obj
	)		`[inline]`

Insert sematics for std::insert_iterator.

Note:: The passed-in iterator is ignored.

Parameters:

obj	The element to insert.

Returns:: An iterator pointing to the element.

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

key_equal ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::key_eq ( ) const [inline]

Get the key comparison functor used by the container.

Returns:: A copy of the container's key_equal object.

Concept: stl::hashed_associative_container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

float ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::load_factor ( ) const [inline]

Concept: tr1::unordered_associative_container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

size_type ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::max_bucket_count ( ) const [inline]

Concept: stl::hashed_associative_container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

float ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::max_load_factor ( ) const [inline]

Concept: tr1::unordered_associative_container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

void ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::max_load_factor ( float new_grow ) [inline]

Concept: tr1::unordered_associative_container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

size_type ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::max_size ( ) const [inline]

Get the maximum size of the container.

Returns:: The maximum number of elements the container can hold.

Concept: stl::container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

float ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::min_load_factor ( ) const [inline]

Get the min load factor.

Returns:: The min load factor before the container shrinks.

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

void ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::min_load_factor ( float new_shrink ) [inline]

Set the min load factor.

Parameters:

new_shrink The min load factor before the container shrinks.

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

bool ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::operator== ( const dense_hashmap< Key, Data, HashFx, EqualKey, Alloc > & dhm ) const [inline]

Equality operator.

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

data_type& ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::operator[] ( key_type const & key ) [inline]

Element access.

Parameters:

key	The key of the element to access.

Returns:: A reference to the element. If one with the given key does not exist, it will be inserted.

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

bool ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::read_metadata ( FILE * fp ) [inline]

Read the container contents from a file written by write_metadata().

Parameters:

fp	The file to read.

Returns:: True if successful.

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

bool ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::read_nopointer_data ( FILE * fp ) [inline]

Read the container contents from a file written by write_nopointer_data().

Parameters:

fp	The file to read.

Returns:: True if successful.

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

void ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::rehash ( size_type n ) [inline]

Concept: tr1::unordered_associative_container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

void ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::resize ( size_type n ) [inline]

Resize the container to hold at least n elements.

Parameters:

n	The number of elements the container is expected to hold.

Concept: stl::hashed_associative_container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

void ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::set_deleted_key ( key_type const & key ) [inline]

Set the key to use for deleted buckets.

Attention:: YOU MUST CALL THIS BEFORE DELETING ELEMENTS!

Parameters:

key	The key reserved for deleted buckets.

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

void ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::set_empty_key ( key_type const & key ) [inline]

Set the key to use for empty buckets.

Attention:: YOU MUST CALL THIS AFTER CONSTRUCTION!

Parameters:

key	The key reserved for empty buckets.

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

void ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::set_resizing_parameters	(	float	shrink,
		float	grow
	)		`[inline]`

Deprecated:: Use min_load_factor() or max_load_factor() instead.

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

size_type ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::size ( ) const [inline]

Get the size of the container.

Returns:: The number of elements in the container.

Concept: stl::container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

void ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::swap ( dense_hashmap< Key, Data, HashFx, EqualKey, Alloc > & c ) [inline]

Swap method.

Concept: stl::container

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

bool ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::write_metadata ( FILE * fp ) [inline]

Write the container contents to file in a byte-order-independent format.

Parameters:

fp	The file to write.

Returns:: True if successful.

template<class Key , class Data , class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>

bool ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >::write_nopointer_data ( FILE * fp ) [inline]

Write the container contents to file in an architecture-dependent format.

Parameters:

fp	The file to write.

Returns:: True if successful.

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

ash/dense_hashmap.h

Public Types

Public Member Functions

Related Functions

Detailed Description

template<class Key, class Data, class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >> class ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

template<class Key, class Data, class HashFx = _ASH_HASH<Key>, class EqualKey = equal_to<Key>, class Alloc = libc_allocator_with_realloc< pair<const Key, Data> >>
class ash::dense_hashmap< Key, Data, HashFx, EqualKey, Alloc >