Definition of a B-tree class which can be used as a generic dictionary (insert-only). More...
#include <vector>#include <iostream>#include <string>#include <sstream>#include "btree_given.cpp"#include "btree.cpp"
Include dependency graph for btree.h: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.
- Date
- Winter 2013
Function Documentation
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
-
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.
