Stxxl  1.2.1
map.h
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 <dementiev@ira.uka.de>
7  *
8  * Distributed under the Boost Software License, Version 1.0.
9  * (See accompanying file LICENSE_1_0.txt or copy at
10  * http://www.boost.org/LICENSE_1_0.txt)
11  **************************************************************************/
12 
13 #ifndef STXXL_MAP_HEADER
14 #define STXXL_MAP_HEADER
15 
16 #include <stxxl/bits/noncopyable.h>
17 #include <stxxl/bits/containers/btree/btree.h>
18 
19 
20 __STXXL_BEGIN_NAMESPACE
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 
36 
38 
72 template <class KeyType,
73  class DataType,
74  class CompareType,
75  unsigned RawNodeSize = 16 * 1024, // 16 KBytes default
76  unsigned RawLeafSize = 128 * 1024, // 128 KBytes default
77  class PDAllocStrategy = stxxl::SR
78  >
79 class map : private noncopyable
80 {
81  typedef btree::btree<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> impl_type;
82 
83  impl_type Impl;
84 
85 public:
88 
89  typedef typename impl_type::key_type key_type;
90  typedef typename impl_type::data_type data_type;
91  typedef typename impl_type::data_type mapped_type;
92  typedef typename impl_type::value_type value_type;
93  typedef typename impl_type::key_compare key_compare;
94  typedef typename impl_type::value_compare value_compare;
95  typedef typename impl_type::pointer pointer;
96  typedef typename impl_type::reference reference;
97  typedef typename impl_type::const_reference const_reference;
98  typedef typename impl_type::size_type size_type;
99  typedef typename impl_type::difference_type difference_type;
100  typedef typename impl_type::iterator iterator;
101  typedef typename impl_type::const_iterator const_iterator;
102 
103  iterator begin() { return Impl.begin(); }
104  iterator end() { return Impl.end(); }
105  const_iterator begin() const { return Impl.begin(); }
106  const_iterator end() const { return Impl.end(); }
107  const_iterator cbegin() const { return begin(); }
108  const_iterator cend() const { return end(); }
109  size_type size() const { return Impl.size(); }
110  size_type max_size() const { return Impl.max_size(); }
111  bool empty() const { return Impl.empty(); }
112  key_compare key_comp() const { return Impl.key_comp(); }
113  value_compare value_comp() const { return Impl.value_comp(); }
114 
118  map(unsigned_type node_cache_size_in_bytes,
119  unsigned_type leaf_cache_size_in_bytes
120  ) : Impl(node_cache_size_in_bytes, leaf_cache_size_in_bytes)
121  { }
122 
127  map(const key_compare & c_,
128  unsigned_type node_cache_size_in_bytes,
129  unsigned_type leaf_cache_size_in_bytes
130  ) : Impl(c_, node_cache_size_in_bytes, leaf_cache_size_in_bytes)
131  { }
132 
142  template <class InputIterator>
143  map(InputIterator b,
144  InputIterator e,
145  unsigned_type node_cache_size_in_bytes,
146  unsigned_type leaf_cache_size_in_bytes,
147  bool range_sorted = false,
148  double node_fill_factor = 0.75,
149  double leaf_fill_factor = 0.6
150  ) : Impl(b, e, node_cache_size_in_bytes, leaf_cache_size_in_bytes,
151  range_sorted, node_fill_factor, leaf_fill_factor)
152  { }
153 
164  template <class InputIterator>
165  map(InputIterator b,
166  InputIterator e,
167  const key_compare & c_,
168  unsigned_type node_cache_size_in_bytes,
169  unsigned_type leaf_cache_size_in_bytes,
170  bool range_sorted = false,
171  double node_fill_factor = 0.75,
172  double leaf_fill_factor = 0.6
173  ) : Impl(b, e, c_, node_cache_size_in_bytes, leaf_cache_size_in_bytes,
174  range_sorted, node_fill_factor, leaf_fill_factor)
175  { }
176 
177  void swap(map & obj) { std::swap(Impl, obj.Impl); }
178  std::pair<iterator, bool> insert(const value_type & x)
179  {
180  return Impl.insert(x);
181  }
182  iterator insert(iterator pos, const value_type & x)
183  {
184  return Impl.insert(pos, x);
185  }
186  template <class InputIterator>
187  void insert(InputIterator b, InputIterator e)
188  {
189  Impl.insert(b, e);
190  }
191  void erase(iterator pos)
192  {
193  Impl.erase(pos);
194  }
195  size_type erase(const key_type & k)
196  {
197  return Impl.erase(k);
198  }
199  void erase(iterator first, iterator last)
200  {
201  Impl.erase(first, last);
202  }
203  void clear()
204  {
205  Impl.clear();
206  }
207  iterator find(const key_type & k)
208  {
209  return Impl.find(k);
210  }
211  const_iterator find(const key_type & k) const
212  {
213  return Impl.find(k);
214  }
215  size_type count(const key_type & k)
216  {
217  return Impl.count(k);
218  }
219  iterator lower_bound(const key_type & k)
220  {
221  return Impl.lower_bound(k);
222  }
223  const_iterator lower_bound(const key_type & k) const
224  {
225  return Impl.lower_bound(k);
226  }
227  iterator upper_bound(const key_type & k)
228  {
229  return Impl.upper_bound(k);
230  }
231  const_iterator upper_bound(const key_type & k) const
232  {
233  return Impl.upper_bound(k);
234  }
235  std::pair<iterator, iterator> equal_range(const key_type & k)
236  {
237  return Impl.equal_range(k);
238  }
239  std::pair<const_iterator, const_iterator> equal_range(const key_type & k) const
240  {
241  return Impl.equal_range(k);
242  }
243  data_type & operator [] (const key_type & k)
244  {
245  return Impl[k];
246  }
247 
250  {
251  Impl.enable_prefetching();
252  }
253 
256  {
257  Impl.disable_prefetching();
258  }
259 
262  {
263  return Impl.prefetching_enabled();
264  }
265 
267  void print_statistics(std::ostream & o) const
268  {
269  Impl.print_statistics(o);
270  }
271 
274  {
275  Impl.reset_statistics();
276  }
277 
279  template <class KeyType_,
280  class DataType_,
281  class CompareType_,
282  unsigned RawNodeSize_,
283  unsigned RawLeafSize_,
284  class PDAllocStrategy_>
288  template <class KeyType_,
289  class DataType_,
290  class CompareType_,
291  unsigned RawNodeSize_,
292  unsigned RawLeafSize_,
293  class PDAllocStrategy_>
294  friend bool operator < (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & a,
297  template <class KeyType_,
298  class DataType_,
299  class CompareType_,
300  unsigned RawNodeSize_,
301  unsigned RawLeafSize_,
302  class PDAllocStrategy_>
306  template <class KeyType_,
307  class DataType_,
308  class CompareType_,
309  unsigned RawNodeSize_,
310  unsigned RawLeafSize_,
311  class PDAllocStrategy_>
315  template <class KeyType_,
316  class DataType_,
317  class CompareType_,
318  unsigned RawNodeSize_,
319  unsigned RawLeafSize_,
320  class PDAllocStrategy_>
321  friend bool operator <= (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & a,
324  template <class KeyType_,
325  class DataType_,
326  class CompareType_,
327  unsigned RawNodeSize_,
328  unsigned RawLeafSize_,
329  class PDAllocStrategy_>
333 };
334 
335 template <class KeyType,
336  class DataType,
337  class CompareType,
338  unsigned RawNodeSize,
339  unsigned RawLeafSize,
340  class PDAllocStrategy
341  >
344 {
345  return a.Impl == b.Impl;
346 }
347 
348 template <class KeyType,
349  class DataType,
350  class CompareType,
351  unsigned RawNodeSize,
352  unsigned RawLeafSize,
353  class PDAllocStrategy
354  >
355 inline bool operator < (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a,
357 {
358  return a.Impl < b.Impl;
359 }
360 
361 template <class KeyType,
362  class DataType,
363  class CompareType,
364  unsigned RawNodeSize,
365  unsigned RawLeafSize,
366  class PDAllocStrategy
367  >
370 {
371  return a.Impl > b.Impl;
372 }
373 
374 template <class KeyType,
375  class DataType,
376  class CompareType,
377  unsigned RawNodeSize,
378  unsigned RawLeafSize,
379  class PDAllocStrategy
380  >
383 {
384  return a.Impl != b.Impl;
385 }
386 
387 template <class KeyType,
388  class DataType,
389  class CompareType,
390  unsigned RawNodeSize,
391  unsigned RawLeafSize,
392  class PDAllocStrategy
393  >
394 inline bool operator <= (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a,
396 {
397  return a.Impl <= b.Impl;
398 }
399 
400 template <class KeyType,
401  class DataType,
402  class CompareType,
403  unsigned RawNodeSize,
404  unsigned RawLeafSize,
405  class PDAllocStrategy
406  >
409 {
410  return a.Impl >= b.Impl;
411 }
412 
414 
415 __STXXL_END_NAMESPACE
416 
417 namespace std
418 {
419  template <class KeyType,
420  class DataType,
421  class CompareType,
422  unsigned RawNodeSize,
423  unsigned RawLeafSize,
424  class PDAllocStrategy
425  >
426  void swap(stxxl::map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a,
427  stxxl::map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & b
428  )
429  {
430  a.swap(b);
431  }
432 }
433 
434 #endif // !STXXL_MAP_HEADER