RAUL  0.8.0
Public Member Functions | Friends | List of all members
Raul::Table< K, T > Class Template Reference

Slow insertion, fast lookup, cache optimized, super fast sorted iteration. More...

#include <Table.hpp>

Inherits boost::noncopyable.

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. More...
 
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. More...
 
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. More...
 
iterator find_range_end (iterator left, bool(*comp)(const K &, const K &))
 Find the end of a range using a custom comparator. More...
 
T & operator[] (const K &key)
 Insert an item, and return a reference to it's value. More...
 
const_iterator begin () const
 
const_iterator end () const
 
iterator begin ()
 
iterator end ()
 

Friends

class iterator
 

Detailed Description

template<typename K, typename T>
class Raul::Table< K, T >

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.

Member Function Documentation

◆ insert()

template<typename K , typename T >
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)

◆ cram()

template<typename K , typename T >
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

◆ find_range_end() [1/2]

template<typename K , typename T >
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.

◆ find_range_end() [2/2]

template<typename K , typename T >
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.

◆ operator[]()

template<typename K , typename T >
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.


The documentation for this class was generated from the following files: