18 #ifndef RAUL_TABLE_HPP
19 #define RAUL_TABLE_HPP
25 #include <boost/utility.hpp>
27 #include "raul/SharedPtr.hpp"
41 template <
typename K,
typename T>
42 class Table :
public boost::noncopyable {
45 Table<K, T>(
size_t capacity) : _entries(capacity) {}
47 void clear() { _entries.clear(); }
48 bool empty()
const {
return _entries.empty(); }
49 void reserve(
size_t n) { _entries.reserve(n); }
51 struct const_iterator {
52 const_iterator(
const Table<K,T>& t,
size_t i) : _table(&t), _index(i) {}
53 inline const std::pair<const K, T> operator*()
const {
return _table->_entries[_index]; }
54 inline const std::pair<const K, T>* operator->()
const {
return (std::pair<const K, T>*)&_table->_entries[_index]; }
55 inline const_iterator& operator++() { ++_index;
return *
this; }
56 inline const_iterator& operator--() { --_index;
return *
this; }
57 inline bool operator==(
const const_iterator& i)
const {
return _index == i._index; }
58 inline bool operator!=(
const const_iterator& i)
const {
return _index != i._index; }
59 void operator=(
const const_iterator& i) { _table = i._table; _index = i._index; }
61 friend class Table<K,T>;
67 iterator(
Table<K,T>& t,
size_t i) : _table(&t), _index(i) {}
68 inline std::pair<K, T>& operator*()
const {
return (std::pair<K, T>&)_table->_entries[_index]; }
69 inline std::pair<K, T>* operator->()
const {
return (std::pair<K, T>*)&_table->_entries[_index]; }
70 inline iterator& operator++() { ++_index;
return *
this; }
71 inline iterator& operator--() { --_index;
return *
this; }
72 inline bool operator==(
const iterator& i)
const {
return _index == i._index; }
73 inline bool operator!=(
const iterator& i)
const {
return _index != i._index; }
74 operator const_iterator() {
return *(const_iterator*)
this; }
75 iterator& operator=(
const iterator& i) { _table = i._table; _index = i._index;
return *
this; }
77 friend class Table<K,T>;
82 inline size_t size()
const {
return _entries.size(); }
84 std::pair<iterator,bool>
insert(
const std::pair<K, T>& entry);
86 void erase(
const K& key);
87 void erase(iterator i);
88 void erase(iterator start, iterator end);
91 SharedPtr< Table<K, T> >
yank(iterator start, iterator end);
95 const_iterator
find(const_iterator start, const_iterator end,
const K& key)
const;
96 const_iterator
find(
const K& key)
const;
98 iterator
find(const_iterator start, const_iterator end,
const K& key);
99 iterator
find(
const K& key);
101 const_iterator
find_range_end(const_iterator left,
bool (*comp)(
const K&,
const K&))
const;
102 iterator
find_range_end(iterator left,
bool (*comp)(
const K&,
const K&));
106 const_iterator begin()
const {
return const_iterator(*
this, 0); }
107 const_iterator end()
const {
return const_iterator(*
this, size()); }
108 iterator begin() {
return iterator(*
this, 0); }
109 iterator end() {
return iterator(*
this, size()); }
112 #ifdef TABLE_SORT_DEBUG
113 bool is_sorted()
const;
116 friend class iterator;
118 typedef std::pair<K, T> Entry;
120 std::vector<Entry> _entries;
126 #endif // RAUL_TABLE_HPP
SharedPtr< Table< K, T > > yank(iterator start, iterator end)
Erase and return a range of entries.
Definition: TableImpl.hpp:204
std::pair< iterator, bool > insert(const std::pair< K, T > &entry)
Add an item to the table, using entry.first as the search key.
Definition: TableImpl.hpp:265
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 las...
Definition: TableImpl.hpp:396
T & operator[](const K &key)
Insert an item, and return a reference to it's value.
Definition: TableImpl.hpp:336
Slow insertion, fast lookup, cache optimized, super fast sorted iteration.
Definition: Table.hpp:42
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.
Definition: TableImpl.hpp:126
std::pair< iterator, bool > cram(const Table< K, T > &range)
Cram a range of entries back in.
Definition: TableImpl.hpp:219
const_iterator find(const_iterator start, const_iterator end, const K &key) const
Binary search (O(log(end - start)))
Definition: TableImpl.hpp:76