Specialized B+ tree template class implementing STL's map container. More...

#include <btree_map.h>

Public Types
typedef _Key	key_type
	First template parameter: The key type of the btree.
typedef _Data	data_type
	Second template parameter: The data type associated with each key.
typedef _Compare	key_compare
	Third template parameter: Key comparison function object.
typedef _Traits	traits
	Fourth template parameter: Traits object used to define more parameters of the B+ tree.
typedef _Alloc	allocator_type
	Fifth template parameter: STL allocator.
typedef btree_map< key_type, data_type, key_compare, traits, allocator_type >	self
	Typedef of our own type.
typedef std::pair< key_type, data_type >	value_type
	Construct the STL-required value_type as a composition pair of key and data types.
typedef stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >	btree_impl
	Implementation type of the btree_base.
typedef btree_impl::value_compare	value_compare
	Function class comparing two value_type pairs.
typedef btree_impl::size_type	size_type
	Size type used to count keys.
typedef btree_impl::tree_stats	tree_stats
	Small structure containing statistics about the tree.
typedef btree_impl::iterator	iterator
	STL-like iterator object for B+ tree items.
typedef btree_impl::const_iterator	const_iterator
	STL-like iterator object for B+ tree items.
typedef btree_impl::reverse_iterator	reverse_iterator
	create mutable reverse iterator by using STL magic
typedef btree_impl::const_reverse_iterator	const_reverse_iterator
	create constant reverse iterator by using STL magic
Public Member Functions
	btree_map (const allocator_type &alloc=allocator_type())
	Default constructor initializing an empty B+ tree with the standard key comparison function.
	btree_map (const key_compare &kcf, const allocator_type &alloc=allocator_type())
	Constructor initializing an empty B+ tree with a special key comparison object.
template<class InputIterator >
	btree_map (InputIterator first, InputIterator last, const allocator_type &alloc=allocator_type())
	Constructor initializing a B+ tree with the range [first,last)
template<class InputIterator >
	btree_map (InputIterator first, InputIterator last, const key_compare &kcf, const allocator_type &alloc=allocator_type())
	Constructor initializing a B+ tree with the range [first,last) and a special key comparison object.
	~btree_map ()
	Frees up all used B+ tree memory pages.
void	swap (self &from)
	Fast swapping of two identical B+ tree objects.
key_compare	key_comp () const
	Constant access to the key comparison object sorting the B+ tree.
value_compare	value_comp () const
	Constant access to a constructed value_type comparison object.
allocator_type	get_allocator () const
	Return the base node allocator provided during construction.
void	clear ()
	Frees all key/data pairs and all nodes of the tree.
iterator	begin ()
	Constructs a read/data-write iterator that points to the first slot in the first leaf of the B+ tree.
iterator	end ()
	Constructs a read/data-write iterator that points to the first invalid slot in the last leaf of the B+ tree.
const_iterator	begin () const
	Constructs a read-only constant iterator that points to the first slot in the first leaf of the B+ tree.
const_iterator	end () const
	Constructs a read-only constant iterator that points to the first invalid slot in the last leaf of the B+ tree.
reverse_iterator	rbegin ()
	Constructs a read/data-write reverse iterator that points to the first invalid slot in the last leaf of the B+ tree.
reverse_iterator	rend ()
	Constructs a read/data-write reverse iterator that points to the first slot in the first leaf of the B+ tree.
const_reverse_iterator	rbegin () const
	Constructs a read-only reverse iterator that points to the first invalid slot in the last leaf of the B+ tree.
const_reverse_iterator	rend () const
	Constructs a read-only reverse iterator that points to the first slot in the first leaf of the B+ tree.
size_type	size () const
	Return the number of key/data pairs in the B+ tree.
bool	empty () const
	Returns true if there is at least one key/data pair in the B+ tree.
size_type	max_size () const
	Returns the largest possible size of the B+ Tree.
const tree_stats &	get_stats () const
	Return a const reference to the current statistics.
bool	exists (const key_type &key) const
	Non-STL function checking whether a key is in the B+ tree.
iterator	find (const key_type &key)
	Tries to locate a key in the B+ tree and returns an iterator to the key/data slot if found.
const_iterator	find (const key_type &key) const
	Tries to locate a key in the B+ tree and returns an constant iterator to the key/data slot if found.
size_type	count (const key_type &key) const
	Tries to locate a key in the B+ tree and returns the number of identical key entries found.
iterator	lower_bound (const key_type &key)
	Searches the B+ tree and returns an iterator to the first pair equal to or greater than key, or end() if all keys are smaller.
const_iterator	lower_bound (const key_type &key) const
	Searches the B+ tree and returns a constant iterator to the first pair equal to or greater than key, or end() if all keys are smaller.
iterator	upper_bound (const key_type &key)
	Searches the B+ tree and returns an iterator to the first pair greater than key, or end() if all keys are smaller or equal.
const_iterator	upper_bound (const key_type &key) const
	Searches the B+ tree and returns a constant iterator to the first pair greater than key, or end() if all keys are smaller or equal.
std::pair< iterator, iterator >	equal_range (const key_type &key)
	Searches the B+ tree and returns both lower_bound() and upper_bound().
std::pair< const_iterator, const_iterator >	equal_range (const key_type &key) const
	Searches the B+ tree and returns both lower_bound() and upper_bound().
bool	operator== (const self &other) const
	Equality relation of B+ trees of the same type.
bool	operator!= (const self &other) const
	Inequality relation. Based on operator==.
bool	operator< (const self &other) const
	Total ordering relation of B+ trees of the same type.
bool	operator> (const self &other) const
	Greater relation. Based on operator<.
bool	operator<= (const self &other) const
	Less-equal relation. Based on operator<.
bool	operator>= (const self &other) const
	Greater-equal relation. Based on operator<.
self &	operator= (const self &other)
	*** Fast Copy: Assign Operator and Copy Constructors
	btree_map (const self &other)
	Copy constructor.
std::pair< iterator, bool >	insert (const value_type &x)
	Attempt to insert a key/data pair into the B+ tree.
std::pair< iterator, bool >	insert (const key_type &key, const data_type &data)
	Attempt to insert a key/data pair into the B+ tree.
std::pair< iterator, bool >	insert2 (const key_type &key, const data_type &data)
	Attempt to insert a key/data pair into the B+ tree.
iterator	insert (iterator hint, const value_type &x)
	Attempt to insert a key/data pair into the B+ tree.
iterator	insert2 (iterator hint, const key_type &key, const data_type &data)
	Attempt to insert a key/data pair into the B+ tree.
data_type &	operator[] (const key_type &key)
	Returns a reference to the object that is associated with a particular key.
template<typename InputIterator >
void	insert (InputIterator first, InputIterator last)
	Attempt to insert the range [first,last) of value_type pairs into the B+ tree.
bool	erase_one (const key_type &key)
	Erases the key/data pairs associated with the given key.
size_type	erase (const key_type &key)
	Erases all the key/data pairs associated with the given key.
void	erase (iterator iter)
	Erase the key/data pair referenced by the iterator.
void	erase (iterator, iterator)
	Erase all key/data pairs in the range [first,last).
void	print (std::ostream &os) const
	Print out the B+ tree structure with keys onto the given ostream.
void	print_leaves (std::ostream &os) const
	Print out only the leaves via the double linked list.
void	verify () const
	Run a thorough verification of all B+ tree invariants.
void	dump (std::ostream &os) const
	Dump the contents of the B+ tree out onto an ostream as a binary image.
bool	restore (std::istream &is)
	Restore a binary image of a dumped B+ tree from an istream.
Static Public Attributes
static const unsigned short	leafslotmax = btree_impl::leafslotmax
	Base B+ tree parameter: The number of key/data slots in each leaf.
static const unsigned short	innerslotmax = btree_impl::innerslotmax
	Base B+ tree parameter: The number of key slots in each inner node, this can differ from slots in each leaf.
static const unsigned short	minleafslots = btree_impl::minleafslots
	Computed B+ tree parameter: The minimum number of key/data slots used in a leaf.
static const unsigned short	mininnerslots = btree_impl::mininnerslots
	Computed B+ tree parameter: The minimum number of key slots used in an inner node.
static const bool	selfverify = btree_impl::selfverify
	Debug parameter: Enables expensive and thorough checking of the B+ tree invariants after each insert/erase operation.
static const bool	debug = btree_impl::debug
	Debug parameter: Prints out lots of debug information about how the algorithms change the tree.
static const bool	allow_duplicates = btree_impl::allow_duplicates
	Operational parameter: Allow duplicate keys in the btree.
Private Attributes
btree_impl	tree
	The contained implementation object.

Detailed Description

template<typename _Key, typename _Data, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>
class stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >

Specialized B+ tree template class implementing STL's map container.

Implements the STL map using a B+ tree. It can be used as a drop-in replacement for std::map. Not all asymptotic time requirements are met in theory. The class has a traits class defining B+ tree properties like slots and self-verification. Furthermore an allocator can be specified for tree nodes.

Most noteworthy difference to the default red-black implementation of std::map is that the B+ tree does not hold key and data pair together in memory. Instead each B+ tree node has two arrays of keys and data values. This design directly generates many problems in implementing the iterator's operator's which return value_type composition pairs.

Definition at line 50 of file btree_map.h.

Member Typedef Documentation

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

typedef _Alloc stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::allocator_type

Fifth template parameter: STL allocator.

Definition at line 71 of file btree_map.h.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

typedef stx::btree<key_type, data_type, value_type, key_compare, traits, false, allocator_type> stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::btree_impl

Implementation type of the btree_base.

Definition at line 89 of file btree_map.h.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

typedef btree_impl::const_iterator stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::const_iterator

STL-like iterator object for B+ tree items.

The iterator points to a specific slot number in a leaf.

Definition at line 141 of file btree_map.h.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

typedef btree_impl::const_reverse_iterator stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::const_reverse_iterator

create constant reverse iterator by using STL magic

Definition at line 147 of file btree_map.h.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

typedef _Data stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::data_type

Second template parameter: The data type associated with each key.

Stored in the B+ tree's leaves

Definition at line 61 of file btree_map.h.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

typedef btree_impl::iterator stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::iterator

STL-like iterator object for B+ tree items.

The iterator points to a specific slot number in a leaf.

Definition at line 137 of file btree_map.h.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

typedef _Compare stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::key_compare

Third template parameter: Key comparison function object.

Definition at line 64 of file btree_map.h.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

typedef _Key stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::key_type

First template parameter: The key type of the btree.

This is stored in inner nodes and leaves

Definition at line 57 of file btree_map.h.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

typedef btree_impl::reverse_iterator stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::reverse_iterator

create mutable reverse iterator by using STL magic

Definition at line 144 of file btree_map.h.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

typedef btree_map<key_type, data_type, key_compare, traits, allocator_type> stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::self

Typedef of our own type.

Definition at line 82 of file btree_map.h.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

typedef btree_impl::size_type stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::size_type

Size type used to count keys.

Definition at line 95 of file btree_map.h.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

typedef _Traits stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::traits

Fourth template parameter: Traits object used to define more parameters of the B+ tree.

Definition at line 68 of file btree_map.h.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

typedef btree_impl::tree_stats stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::tree_stats

Small structure containing statistics about the tree.

Definition at line 98 of file btree_map.h.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

typedef btree_impl::value_compare stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::value_compare

Function class comparing two value_type pairs.

Definition at line 92 of file btree_map.h.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

typedef std::pair<key_type, data_type> stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::value_type

Construct the STL-required value_type as a composition pair of key and data types.

Definition at line 86 of file btree_map.h.

Constructor & Destructor Documentation

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::btree_map ( const allocator_type & alloc = allocator_type() ) [inline, explicit]

Default constructor initializing an empty B+ tree with the standard key comparison function.

Definition at line 160 of file btree_map.h.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::btree_map	(	const key_compare &	kcf,
		const allocator_type &	alloc = `allocator_type()`
	)		`[inline, explicit]`

Constructor initializing an empty B+ tree with a special key comparison object.

Definition at line 167 of file btree_map.h.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

template<class InputIterator >

stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::btree_map	(	InputIterator	first,
		InputIterator	last,
		const allocator_type &	alloc = `allocator_type()`
	)		`[inline]`

Constructor initializing a B+ tree with the range [first,last)

Definition at line 175 of file btree_map.h.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

template<class InputIterator >

stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::btree_map	(	InputIterator	first,
		InputIterator	last,
		const key_compare &	kcf,
		const allocator_type &	alloc = `allocator_type()`
	)		`[inline]`

Constructor initializing a B+ tree with the range [first,last) and a special key comparison object.

Definition at line 184 of file btree_map.h.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::~btree_map ( ) [inline]

Frees up all used B+ tree memory pages.

Definition at line 191 of file btree_map.h.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::btree_map ( const self & other ) [inline]

Copy constructor.

The newly initialized B+ tree object will contain a copy of all key/data pairs.

Definition at line 453 of file btree_map.h.

Member Function Documentation

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

iterator stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::begin ( ) [inline]

Constructs a read/data-write iterator that points to the first slot in the first leaf of the B+ tree.

Definition at line 240 of file btree_map.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::begin(), and stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

const_iterator stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::begin ( ) const [inline]

Constructs a read-only constant iterator that points to the first slot in the first leaf of the B+ tree.

Definition at line 254 of file btree_map.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::begin(), and stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

void stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::clear ( ) [inline]

Frees all key/data pairs and all nodes of the tree.

Definition at line 230 of file btree_map.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::clear(), and stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

size_type stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::count ( const key_type & key ) const [inline]

Tries to locate a key in the B+ tree and returns the number of identical key entries found.

Since this is a unique map, count() returns either 0 or 1.

Definition at line 349 of file btree_map.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::count(), and stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

void stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::dump ( std::ostream & os ) const [inline]

Dump the contents of the B+ tree out onto an ostream as a binary image.

The image contains memory pointers which will be fixed when the image is restored. For this to work your key_type and data_type must be integral types and contain no pointers or references.

Definition at line 583 of file btree_map.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::dump(), and stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

bool stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::empty ( ) const [inline]

Returns true if there is at least one key/data pair in the B+ tree.

Definition at line 304 of file btree_map.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::empty(), and stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

const_iterator stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::end ( ) const [inline]

Constructs a read-only constant iterator that points to the first invalid slot in the last leaf of the B+ tree.

Definition at line 261 of file btree_map.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::end(), and stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

iterator stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::end ( ) [inline]

Constructs a read/data-write iterator that points to the first invalid slot in the last leaf of the B+ tree.

Definition at line 247 of file btree_map.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::end(), and stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

std::pair<iterator, iterator> stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::equal_range ( const key_type & key ) [inline]

Searches the B+ tree and returns both lower_bound() and upper_bound().

Definition at line 385 of file btree_map.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::equal_range(), and stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

std::pair<const_iterator, const_iterator> stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::equal_range ( const key_type & key ) const [inline]

Searches the B+ tree and returns both lower_bound() and upper_bound().

Definition at line 391 of file btree_map.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::equal_range(), and stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

size_type stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::erase ( const key_type & key ) [inline]

Erases all the key/data pairs associated with the given key.

This is implemented using erase_one().

Definition at line 528 of file btree_map.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::erase(), and stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

void stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::erase ( iterator iter ) [inline]

Erase the key/data pair referenced by the iterator.

Definition at line 534 of file btree_map.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::erase(), and stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

void stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::erase	(	iterator	,
		iterator
	)		`[inline]`

Erase all key/data pairs in the range [first,last).

This function is currently not implemented by the B+ Tree.

Definition at line 542 of file btree_map.h.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

bool stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::erase_one ( const key_type & key ) [inline]

Erases the key/data pairs associated with the given key.

For this unique-associative map there is no difference to erase().

Definition at line 521 of file btree_map.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::erase_one(), and stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

bool stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::exists ( const key_type & key ) const [inline]

Non-STL function checking whether a key is in the B+ tree.

The same as (find(k) != end()) or (count() != 0).

Definition at line 327 of file btree_map.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::exists(), and stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

iterator stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::find ( const key_type & key ) [inline]

Tries to locate a key in the B+ tree and returns an iterator to the key/data slot if found.

If unsuccessful it returns end().

Definition at line 334 of file btree_map.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::find(), and stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

const_iterator stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::find ( const key_type & key ) const [inline]

Tries to locate a key in the B+ tree and returns an constant iterator to the key/data slot if found.

If unsuccessful it returns end().

Definition at line 341 of file btree_map.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::find(), and stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

allocator_type stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::get_allocator ( ) const [inline]

Return the base node allocator provided during construction.

Definition at line 221 of file btree_map.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::get_allocator(), and stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

const tree_stats& stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::get_stats ( ) const [inline]

Return a const reference to the current statistics.

Definition at line 317 of file btree_map.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::get_stats(), and stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

std::pair<iterator, bool> stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::insert ( const value_type & x ) [inline]

Attempt to insert a key/data pair into the B+ tree.

Fails if the pair is already present.

Definition at line 463 of file btree_map.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::insert2(), and stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::tree.

Referenced by stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::operator[]().

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

std::pair<iterator, bool> stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::insert	(	const key_type &	key,
		const data_type &	data
	)		`[inline]`

Attempt to insert a key/data pair into the B+ tree.

Beware that if key_type == data_type, then the template iterator insert() is called instead. Fails if the inserted pair is already present.

Definition at line 471 of file btree_map.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::insert2(), and stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

iterator stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::insert	(	iterator	hint,
		const value_type &	x
	)		`[inline]`

Attempt to insert a key/data pair into the B+ tree.

The iterator hint is currently ignored by the B+ tree insertion routine.

Definition at line 487 of file btree_map.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::insert2(), and stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

template<typename InputIterator >

void stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::insert	(	InputIterator	first,
		InputIterator	last
	)		`[inline]`

Attempt to insert the range [first,last) of value_type pairs into the B+ tree.

Each key/data pair is inserted individually.

Definition at line 511 of file btree_map.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::insert(), and stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

std::pair<iterator, bool> stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::insert2	(	const key_type &	key,
		const data_type &	data
	)		`[inline]`

Attempt to insert a key/data pair into the B+ tree.

This function is the same as the other insert, however if key_type == data_type then the non-template function cannot be called. Fails if the inserted pair is already present.

Definition at line 480 of file btree_map.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::insert2(), and stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

iterator stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::insert2	(	iterator	hint,
		const key_type &	key,
		const data_type &	data
	)		`[inline]`

Attempt to insert a key/data pair into the B+ tree.

The iterator hint is currently ignored by the B+ tree insertion routine.

Definition at line 494 of file btree_map.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::insert2(), and stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

key_compare stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::key_comp ( ) const [inline]

Constant access to the key comparison object sorting the B+ tree.

Definition at line 205 of file btree_map.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::key_comp(), and stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

iterator stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::lower_bound ( const key_type & key ) [inline]

Searches the B+ tree and returns an iterator to the first pair equal to or greater than key, or end() if all keys are smaller.

Definition at line 356 of file btree_map.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::lower_bound(), and stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

const_iterator stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::lower_bound ( const key_type & key ) const [inline]

Searches the B+ tree and returns a constant iterator to the first pair equal to or greater than key, or end() if all keys are smaller.

Definition at line 364 of file btree_map.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::lower_bound(), and stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

size_type stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::max_size ( ) const [inline]

Returns the largest possible size of the B+ Tree.

This is just a function required by the STL standard, the B+ Tree can hold more items.

Definition at line 311 of file btree_map.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::max_size(), and stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

bool stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::operator!= ( const self & other ) const [inline]

Inequality relation. Based on operator==.

Definition at line 408 of file btree_map.h.

References stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

bool stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::operator< ( const self & other ) const [inline]

Total ordering relation of B+ trees of the same type.

It uses std::lexicographical_compare() for the actual comparison of elements.

Definition at line 415 of file btree_map.h.

References stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

bool stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::operator<= ( const self & other ) const [inline]

Less-equal relation. Based on operator<.

Definition at line 427 of file btree_map.h.

References stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

self& stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::operator= ( const self & other ) [inline]

*** Fast Copy: Assign Operator and Copy Constructors

Assignment operator. All the key/data pairs are copied

Definition at line 442 of file btree_map.h.

References stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

bool stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::operator== ( const self & other ) const [inline]

Equality relation of B+ trees of the same type.

B+ trees of the same size and equal elements (both key and data) are considered equal.

Definition at line 402 of file btree_map.h.

References stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

bool stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::operator> ( const self & other ) const [inline]

Greater relation. Based on operator<.

Definition at line 421 of file btree_map.h.

References stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

bool stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::operator>= ( const self & other ) const [inline]

Greater-equal relation. Based on operator<.

Definition at line 433 of file btree_map.h.

References stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Data , typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, typename _Alloc = std::allocator<std::pair<_Key, _Data> >>

data_type& stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::operator[] ( const key_type & key ) [inline]

Returns a reference to the object "paramr[]" ref="ab3268177427359a66c11b7f641bb99ae" args="(const key_type &key)" -->