13 #ifndef STXXL_MAP_HEADER
14 #define STXXL_MAP_HEADER
16 #include <stxxl/bits/noncopyable.h>
17 #include <stxxl/bits/containers/btree/btree.h>
20 __STXXL_BEGIN_NAMESPACE
24 template <
class KeyType,
72 template <
class KeyType,
75 unsigned RawNodeSize = 16 * 1024,
76 unsigned RawLeafSize = 128 * 1024,
77 class PDAllocStrategy = stxxl::SR
79 class map :
private noncopyable
81 typedef btree::btree<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> impl_type;
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;
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(); }
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)
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)
142 template <
class InputIterator>
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)
164 template <
class InputIterator>
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)
177 void swap(
map & obj) { std::swap(Impl, obj.Impl); }
178 std::pair<iterator, bool> insert(
const value_type & x)
180 return Impl.insert(x);
182 iterator insert(iterator pos,
const value_type & x)
184 return Impl.insert(pos, x);
186 template <
class InputIterator>
187 void insert(InputIterator b, InputIterator e)
191 void erase(iterator pos)
195 size_type erase(
const key_type & k)
197 return Impl.erase(k);
199 void erase(iterator first, iterator last)
201 Impl.erase(first, last);
207 iterator find(
const key_type & k)
211 const_iterator find(
const key_type & k)
const
215 size_type count(
const key_type & k)
217 return Impl.count(k);
219 iterator lower_bound(
const key_type & k)
221 return Impl.lower_bound(k);
223 const_iterator lower_bound(
const key_type & k)
const
225 return Impl.lower_bound(k);
227 iterator upper_bound(
const key_type & k)
229 return Impl.upper_bound(k);
231 const_iterator upper_bound(
const key_type & k)
const
233 return Impl.upper_bound(k);
235 std::pair<iterator, iterator> equal_range(
const key_type & k)
237 return Impl.equal_range(k);
239 std::pair<const_iterator, const_iterator> equal_range(
const key_type & k)
const
241 return Impl.equal_range(k);
243 data_type & operator [] (
const key_type & k)
251 Impl.enable_prefetching();
257 Impl.disable_prefetching();
263 return Impl.prefetching_enabled();
269 Impl.print_statistics(o);
275 Impl.reset_statistics();
279 template <
class KeyType_,
282 unsigned RawNodeSize_,
283 unsigned RawLeafSize_,
284 class PDAllocStrategy_>
288 template <
class KeyType_,
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_,
300 unsigned RawNodeSize_,
301 unsigned RawLeafSize_,
302 class PDAllocStrategy_>
306 template <
class KeyType_,
309 unsigned RawNodeSize_,
310 unsigned RawLeafSize_,
311 class PDAllocStrategy_>
315 template <
class KeyType_,
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_,
327 unsigned RawNodeSize_,
328 unsigned RawLeafSize_,
329 class PDAllocStrategy_>
335 template <
class KeyType,
338 unsigned RawNodeSize,
339 unsigned RawLeafSize,
340 class PDAllocStrategy
345 return a.Impl == b.Impl;
348 template <
class KeyType,
351 unsigned RawNodeSize,
352 unsigned RawLeafSize,
353 class PDAllocStrategy
355 inline bool operator < (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a,
358 return a.Impl < b.Impl;
361 template <
class KeyType,
364 unsigned RawNodeSize,
365 unsigned RawLeafSize,
366 class PDAllocStrategy
371 return a.Impl > b.Impl;
374 template <
class KeyType,
377 unsigned RawNodeSize,
378 unsigned RawLeafSize,
379 class PDAllocStrategy
384 return a.Impl != b.Impl;
387 template <
class KeyType,
390 unsigned RawNodeSize,
391 unsigned RawLeafSize,
392 class PDAllocStrategy
394 inline bool operator <= (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a,
397 return a.Impl <= b.Impl;
400 template <
class KeyType,
403 unsigned RawNodeSize,
404 unsigned RawLeafSize,
405 class PDAllocStrategy
410 return a.Impl >= b.Impl;
415 __STXXL_END_NAMESPACE
419 template <
class KeyType,
422 unsigned RawNodeSize,
423 unsigned RawLeafSize,
424 class PDAllocStrategy
426 void swap(stxxl::map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a,
427 stxxl::map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & b
434 #endif // !STXXL_MAP_HEADER