lab_btree
Belligerent BTrees
btree.h File Reference

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

◆ insertion_idx()

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.

Parameters
elementsA sorted vector of some type.
valA 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.