STXXL  1.4-dev
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
map.h
Go to the documentation of this file.
1 /***************************************************************************
2  * include/stxxl/bits/containers/map.h
3  *
4  * Part of the STXXL. See http://stxxl.sourceforge.net
5  *
6  * Copyright (C) 2006 Roman Dementiev <[email protected]>
7  * Copyright (C) 2008, 2009 Andreas Beckmann <[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_MAP_HEADER
15 #define STXXL_CONTAINERS_MAP_HEADER
16 
17 #include <stxxl/bits/noncopyable.h>
19 
21 
22 namespace btree {
23 
24 template <class KeyType,
25  class DataType,
26  class CompareType,
27  unsigned LogNodeSize,
28  unsigned LogLeafSize,
29  class PDAllocStrategy
30  >
31 class btree;
32 
33 } // namespace btree
34 
35 //! \addtogroup stlcont
36 //! \{
37 
38 //! External associative container (map). \n
39 //! <b> Introduction </b> to map container: see \ref tutorial_map tutorial. \n
40 //! <b> Design and Internals </b> of map container: see \ref design_map
41 //!
42 //! \tparam KeyType key type (POD with no references to internal memory)
43 //! \tparam DataType data type (POD with no references to internal memory)
44 //! \tparam CompareType comparison type used to determine
45 //! whether a key is smaller than another one.
46 //! If CompareType()(x,y) is true, then x is smaller than y.
47 //! CompareType must also provide a static \c max_value method, that returns
48 //! a value of type KeyType that is
49 //! larger than any key stored in map : i.e. for all \b x in map holds
50 //! CompareType()(x,CompareType::max_value())
51 //!
52 //! <BR>
53 //! Example: :
54 //! \verbatim
55 //! struct CmpIntGreater
56 //! {
57 //! bool operator () (const int & a, const int & b) const { return a>b; }
58 //! static int max_value() { return std::numeric_limits<int>::min(); }
59 //! };
60 //! \endverbatim
61 //! Another example:
62 //! \verbatim
63 //! struct CmpIntLess
64 //! {
65 //! bool operator () (const int & a, const int & b) const { return a<b; }
66 //! static int max_value() const { return std::numeric_limits<int>::max(); }
67 //! };
68 //! \endverbatim
69 //! Note that CompareType must define a strict weak ordering.
70 //! (<A HREF="http://www.sgi.com/tech/stl/StrictWeakOrdering.html">see what it is</A>)
71 //! \tparam RawNodeSize size of internal nodes of map in bytes (btree implementation).
72 //! \tparam RawLeafSize size of leaves of map in bytes (btree implementation).
73 //! \tparam PDAllocStrategy parallel disk allocation strategy (\c stxxl::SR is recommended and default)
74 //!
75 template <class KeyType,
76  class DataType,
77  class CompareType,
78  unsigned RawNodeSize = 16* 1024, // 16 KBytes default
79  unsigned RawLeafSize = 128* 1024, // 128 KBytes default
80  class PDAllocStrategy = stxxl::SR
81  >
82 class map : private noncopyable
83 {
85 
87 
88 public:
91 
92  typedef typename impl_type::key_type key_type;
93  typedef typename impl_type::data_type data_type;
98  typedef typename impl_type::pointer pointer;
100  typedef typename impl_type::reference reference;
102  typedef typename impl_type::size_type size_type;
104  typedef typename impl_type::iterator iterator;
106  typedef std::reverse_iterator<iterator> reverse_iterator;
107  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
108 
109  //! \name Iterators
110  //! \{
111 
112  iterator begin() { return impl.begin(); }
113  iterator end() { return impl.end(); }
114  const_iterator begin() const { return impl.begin(); }
115  const_iterator end() const { return impl.end(); }
116  const_iterator cbegin() const { return begin(); }
117  const_iterator cend() const { return end(); }
118 
120  {
121  return reverse_iterator(end());
122  }
124  {
125  return const_reverse_iterator(end());
126  }
128  {
129  return const_reverse_iterator(end());
130  }
132  {
133  return reverse_iterator(begin());
134  }
136  {
137  return const_reverse_iterator(begin());
138  }
140  {
141  return const_reverse_iterator(begin());
142  }
143 
144  //! \}
145 
146  //! \name Capacity
147  //! \{
148 
149  size_type size() const { return impl.size(); }
150  size_type max_size() const { return impl.max_size(); }
151  bool empty() const { return impl.empty(); }
152 
153  //! \}
154 
155  //! \name Observers
156  //! \{
157 
158  key_compare key_comp() const { return impl.key_comp(); }
159  value_compare value_comp() const { return impl.value_comp(); }
160 
161  //! \}
162 
163  //! \name Constructors/Destructors
164  //! \{
165 
166  //! A constructor
167  //! \param node_cache_size_in_bytes size of node cache in bytes (btree implementation)
168  //! \param leaf_cache_size_in_bytes size of leaf cache in bytes (btree implementation)
169  map(unsigned_type node_cache_size_in_bytes,
170  unsigned_type leaf_cache_size_in_bytes
171  ) : impl(node_cache_size_in_bytes, leaf_cache_size_in_bytes)
172  { }
173 
174  //! A constructor
175  //! \param c_ comparator object
176  //! \param node_cache_size_in_bytes size of node cache in bytes (btree implementation)
177  //! \param leaf_cache_size_in_bytes size of leaf cache in bytes (btree implementation)
178  map(const key_compare& c_,
179  unsigned_type node_cache_size_in_bytes,
180  unsigned_type leaf_cache_size_in_bytes
181  ) : impl(c_, node_cache_size_in_bytes, leaf_cache_size_in_bytes)
182  { }
183 
184  //! Constructs a map from a given input range
185  //! \param b beginning of the range
186  //! \param e end of the range
187  //! \param node_cache_size_in_bytes size of node cache in bytes (btree implementation)
188  //! \param leaf_cache_size_in_bytes size of leaf cache in bytes (btree implementation)
189  //! \param range_sorted if \c true than the constructor assumes that the range is sorted
190  //! and performs a fast bottom-up bulk construction of the map (btree implementation)
191  //! \param node_fill_factor node fill factor in [0,1] for bulk construction
192  //! \param leaf_fill_factor leaf fill factor in [0,1] for bulk construction
193  template <class InputIterator>
194  map(InputIterator b,
195  InputIterator e,
196  unsigned_type node_cache_size_in_bytes,
197  unsigned_type leaf_cache_size_in_bytes,
198  bool range_sorted = false,
199  double node_fill_factor = 0.75,
200  double leaf_fill_factor = 0.6
201  ) : impl(b, e, node_cache_size_in_bytes, leaf_cache_size_in_bytes,
202  range_sorted, node_fill_factor, leaf_fill_factor)
203  { }
204 
205  //! Constructs a map from a given input range
206  //! \param b beginning of the range
207  //! \param e end of the range
208  //! \param c_ comparator object
209  //! \param node_cache_size_in_bytes size of node cache in bytes (btree implementation)
210  //! \param leaf_cache_size_in_bytes size of leaf cache in bytes (btree implementation)
211  //! \param range_sorted if \c true than the constructor assumes that the range is sorted
212  //! and performs a fast bottom-up bulk construction of the map (btree implementation)
213  //! \param node_fill_factor node fill factor in [0,1] for bulk construction
214  //! \param leaf_fill_factor leaf fill factor in [0,1] for bulk construction
215  template <class InputIterator>
216  map(InputIterator b,
217  InputIterator e,
218  const key_compare& c_,
219  unsigned_type node_cache_size_in_bytes,
220  unsigned_type leaf_cache_size_in_bytes,
221  bool range_sorted = false,
222  double node_fill_factor = 0.75,
223  double leaf_fill_factor = 0.6
224  ) : impl(b, e, c_, node_cache_size_in_bytes, leaf_cache_size_in_bytes,
225  range_sorted, node_fill_factor, leaf_fill_factor)
226  { }
227 
228  //! \}
229 
230  //! \name Modifiers
231  //! \{
232 
233  void swap(map& obj) { std::swap(impl, obj.impl); }
234  std::pair<iterator, bool> insert(const value_type& x)
235  {
236  return impl.insert(x);
237  }
239  {
240  return impl.insert(pos, x);
241  }
242  template <class InputIterator>
243  void insert(InputIterator b, InputIterator e)
244  {
245  impl.insert(b, e);
246  }
247  void erase(iterator pos)
248  {
249  impl.erase(pos);
250  }
252  {
253  return impl.erase(k);
254  }
255  void erase(iterator first, iterator last)
256  {
257  impl.erase(first, last);
258  }
259  void clear()
260  {
261  impl.clear();
262  }
263 
264  //! \}
265 
266  //! \name Operations
267  //! \{
268 
270  {
271  return impl.find(k);
272  }
273  const_iterator find(const key_type& k) const
274  {
275  return impl.find(k);
276  }
278  {
279  return impl.count(k);
280  }
282  {
283  return impl.lower_bound(k);
284  }
286  {
287  return impl.lower_bound(k);
288  }
290  {
291  return impl.upper_bound(k);
292  }
294  {
295  return impl.upper_bound(k);
296  }
297  std::pair<iterator, iterator> equal_range(const key_type& k)
298  {
299  return impl.equal_range(k);
300  }
301  std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const
302  {
303  return impl.equal_range(k);
304  }
305 
306  //! \}
307 
308  //! \name Operators
309  //! \{
310 
311  data_type& operator [] (const key_type& k)
312  {
313  return impl[k];
314  }
315 
316  //! \}
317 
318  //! \name Miscellaneous
319  //! \{
320 
321  //! Enables leaf prefetching during scanning
323  {
324  impl.enable_prefetching();
325  }
326 
327  //! Disables leaf prefetching during scanning
329  {
330  impl.disable_prefetching();
331  }
332 
333  //! Returns the status of leaf prefetching during scanning
335  {
336  return impl.prefetching_enabled();
337  }
338 
339  //! Prints cache statistics
340  void print_statistics(std::ostream& o) const
341  {
342  impl.print_statistics(o);
343  }
344 
345  //! Resets cache statistics
347  {
348  impl.reset_statistics();
349  }
350 
351  //! \}
352 
353  //////////////////////////////////////////////////
354  template <class KeyType_,
355  class DataType_,
356  class CompareType_,
357  unsigned RawNodeSize_,
358  unsigned RawLeafSize_,
359  class PDAllocStrategy_>
362  //////////////////////////////////////////////////
363  template <class KeyType_,
364  class DataType_,
365  class CompareType_,
366  unsigned RawNodeSize_,
367  unsigned RawLeafSize_,
368  class PDAllocStrategy_>
369  friend bool operator < (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_>& a,
371  //////////////////////////////////////////////////
372  template <class KeyType_,
373  class DataType_,
374  class CompareType_,
375  unsigned RawNodeSize_,
376  unsigned RawLeafSize_,
377  class PDAllocStrategy_>
380  //////////////////////////////////////////////////
381  template <class KeyType_,
382  class DataType_,
383  class CompareType_,
384  unsigned RawNodeSize_,
385  unsigned RawLeafSize_,
386  class PDAllocStrategy_>
389  //////////////////////////////////////////////////
390  template <class KeyType_,
391  class DataType_,
392  class CompareType_,
393  unsigned RawNodeSize_,
394  unsigned RawLeafSize_,
395  class PDAllocStrategy_>
396  friend bool operator <= (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_>& a,
398  //////////////////////////////////////////////////
399  template <class KeyType_,
400  class DataType_,
401  class CompareType_,
402  unsigned RawNodeSize_,
403  unsigned RawLeafSize_,
404  class PDAllocStrategy_>
407  //////////////////////////////////////////////////
408 };
409 
410 template <class KeyType,
411  class DataType,
412  class CompareType,
413  unsigned RawNodeSize,
414  unsigned RawLeafSize,
415  class PDAllocStrategy
416  >
419 {
420  return a.impl == b.impl;
421 }
422 
423 template <class KeyType,
424  class DataType,
425  class CompareType,
426  unsigned RawNodeSize,
427  unsigned RawLeafSize,
428  class PDAllocStrategy
429  >
430 inline bool operator < (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy>& a,
432 {
433  return a.impl < b.impl;
434 }
435 
436 template <class KeyType,
437  class DataType,
438  class CompareType,
439  unsigned RawNodeSize,
440  unsigned RawLeafSize,
441  class PDAllocStrategy
442  >
445 {
446  return a.impl > b.impl;
447 }
448 
449 template <class KeyType,
450  class DataType,
451  class CompareType,
452  unsigned RawNodeSize,
453  unsigned RawLeafSize,
454  class PDAllocStrategy
455  >
458 {
459  return a.impl != b.impl;
460 }
461 
462 template <class KeyType,
463  class DataType,
464  class CompareType,
465  unsigned RawNodeSize,
466  unsigned RawLeafSize,
467  class PDAllocStrategy
468  >
469 inline bool operator <= (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy>& a,
471 {
472  return a.impl <= b.impl;
473 }
474 
475 template <class KeyType,
476  class DataType,
477  class CompareType,
478  unsigned RawNodeSize,
479  unsigned RawLeafSize,
480  class PDAllocStrategy
481  >
484 {
485  return a.impl >= b.impl;
486 }
487 
488 //! \}
489 
491 
492 namespace std {
493 
494 template <class KeyType,
495  class DataType,
496  class CompareType,
497  unsigned RawNodeSize,
498  unsigned RawLeafSize,
499  class PDAllocStrategy
500  >
503  )
504 {
505  a.swap(b);
506 }
507 
508 } // namespace std
509 
510 #endif // !STXXL_CONTAINERS_MAP_HEADER
impl_type::key_compare key_compare
Definition: map.h:96
const_reverse_iterator rend() const
Definition: map.h:135
impl_type::reference reference
Definition: map.h:100
const_iterator upper_bound(const key_type &k) const
Definition: map.h:293
stxxl::uint64 size_type
Definition: btree.h:49
const_reverse_iterator rbegin() const
Definition: map.h:123
size_type erase(const key_type &k)
Definition: map.h:251
const_iterator cbegin() const
Definition: map.h:116
const_iterator find(const key_type &k) const
Definition: map.h:273
map(unsigned_type node_cache_size_in_bytes, unsigned_type leaf_cache_size_in_bytes)
A constructor.
Definition: map.h:169
value_type & reference
Definition: btree.h:52
iterator find(const key_type &k)
Definition: map.h:269
impl_type::node_block_type node_block_type
Definition: map.h:89
size_type max_size() const
Definition: map.h:150
impl_type::key_type key_type
Definition: map.h:92
bool empty() const
Definition: map.h:151
impl_type::pointer pointer
Definition: map.h:98
std::reverse_iterator< const_iterator > const_reverse_iterator
Definition: map.h:107
const_iterator lower_bound(const key_type &k) const
Definition: map.h:285
iterator begin()
Definition: map.h:112
impl_type impl
Definition: map.h:86
void print_statistics(std::ostream &o) const
Prints cache statistics.
Definition: map.h:340
iterator lower_bound(const key_type &k)
Definition: map.h:281
std::pair< const key_type, data_type > value_type
Definition: btree.h:51
iterator end()
Definition: map.h:113
std::pair< iterator, bool > insert(const value_type &x)
Definition: map.h:234
Block containing elements of fixed length.
Definition: typed_block.h:237
size_type count(const key_type &k)
Definition: map.h:277
stxxl::int64 difference_type
Definition: btree.h:50
bool operator!=(const uint_pair &b) const
inequality checking operator
Definition: uint_types.h:198
impl_type::leaf_block_type leaf_block_type
Definition: map.h:90
CompareType key_compare
Definition: btree.h:42
iterator upper_bound(const key_type &k)
Definition: map.h:289
void enable_prefetching()
Enables leaf prefetching during scanning.
Definition: map.h:322
const value_type & const_reference
Definition: btree.h:53
bool operator>(const uint_pair &b) const
greater comparison operator
Definition: uint_types.h:216
impl_type::difference_type difference_type
Definition: map.h:103
bool operator>=(const uint_pair &b) const
greater-or-equal comparison operator
Definition: uint_types.h:222
value_compare value_comp() const
Definition: map.h:159
void clear()
Definition: map.h:259
const_reverse_iterator crend() const
Definition: map.h:139
#define STXXL_BEGIN_NAMESPACE
Definition: namespace.h:16
iterator insert(iterator pos, const value_type &x)
Definition: map.h:238
map(InputIterator b, InputIterator e, const key_compare &c_, unsigned_type node_cache_size_in_bytes, unsigned_type leaf_cache_size_in_bytes, bool range_sorted=false, double node_fill_factor=0.75, double leaf_fill_factor=0.6)
Constructs a map from a given input range.
Definition: map.h:216
bool prefetching_enabled()
Returns the status of leaf prefetching during scanning.
Definition: map.h:334
Simple randomized disk allocation scheme functor.
Definition: block_alloc.h:93
void reset_statistics()
Resets cache statistics.
Definition: map.h:346
KeyType key_type
Definition: btree.h:40
const_reverse_iterator crbegin() const
Definition: map.h:127
value_type const * const_pointer
Definition: btree.h:55
void swap(map &obj)
Definition: map.h:233
impl_type::data_type data_type
Definition: map.h:93
reverse_iterator rbegin()
Definition: map.h:119
void erase(iterator first, iterator last)
Definition: map.h:255
size_type size() const
Definition: map.h:149
map(const key_compare &c_, unsigned_type node_cache_size_in_bytes, unsigned_type leaf_cache_size_in_bytes)
A constructor.
Definition: map.h:178
std::pair< const_iterator, const_iterator > equal_range(const key_type &k) const
Definition: map.h:301
choose_int_types< my_pointer_size >::unsigned_type unsigned_type
Definition: types.h:64
impl_type::const_reference const_reference
Definition: map.h:101
value_type * pointer
Definition: btree.h:54
std::pair< iterator, iterator > equal_range(const key_type &k)
Definition: map.h:297
impl_type::size_type size_type
Definition: map.h:102
std::reverse_iterator< iterator > reverse_iterator
Definition: map.h:106
map(InputIterator b, InputIterator e, unsigned_type node_cache_size_in_bytes, unsigned_type leaf_cache_size_in_bytes, bool range_sorted=false, double node_fill_factor=0.75, double leaf_fill_factor=0.6)
Constructs a map from a given input range.
Definition: map.h:194
External associative container (map). Introduction to map container: see STXXL Map (B+-tree) tutor...
Definition: map.h:82
btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy > impl_type
Definition: map.h:84
void disable_prefetching()
Disables leaf prefetching during scanning.
Definition: map.h:328
DataType data_type
Definition: btree.h:41
void erase(iterator pos)
Definition: map.h:247
key_compare key_comp() const
Definition: map.h:158
impl_type::const_pointer const_pointer
Definition: map.h:99
void insert(InputIterator b, InputIterator e)
Definition: map.h:243
impl_type::value_compare value_compare
Definition: map.h:97
reverse_iterator rend()
Definition: map.h:131
impl_type::const_iterator const_iterator
Definition: map.h:105
impl_type::data_type mapped_type
Definition: map.h:94
const_iterator cend() const
Definition: map.h:117
impl_type::value_type value_type
Definition: map.h:95
bool operator==(const uint_pair &b) const
equality checking operator
Definition: uint_types.h:192
const_iterator end() const
Definition: map.h:115
#define STXXL_END_NAMESPACE
Definition: namespace.h:17
impl_type::iterator iterator
Definition: map.h:104
const_iterator begin() const
Definition: map.h:114