Detailed Description

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>
class stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >

Main implementation of external memory 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

Definition at line 60 of file hash_map.h.

Inheritance diagram for stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >:

Collaboration diagram for stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >:

Classes
struct	AddHashStream

struct	Cmp
	Comparator object for values as required by stxxl::sort. More...

struct	equal_to
	Construct an equality predicate from the comparison operator. More...

struct	HashedValueExtractor
	Functor to extracts the actual value from a HashedValue-struct. More...

struct	HashingStream
	Will return from its input-stream all values that are to be stored in the given bucket. More...

struct	StripHashFunctor
	Extracts the value-part (ignoring the hashvalue); required by HashingStream (see above) More...

struct	UniqueValueStream
	Stream for filtering duplicates. More...

Public Types
enum	{ block_raw_size = SubBlocksPerBlock * SubBlockSize, subblock_raw_size = SubBlockSize }
	subblock- and block-size in bytes More...

enum	{ subblocks_per_block = SubBlocksPerBlock, subblock_size = SubBlockSize / sizeof(value_type) }
	Subblock-size as number of elements, block-size as number of subblocks. More...

typedef AllocatorType	allocator_type
	allocator template type More...

typedef std::vector< bid_type >	bid_container_type
	container for block-bids More...

typedef bid_container_type::iterator	bid_iterator_type
	iterator for block-bids More...

typedef block_type::bid_type	bid_type
	block-identifier for blocks More...

typedef block_cache< block_type >	block_cache_type

typedef typed_block < block_raw_size, subblock_type >	block_type
	a block consists of block_size subblocks More...

typedef bucket< node_type >	bucket_type
	buckets More...

typedef std::vector< bucket_type >	buckets_container_type

typedef hash_map_const_iterator < self_type >	const_iterator

typedef value_type const *	const_pointer
	const pointer to type of keys More...

typedef const value_type &	const_reference
	type for constant value-references More...

typedef stxxl::int64	difference_type

typedef stxxl::external_size_type	external_size_type

typedef HashType	hasher
	type of (mother) hash-function More...

typedef stxxl::internal_size_type	internal_size_type

typedef hash_map_iterator < self_type >	iterator

typedef iterator_map< self_type >	iterator_map_type
	for tracking active iterators More...

typedef KeyCompareType	key_compare
	functor that imposes a ordering on keys (but see _lt()) More...

typedef equal_to	key_equal
	Type of constructed equality predicate. More...

typedef KeyType	key_type
	type of the keys being used More...

typedef MappedType	mapped_type
	type of the data to be stored More...

typedef allocator_type::template rebind< node_type >::other	node_allocator_type

typedef node< value_type >	node_type
	nodes for internal-memory buffer More...

typedef value_type *	pointer
	pointer to type of keys More...

typedef buffered_reader < block_cache_type, bid_iterator_type >	reader_type

typedef value_type &	reference
	type for value-references More...

enum	source_type { src_internal, src_external, src_unknown }

typedef subblock_type::bid_type	subblock_bid_type
	block-identifier for subblocks More...

typedef typed_block < subblock_raw_size, value_type >	subblock_type
	a subblock consists of subblock_size values More...

typedef std::pair< KeyType, MappedType >	value_type
	actually store (key-data)-pairs More...

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

template<class InputIterator >
	hash_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=128 1024 1024, const allocator_type &a=allocator_type())
	Construct a new hash-map and insert all values in the range [f,l) More...

	~hash_map ()

iterator	begin ()
	Returns an iterator pointing to the beginning of the hash-map. More...

const_iterator	begin () const
	Returns a const_interator pointing to the beginning of the hash-map. More...

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

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

internal_size_type	buffer_size () const
	Number of bytes occupied by buffer. More...

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

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

bool	empty () const
	Check if container is empty. More...

iterator	end ()
	Returns an iterator pointing to the end of the hash-map. More...

const_iterator	end () const
	Returns a const_iterator pointing to the end of the hash-map. 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...

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...

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...

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

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

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...

template<class InputIterator >
void	insert (InputIterator f, InputIterator l, internal_size_type mem)
	Bulk-insert of values in the range [f, l) 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...

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

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

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

internal_size_type	max_bucket_count () const
	Maximum number of buckets. 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...

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

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...

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

void	opt_load_factor (float z)
	Set desired load-factor. 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...

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

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

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

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...

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

Protected Types
typedef HashedValue< self_type >	hashed_value_type

typedef hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock >	self_type

Protected Member Functions
template<class Iterator >
Iterator	_begin () const
	iterator pointing to the beginnning of the hash-map More...

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

internal_size_type	_bkt_num (const key_type &key, internal_size_type n) const
	Bucket-index for values with given key. More...

void	_dump_bucket_statistics ()

void	_dump_buckets ()

void	_dump_external ()

template<class Iterator >
Iterator	_end () const
	iterator pointing to the end of the hash-map (iterator-type as template-parameter) More...

bool	_eq (const key_type &a, const key_type &b) const
	true iff a == b. note: it is mandatory that equal keys yield equal hash-values => hashing not neccessary for equality-testing. More...

void	_erase_nodes (node_type first, node_type last)
	Free nodes in range [first, last). If last is NULL all nodes will be freed. More...

tuple< external_size_type, value_type >	_find_key_external (const bucket_type &bucket, const key_type &key) const
	Search for key in external part of bucket. More...

node_type *	_find_key_internal (const bucket_type &bucket, const key_type &key) const
	Locate the given key in the internal-memory chained list. More...

bool	_geq (const key_type &a, const key_type &b) const
	true iff a >= b More...

node_type *	_get_node ()
	Allocate a new buffer-node. More...

bool	_gt (const key_type &a, const key_type &b) const
	true iff a > b More...

bool	_leq (const key_type &a, const key_type &b) const
	true iff a <= b More...

subblock_type *	_load_subblock (const bucket_type &bucket, internal_size_type which_subblock) const
	Load the given bucket's i-th subblock. More...

bool	_lt (const key_type &a, const key_type &b) const

void	_make_conscious ()
	After using *oblivious_-methods only an estimate for the total number of elements can be given. More...

node_type *	_new_node (const value_type &value, node_type *nxt, bool del)
	Allocate a new buffer-node and initialize with given value, node and deleted-flag. More...

void	_put_node (node_type *node)
	Free given node. More...

void	_rebuild_buckets (internal_size_type n_desired=0)

Protected Attributes
bid_container_type	bids_
	blocks-ids of allocated blocks More...

block_cache_type	block_cache_

buckets_container_type	buckets_
	array of bucket More...

internal_size_type	buffer_size_
	size of internal-memory buffer in number of entries More...

key_compare	cmp_
	user supplied strict-weak-ordering for keys More...

hasher	hash_
	user supplied mother hash-function More...

iterator_map_type	iterator_map_
	keeps track of all active iterators More...

internal_size_type	max_buffer_size_
	maximum size for internal-memory buffer More...

external_size_type	n_found_external

external_size_type	n_found_internal

external_size_type	n_not_found

external_size_type	n_subblocks_loaded

node_allocator_type	node_allocator_
	used to allocate new nodes for internal buffer More...

external_size_type	num_total_
	(estimated) number of values More...

bool	oblivious_
	false if the total-number of values is correct (false) or true if estimated (true); see *oblivious_-methods More...

float	opt_load_factor_
	desired load factor after rehashing More...

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

Member Typedef Documentation

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef AllocatorType stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::allocator_type

allocator template type

Definition at line 91 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef std::vector<bid_type> stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::bid_container_type

container for block-bids

Definition at line 118 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef bid_container_type::iterator stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::bid_iterator_type

iterator for block-bids

Definition at line 120 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef block_type::bid_type stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::bid_type

block-identifier for blocks

Definition at line 116 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef block_cache<block_type> stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::block_cache_type

Definition at line 134 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef typed_block<block_raw_size, subblock_type> stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::block_type

a block consists of block_size subblocks

Definition at line 111 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef bucket<node_type> stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::bucket_type

buckets

Definition at line 127 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef std::vector<bucket_type> stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::buckets_container_type

Definition at line 129 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef hash_map_const_iterator<self_type> stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::const_iterator

Definition at line 94 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef value_type const* stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::const_pointer

const pointer to type of keys

Definition at line 80 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef const value_type& stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::const_reference

type for constant value-references

Definition at line 76 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef stxxl::int64 stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::difference_type

Definition at line 84 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef stxxl::external_size_type stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::external_size_type

Definition at line 82 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef HashedValue<self_type> stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::hashed_value_type

protected

Definition at line 1050 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef HashType stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::hasher

type of (mother) hash-function

Definition at line 87 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef stxxl::internal_size_type stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::internal_size_type

Definition at line 83 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef hash_map_iterator<self_type> stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::iterator

Definition at line 93 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef iterator_map<self_type> stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::iterator_map_type

for tracking active iterators

Definition at line 132 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef KeyCompareType stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::key_compare

functor that imposes a ordering on keys (but see _lt())

Definition at line 89 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef equal_to stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::key_equal

Type of constructed equality predicate.

Definition at line 1547 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef KeyType stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::key_type

type of the keys being used

Definition at line 68 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef MappedType stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::mapped_type

type of the data to be stored

Definition at line 70 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef allocator_type::template rebind<node_type>::other stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::node_allocator_type

Definition at line 138 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef node<value_type> stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::node_type

nodes for internal-memory buffer

Definition at line 125 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef value_type* stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::pointer

pointer to type of keys

Definition at line 78 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef buffered_reader<block_cache_type, bid_iterator_type> stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::reader_type

Definition at line 136 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef value_type& stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::reference

type for value-references

Definition at line 74 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef hash_map<KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock> stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::self_type

protected

Definition at line 64 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef subblock_type::bid_type stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::subblock_bid_type

block-identifier for subblocks

Definition at line 114 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef typed_block<subblock_raw_size, value_type> stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::subblock_type

a subblock consists of subblock_size values

Definition at line 109 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

typedef std::pair<KeyType, MappedType> stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::value_type

actually store (key-data)-pairs

Definition at line 72 of file hash_map.h.

Member Enumeration Documentation

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

anonymous enum

subblock- and block-size in bytes

Enumerator
block_raw_size
subblock_raw_size

Definition at line 97 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

anonymous enum

Subblock-size as number of elements, block-size as number of subblocks.

Enumerator
subblocks_per_block
subblock_size

Definition at line 103 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

enum stxxl::hash_map::hash_map::source_type

Enumerator
src_internal
src_external
src_unknown

Definition at line 122 of file hash_map.h.

Constructor & Destructor Documentation

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::hash_map	(	internal_size_type	n = `0`,
		const hasher &	hf = `hasher()`,
		const key_compare &	cmp = `key_compare()`,
		internal_size_type	buffer_size = `12810241024`,
		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 176 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

template<class InputIterator >

stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::hash_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 = `12810241024`,
		const allocator_type &	a = `allocator_type()`
	)

inline

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

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 210 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::~hash_map ( )

inline

Definition at line 233 of file hash_map.h.

Member Function Documentation

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

template<class Iterator >

Iterator stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::_begin ( ) const

inlineprotected

iterator pointing to the beginnning of the hash-map

Definition at line 849 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

internal_size_type stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::_bkt_num ( const key_type & key ) const

inlineprotected

Bucket-index for values with given key.

Definition at line 924 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

internal_size_type stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::_bkt_num	(	const key_type &	key,
		internal_size_type	n
	)		const

inlineprotected

Bucket-index for values with given key.

The total number of buckets has to be specified as well. The bucket number is determined by $ bucket_num = (hash/max_hash)*n_buckets $ max_hash is in fact 2^63-1 (internal_size_type=uint64 (or uint32)) but we rather divide by 2^64, so we can use plain integer arithmetic easily (there should be only a small difference): this way we must only calculate the upper 64 bits of the product hash*n_buckets and we're done. See http://www.cs.uaf.edu/~cs301/notes/Chapter5/node5.html

TODO maybe specialize double arithmetic to integer. the old code was faulty -tb.

Definition at line 939 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

void stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::_dump_bucket_statistics ( )

inlineprotected

Definition at line 1512 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

void stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::_dump_buckets ( )

inlineprotected

Definition at line 1484 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

void stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::_dump_external ( )

inlineprotected

Definition at line 1465 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

template<class Iterator >

Iterator stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::_end ( ) const

inlineprotected

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

Definition at line 867 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

bool stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::_eq	(	const key_type &	a,
		const key_type &	b
	)		const

inlineprotected

true iff a == b. note: it is mandatory that equal keys yield equal hash-values => hashing not neccessary for equality-testing.

Definition at line 1454 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

void stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::_erase_nodes	(	node_type *	first,
		node_type *	last
	)

inlineprotected

Free nodes in range [first, last). If last is NULL all nodes will be freed.

Definition at line 912 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

tuple<external_size_type, value_type> stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::_find_key_external	(	const bucket_type &	bucket,
		const key_type &	key
	)		const

inlineprotected

Search for key in external part of bucket.

Return value is (i_external, value), where i_ext = bucket._num_external if key could not be found.

TODO: replace with bucket.n_external_ % subblock_size

Definition at line 973 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

node_type* stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::_find_key_internal	(	const bucket_type &	bucket,
		const key_type &	key
	)		const

inlineprotected

Locate the given key in the internal-memory chained list.

If the key is not present, the node with the biggest key smaller than the given key is returned. Note that the returned value may be zero: either because the chained list is empty or because the given key is smaller than all other keys in the chained list.

Definition at line 956 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

bool stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::_geq	(	const key_type &	a,
		const key_type &	b
	)		const

inlineprotected

true iff a >= b

Definition at line 1450 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

node_type* stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::_get_node ( )

inlineprotected

Allocate a new buffer-node.

Definition at line 888 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

bool stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::_gt	(	const key_type &	a,
		const key_type &	b
	)		const

inlineprotected

true iff a > b

Definition at line 1446 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

bool stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::_leq	(	const key_type &	a,
		const key_type &	b
	)		const

inlineprotected

true iff a <= b

Definition at line 1448 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

subblock_type* stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::_load_subblock	(	const bucket_type &	bucket,
		internal_size_type	which_subblock
	)		const

inlineprotected

Load the given bucket's i-th subblock.

Since a bucket may be spread over several blocks, we must

determine in which block the requested subblock is located
at which position within the obove-mentioned block the questioned subblock is located

Definition at line 1034 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

bool stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::_lt	(	const key_type &	a,
		const key_type &	b
	)		const

inlineprotected

Definition at line 1436 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

void stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::_make_conscious ( )

inlineprotected

After using *oblivious_-methods only an estimate for the total number of elements can be given.

This method accesses external memory to calculate the exact number.

TODO: make const again

Definition at line 257 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

node_type* stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::_new_node	(	const value_type &	value,
		node_type *	nxt,
		bool	del
	)

inlineprotected

Allocate a new buffer-node and initialize with given value, node and deleted-flag.

Definition at line 901 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

void stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::_put_node ( node_type * node )

inlineprotected

Free given node.

Definition at line 894 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

void stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::_rebuild_buckets ( internal_size_type n_desired = 0 )

inlineprotected

Definition at line 1112 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

iterator stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::begin ( )

inline

Returns an iterator pointing to the beginning of the hash-map.

Definition at line 875 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

const_iterator stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::begin ( ) const

inline

Returns a const_interator pointing to the beginning of the hash-map.

Definition at line 878 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

internal_size_type stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::bucket_count ( ) const

inline

Number of buckets.

Definition at line 791 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

internal_size_type stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::bucket_index ( const key_type & k ) const

inline

Bucket-index for values with given key.

Definition at line 799 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

internal_size_type stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::buffer_size ( ) const

inline

Number of bytes occupied by buffer.

Definition at line 825 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

void stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::clear ( )

inline

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

Definition at line 543 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

external_size_type stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::count ( const key_type & k ) const

inline

Number of values with given key.

Parameters

k	key for value to look up

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

Definition at line 718 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

bool stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::empty ( ) const

inline

Check if container is empty.

Definition at line 296 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

iterator stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::end ( )

inline

Returns an iterator pointing to the end of the hash-map.

Definition at line 881 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

const_iterator stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::end ( ) const

inline

Returns a const_iterator pointing to the end of the hash-map.

Definition at line 884 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

std::pair<iterator, iterator> stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::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 727 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

std::pair<const_iterator, const_iterator> stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::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 736 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

void stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::erase ( const_iterator it )

inline

Erase value by iterator.

Parameters

it	iterator pointing to the value to erase

Definition at line 421 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

external_size_type stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::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 453 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

void stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::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 507 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

iterator stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::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 623 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

const_iterator stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::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 680 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

allocator_type stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::get_allocator ( ) const

inline

Get node memory allocator.

Definition at line 248 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

hasher stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::hash_function ( ) const

inline

Hash-function used by this hash-map.

Definition at line 240 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

std::pair<iterator, bool> stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::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

Definition at line 310 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

template<class InputIterator >

void stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::insert	(	InputIterator	f,
		InputIterator	l,
		internal_size_type	mem
	)

inline

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

Parameters

f	beginning of the range
l	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

values already stored in the hashtable ("old values")

old values, that are to be stored in a certain (new) bucket

values to insert ("new values")

new values with added hash: (hash, (key, mapped))

new values sorted by <hash-value, key>

new values sorted by <hash-value, key> with duplicates eliminated

new values, that are to be stored in a certain bucket

Definition at line 1298 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

iterator stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::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 375 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

key_compare stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::key_cmp ( ) const

inline

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

Definition at line 244 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

key_equal stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::key_eq ( ) const

inline

Constructed equality predicate used by this hash-map.

Definition at line 1550 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

float stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::load_factor ( ) const

inline

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

Definition at line 804 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

internal_size_type stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::max_bucket_count ( ) const

inline

Maximum number of buckets.

Definition at line 795 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

internal_size_type stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::max_buffer_size ( ) const

inline

Maximum buffer size in byte.

Definition at line 832 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

void stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::max_buffer_size ( internal_size_type buffer_size )

inline

Set maximum buffer size.

Parameters

buffer_size new size in byte

Definition at line 839 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

external_size_type stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::max_size ( ) const

inline

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

Definition at line 290 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

mapped_type& stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::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 744 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

float stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::opt_load_factor ( ) const

inline

Get desired load-factor.

Definition at line 808 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

void stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::opt_load_factor ( float z )

inline

Set desired load-factor.

Definition at line 811 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

void stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::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 1558 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

void stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::print_statistics ( std::ostream & o = std::cout ) const

inline

Print short general statistics to output stream.

Definition at line 609 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

void stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::rehash ( internal_size_type n = 0 )

inline

Rehash with (at least) n buckets.

Definition at line 819 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

void stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::reset_statistics ( )

inline

Reset hash-map statistics.

Definition at line 602 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

external_size_type stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::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 282 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

void stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::swap ( self_type & obj )

inline

Exchange stored values with another hash-map.

Parameters

obj	hash-map to swap values with

Definition at line 570 of file hash_map.h.

Member Data Documentation

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

bid_container_type stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::bids_

protected

blocks-ids of allocated blocks

Definition at line 148 of file hash_map.h.

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

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

block_cache_type stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::block_cache_

mutableprotected

Definition at line 156 of file hash_map.h.

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

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

buckets_container_type stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::buckets_

protected

array of bucket

Definition at line 146 of file hash_map.h.

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

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

internal_size_type stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::buffer_size_

protected

size of internal-memory buffer in number of entries

Definition at line 150 of file hash_map.h.

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

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

key_compare stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::cmp_

protected

user supplied strict-weak-ordering for keys

Definition at line 144 of file hash_map.h.

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

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

hasher stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::hash_

protected

user supplied mother hash-function

Definition at line 142 of file hash_map.h.

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

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

iterator_map_type stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::iterator_map_

protected

keeps track of all active iterators

Definition at line 154 of file hash_map.h.

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

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

internal_size_type stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::max_buffer_size_

protected

maximum size for internal-memory buffer

Definition at line 152 of file hash_map.h.

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

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

external_size_type stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::n_found_external

mutableprotected

Definition at line 597 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

external_size_type stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::n_found_internal

mutableprotected

Definition at line 596 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

external_size_type stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::n_not_found

mutableprotected

Definition at line 598 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

external_size_type stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::n_subblocks_loaded

mutableprotected

Definition at line 595 of file hash_map.h.

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

node_allocator_type stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::node_allocator_

protected

used to allocate new nodes for internal buffer

Definition at line 158 of file hash_map.h.

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

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

external_size_type stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::num_total_

mutableprotected

(estimated) number of values

Definition at line 163 of file hash_map.h.

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

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

bool stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::oblivious_

mutableprotected

false if the total-number of values is correct (false) or true if estimated (true); see *oblivious_-methods

Definition at line 161 of file hash_map.h.

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

template<class KeyType, class MappedType, class HashType, class KeyCompareType, unsigned SubBlockSize = 4*1024, unsigned SubBlocksPerBlock = 256, class AllocatorType = std::allocator<std::pair<const KeyType, MappedType> >>

float stxxl::hash_map::hash_map< KeyType, MappedType, HashType, KeyCompareType, SubBlockSize, SubBlocksPerBlock, AllocatorType >::opt_load_factor_

protected

desired load factor after rehashing

Definition at line 165 of file hash_map.h.

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

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

include/stxxl/bits/containers/hash_map/hash_map.h

Detailed Description

Classes

Public Types

Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Additional Inherited Members

Member Typedef Documentation

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation