http://stxxl.sourceforge.net
<dementiev@ira.uka.de>
<beckmann@cs.uni-frankfurt.de>
http://www.boost.org/LICENSE_1_0.txt
#ifndef STXXL_MAP_HEADER
#define STXXL_MAP_HEADER
#include <stxxl/bits/noncopyable.h>
#include <stxxl/bits/containers/btree/btree.h>
__STXXL_BEGIN_NAMESPACE
namespace btree
{
template <class KeyType,
class DataType,
class CompareType,
unsigned LogNodeSize,
unsigned LogLeafSize,
class PDAllocStrategy
>
class btree;
}
template <class KeyType,
class DataType,
class CompareType,
unsigned RawNodeSize = 16 * 1024,
unsigned RawLeafSize = 128 * 1024,
class PDAllocStrategy = stxxl::SR
>
class map : private noncopyable
{
typedef btree::btree<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> impl_type;
impl_type Impl;
public:
typedef typename impl_type::node_block_type node_block_type;
typedef typename impl_type::leaf_block_type leaf_block_type;
typedef typename impl_type::key_type key_type;
typedef typename impl_type::data_type data_type;
typedef typename impl_type::data_type mapped_type;
typedef typename impl_type::value_type value_type;
typedef typename impl_type::key_compare key_compare;
typedef typename impl_type::value_compare value_compare;
typedef typename impl_type::pointer pointer;
typedef typename impl_type::const_pointer const_pointer;
typedef typename impl_type::reference reference;
typedef typename impl_type::const_reference const_reference;
typedef typename impl_type::size_type size_type;
typedef typename impl_type::difference_type difference_type;
typedef typename impl_type::iterator iterator;
typedef typename impl_type::const_iterator const_iterator;
typedef std::reverse_iterator<iterator> reverse_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
iterator begin() { return Impl.begin(); }
iterator end() { return Impl.end(); }
const_iterator begin() const { return Impl.begin(); }
const_iterator end() const { return Impl.end(); }
const_iterator cbegin() const { return begin(); }
const_iterator cend() const { return end(); }
reverse_iterator rbegin()
{
return reverse_iterator(end());
}
const_reverse_iterator rbegin() const
{
return const_reverse_iterator(end());
}
const_reverse_iterator crbegin() const
{
return const_reverse_iterator(end());
}
reverse_iterator rend()
{
return reverse_iterator(begin());
}
const_reverse_iterator rend() const
{
return const_reverse_iterator(begin());
}
const_reverse_iterator crend() const
{
return const_reverse_iterator(begin());
}
size_type size() const { return Impl.size(); }
size_type max_size() const { return Impl.max_size(); }
bool empty() const { return Impl.empty(); }
key_compare key_comp() const { return Impl.key_comp(); }
value_compare value_comp() const { return Impl.value_comp(); }
map(unsigned_type node_cache_size_in_bytes,
unsigned_type leaf_cache_size_in_bytes
) : Impl(node_cache_size_in_bytes, leaf_cache_size_in_bytes)
{ }
map(const key_compare & c_,
unsigned_type node_cache_size_in_bytes,
unsigned_type leaf_cache_size_in_bytes
) : Impl(c_, node_cache_size_in_bytes, leaf_cache_size_in_bytes)
{ }
template <class InputIterator>
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
) : Impl(b, e, node_cache_size_in_bytes, leaf_cache_size_in_bytes,
range_sorted, node_fill_factor, leaf_fill_factor)
{ }
template <class InputIterator>
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
) : Impl(b, e, c_, node_cache_size_in_bytes, leaf_cache_size_in_bytes,
range_sorted, node_fill_factor, leaf_fill_factor)
{ }
void swap(map & obj) { std::swap(Impl, obj.Impl); }
std::pair<iterator, bool> insert(const value_type & x)
{
return Impl.insert(x);
}
iterator insert(iterator pos, const value_type & x)
{
return Impl.insert(pos, x);
}
template <class InputIterator>
void insert(InputIterator b, InputIterator e)
{
Impl.insert(b, e);
}
void erase(iterator pos)
{
Impl.erase(pos);
}
size_type erase(const key_type & k)
{
return Impl.erase(k);
}
void erase(iterator first, iterator last)
{
Impl.erase(first, last);
}
void clear()
{
Impl.clear();
}
iterator find(const key_type & k)
{
return Impl.find(k);
}
const_iterator find(const key_type & k) const
{
return Impl.find(k);
}
size_type count(const key_type & k)
{
return Impl.count(k);
}
iterator lower_bound(const key_type & k)
{
return Impl.lower_bound(k);
}
const_iterator lower_bound(const key_type & k) const
{
return Impl.lower_bound(k);
}
iterator upper_bound(const key_type & k)
{
return Impl.upper_bound(k);
}
const_iterator upper_bound(const key_type & k) const
{
return Impl.upper_bound(k);
}
std::pair<iterator, iterator> equal_range(const key_type & k)
{
return Impl.equal_range(k);
}
std::pair<const_iterator, const_iterator> equal_range(const key_type & k) const
{
return Impl.equal_range(k);
}
data_type & operator [] (const key_type & k)
{
return Impl[k];
}
void enable_prefetching()
{
Impl.enable_prefetching();
}
void disable_prefetching()
{
Impl.disable_prefetching();
}
bool prefetching_enabled()
{
return Impl.prefetching_enabled();
}
void print_statistics(std::ostream & o) const
{
Impl.print_statistics(o);
}
void reset_statistics()
{
Impl.reset_statistics();
}
template <class KeyType_,
class DataType_,
class CompareType_,
unsigned RawNodeSize_,
unsigned RawLeafSize_,
class PDAllocStrategy_>
friend bool operator == (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & a,
const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & b);
template <class KeyType_,
class DataType_,
class CompareType_,
unsigned RawNodeSize_,
unsigned RawLeafSize_,
class PDAllocStrategy_>
friend bool operator < (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & a,
const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & b);
template <class KeyType_,
class DataType_,
class CompareType_,
unsigned RawNodeSize_,
unsigned RawLeafSize_,
class PDAllocStrategy_>
friend bool operator > (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & a,
const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & b);
template <class KeyType_,
class DataType_,
class CompareType_,
unsigned RawNodeSize_,
unsigned RawLeafSize_,
class PDAllocStrategy_>
friend bool operator != (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & a,
const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & b);
template <class KeyType_,
class DataType_,
class CompareType_,
unsigned RawNodeSize_,
unsigned RawLeafSize_,
class PDAllocStrategy_>
friend bool operator <= (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & a,
const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & b);
template <class KeyType_,
class DataType_,
class CompareType_,
unsigned RawNodeSize_,
unsigned RawLeafSize_,
class PDAllocStrategy_>
friend bool operator >= (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & a,
const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & b);
};
template <class KeyType,
class DataType,
class CompareType,
unsigned RawNodeSize,
unsigned RawLeafSize,
class PDAllocStrategy
>
inline bool operator == (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a,
const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & b)
{
return a.Impl == b.Impl;
}
template <class KeyType,
class DataType,
class CompareType,
unsigned RawNodeSize,
unsigned RawLeafSize,
class PDAllocStrategy
>
inline bool operator < (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a,
const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & b)
{
return a.Impl < b.Impl;
}
template <class KeyType,
class DataType,
class CompareType,
unsigned RawNodeSize,
unsigned RawLeafSize,
class PDAllocStrategy
>
inline bool operator > (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a,
const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & b)
{
return a.Impl > b.Impl;
}
template <class KeyType,
class DataType,
class CompareType,
unsigned RawNodeSize,
unsigned RawLeafSize,
class PDAllocStrategy
>
inline bool operator != (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a,
const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & b)
{
return a.Impl != b.Impl;
}
template <class KeyType,
class DataType,
class CompareType,
unsigned RawNodeSize,
unsigned RawLeafSize,
class PDAllocStrategy
>
inline bool operator <= (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a,
const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & b)
{
return a.Impl <= b.Impl;
}
template <class KeyType,
class DataType,
class CompareType,
unsigned RawNodeSize,
unsigned RawLeafSize,
class PDAllocStrategy
>
inline bool operator >= (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a,
const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & b)
{
return a.Impl >= b.Impl;
}
__STXXL_END_NAMESPACE
namespace std
{
template <class KeyType,
class DataType,
class CompareType,
unsigned RawNodeSize,
unsigned RawLeafSize,
class PDAllocStrategy
>
void swap(stxxl::map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a,
stxxl::map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & b
)
{
a.swap(b);
}
}
#endif