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

#include <btree_map.hpp>

Classes
struct	key_of_value
	Key Extractor Struct. More...

Public Types
Template Parameter Types
typedef Key_	key_type
	First template parameter: The key type of the btree. More...

typedef Data_	data_type
	Second template parameter: The value type associated with each key. More...

typedef Compare_	key_compare
	Third template parameter: Key comparison function object. More...

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

typedef Alloc_	allocator_type
	Fifth template parameter: STL allocator. More...

Constructed Types
typedef btree_map< key_type, data_type, key_compare, traits, allocator_type >	self
	Typedef of our own type. More...

typedef std::pair< key_type, data_type >	value_type
	Construct the STL-required value_type as a composition pair of key and data types. More...

typedef BTree< key_type, value_type, key_of_value, key_compare, traits, false, allocator_type >	btree_impl
	Implementation type of the btree_base. More...

typedef btree_impl::value_compare	value_compare
	Function class comparing two value_type pairs. More...

typedef btree_impl::size_type	size_type
	Size type used to count keys. More...

typedef btree_impl::tree_stats	tree_stats
	Small structure containing statistics about the tree. More...

Iterators and Reverse Iterators
typedef btree_impl::iterator	iterator
	STL-like iterator object for B+ tree items. More...

typedef btree_impl::const_iterator	const_iterator
	STL-like iterator object for B+ tree items. More...

typedef btree_impl::reverse_iterator	reverse_iterator
	create mutable reverse iterator by using STL magic More...

typedef btree_impl::const_reverse_iterator	const_reverse_iterator
	create constant reverse iterator by using STL magic More...

Public Member Functions
Constructors and Destructor
	btree_map (const allocator_type &alloc=allocator_type())
	Default constructor initializing an empty B+ tree with the standard key comparison function. More...

	btree_map (const key_compare &kcf, const allocator_type &alloc=allocator_type())
	Constructor initializing an empty B+ tree with a special key comparison object. More...

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) More...

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. More...

	~btree_map ()
	Frees up all used B+ tree memory pages. More...

void	swap (btree_map &from)
	Fast swapping of two identical B+ tree objects. More...

Key and Value Comparison Function Objects
key_compare	key_comp () const
	Constant access to the key comparison object sorting the B+ tree. More...

value_compare	value_comp () const
	Constant access to a constructed value_type comparison object. More...

Allocators
allocator_type	get_allocator () const
	Return the base node allocator provided during construction. More...

Fast Destruction of the B+ Tree
void	clear ()
	Frees all key/data pairs and all nodes of the tree. More...

STL Iterator Construction Functions
iterator	begin ()
	Constructs a read/data-write iterator that points to the first slot in the first leaf of the B+ tree. More...

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

const_iterator	begin () const
	Constructs a read-only constant iterator that points to the first slot in the first leaf of the B+ tree. More...

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. More...

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. More...

reverse_iterator	rend ()
	Constructs a read/data-write reverse iterator that points to the first slot in the first leaf of the B+ tree. More...

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. More...

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. More...

Access Functions to the Item Count
size_type	size () const
	Return the number of key/data pairs in the B+ tree. More...

bool	empty () const
	Returns true if there is at least one key/data pair in the B+ tree. More...

size_type	max_size () const
	Returns the largest possible size of the B+ Tree. More...

const tree_stats &	get_stats () const
	Return a const reference to the current statistics. More...

STL Access Functions Querying the Tree by Descending to a Leaf
bool	exists (const key_type &key) const
	Non-STL function checking whether a key is in the B+ tree. More...

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. More...

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. More...

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. More...

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. More...

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. More...

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. More...

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. More...

std::pair< iterator, iterator >	equal_range (const key_type &key)
	Searches the B+ tree and returns both lower_bound() and upper_bound(). More...

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(). More...

B+ Tree Object Comparison Functions
bool	operator== (const btree_map &other) const
	Equality relation of B+ trees of the same type. More...

bool	operator!= (const btree_map &other) const
	Inequality relation. Based on operator==. More...

bool	operator< (const btree_map &other) const
	Total ordering relation of B+ trees of the same type. More...

bool	operator> (const btree_map &other) const
	Greater relation. Based on operator<. More...

bool	operator<= (const btree_map &other) const
	Less-equal relation. Based on operator<. More...

bool	operator>= (const btree_map &other) const
	Greater-equal relation. Based on operator<. More...

Fast Copy: Assign Operator and Copy Constructors
btree_map &	operator= (const btree_map &other)
	Assignment operator. All the key/data pairs are copied. More...

	btree_map (const btree_map &other)
	Copy constructor. More...

Public Insertion Functions
std::pair< iterator, bool >	insert (const value_type &x)
	Attempt to insert a key/data pair into the B+ tree. More...

std::pair< iterator, bool >	insert2 (const key_type &key, const data_type &data)
	Attempt to insert a key/data pair into the B+ tree. More...

iterator	insert (iterator hint, const value_type &x)
	Attempt to insert a key/data pair into the B+ tree. More...

iterator	insert2 (iterator hint, const key_type &key, const data_type &data)
	Attempt to insert a key/data pair into the B+ tree. More...

data_type &	operator[] (const key_type &key)
	Returns a reference to the object that is associated with a particular key. More...

template<typename InputIterator >
void	insert (InputIterator first, InputIterator last)
	Attempt to insert the range [first,last) of value_type pairs into the B+ tree. More...

template<typename Iterator >
void	bulk_load (Iterator first, Iterator last)
	Bulk load a sorted range [first,last). More...

Public Erase Functions
bool	erase_one (const key_type &key)
	Erases the key/data pairs associated with the given key. More...

size_type	erase (const key_type &key)
	Erases all the key/data pairs associated with the given key. More...

void	erase (iterator iter)
	Erase the key/data pair referenced by the iterator. More...

Verification of B+ Tree Invariants
void	verify () const
	Run a thorough verification of all B+ tree invariants. More...

Public Attributes
	TLX_BTREE_FRIENDS

Static Public Attributes
Static Constant Options and Values of the B+ Tree
static const unsigned short	leaf_slotmax
	Base B+ tree parameter: The number of key/data slots in each leaf. More...

static const unsigned short	inner_slotmax
	Base B+ tree parameter: The number of key slots in each inner node, this can differ from slots in each leaf. More...

static const unsigned short	leaf_slotmin
	Computed B+ tree parameter: The minimum number of key/data slots used in a leaf. More...

static const unsigned short	inner_slotmin
	Computed B+ tree parameter: The minimum number of key slots used in an inner node. More...

static const bool	self_verify
	Debug parameter: Enables expensive and thorough checking of the B+ tree invariants after each insert/erase operation. More...

static const bool	debug
	Debug parameter: Prints out lots of debug information about how the algorithms change the tree. More...

static const bool	allow_duplicates
	Operational parameter: Allow duplicate keys in the btree. More...

Private Attributes
Tree Implementation Object
btree_impl	tree_
	The contained implementation object. More...

Detailed Description

template<typename Key_, typename Data_, typename Compare_ = std::less<Key_>, typename Traits_ = btree_default_traits<Key_, std::pair<Key_, Data_> >, typename Alloc_ = std::allocator<std::pair<Key_, Data_> >>
class tlx::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.

Definition at line 39 of file btree_map.hpp.

Member Typedef Documentation

typedef Alloc_ allocator_type

Fifth template parameter: STL allocator.

Definition at line 61 of file btree_map.hpp.

typedef BTree<key_type, value_type, key_of_value, key_compare, traits, false, allocator_type> btree_impl

Implementation type of the btree_base.

Definition at line 90 of file btree_map.hpp.

typedef btree_impl::const_iterator const_iterator

STL-like iterator object for B+ tree items.

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

Definition at line 148 of file btree_map.hpp.

typedef btree_impl::const_reverse_iterator const_reverse_iterator

create constant reverse iterator by using STL magic

Definition at line 154 of file btree_map.hpp.

typedef Data_ data_type

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

Stored in the B+ tree's leaves

Definition at line 51 of file btree_map.hpp.

typedef btree_impl::iterator iterator

STL-like iterator object for B+ tree items.

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

Definition at line 144 of file btree_map.hpp.

typedef Compare_ key_compare

Third template parameter: Key comparison function object.

Definition at line 54 of file btree_map.hpp.

typedef Key_ key_type

First template parameter: The key type of the btree.

This is stored in inner nodes.

Definition at line 47 of file btree_map.hpp.

typedef btree_impl::reverse_iterator reverse_iterator

create mutable reverse iterator by using STL magic

Definition at line 151 of file btree_map.hpp.

typedef btree_map<key_type, data_type, key_compare, traits, allocator_type> self

Typedef of our own type.

Definition at line 76 of file btree_map.hpp.

typedef btree_impl::size_type size_type

Size type used to count keys.

Definition at line 96 of file btree_map.hpp.

typedef Traits_ traits

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

Definition at line 58 of file btree_map.hpp.

typedef btree_impl::tree_stats tree_stats

Small structure containing statistics about the tree.

Definition at line 99 of file btree_map.hpp.

typedef btree_impl::value_compare value_compare

Function class comparing two value_type pairs.

Definition at line 93 of file btree_map.hpp.

typedef std::pair<key_type, data_type> value_type

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

Definition at line 80 of file btree_map.hpp.

Constructor & Destructor Documentation

btree_map ( const allocator_type & alloc = allocator_type() )

inlineexplicit

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

Definition at line 173 of file btree_map.hpp.

btree_map	(	const key_compare &	kcf,
		const allocator_type &	alloc = `allocator_type()`
	)

inlineexplicit

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

Definition at line 179 of file btree_map.hpp.

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 186 of file btree_map.hpp.

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 194 of file btree_map.hpp.

~btree_map ( )

inline

Frees up all used B+ tree memory pages.

Definition at line 200 of file btree_map.hpp.

btree_map ( const btree_map< Key_, Data_, Compare_, Traits_, Alloc_ > & other )

inline

Copy constructor.

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

Definition at line 447 of file btree_map.hpp.

Member Function Documentation

iterator 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 255 of file btree_map.hpp.

const_iterator 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 267 of file btree_map.hpp.

void bulk_load	(	Iterator	first,
		Iterator	last
	)

inline

Bulk load a sorted range [first,last).

Loads items into leaves and constructs a B-tree above them. The tree must be empty when calling this function.

Definition at line 502 of file btree_map.hpp.

void clear ( )

inline

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

Definition at line 243 of file btree_map.hpp.

size_type 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 355 of file btree_map.hpp.

bool empty ( ) const

inline

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

Definition at line 313 of file btree_map.hpp.

iterator 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 261 of file btree_map.hpp.

const_iterator 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 273 of file btree_map.hpp.

std::pair<iterator, iterator> equal_range ( const key_type & key )

inline

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

Definition at line 384 of file btree_map.hpp.

std::pair<const_iterator, const_iterator> equal_range ( const key_type & key ) const

inline

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

Definition at line 390 of file btree_map.hpp.

size_type 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 520 of file btree_map.hpp.

void erase ( iterator iter )

inline

Erase the key/data pair referenced by the iterator.

Definition at line 525 of file btree_map.hpp.

bool 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 514 of file btree_map.hpp.

bool 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 336 of file btree_map.hpp.

iterator 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 342 of file btree_map.hpp.

const_iterator 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 348 of file btree_map.hpp.

allocator_type get_allocator ( ) const

inline

Return the base node allocator provided during construction.

Definition at line 232 of file btree_map.hpp.

const tree_stats& get_stats ( ) const

inline

Return a const reference to the current statistics.

Definition at line 324 of file btree_map.hpp.

std::pair<iterator, bool> 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 459 of file btree_map.hpp.

iterator 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 472 of file btree_map.hpp.

void 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 494 of file btree_map.hpp.

std::pair<iterator, bool> 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. Fails if the inserted pair is already present.

Definition at line 465 of file btree_map.hpp.

iterator 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 478 of file btree_map.hpp.

key_compare key_comp ( ) const

inline

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

Definition at line 215 of file btree_map.hpp.

iterator 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 361 of file btree_map.hpp.

const_iterator 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 367 of file btree_map.hpp.

size_type 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 319 of file btree_map.hpp.

bool operator!= ( const btree_map< Key_, Data_, Compare_, Traits_, Alloc_ > & other ) const

inline

Inequality relation. Based on operator==.

Definition at line 407 of file btree_map.hpp.

bool operator< ( const btree_map< Key_, Data_, Compare_, Traits_, Alloc_ > & 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 413 of file btree_map.hpp.

bool operator<= ( const btree_map< Key_, Data_, Compare_, Traits_, Alloc_ > & other ) const

inline

Less-equal relation. Based on operator<.

Definition at line 423 of file btree_map.hpp.

btree_map& operator= ( const btree_map< Key_, Data_, Compare_, Traits_, Alloc_ > & other )

inline

Assignment operator. All the key/data pairs are copied.

Definition at line 439 of file btree_map.hpp.

bool operator== ( const btree_map< Key_, Data_, Compare_, Traits_, Alloc_ > & 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.hpp.

bool operator> ( const btree_map< Key_, Data_, Compare_, Traits_, Alloc_ > & other ) const

inline

Greater relation. Based on operator<.

Definition at line 418 of file btree_map.hpp.

bool operator>= ( const btree_map< Key_, Data_, Compare_, Traits_, Alloc_ > & other ) const

inline

Greater-equal relation. Based on operator<.

Definition at line 428 of file btree_map.hpp.

data_type& operator[] ( const key_type & key )

inline

Returns a reference to the object that is associated with a particular key.

If the map does not already contain such an object, operator[] inserts the default object data_type().

Definition at line 486 of file btree_map.hpp.

reverse_iterator rbegin ( )

inline

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

Uses STL magic.

Definition at line 279 of file btree_map.hpp.

const_reverse_iterator rbegin ( ) const

inline

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

Uses STL magic.

Definition at line 291 of file btree_map.hpp.

reverse_iterator rend ( )

inline

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

Uses STL magic.

Definition at line 285 of file btree_map.hpp.

const_reverse_iterator rend ( ) const

inline

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

Uses STL magic.

Definition at line 297 of file btree_map.hpp.

size_type size ( ) const

inline

Return the number of key/data pairs in the B+ tree.

Definition at line 308 of file btree_map.hpp.

void swap ( btree_map< Key_, Data_, Compare_, Traits_, Alloc_ > & from )

inline

Fast swapping of two identical B+ tree objects.

Definition at line 204 of file btree_map.hpp.

iterator upper_bound ( const key_type & key )

inline

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

Definition at line 373 of file btree_map.hpp.

const_iterator upper_bound ( const key_type & key ) const

inline

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.

Definition at line 379 of file btree_map.hpp.

value_compare value_comp ( ) const

inline

Constant access to a constructed value_type comparison object.

required by the STL

Definition at line 221 of file btree_map.hpp.

void verify ( ) const

inline

Run a thorough verification of all B+ tree invariants.

The program aborts via TLX_BTREE_ASSERT() if something is wrong.

Definition at line 566 of file btree_map.hpp.

Member Data Documentation

const bool allow_duplicates

static

Operational parameter: Allow duplicate keys in the btree.

Definition at line 134 of file btree_map.hpp.

const bool debug

static

Debug parameter: Prints out lots of debug information about how the algorithms change the tree.

Requires the header file to be compiled with TLX_BTREE_DEBUG and the key type must be std::ostream printable.

Definition at line 131 of file btree_map.hpp.

const unsigned short inner_slotmax

static

Base B+ tree parameter: The number of key slots in each inner node, this can differ from slots in each leaf.

Definition at line 112 of file btree_map.hpp.

const unsigned short inner_slotmin

static

Computed B+ tree parameter: The minimum number of key slots used in an inner node.

If fewer slots are used, the inner node will be merged or slots shifted from it's siblings.

Definition at line 122 of file btree_map.hpp.

const unsigned short leaf_slotmax

static

Base B+ tree parameter: The number of key/data slots in each leaf.

Definition at line 108 of file btree_map.hpp.

const unsigned short leaf_slotmin

static

Computed B+ tree parameter: The minimum number of key/data slots used in a leaf.

If fewer slots are used, the leaf will be merged or slots shifted from it's siblings.

Definition at line 117 of file btree_map.hpp.

const bool self_verify

static

Debug parameter: Enables expensive and thorough checking of the B+ tree invariants after each insert/erase operation.

Definition at line 126 of file btree_map.hpp.

TLX_BTREE_FRIENDS

Definition at line 68 of file btree_map.hpp.

btree_impl tree_

private

The contained implementation object.

Definition at line 163 of file btree_map.hpp.

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

tlx/container/btree_map.hpp

Classes

Public Types

Public Member Functions

Public Attributes

Static Public Attributes

Private Attributes

Detailed Description

template<typename Key_, typename Data_, typename Compare_ = std::less<Key_>, typename Traits_ = btree_default_traits<Key_, std::pair<Key_, Data_> >, typename Alloc_ = std::allocator<std::pair<Key_, Data_> >> class tlx::btree_map< Key_, Data_, Compare_, Traits_, Alloc_ >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<typename Key_, typename Data_, typename Compare_ = std::less<Key_>, typename Traits_ = btree_default_traits<Key_, std::pair<Key_, Data_> >, typename Alloc_ = std::allocator<std::pair<Key_, Data_> >>
class tlx::btree_map< Key_, Data_, Compare_, Traits_, Alloc_ >