ash::sparse_hashmap< Key, Data, HashFx, EqualKey, Alloc > Class Template Reference

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

#include <ash/sparse_hashmap.h>

List of all members.

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	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 sparse_hashmap &shm) 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.
	sparse_hashmap (size_type n=0, hasher const &h=hasher(), key_equal const &k=key_equal())
	Default constructor.
template<class InputIterator >
	sparse_hashmap (InputIterator f, InputIterator l, size_type n=0, hasher const &h=hasher(), key_equal const &k=key_equal())
	Iterative constructor.
void	swap (sparse_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 (const key_type &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.
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 Data , class HashFx , class EqualKey , class Alloc >
void	swap (sparse_hashmap< Key, Data, HashFx, EqualKey, Alloc > &x, sparse_hashmap< Key, Data, 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::sparse_hashmap< Key, Data, HashFx, EqualKey, Alloc >

A STL-like hashmap with sparse_hashtable as the backend.

Concepts:

stl::unique_hashed_associative_container

Concepts:

stl::pair_associative_container

Template Parameters:

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

This is just a very thin wrapper over sparse_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).

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(): Unlike STL's hash_map, if you want to use erase() you must call set_deleted_key() after construction.

2) resize(0): When an item is deleted, its memory isn't freed right away. This is what 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 dense_hashmap 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.

Todo:

csilvers: implement Alloc get_allocator() const;

---

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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_hashmap< Key, Data, HashFx, EqualKey, Alloc >::sparse_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::sparse_hashmap< Key, Data, HashFx, EqualKey, Alloc >::sparse_hashmap	(	InputIterator	f,
		InputIterator	l,
		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.
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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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> >>

size_type ash::sparse_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::sparse_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::sparse_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> >>

iterator ash::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_hashmap< Key, Data, HashFx, EqualKey, Alloc >::equal_range

(

const key_type &

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::sparse_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::sparse_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::sparse_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::sparse_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:

An 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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_hashmap< Key, Data, HashFx, EqualKey, Alloc >::operator==

(

const sparse_hashmap< Key, Data, HashFx, EqualKey, Alloc > &

shm

)

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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_hashmap< Key, Data, HashFx, EqualKey, Alloc >::swap

(

sparse_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::sparse_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::sparse_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/sparse_hashmap.h