STX B+ Tree Template Classes: stx::btree_multimap< _Key, _Data, _Compare,

List of all members.


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 btree_multimap < key_type, data_type, key_compare, traits >	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, true >	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_multimap ()
	Default constructor initializing an empty B+ tree with the standard key comparison function.
	btree_multimap (const key_compare &kcf)
	Constructor initializing an empty B+ tree with a special key comparison object.
template<class InputIterator>
	btree_multimap (InputIterator first, InputIterator last)
	Constructor initializing a B+ tree with the range [first,last).
template<class InputIterator>
	btree_multimap (InputIterator first, InputIterator last, const key_compare &kcf)
	Constructor initializing a B+ tree with the range [first,last) and a special key comparison object.
	~btree_multimap ()
	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.
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 key less or equal to the parameter.
const_iterator	lower_bound (const key_type &key) const
	Searches the B+ tree and returns an constant iterator to the first key less or equal to the parameter.
iterator	upper_bound (const key_type &key)
	Searches the B+ tree and returns an iterator to the first key greater than the parameter.
const_iterator	upper_bound (const key_type &key) const
	Searches the B+ tree and returns an constant iterator to the first key greater than the parameter.
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_multimap (const self &other)
	Copy constructor.
iterator	insert (const value_type &x)
	Attempt to insert a key/data pair into the B+ tree.
iterator	insert (const key_type &key, const data_type &data)
	Attempt to insert a key/data pair into the B+ tree.
iterator	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.
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 one (the first) of 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>>
class stx::btree_multimap< _Key, _Data, _Compare, _Traits >

Implements the STL multimap using a B+ tree. It can be used as a drop-in replacement for std::multimap. Not all asymptotic time requirements are met in theory. There is no allocator template parameter, instead the class has a traits class defining B+ tree properties like slots and self-verification.

Most noteworthy difference to the default red-black implementation of std::multimap 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.

Member Typedef Documentation