STXXL  1.4.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
unordered_map.h
Go to the documentation of this file.
1 /***************************************************************************
2  * include/stxxl/bits/containers/unordered_map.h
3  *
4  * Part of the STXXL. See http://stxxl.sourceforge.net
5  *
6  * Copyright (C) 2008 Markus Westphal <[email protected]>
7  * Copyright (C) 2014 Timo Bingmann <[email protected]>
8  *
9  * Distributed under the Boost Software License, Version 1.0.
10  * (See accompanying file LICENSE_1_0.txt or copy at
11  * http://www.boost.org/LICENSE_1_0.txt)
12  **************************************************************************/
13 
14 #ifndef STXXL_CONTAINERS_UNORDERED_MAP_HEADER
15 #define STXXL_CONTAINERS_UNORDERED_MAP_HEADER
16 
17 #include <stxxl/bits/noncopyable.h>
19 
21 
22 namespace hash_map {
23 
24 template <
25  class KeyType,
26  class DataType,
27  class HashType,
28  class CompareType,
29  unsigned SubBlockSize,
30  unsigned SubBlocksPerBlock,
31  class Alloc
32  >
33 class hash_map;
34 
35 } // namespace hash_map
36 
37 //! \addtogroup stlcont
38 //! \{
39 
40 /*!
41  * An external memory implementation of the STL unordered_map container, which
42  * is based on an external memory hash map. For more information see \ref
43  * tutorial_unordered_map.
44  *
45  * \tparam KeyType the key type
46  * \tparam MappedType the mapped type associated with a key
47  * \tparam HashType a hash functional
48  * \tparam CompareType a less comparison relation for KeyType
49  * \tparam SubBlockSize the raw size of a subblock (caching granularity)
50  * (default: 8192)
51  * \tparam SubBlocksPerBlock the number of subblocks per external block
52  * (default: 256 -> 2MB blocks)
53  * \tparam AllocType allocator for internal-memory buffer
54  */
55 template <
56  class KeyType,
57  class MappedType,
58  class HashType,
59  class CompareType,
60  unsigned SubBlockSize = 8* 1024,
61  unsigned SubBlocksPerBlock = 256,
62  class AllocType = std::allocator<std::pair<const KeyType, MappedType> >
63  >
64 class unordered_map : private noncopyable
65 {
66  typedef hash_map::hash_map<KeyType, MappedType, HashType, CompareType,
67  SubBlockSize, SubBlocksPerBlock, AllocType> impl_type;
68 
70 
71 public:
72  //! \name Types
73  //! \{
74 
75  //! the first template parameter (Key)
76  typedef typename impl_type::key_type key_type;
77  //! the second template parameter (T)
79  //! pair<const key_type,mapped_type>
81  //! the third template parameter (HashType)
82  typedef typename impl_type::hasher hasher;
83  //! the fourth template parameter (CompareType) (!!! not: equality compare)
85  //! the fifth template parameter (AllocType)
86  typedef AllocType allocator_type;
87 
88  typedef typename impl_type::reference reference;
90  typedef typename impl_type::pointer pointer;
92 
95 
98 
99  typedef typename impl_type::iterator iterator;
101 
102  //! constructed equality predicate for key
103  typedef typename impl_type::key_equal key_equal;
104 
105  //! \}
106 
107  //! \name Constructors
108  //! \{
109 
110  /*!
111  * Construct a new hash-map
112  *
113  * \param n initial number of buckets
114  * \param hf hash-function
115  * \param cmp comparator-object
116  * \param buffer_size size of internal-memory buffer in bytes
117  * \param a allocation-strategory for internal-memory buffer
118  */
120  const hasher& hf = hasher(),
121  const key_compare& cmp = key_compare(),
122  internal_size_type buffer_size = 100*1024*1024,
123  const allocator_type& a = allocator_type())
124  : impl(n, hf, cmp, buffer_size, a)
125  { }
126 
127  /*!
128  * Construct a new hash-map and insert all values in the range [begin,end)
129  *
130  * \param begin beginning of the range
131  * \param end end of the range
132  * \param mem_to_sort internal memory that may be used for
133  * bulk-construction (not to be confused with the buffer-memory)
134  * \param n initial number of buckets
135  * \param hf hash-function
136  * \param cmp comparator-object
137  * \param buffer_size size of internal-memory buffer in bytes
138  * \param a allocation-strategory for internal-memory buffer
139  */
140  template <class InputIterator>
141  unordered_map(InputIterator begin, InputIterator end,
142  internal_size_type mem_to_sort = 256*1024*1024,
143  internal_size_type n = 0,
144  const hasher& hf = hasher(),
145  const key_compare& cmp = key_compare(),
146  internal_size_type buffer_size = 100*1024*1024,
147  const allocator_type& a = allocator_type())
148  : impl(begin, end, mem_to_sort, n, hf, cmp, buffer_size, a)
149  { }
150 
151  //! \}
152 
153  //! \name Size and Capacity
154  //! \{
155 
156  //! Number of values currently stored. Note: If the correct number is
157  //! currently unknown (because **oblivous-methods** were used), external
158  //! memory will be scanned.
160  {
161  return impl.size();
162  }
163 
164  //! The hash-map may store up to this number of values
166  {
167  return impl.max_size();
168  }
169 
170  //! Check if container is empty, see size() about oblivious-methods.
171  bool empty() const
172  {
173  return impl.empty();
174  }
175 
176  //! \}
177 
178  //! \name Iterators
179  //! \{
180 
181  //! iterator pointing to the beginnning of the hash-map
183  {
184  return impl.begin();
185  }
186 
187  //! iterator pointing to the end of the hash-map (iterator-type as
188  //! template-parameter)
190  {
191  return impl.end();
192  }
193 
194  //! iterator pointing to the beginnning of the hash-map
196  {
197  return impl.begin();
198  }
199 
200  //! iterator pointing to the end of the hash-map (iterator-type as
201  //! template-parameter)
203  {
204  return impl.end();
205  }
206 
207  //! \}
208 
209  //! \name Lookup and Element Access
210  //! \{
211 
212  //! Convenience operator to quickly insert or find values. Use with caution
213  //! since using this operator will check external-memory.
214  mapped_type& operator [] (const key_type& key)
215  {
216  return impl[key];
217  }
218 
219  //! Look up value by key. Non-const access.
220  //! \param key key for value to look up
221  iterator find(const key_type& key)
222  {
223  return impl.find(key);
224  }
225 
226  //! Look up value by key. Const access.
227  //! \param key key for value to look up
228  const_iterator find(const key_type& key) const
229  {
230  return impl.find(key);
231  }
232 
233  //! Number of values with given key
234  //! \param key key for value to look up
235  //! \return 0 or 1 depending on the presence of a value with the given key
237  {
238  return impl.count(key);
239  }
240 
241  //! Finds a range containing all values with given key. Non-const access
242  //! \param key key to look for#
243  //! \return range may be empty or contains exactly one value
244  std::pair<iterator, iterator>
245  equal_range(const key_type& key)
246  {
247  return impl.equal_range(key);
248  }
249 
250  //! Finds a range containing all values with given key. Const access
251  //! \param key key to look for#
252  //! \return range may be empty or contains exactly one value
253  std::pair<const_iterator, const_iterator>
254  equal_range(const key_type& key) const
255  {
256  return impl.equal_range(key);
257  }
258 
259  //! \}
260 
261  //! \name Modifiers: Insert
262  //! \{
263 
264  /*!
265  * Insert a new value if no value with the same key is already present;
266  * external memory must therefore be accessed
267  *
268  * \param value what to insert
269  * \return a tuple whose second part is true iff the value was actually
270  * added (no value with the same key present); the first part is an
271  * iterator pointing to the newly inserted or already stored value
272  */
273  std::pair<iterator, bool> insert(const value_type& value)
274  {
275  return impl.insert(value);
276  }
277 
278  //! Insert a value; external memory is not accessed so that another value
279  //! with the same key may be overwritten
280  //! \param value what to insert
281  //! \return iterator pointing to the inserted value
283  {
284  return impl.insert_oblivious(value);
285  }
286 
287  //! Bulk-insert of values in the range [f, l)
288  //! \param first beginning of the range
289  //! \param last end of the range
290  //! \param mem internal memory that may be used (note: this memory will be
291  //! used additionally to the buffer). The more the better
292  template <class InputIterator>
293  void insert(InputIterator first, InputIterator last, internal_size_type mem)
294  {
295  impl.insert(first, last, mem);
296  }
297 
298  //! \}
299 
300  //! \name Modifiers: Erase
301  //! \{
302 
303  //! Erase value by iterator
304  //! \param it iterator pointing to the value to erase
306  {
307  impl.erase(it);
308  }
309 
310  //! Erase value by key; check external memory
311  //! \param key key of value to erase
312  //! \return number of values actually erased (0 or 1)
314  {
315  return impl.erase(key);
316  }
317 
318  //! Erase value by key but without looking at external memory
319  //! \param key key for value to release
320  void erase_oblivious(const key_type& key)
321  {
322  impl.erase_oblivious(key);
323  }
324 
325  //! Reset hash-map: erase all values, invalidate all iterators
326  void clear()
327  {
328  impl.clear();
329  }
330 
331  //! Exchange stored values with another hash-map
332  //! \param obj hash-map to swap values with
333  void swap(unordered_map& obj)
334  {
335  std::swap(impl, obj.impl);
336  }
337 
338  //! \}
339 
340  //! \name Bucket Interface
341  //! \{
342 
343  //! Number of buckets
345  {
346  return impl.bucket_count();
347  }
348 
349  //! Maximum number of buckets
351  {
352  return impl.max_bucket_count();
353  }
354 
355  // bucket_size()?
356 
357  //! Bucket-index for values with given key.
359  {
360  return impl.bucket_index(k);
361  }
362 
363  //! \}
364 
365  //! \name Hash Policy
366  //! \{
367 
368  //! Average number of (sub)blocks occupied by a bucket.
369  float load_factor() const
370  {
371  return impl.load_factor();
372  }
373 
374  //! Set desired load-factor
375  float opt_load_factor() const
376  {
377  return impl.opt_load_factor();
378  }
379 
380  //! Set desired load-factor
381  void opt_load_factor(float z)
382  {
383  impl.opt_load_factor(z);
384  }
385 
386  //! Rehash with (at least) n buckets
388  {
389  impl.rehash(n);
390  }
391 
392  //! \}
393 
394  //! \name Observers
395  //! \{
396 
397  //! Hash-function used by this hash-map
399  {
400  return impl.hash_function();
401  }
402 
403  //! Strict-weak-ordering used by this hash-map
405  {
406  return impl.key_cmp();
407  }
408 
409  //! Constructed equality predicate used by this hash-map
411  {
412  return impl.key_eq();
413  }
414 
415  //! Get node memory allocator
417  {
418  return impl.get_allocator();
419  }
420 
421  //! \}
422 
423  //! \name Internal Memory Buffer Policy
424  //! \{
425 
426  //! Number of bytes occupied by buffer
428  {
429  return impl.buffer_size();
430  }
431 
432  //! Maximum buffer size in byte
434  {
435  return impl.max_buffer_size();
436  }
437 
438  //! Set maximum buffer size
439  //! \param buffer_size new size in byte
441  {
442  impl.max_buffer_size(buffer_size);
443  }
444 
445  //! \}
446 
447  //! \name Statistics
448  //! \{
449 
450  //! Reset hash-map statistics
452  {
453  impl.reset_statistics();
454  }
455 
456  //! Print short general statistics to output stream
457  void print_statistics(std::ostream& o = std::cout) const
458  {
459  impl.print_statistics(o);
460  }
461 
462  //! Even more statistics: Number of buckets, number of values, buffer-size,
463  //! values per bucket
464  void print_load_statistics(std::ostream& o = std::cout) const
465  {
466  impl.print_load_statistics(o);
467  }
468 
469  // \}
470 };
471 
472 //! \}
473 
475 
476 namespace std {
477 
478 template <
479  class KeyType,
480  class MappedType,
481  class HashType,
482  class CompareType,
483  unsigned SubBlockSize,
484  unsigned SubBlocksPerBlock,
485  class AllocType
486  >
487 void swap(stxxl::unordered_map<KeyType, MappedType, HashType, CompareType,
488  SubBlockSize, SubBlocksPerBlock, AllocType>& a,
489  stxxl::unordered_map<KeyType, MappedType, HashType, CompareType,
490  SubBlockSize, SubBlocksPerBlock, AllocType>& b
491  )
492 {
493  a.swap(b);
494 }
495 
496 } // namespace std
497 
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
Definition: unordered_map.h:94
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)
Definition: unordered_map.h:86
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
Definition: unordered_map.h:89
impl_type::internal_size_type internal_size_type
Definition: unordered_map.h:97
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.
float load_factor() const
Average number of (sub)blocks occupied by a bucket.
impl_type::reference reference
Definition: unordered_map.h:88
impl_type::iterator iterator
Definition: unordered_map.h:99
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.
impl_type::external_size_type external_size_type
Definition: unordered_map.h:96
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
Definition: unordered_map.h:67
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
Definition: namespace.h:16
An external memory implementation of the STL unordered_map container, which is based on an external m...
Definition: unordered_map.h:64
internal_size_type bucket(const key_type &k) const
Bucket-index for values with given key.
impl_type::const_pointer const_pointer
Definition: unordered_map.h:91
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
Definition: unordered_map.h:93
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)
Definition: unordered_map.h:82
external_size_type max_size() const
The hash-map may store up to this number of values.
impl_type::value_type value_type
pair&lt;const key_type,mapped_type&gt;
Definition: unordered_map.h:80
impl_type::pointer pointer
Definition: unordered_map.h:90
internal_size_type buffer_size() const
Number of bytes occupied by buffer.
Main implementation of external memory hash map.
Definition: hash_map.h:60
impl_type::key_compare key_compare
the fourth template parameter (CompareType) (!!! not: equality compare)
Definition: unordered_map.h:84
hasher hash_function() const
Hash-function used by this hash-map.
void rehash(internal_size_type n)
Rehash with (at least) n buckets.
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.
impl_type::key_type key_type
the first template parameter (Key)
Definition: unordered_map.h:76
float opt_load_factor() const
Set desired load-factor.
#define STXXL_END_NAMESPACE
Definition: namespace.h:17
impl_type::mapped_type mapped_type
the second template parameter (T)
Definition: unordered_map.h:78
void insert(InputIterator first, InputIterator last, internal_size_type mem)
Bulk-insert of values in the range [f, l)
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.