Stxxl  1.3.2
Public Types | Public Member Functions | Friends | List of all members
map< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy > Class Template Reference

External associative container. More...

#include <map.h>

Inherits noncopyable.

Public Types

typedef impl_type::node_block_type node_block_type
 
typedef impl_type::leaf_block_type leaf_block_type
 
typedef impl_type::key_type key_type
 
typedef impl_type::data_type data_type
 
typedef impl_type::data_type mapped_type
 
typedef impl_type::value_type value_type
 
typedef impl_type::key_compare key_compare
 
typedef impl_type::value_compare value_compare
 
typedef impl_type::pointer pointer
 
typedef impl_type::const_pointer const_pointer
 
typedef impl_type::reference reference
 
typedef impl_type::const_reference const_reference
 
typedef impl_type::size_type size_type
 
typedef impl_type::difference_type difference_type
 
typedef impl_type::iterator iterator
 
typedef impl_type::const_iterator const_iterator
 
typedef std::reverse_iterator
< iterator > 
reverse_iterator
 
typedef std::reverse_iterator
< const_iterator > 
const_reverse_iterator
 

Public Member Functions

iterator begin ()
 
iterator end ()
 
const_iterator begin () const
 
const_iterator end () const
 
const_iterator cbegin () const
 
const_iterator cend () const
 
reverse_iterator rbegin ()
 
const_reverse_iterator rbegin () const
 
const_reverse_iterator crbegin () const
 
reverse_iterator rend ()
 
const_reverse_iterator rend () const
 
const_reverse_iterator crend () const
 
size_type size () const
 
size_type max_size () const
 
bool empty () const
 
key_compare key_comp () const
 
value_compare value_comp () const
 
 map (unsigned_type node_cache_size_in_bytes, unsigned_type leaf_cache_size_in_bytes)
 A constructor. More...
 
 map (const key_compare &c_, unsigned_type node_cache_size_in_bytes, unsigned_type leaf_cache_size_in_bytes)
 A constructor. More...
 
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)
 Constructs a map from a given input range. More...
 
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)
 Constructs a map from a given input range. More...
 
void swap (map &obj)
 
std::pair< iterator, bool > insert (const value_type &x)
 
iterator insert (iterator pos, const value_type &x)
 
template<class InputIterator >
void insert (InputIterator b, InputIterator e)
 
void erase (iterator pos)
 
size_type erase (const key_type &k)
 
void erase (iterator first, iterator last)
 
void clear ()
 
iterator find (const key_type &k)
 
const_iterator find (const key_type &k) const
 
size_type count (const key_type &k)
 
iterator lower_bound (const key_type &k)
 
const_iterator lower_bound (const key_type &k) const
 
iterator upper_bound (const key_type &k)
 
const_iterator upper_bound (const key_type &k) const
 
std::pair< iterator, iterator > equal_range (const key_type &k)
 
std::pair< const_iterator,
const_iterator > 
equal_range (const key_type &k) const
 
data_type & operator[] (const key_type &k)
 
void enable_prefetching ()
 Enables leaf prefetching during scanning. More...
 
void disable_prefetching ()
 Disables leaf prefetching during scanning. More...
 
bool prefetching_enabled ()
 Returns the status of leaf prefetching during scanning. More...
 
void print_statistics (std::ostream &o) const
 Prints cache statistics. More...
 
void reset_statistics ()
 Resets cache statistics. More...
 

Friends

template<class KeyType_ , class DataType_ , class CompareType_ , unsigned RawNodeSize_, unsigned RawLeafSize_, class PDAllocStrategy_ >
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_ >
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_ >
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_ >
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_ >
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_ >
bool operator>= (const map< KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_ > &a, const map< KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_ > &b)
 

Detailed Description

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize = 16 * 1024, unsigned RawLeafSize = 128 * 1024, class PDAllocStrategy = stxxl::SR>
class map< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >

External associative container.

\tparam KeyType key type (POD with no references to internal memory)
\tparam DataType data type (POD with no references to internal memory)
\tparam CompareType comparison type used to determine
whether a key is smaller than another one.
If CompareType()(x,y) is true, then x is smaller than y.
CompareType must also provide a static \c max_value method, that returns
a value of type KeyType that is
larger than any key stored in map : i.e. for all \b x in map holds
CompareType()(x,CompareType::max_value())

<BR>
Example: :
//! struct CmpIntGreater
//! {
//!   bool operator () (const int & a, const int & b) const { return a>b; }
//!   static int max_value() { return std::numeric_limits<int>::min(); }
//! };
//! 

Another example:

//! struct CmpIntLess
//! {
//!   bool operator () (const int & a, const int & b) const { return a<b; }
//!   static int max_value() const  { return std::numeric_limits<int>::max(); }
//! };
//! 

Note that CompareType must define a strict weak ordering. (see what it is)

Template Parameters
RawNodeSizesize of internal nodes of map in bytes (btree implementation).
RawLeafSizesize of leaves of map in bytes (btree implementation).
PDAllocStrategyparallel disk allocation strategy (stxxl::SR is recommended and default)

Constructor & Destructor Documentation

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize = 16 * 1024, unsigned RawLeafSize = 128 * 1024, class PDAllocStrategy = stxxl::SR>
map< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::map ( unsigned_type  node_cache_size_in_bytes,
unsigned_type  leaf_cache_size_in_bytes 
)
inline

A constructor.

Parameters
node_cache_size_in_bytessize of node cache in bytes (btree implementation)
leaf_cache_size_in_bytessize of leaf cache in bytes (btree implementation)
template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize = 16 * 1024, unsigned RawLeafSize = 128 * 1024, class PDAllocStrategy = stxxl::SR>
map< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::map ( const key_compare &  c_,
unsigned_type  node_cache_size_in_bytes,
unsigned_type  leaf_cache_size_in_bytes 
)
inline

A constructor.

Parameters
c_comparator object
node_cache_size_in_bytessize of node cache in bytes (btree implementation)
leaf_cache_size_in_bytessize of leaf cache in bytes (btree implementation)
template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize = 16 * 1024, unsigned RawLeafSize = 128 * 1024, class PDAllocStrategy = stxxl::SR>
template<class InputIterator >
map< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::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 
)
inline

Constructs a map from a given input range.

Parameters
bbeginning of the range
eend of the range
node_cache_size_in_bytessize of node cache in bytes (btree implementation)
leaf_cache_size_in_bytessize of leaf cache in bytes (btree implementation)
range_sortedif true than the constructor assumes that the range is sorted and performs a fast bottom-up bulk construction of the map (btree implementation)
node_fill_factornode fill factor in [0,1] for bulk construction
leaf_fill_factorleaf fill factor in [0,1] for bulk construction
template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize = 16 * 1024, unsigned RawLeafSize = 128 * 1024, class PDAllocStrategy = stxxl::SR>
template<class InputIterator >
map< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::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 
)
inline

Constructs a map from a given input range.

Parameters
bbeginning of the range
eend of the range
c_comparator object
node_cache_size_in_bytessize of node cache in bytes (btree implementation)
leaf_cache_size_in_bytessize of leaf cache in bytes (btree implementation)
range_sortedif true than the constructor assumes that the range is sorted and performs a fast bottom-up bulk construction of the map (btree implementation)
node_fill_factornode fill factor in [0,1] for bulk construction
leaf_fill_factorleaf fill factor in [0,1] for bulk construction

Member Function Documentation

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize = 16 * 1024, unsigned RawLeafSize = 128 * 1024, class PDAllocStrategy = stxxl::SR>
void map< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::disable_prefetching ( )
inline

Disables leaf prefetching during scanning.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize = 16 * 1024, unsigned RawLeafSize = 128 * 1024, class PDAllocStrategy = stxxl::SR>
void map< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::enable_prefetching ( )
inline

Enables leaf prefetching during scanning.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize = 16 * 1024, unsigned RawLeafSize = 128 * 1024, class PDAllocStrategy = stxxl::SR>
bool map< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::prefetching_enabled ( )
inline

Returns the status of leaf prefetching during scanning.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize = 16 * 1024, unsigned RawLeafSize = 128 * 1024, class PDAllocStrategy = stxxl::SR>
void map< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::print_statistics ( std::ostream &  o) const
inline

Prints cache statistics.

template<class KeyType, class DataType, class CompareType, unsigned RawNodeSize = 16 * 1024, unsigned RawLeafSize = 128 * 1024, class PDAllocStrategy = stxxl::SR>
void map< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::reset_statistics ( )
inline

Resets cache statistics.


The documentation for this class was generated from the following file: