14 #ifndef STXXL_CONTAINERS_UNORDERED_MAP_HEADER
15 #define STXXL_CONTAINERS_UNORDERED_MAP_HEADER
29 unsigned SubBlockSize,
30 unsigned SubBlocksPerBlock,
60 unsigned SubBlockSize = 8* 1024,
61 unsigned SubBlocksPerBlock = 256,
62 class AllocType = std::allocator<std::pair<const KeyType, MappedType> >
67 SubBlockSize, SubBlocksPerBlock, AllocType>
impl_type;
124 : impl(n, hf, cmp, buffer_size, a)
140 template <
class InputIterator>
148 : impl(begin, end, mem_to_sort, n, hf, cmp, buffer_size, a)
167 return impl.max_size();
223 return impl.find(key);
230 return impl.find(key);
238 return impl.count(key);
244 std::pair<iterator, iterator>
247 return impl.equal_range(key);
253 std::pair<const_iterator, const_iterator>
256 return impl.equal_range(key);
275 return impl.insert(value);
284 return impl.insert_oblivious(value);
292 template <
class InputIterator>
295 impl.insert(first, last, mem);
315 return impl.erase(key);
322 impl.erase_oblivious(key);
335 std::swap(impl, obj.
impl);
346 return impl.bucket_count();
352 return impl.max_bucket_count();
360 return impl.bucket_index(k);
371 return impl.load_factor();
377 return impl.opt_load_factor();
383 impl.opt_load_factor(z);
400 return impl.hash_function();
406 return impl.key_cmp();
412 return impl.key_eq();
418 return impl.get_allocator();
429 return impl.buffer_size();
435 return impl.max_buffer_size();
442 impl.max_buffer_size(buffer_size);
453 impl.reset_statistics();
459 impl.print_statistics(o);
466 impl.print_load_statistics(o);
483 unsigned SubBlockSize,
484 unsigned SubBlocksPerBlock,
488 SubBlockSize, SubBlocksPerBlock, AllocType>& a,
490 SubBlockSize, SubBlocksPerBlock, AllocType>& b
498 #endif // !STXXL_CONTAINERS_UNORDERED_MAP_HEADER
void print_load_statistics(std::ostream &o=std::cout) const
Even more statistics: Number of buckets, number of values, buffer-size, values per bucket...
impl_type::difference_type difference_type
allocator_type get_allocator() const
Get node memory allocator.
iterator begin()
iterator pointing to the beginnning of the hash-map
AllocType allocator_type
the fifth template parameter (AllocType)
KeyType key_type
type of the keys being used
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)
impl_type::key_equal key_equal
constructed equality predicate for key
const_iterator begin() const
iterator pointing to the beginnning of the hash-map
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 b...
void clear()
Reset hash-map: erase all values, invalidate all iterators.
void opt_load_factor(float z)
Set desired load-factor.
external_size_type count(const key_type &key) const
Number of values with given key.
impl_type::const_reference const_reference
impl_type::internal_size_type internal_size_type
key_compare key_comp() const
Strict-weak-ordering used by this hash-map.
internal_size_type max_bucket_count() const
Maximum number of buckets.
iterator end()
iterator pointing to the end of the hash-map (iterator-type as template-parameter) ...
impl_type::const_iterator const_iterator
const_iterator end() const
iterator pointing to the end of the hash-map (iterator-type as template-parameter) ...
std::pair< iterator, iterator > equal_range(const key_type &key)
Finds a range containing all values with given key. Non-const access.
stxxl::internal_size_type internal_size_type
float load_factor() const
Average number of (sub)blocks occupied by a bucket.
impl_type::reference reference
impl_type::iterator iterator
equal_to key_equal
Type of constructed equality predicate.
HashType hasher
type of (mother) hash-function
const_iterator find(const key_type &key) const
Look up value by key. Const access.
void max_buffer_size(internal_size_type buffer_size)
Set maximum buffer size.
void swap(unordered_map &obj)
Exchange stored values with another hash-map.
const value_type & const_reference
type for constant value-references
impl_type::external_size_type external_size_type
std::pair< const_iterator, const_iterator > equal_range(const key_type &key) const
Finds a range containing all values with given key. Const access.
hash_map::hash_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType > impl_type
void reset_statistics()
Reset hash-map statistics.
iterator find(const key_type &key)
Look up value by key. Non-const access.
#define STXXL_BEGIN_NAMESPACE
value_type & reference
type for value-references
std::pair< KeyType, MappedType > value_type
actually store (key-data)-pairs
An external memory implementation of the STL unordered_map container, which is based on an external m...
internal_size_type bucket(const key_type &k) const
Bucket-index for values with given key.
impl_type::const_pointer const_pointer
key_equal key_eq() const
Constructed equality predicate used by this hash-map.
external_size_type size() const
Number of values currently stored. Note: If the correct number is currently unknown (because oblivous...
internal_size_type max_buffer_size() const
Maximum buffer size in byte.
impl_type::external_size_type size_type
void print_statistics(std::ostream &o=std::cout) const
Print short general statistics to output stream.
impl_type::hasher hasher
the third template parameter (HashType)
external_size_type max_size() const
The hash-map may store up to this number of values.
CompareType key_compare
functor that imposes a ordering on keys (but see _lt())
impl_type::value_type value_type
pair<const key_type,mapped_type>
impl_type::pointer pointer
internal_size_type buffer_size() const
Number of bytes occupied by buffer.
Main implementation of external memory hash map.
impl_type::key_compare key_compare
the fourth template parameter (CompareType) (!!! not: equality compare)
hasher hash_function() const
Hash-function used by this hash-map.
stxxl::external_size_type external_size_type
void rehash(internal_size_type n)
Rehash with (at least) n buckets.
value_type const * const_pointer
const pointer to type of keys
MappedType mapped_type
type of the data to be stored
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 overwr...
internal_size_type bucket_count() const
Number of buckets.
void erase(const_iterator it)
Erase value by iterator.
void erase_oblivious(const key_type &key)
Erase value by key but without looking at external memory.
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.
value_type * pointer
pointer to type of keys
impl_type::key_type key_type
the first template parameter (Key)
float opt_load_factor() const
Set desired load-factor.
#define STXXL_END_NAMESPACE
impl_type::mapped_type mapped_type
the second template parameter (T)
void insert(InputIterator first, InputIterator last, internal_size_type mem)
Bulk-insert of values in the range [f, l)
stxxl::int64 difference_type
bool empty() const
Check if container is empty, see size() about oblivious-methods.
external_size_type erase(const key_type &key)
Erase value by key; check external memory.