18 #ifndef RAUL_TABLE_HPP
19 #define RAUL_TABLE_HPP
23 #include <boost/utility.hpp>
24 #include "SharedPtr.hpp"
37 template <
typename K,
typename T>
38 class Table :
public boost::noncopyable {
41 Table<K, T>(
size_t capacity) : _entries(capacity) {}
43 void clear() { _entries.clear(); }
44 bool empty()
const {
return _entries.empty(); }
45 void reserve(
size_t n) { _entries.reserve(n); }
47 struct const_iterator {
48 const_iterator(
const Table<K,T>& t,
size_t i) : _table(&t), _index(i) {}
49 inline const std::pair<const K, T> operator*()
const {
return _table->_entries[_index]; }
50 inline const std::pair<const K, T>* operator->()
const {
return (std::pair<const K, T>*)&_table->_entries[_index]; }
51 inline const_iterator& operator++() { ++_index;
return *
this; }
52 inline const_iterator& operator--() { --_index;
return *
this; }
53 inline bool operator==(
const const_iterator& i)
const {
return _index == i._index; }
54 inline bool operator!=(
const const_iterator& i)
const {
return _index != i._index; }
55 void operator=(
const const_iterator& i) { _table = i._table; _index = i._index; }
57 friend class Table<K,T>;
63 iterator(
Table<K,T>& t,
size_t i) : _table(&t), _index(i) {}
64 inline std::pair<K, T>& operator*()
const {
return (std::pair<K, T>&)_table->_entries[_index]; }
65 inline std::pair<K, T>* operator->()
const {
return (std::pair<K, T>*)&_table->_entries[_index]; }
66 inline iterator& operator++() { ++_index;
return *
this; }
67 inline iterator& operator--() { --_index;
return *
this; }
68 inline bool operator==(
const iterator& i)
const {
return _index == i._index; }
69 inline bool operator!=(
const iterator& i)
const {
return _index != i._index; }
70 operator const_iterator() {
return *(const_iterator*)
this; }
71 iterator& operator=(
const iterator& i) { _table = i._table; _index = i._index;
return *
this; }
73 friend class Table<K,T>;
78 inline size_t size()
const {
return _entries.size(); }
80 std::pair<iterator,bool>
insert(
const std::pair<K, T>& entry);
82 void erase(
const K& key);
83 void erase(iterator i);
84 void erase(iterator start, iterator end);
87 SharedPtr< Table<K, T> >
yank(iterator start, iterator end);
91 const_iterator
find(const_iterator start, const_iterator end,
const K& key)
const;
92 const_iterator
find(
const K& key)
const;
94 iterator
find(const_iterator start, const_iterator end,
const K& key);
95 iterator
find(
const K& key);
97 const_iterator
find_range_end(const_iterator left,
bool (*comp)(
const K&,
const K&))
const;
98 iterator
find_range_end(iterator left,
bool (*comp)(
const K&,
const K&));
102 const_iterator begin()
const {
return const_iterator(*
this, 0); }
103 const_iterator end()
const {
return const_iterator(*
this, size()); }
104 iterator begin() {
return iterator(*
this, 0); }
105 iterator end() {
return iterator(*
this, size()); }
108 #ifdef TABLE_SORT_DEBUG
109 bool is_sorted()
const;
112 friend class iterator;
114 typedef std::pair<K, T> Entry;
116 std::vector<Entry> _entries;
122 #endif // RAUL_TABLE_HPP
SharedPtr< Table< K, T > > yank(iterator start, iterator end)
Erase and return a range of entries.
Definition: TableImpl.hpp:201
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:268
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:399
T & operator[](const K &key)
Insert an item, and return a reference to it's value.
Definition: TableImpl.hpp:339
Slow insertion, fast lookup, cache optimized, super fast sorted iteration.
Definition: Table.hpp:38
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:123
std::pair< iterator, bool > cram(const Table< K, T > &range)
Cram a range of entries back in.
Definition: TableImpl.hpp:216
const_iterator find(const_iterator start, const_iterator end, const K &key) const
Binary search (O(log(end - start)))
Definition: TableImpl.hpp:73