Definition of a B-tree class which can be used as a generic dictionary (insert-only). More...

Classes
class	BTree< K, V >
	BTree class. More...

struct	BTree< K, V >::DataPair
	A fancy key-value pair which acts as elements in the BTree. More...

struct	BTree< K, V >::BTreeNode
	A class for the basic node structure of the BTree. More...

Functions
template<class T , class C >
size_t	insertion_idx (const std::vector< T > &elements, const C &val)
	Generalized function for finding the insertion index of a given element into a given sorted vector. More...

Detailed Description

Definition of a B-tree class which can be used as a generic dictionary (insert-only).

Designed to take advantage of caching to be faster than standard balanced binary search trees.

Function Documentation

template<class T , class C >

Generalized function for finding the insertion index of a given element into a given sorted vector.

Parameters

elements	A sorted vector of some type.
val	A value which represents something to be inserted into the vector. Must either be the same type as T, or one that can compare to it. E.g. for the elements of a BTreeNode we might pass in either a DataPair value or a K value (the key).

Returns: The index at which val could be inserted into elements to maintain the sorted order of elements. If val occurs in elements, then this returns the index of val in elements.