Stxxl 1.2.1
|
00001 /*************************************************************************** 00002 * include/stxxl/bits/containers/map.h 00003 * 00004 * Part of the STXXL. See http://stxxl.sourceforge.net 00005 * 00006 * Copyright (C) 2006 Roman Dementiev <dementiev@ira.uka.de> 00007 * 00008 * Distributed under the Boost Software License, Version 1.0. 00009 * (See accompanying file LICENSE_1_0.txt or copy at 00010 * http://www.boost.org/LICENSE_1_0.txt) 00011 **************************************************************************/ 00012 00013 #ifndef STXXL_MAP_HEADER 00014 #define STXXL_MAP_HEADER 00015 00016 #include <stxxl/bits/noncopyable.h> 00017 #include <stxxl/bits/containers/btree/btree.h> 00018 00019 00020 __STXXL_BEGIN_NAMESPACE 00021 00022 namespace btree 00023 { 00024 template <class KeyType, 00025 class DataType, 00026 class CompareType, 00027 unsigned LogNodeSize, 00028 unsigned LogLeafSize, 00029 class PDAllocStrategy 00030 > 00031 class btree; 00032 } 00033 00036 00038 00072 template <class KeyType, 00073 class DataType, 00074 class CompareType, 00075 unsigned RawNodeSize = 16 * 1024, // 16 KBytes default 00076 unsigned RawLeafSize = 128 * 1024, // 128 KBytes default 00077 class PDAllocStrategy = stxxl::SR 00078 > 00079 class map : private noncopyable 00080 { 00081 typedef btree::btree<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> impl_type; 00082 00083 impl_type Impl; 00084 00085 public: 00086 typedef typename impl_type::node_block_type node_block_type; 00087 typedef typename impl_type::leaf_block_type leaf_block_type; 00088 00089 typedef typename impl_type::key_type key_type; 00090 typedef typename impl_type::data_type data_type; 00091 typedef typename impl_type::data_type mapped_type; 00092 typedef typename impl_type::value_type value_type; 00093 typedef typename impl_type::key_compare key_compare; 00094 typedef typename impl_type::value_compare value_compare; 00095 typedef typename impl_type::pointer pointer; 00096 typedef typename impl_type::reference reference; 00097 typedef typename impl_type::const_reference const_reference; 00098 typedef typename impl_type::size_type size_type; 00099 typedef typename impl_type::difference_type difference_type; 00100 typedef typename impl_type::iterator iterator; 00101 typedef typename impl_type::const_iterator const_iterator; 00102 00103 iterator begin() { return Impl.begin(); } 00104 iterator end() { return Impl.end(); } 00105 const_iterator begin() const { return Impl.begin(); } 00106 const_iterator end() const { return Impl.end(); } 00107 const_iterator cbegin() const { return begin(); } 00108 const_iterator cend() const { return end(); } 00109 size_type size() const { return Impl.size(); } 00110 size_type max_size() const { return Impl.max_size(); } 00111 bool empty() const { return Impl.empty(); } 00112 key_compare key_comp() const { return Impl.key_comp(); } 00113 value_compare value_comp() const { return Impl.value_comp(); } 00114 00118 map(unsigned_type node_cache_size_in_bytes, 00119 unsigned_type leaf_cache_size_in_bytes 00120 ) : Impl(node_cache_size_in_bytes, leaf_cache_size_in_bytes) 00121 { } 00122 00127 map(const key_compare & c_, 00128 unsigned_type node_cache_size_in_bytes, 00129 unsigned_type leaf_cache_size_in_bytes 00130 ) : Impl(c_, node_cache_size_in_bytes, leaf_cache_size_in_bytes) 00131 { } 00132 00142 template <class InputIterator> 00143 map(InputIterator b, 00144 InputIterator e, 00145 unsigned_type node_cache_size_in_bytes, 00146 unsigned_type leaf_cache_size_in_bytes, 00147 bool range_sorted = false, 00148 double node_fill_factor = 0.75, 00149 double leaf_fill_factor = 0.6 00150 ) : Impl(b, e, node_cache_size_in_bytes, leaf_cache_size_in_bytes, 00151 range_sorted, node_fill_factor, leaf_fill_factor) 00152 { } 00153 00164 template <class InputIterator> 00165 map(InputIterator b, 00166 InputIterator e, 00167 const key_compare & c_, 00168 unsigned_type node_cache_size_in_bytes, 00169 unsigned_type leaf_cache_size_in_bytes, 00170 bool range_sorted = false, 00171 double node_fill_factor = 0.75, 00172 double leaf_fill_factor = 0.6 00173 ) : Impl(b, e, c_, node_cache_size_in_bytes, leaf_cache_size_in_bytes, 00174 range_sorted, node_fill_factor, leaf_fill_factor) 00175 { } 00176 00177 void swap(map & obj) { std::swap(Impl, obj.Impl); } 00178 std::pair<iterator, bool> insert(const value_type & x) 00179 { 00180 return Impl.insert(x); 00181 } 00182 iterator insert(iterator pos, const value_type & x) 00183 { 00184 return Impl.insert(pos, x); 00185 } 00186 template <class InputIterator> 00187 void insert(InputIterator b, InputIterator e) 00188 { 00189 Impl.insert(b, e); 00190 } 00191 void erase(iterator pos) 00192 { 00193 Impl.erase(pos); 00194 } 00195 size_type erase(const key_type & k) 00196 { 00197 return Impl.erase(k); 00198 } 00199 void erase(iterator first, iterator last) 00200 { 00201 Impl.erase(first, last); 00202 } 00203 void clear() 00204 { 00205 Impl.clear(); 00206 } 00207 iterator find(const key_type & k) 00208 { 00209 return Impl.find(k); 00210 } 00211 const_iterator find(const key_type & k) const 00212 { 00213 return Impl.find(k); 00214 } 00215 size_type count(const key_type & k) 00216 { 00217 return Impl.count(k); 00218 } 00219 iterator lower_bound(const key_type & k) 00220 { 00221 return Impl.lower_bound(k); 00222 } 00223 const_iterator lower_bound(const key_type & k) const 00224 { 00225 return Impl.lower_bound(k); 00226 } 00227 iterator upper_bound(const key_type & k) 00228 { 00229 return Impl.upper_bound(k); 00230 } 00231 const_iterator upper_bound(const key_type & k) const 00232 { 00233 return Impl.upper_bound(k); 00234 } 00235 std::pair<iterator, iterator> equal_range(const key_type & k) 00236 { 00237 return Impl.equal_range(k); 00238 } 00239 std::pair<const_iterator, const_iterator> equal_range(const key_type & k) const 00240 { 00241 return Impl.equal_range(k); 00242 } 00243 data_type & operator [] (const key_type & k) 00244 { 00245 return Impl[k]; 00246 } 00247 00249 void enable_prefetching() 00250 { 00251 Impl.enable_prefetching(); 00252 } 00253 00255 void disable_prefetching() 00256 { 00257 Impl.disable_prefetching(); 00258 } 00259 00261 bool prefetching_enabled() 00262 { 00263 return Impl.prefetching_enabled(); 00264 } 00265 00267 void print_statistics(std::ostream & o) const 00268 { 00269 Impl.print_statistics(o); 00270 } 00271 00273 void reset_statistics() 00274 { 00275 Impl.reset_statistics(); 00276 } 00277 00279 template <class KeyType_, 00280 class DataType_, 00281 class CompareType_, 00282 unsigned RawNodeSize_, 00283 unsigned RawLeafSize_, 00284 class PDAllocStrategy_> 00285 friend bool operator == (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & a, 00286 const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & b); 00288 template <class KeyType_, 00289 class DataType_, 00290 class CompareType_, 00291 unsigned RawNodeSize_, 00292 unsigned RawLeafSize_, 00293 class PDAllocStrategy_> 00294 friend bool operator < (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & a, 00295 const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & b); 00297 template <class KeyType_, 00298 class DataType_, 00299 class CompareType_, 00300 unsigned RawNodeSize_, 00301 unsigned RawLeafSize_, 00302 class PDAllocStrategy_> 00303 friend bool operator > (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & a, 00304 const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & b); 00306 template <class KeyType_, 00307 class DataType_, 00308 class CompareType_, 00309 unsigned RawNodeSize_, 00310 unsigned RawLeafSize_, 00311 class PDAllocStrategy_> 00312 friend bool operator != (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & a, 00313 const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & b); 00315 template <class KeyType_, 00316 class DataType_, 00317 class CompareType_, 00318 unsigned RawNodeSize_, 00319 unsigned RawLeafSize_, 00320 class PDAllocStrategy_> 00321 friend bool operator <= (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & a, 00322 const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & b); 00324 template <class KeyType_, 00325 class DataType_, 00326 class CompareType_, 00327 unsigned RawNodeSize_, 00328 unsigned RawLeafSize_, 00329 class PDAllocStrategy_> 00330 friend bool operator >= (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & a, 00331 const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & b); 00333 }; 00334 00335 template <class KeyType, 00336 class DataType, 00337 class CompareType, 00338 unsigned RawNodeSize, 00339 unsigned RawLeafSize, 00340 class PDAllocStrategy 00341 > 00342 inline bool operator == (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a, 00343 const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & b) 00344 { 00345 return a.Impl == b.Impl; 00346 } 00347 00348 template <class KeyType, 00349 class DataType, 00350 class CompareType, 00351 unsigned RawNodeSize, 00352 unsigned RawLeafSize, 00353 class PDAllocStrategy 00354 > 00355 inline bool operator < (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a, 00356 const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & b) 00357 { 00358 return a.Impl < b.Impl; 00359 } 00360 00361 template <class KeyType, 00362 class DataType, 00363 class CompareType, 00364 unsigned RawNodeSize, 00365 unsigned RawLeafSize, 00366 class PDAllocStrategy 00367 > 00368 inline bool operator > (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a, 00369 const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & b) 00370 { 00371 return a.Impl > b.Impl; 00372 } 00373 00374 template <class KeyType, 00375 class DataType, 00376 class CompareType, 00377 unsigned RawNodeSize, 00378 unsigned RawLeafSize, 00379 class PDAllocStrategy 00380 > 00381 inline bool operator != (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a, 00382 const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & b) 00383 { 00384 return a.Impl != b.Impl; 00385 } 00386 00387 template <class KeyType, 00388 class DataType, 00389 class CompareType, 00390 unsigned RawNodeSize, 00391 unsigned RawLeafSize, 00392 class PDAllocStrategy 00393 > 00394 inline bool operator <= (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a, 00395 const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & b) 00396 { 00397 return a.Impl <= b.Impl; 00398 } 00399 00400 template <class KeyType, 00401 class DataType, 00402 class CompareType, 00403 unsigned RawNodeSize, 00404 unsigned RawLeafSize, 00405 class PDAllocStrategy 00406 > 00407 inline bool operator >= (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a, 00408 const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & b) 00409 { 00410 return a.Impl >= b.Impl; 00411 } 00412 00414 00415 __STXXL_END_NAMESPACE 00416 00417 namespace std 00418 { 00419 template <class KeyType, 00420 class DataType, 00421 class CompareType, 00422 unsigned RawNodeSize, 00423 unsigned RawLeafSize, 00424 class PDAllocStrategy 00425 > 00426 void swap(stxxl::map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a, 00427 stxxl::map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & b 00428 ) 00429 { 00430 a.swap(b); 00431 } 00432 } 00433 00434 #endif // !STXXL_MAP_HEADER