Slow insertion, fast lookup, cache optimized, super fast sorted iteration. More...
#include <Table.hpp>
Public Member Functions | |
| Table (size_t capacity) | |
| void | clear () |
| bool | empty () const |
| void | reserve (size_t n) |
| size_t | size () const |
| std::pair< iterator, bool > | insert (const std::pair< K, T > &entry) |
| Add an item to the table, using entry.first as the search key. | |
| void | erase (const K &key) |
| void | erase (iterator i) |
| void | erase (iterator start, iterator end) |
| Erase a range of elements from first to last, including first but not including last. | |
| void | erase_by_index (size_t start, size_t end) |
| Erase a range of elements from first_index to last_index, including first_index but not including last_index. | |
| SharedPtr< Table< K, T > > | yank (iterator start, iterator end) |
| Erase and return a range of entries. | |
| std::pair< iterator, bool > | cram (const Table< K, T > &range) |
| Cram a range of entries back in. | |
| const_iterator | find (const_iterator start, const_iterator end, const K &key) const |
| Binary search (O(log(end - start))). | |
| const_iterator | find (const K &key) const |
| Binary search (O(log(n))). | |
| iterator | find (const_iterator start, const_iterator end, const K &key) |
| Binary search (O(log(end - start))). | |
| iterator | find (const K &key) |
| Binary search (O(log(n))). | |
| const_iterator | find_range_end (const_iterator left, bool(*comp)(const K &, const K &)) const |
| Find the end of a range using a custom comparator. | |
| iterator | find_range_end (iterator left, bool(*comp)(const K &, const K &)) |
| Find the end of a range using a custom comparator. | |
| T & | operator[] (const K &key) |
| Insert an item, and return a reference to it's value. | |
| const_iterator | begin () const |
| const_iterator | end () const |
| iterator | begin () |
| iterator | end () |
Friends | |
| class | iterator |
Slow insertion, fast lookup, cache optimized, super fast sorted iteration.
This has the advantage over std::map that iterating over the collection is fast and sorted. Possibly also faster in some situations due to all data being in a single chunk of memory, cache optimized, etc.
| std::pair< typename Table< K, T >::iterator, bool > Raul::Table< K, T >::insert | ( | const std::pair< K, T > & | entry | ) |
Add an item to the table, using entry.first as the search key.
An iterator to the element where value was set is returned, and a bool which is true if an insertion took place, or false if an existing entry was updated. Matches std::map::insert interface. O(n) worst case O(log(n)) best case (capacity is large enough)
Referenced by Raul::Table< K, T >::cram(), and Raul::Table< K, T >::operator[]().
| std::pair< typename Table< K, T >::iterator, bool > Raul::Table< K, T >::cram | ( | const Table< K, T > & | range | ) |
Cram a range of entries back in.
Range MUST follow the same ordering guidelines as find_range_end. Return type is the same as insert, iterator points to first inserted entry
References Raul::Table< K, T >::insert().
| Table< K, T >::const_iterator Raul::Table< K, T >::find_range_end | ( | const_iterator | start, | |
| bool(*)(const K &, const K &) | comp | |||
| ) | const |
Find the end of a range using a custom comparator.
Two entries a, b are considered in the range if comp(a, b) returns true.
Returns an iterator exactly one entry past the end of the range (possibly end()).
WARNING: The restrictions on comparator are very strict: ALL items considered equal by comparator must be stored in the Table consecutively i.e. there are no 3 values a, b, c S.T. comp(a) && ! comp(b) && comp(c).
This is useful for very quickly finding all children of a Path, which obey the above rule with lexicographical order.
| Table< K, T >::iterator Raul::Table< K, T >::find_range_end | ( | iterator | start, | |
| bool(*)(const K &, const K &) | comp | |||
| ) |
Find the end of a range using a custom comparator.
Two entries a, b are considered in the range if comp(a, b) returns true.
Returns an iterator exactly one entry past the end of the range (possibly end()).
WARNING: The restrictions on comparator are very strict: ALL items considered equal by comparator must be stored in the Table consecutively i.e. there are no 3 values a, b, c S.T. comp(a) && ! comp(b) && comp(c).
This is useful for very quickly finding all children of a Path, which obey the above rule with lexicographical order.
| T & Raul::Table< K, T >::operator[] | ( | const K & | key | ) |
Insert an item, and return a reference to it's value.
This may be used to insert values with pretty syntax:
table["gorilla"] = "killa";
T must have a default constructor for this to be possible.
References Raul::Table< K, T >::find(), and Raul::Table< K, T >::insert().
1.7.1