template<class K, class V>
class tccollection::BtreeList< K, V >
A very simple binary search based list. It is useful for storage of items by key or just regular storage, it is very efficient for reading, but relatively inefficient for insertions, but only when compared to a linked list. It is however very memory efficient. There are some restrictions on it's use:
- Class V must have a method to get the key: K getKey()
- Class K must be directly comparable using less than, greater than and equals (any primitive would generally work).
On inserts, the list is re-sorted to get it back into order by key, and will grow automatically if needed using the howToGrow parameter passed to the constructor. The list is therefore always sorted by key, and this will generally always involve a memory copy to move around the items.
All keys must be of an unsigned integer type not exceeding uint32_t in length, you look up an item by it's key value, the list will either return NULL or a valid item. You can also obtain all values too, which is always sorted by key and is marked const, do not alter this array.
template<class K, class V>
| tccollection::BtreeList< K, V >::BtreeList |
( |
ioaTreeInternal::KeyAccessor | customAccessor, |
|
|
bsize_t | size = DEFAULT_LIST_SIZE, |
|
|
GrowByMode | howToGrow = DEFAULT_GROW_MODE ) |
|
explicit |
Advanced usage constructor, prefer using the other constructor whenever possible.
This constructor allows you to provide your own key accessor, some other libraries require slightly different ways of accessing the object. For the key accessor you'll be provided with a pointer to a memory area, this area contains the item for which we need the key, you return the key value from the accessor as a uint32_t.
The default key accessor is as follows:
static uint32_t keyAccessor(const void *itm) {
return reinterpret_cast<const V *>(itm)->getKey();
}
- Parameters
-
| customAccessor | the custom accessor that is called to return the key |
| size | the size of the list, optional parameter. |
| howToGrow | the method for growing when space runs out, optional parameter |
template<class K, class V>
Implements the range begin function for use with C++ ranges, represents the beginning of the list, supports using ++ to get the next item, but if using manually check against end() before accessing the value.
For example to iterate you can
(auto& item : mybtreelist) { item.dosomething(); }
- Returns
- an iterator for the beginning of the list. */ BtreeIterator<V> begin() const { return BtreeIterator<V>(0, treeStorage); }
/** An iterator that represnts the value beyond the end of the list, for use with C++ ranges.
- Returns
- an iterator that represents the end of the list. Normally used with begin().
