Detailed Description

template<class KeyType, class MappedType, class HashType, class CompareType, unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>
class stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >

An external memory implementation of the STL unordered_map container, which is based on an external memory hash map.

For more information see STXXL Unordered Map (Hash Map).

Template Parameters

KeyType	the key type
MappedType	the mapped type associated with a key
HashType	a hash functional
CompareType	a less comparison relation for KeyType
SubBlockSize	the raw size of a subblock (caching granularity) (default: 8192)
SubBlocksPerBlock	the number of subblocks per external block (default: 256 -> 2MB blocks)
AllocType	allocator for internal-memory buffer

Examples:: examples/containers/unordered_map1.cpp.

Definition at line 64 of file unordered_map.h.

Inheritance diagram for stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >:

Collaboration diagram for stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >:

Public Types
Types
typedef impl_type::key_type	key_type
	the first template parameter (Key) More...

typedef impl_type::mapped_type	mapped_type
	the second template parameter (T) More...

typedef impl_type::value_type	value_type
	pair<const key_type,mapped_type> More...

typedef impl_type::hasher	hasher
	the third template parameter (HashType) More...

typedef impl_type::key_compare	key_compare
	the fourth template parameter (CompareType) (!!! not: equality compare) More...

typedef AllocType	allocator_type
	the fifth template parameter (AllocType) More...

typedef impl_type::reference	reference

typedef impl_type::const_reference	const_reference

typedef impl_type::pointer	pointer

typedef impl_type::const_pointer	const_pointer

typedef impl_type::external_size_type	size_type

typedef impl_type::difference_type	difference_type

typedef impl_type::external_size_type	external_size_type

typedef impl_type::internal_size_type	internal_size_type

typedef impl_type::iterator	iterator

typedef impl_type::const_iterator	const_iterator

typedef impl_type::key_equal	key_equal
	constructed equality predicate for key More...

Public Member Functions
Constructors
	unordered_map (internal_size_type n=0, const hasher &hf=hasher(), const key_compare &cmp=key_compare(), internal_size_type buffer_size=100 1024 1024, const allocator_type &a=allocator_type())
	Construct a new hash-map. More...

template<class InputIterator >
	unordered_map (InputIterator begin, InputIterator end, internal_size_type mem_to_sort=256 1024 1024, internal_size_type n=0, const hasher &hf=hasher(), const key_compare &cmp=key_compare(), internal_size_type buffer_size=100 1024 1024, const allocator_type &a=allocator_type())
	Construct a new hash-map and insert all values in the range [begin,end) More...

Size and Capacity
external_size_type	size () const
	Number of values currently stored. Note: If the correct number is currently unknown (because oblivous-methods were used), external memory will be scanned. More...

external_size_type	max_size () const
	The hash-map may store up to this number of values. More...

bool	empty () const
	Check if container is empty, see size() about oblivious-methods. More...

Iterators
iterator	begin ()
	iterator pointing to the beginnning of the hash-map More...

iterator	end ()
	iterator pointing to the end of the hash-map (iterator-type as template-parameter) More...

const_iterator	begin () const
	iterator pointing to the beginnning of the hash-map More...

const_iterator	end () const
	iterator pointing to the end of the hash-map (iterator-type as template-parameter) More...

Lookup and Element Access
mapped_type &	operator[] (const key_type &key)
	Convenience operator to quickly insert or find values. Use with caution since using this operator will check external-memory. More...

iterator	find (const key_type &key)
	Look up value by key. Non-const access. More...

const_iterator	find (const key_type &key) const
	Look up value by key. Const access. More...

external_size_type	count (const key_type &key) const
	Number of values with given key. More...

std::pair< iterator, iterator >	equal_range (const key_type &key)
	Finds a range containing all values with given key. Non-const access. More...

std::pair< const_iterator, const_iterator >	equal_range (const key_type &key) const
	Finds a range containing all values with given key. Const access. More...

Modifiers: Insert
std::pair< iterator, bool >	insert (const value_type &value)
	Insert a new value if no value with the same key is already present; external memory must therefore be accessed. More...

iterator	insert_oblivious (const value_type &value)
	Insert a value; external memory is not accessed so that another value with the same key may be overwritten. More...

template<class InputIterator >
void	insert (InputIterator first, InputIterator last, internal_size_type mem)
	Bulk-insert of values in the range [f, l) More...

Modifiers: Erase
void	erase (const_iterator it)
	Erase value by iterator. More...

external_size_type	erase (const key_type &key)
	Erase value by key; check external memory. More...

void	erase_oblivious (const key_type &key)
	Erase value by key but without looking at external memory. More...

void	clear ()
	Reset hash-map: erase all values, invalidate all iterators. More...

void	swap (unordered_map &obj)
	Exchange stored values with another hash-map. More...

Bucket Interface
internal_size_type	bucket_count () const
	Number of buckets. More...

internal_size_type	max_bucket_count () const
	Maximum number of buckets. More...

internal_size_type	bucket (const key_type &k) const
	Bucket-index for values with given key. More...

Hash Policy
float	load_factor () const
	Average number of (sub)blocks occupied by a bucket. More...

float	opt_load_factor () const
	Set desired load-factor. More...

void	opt_load_factor (float z)
	Set desired load-factor. More...

void	rehash (internal_size_type n)
	Rehash with (at least) n buckets. More...

Observers
hasher	hash_function () const
	Hash-function used by this hash-map. More...

key_compare	key_comp () const
	Strict-weak-ordering used by this hash-map. More...

key_equal	key_eq () const
	Constructed equality predicate used by this hash-map. More...

allocator_type	get_allocator () const
	Get node memory allocator. More...

Internal Memory Buffer Policy
internal_size_type	buffer_size () const
	Number of bytes occupied by buffer. More...

internal_size_type	max_buffer_size () const
	Maximum buffer size in byte. More...

void	max_buffer_size (internal_size_type buffer_size)
	Set maximum buffer size. More...

Statistics
void	reset_statistics ()
	Reset hash-map statistics. More...

void	print_statistics (std::ostream &o=std::cout) const
	Print short general statistics to output stream. More...

void	print_load_statistics (std::ostream &o=std::cout) const
	Even more statistics: Number of buckets, number of values, buffer-size, values per bucket. More...

Private Types
typedef hash_map::hash_map < KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >	impl_type

Private Attributes
impl_type	impl

Additional Inherited Members
Private Member Functions inherited from stxxl::noncopyable
	noncopyable ()

Member Typedef Documentation

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef AllocType stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::allocator_type

the fifth template parameter (AllocType)

Definition at line 86 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef impl_type::const_iterator stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::const_iterator

Definition at line 100 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef impl_type::const_pointer stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::const_pointer

Definition at line 91 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef impl_type::const_reference stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::const_reference

Definition at line 89 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef impl_type::difference_type stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::difference_type

Definition at line 94 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef impl_type::external_size_type stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::external_size_type

Definition at line 96 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef impl_type::hasher stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::hasher

the third template parameter (HashType)

Definition at line 82 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef hash_map::hash_map<KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType> stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::impl_type

private

Definition at line 67 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef impl_type::internal_size_type stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::internal_size_type

Definition at line 97 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef impl_type::iterator stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::iterator

Definition at line 99 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef impl_type::key_compare stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::key_compare

the fourth template parameter (CompareType) (!!! not: equality compare)

Definition at line 84 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef impl_type::key_equal stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::key_equal

constructed equality predicate for key

Definition at line 103 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef impl_type::key_type stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::key_type

the first template parameter (Key)

Definition at line 76 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef impl_type::mapped_type stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::mapped_type

the second template parameter (T)

Definition at line 78 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef impl_type::pointer stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::pointer

Definition at line 90 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef impl_type::reference stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::reference

Definition at line 88 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef impl_type::external_size_type stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::size_type

Definition at line 93 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef impl_type::value_type stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::value_type

pair<const key_type,mapped_type>

Definition at line 80 of file unordered_map.h.

Constructor & Destructor Documentation

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::unordered_map	(	internal_size_type	n = `0`,
		const hasher &	hf = `hasher()`,
		const key_compare &	cmp = `key_compare()`,
		internal_size_type	buffer_size = `10010241024`,
		const allocator_type &	a = `allocator_type()`
	)

inline

Construct a new hash-map.

Parameters

n	initial number of buckets
hf	hash-function
cmp	comparator-object
buffer_size	size of internal-memory buffer in bytes
a	allocation-strategory for internal-memory buffer

Definition at line 119 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

template<class InputIterator >

stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::unordered_map	(	InputIterator	begin,
		InputIterator	end,
		internal_size_type	mem_to_sort = `25610241024`,
		internal_size_type	n = `0`,
		const hasher &	hf = `hasher()`,
		const key_compare &	cmp = `key_compare()`,
		internal_size_type	buffer_size = `10010241024`,
		const allocator_type &	a = `allocator_type()`
	)

inline

Construct a new hash-map and insert all values in the range [begin,end)

Parameters

begin	beginning of the range
end	end of the range
mem_to_sort	internal memory that may be used for bulk-construction (not to be confused with the buffer-memory)
n	initial number of buckets
hf	hash-function
cmp	comparator-object
buffer_size	size of internal-memory buffer in bytes
a	allocation-strategory for internal-memory buffer

Definition at line 141 of file unordered_map.h.

Member Function Documentation

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

iterator stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::begin ( )

inline

iterator pointing to the beginnning of the hash-map

Definition at line 182 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

const_iterator stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::begin ( ) const

inline

iterator pointing to the beginnning of the hash-map

Definition at line 195 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

internal_size_type stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::bucket ( const key_type & k ) const

inline

Bucket-index for values with given key.

Definition at line 358 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

internal_size_type stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::bucket_count ( ) const

inline

Number of buckets.

Definition at line 344 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

internal_size_type stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::buffer_size ( ) const

inline

Number of bytes occupied by buffer.

Definition at line 427 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

void stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::clear ( )

inline

Reset hash-map: erase all values, invalidate all iterators.

Definition at line 326 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

external_size_type stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::count ( const key_type & key ) const

inline

Number of values with given key.

Parameters

key	key for value to look up

Returns: 0 or 1 depending on the presence of a value with the given key

Definition at line 236 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

bool stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::empty ( ) const

inline

Check if container is empty, see size() about oblivious-methods.

Definition at line 171 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

iterator stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::end ( )

inline

iterator pointing to the end of the hash-map (iterator-type as template-parameter)

Definition at line 189 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

const_iterator stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::end ( ) const

inline

iterator pointing to the end of the hash-map (iterator-type as template-parameter)

Definition at line 202 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

std::pair<iterator, iterator> stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::equal_range ( const key_type & key )

inline

Finds a range containing all values with given key. Non-const access.

Parameters

key	key to look for#

Returns: range may be empty or contains exactly one value

Definition at line 245 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

std::pair<const_iterator, const_iterator> stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::equal_range ( const key_type & key ) const

inline

Finds a range containing all values with given key. Const access.

Parameters

key	key to look for#

Returns: range may be empty or contains exactly one value

Definition at line 254 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

void stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::erase ( const_iterator it )

inline

Erase value by iterator.

Parameters

it	iterator pointing to the value to erase

Definition at line 305 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

external_size_type stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::erase ( const key_type & key )

inline

Erase value by key; check external memory.

Parameters

key	key of value to erase

Returns: number of values actually erased (0 or 1)

Definition at line 313 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

void stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::erase_oblivious ( const key_type & key )

inline

Erase value by key but without looking at external memory.

Parameters

key	key for value to release

Definition at line 320 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

iterator stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::find ( const key_type & key )

inline

Look up value by key. Non-const access.

Parameters

key	key for value to look up

Definition at line 221 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

const_iterator stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::find ( const key_type & key ) const

inline

Look up value by key. Const access.

Parameters

key	key for value to look up

Definition at line 228 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

allocator_type stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::get_allocator ( ) const

inline

Get node memory allocator.

Definition at line 416 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

hasher stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::hash_function ( ) const

inline

Hash-function used by this hash-map.

Definition at line 398 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

std::pair<iterator, bool> stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::insert ( const value_type & value )

inline

Insert a new value if no value with the same key is already present; external memory must therefore be accessed.

Parameters

value what to insert

Returns: a tuple whose second part is true iff the value was actually added (no value with the same key present); the first part is an iterator pointing to the newly inserted or already stored value

Examples:: examples/containers/unordered_map1.cpp.

Definition at line 273 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

template<class InputIterator >

void stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::insert	(	InputIterator	first,
		InputIterator	last,
		internal_size_type	mem
	)

inline

Bulk-insert of values in the range [f, l)

Parameters

first	beginning of the range
last	end of the range
mem	internal memory that may be used (note: this memory will be used additionally to the buffer). The more the better

Definition at line 293 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

iterator stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::insert_oblivious ( const value_type & value )

inline

Insert a value; external memory is not accessed so that another value with the same key may be overwritten.

Parameters

value what to insert

Returns: iterator pointing to the inserted value

Definition at line 282 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

key_compare stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::key_comp ( ) const

inline

Strict-weak-ordering used by this hash-map.

Definition at line 404 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

key_equal stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::key_eq ( ) const

inline

Constructed equality predicate used by this hash-map.

Definition at line 410 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

float stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::load_factor ( ) const

inline

Average number of (sub)blocks occupied by a bucket.

Definition at line 369 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

internal_size_type stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::max_bucket_count ( ) const

inline

Maximum number of buckets.

Definition at line 350 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

internal_size_type stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::max_buffer_size ( ) const

inline

Maximum buffer size in byte.

Definition at line 433 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

void stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::max_buffer_size ( internal_size_type buffer_size )

inline

Set maximum buffer size.

Parameters

buffer_size new size in byte

Definition at line 440 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

external_size_type stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::max_size ( ) const

inline

The hash-map may store up to this number of values.

Definition at line 165 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

mapped_type& stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::operator[] ( const key_type & key )

inline

Convenience operator to quickly insert or find values. Use with caution since using this operator will check external-memory.

Definition at line 214 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

float stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::opt_load_factor ( ) const

inline

Set desired load-factor.

Definition at line 375 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

void stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::opt_load_factor ( float z )

inline

Set desired load-factor.

Definition at line 381 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

void stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::print_load_statistics ( std::ostream & o = std::cout ) const

inline

Even more statistics: Number of buckets, number of values, buffer-size, values per bucket.

Definition at line 464 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

void stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::print_statistics ( std::ostream & o = std::cout ) const

inline

Print short general statistics to output stream.

Definition at line 457 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

void stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::rehash ( internal_size_type n )

inline

Rehash with (at least) n buckets.

Definition at line 387 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

void stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::reset_statistics ( )

inline

Reset hash-map statistics.

Definition at line 451 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

external_size_type stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::size ( ) const

inline

Number of values currently stored. Note: If the correct number is currently unknown (because oblivous-methods were used), external memory will be scanned.

Definition at line 159 of file unordered_map.h.

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

void stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::swap ( unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType > & obj )

inline

Exchange stored values with another hash-map.

Parameters

obj	hash-map to swap values with

Definition at line 333 of file unordered_map.h.

References stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::impl.

Member Data Documentation

template<class KeyType , class MappedType , class HashType , class CompareType , unsigned SubBlockSize = 8* 1024, unsigned SubBlocksPerBlock = 256, class AllocType = std::allocator<std::pair<const KeyType, MappedType> >>

impl_type stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::impl

private

Definition at line 69 of file unordered_map.h.

Referenced by stxxl::unordered_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::swap().

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

include/stxxl/bits/containers/unordered_map.h

Detailed Description

Public Types

Public Member Functions

Private Types

Private Attributes

Additional Inherited Members

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation