Public Types | Public Member Functions | Friends

map< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy > Class Template Reference
[Containers]

External associative container. More...

#include <map.h>

Inherits noncopyable.

List of all members.

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.
 map (const key_compare &c_, unsigned_type node_cache_size_in_bytes, unsigned_type leaf_cache_size_in_bytes)
 A constructor.
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.
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.
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.
void disable_prefetching ()
 Disables leaf prefetching during scanning.
bool prefetching_enabled ()
 Returns the status of leaf prefetching during scanning.
void print_statistics (std::ostream &o) const
 Prints cache statistics.
void reset_statistics ()
 Resets cache statistics.

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.

Template Parameters:
KeyType key type (POD with no references to internal memory)
DataType data type (POD with no references to internal memory)
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 max_value method, that returns a value of type KeyType that is larger than any key stored in map : i.e. for all x in map holds CompareType()(x,CompareType::max_value())


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:
RawNodeSize size of internal nodes of map in bytes (btree implementation).
RawLeafSize size of leaves of map in bytes (btree implementation).
PDAllocStrategy parallel 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_bytes size of node cache in bytes (btree implementation)
leaf_cache_size_in_bytes size 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_bytes size of node cache in bytes (btree implementation)
leaf_cache_size_in_bytes size 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:
b beginning of the range
e end of the range
node_cache_size_in_bytes size of node cache in bytes (btree implementation)
leaf_cache_size_in_bytes size of leaf cache in bytes (btree implementation)
range_sorted if 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_factor node fill factor in [0,1] for bulk construction
leaf_fill_factor leaf 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:
b beginning of the range
e end of the range
c_ comparator object
node_cache_size_in_bytes size of node cache in bytes (btree implementation)
leaf_cache_size_in_bytes size of leaf cache in bytes (btree implementation)
range_sorted if 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_factor node fill factor in [0,1] for bulk construction
leaf_fill_factor leaf 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:
Generated by  doxygen 1.7.1