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

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:

map.h

Public Types

Public Member Functions

Friends

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 >

Constructor & Destructor Documentation

Member Function Documentation

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 >