diff options
Diffstat (limited to 'raul')
| -rw-r--r-- | raul/Table.hpp | 6 | ||||
| -rw-r--r-- | raul/TableImpl.hpp | 29 |
2 files changed, 25 insertions, 10 deletions
diff --git a/raul/Table.hpp b/raul/Table.hpp index 524d11c..db5216f 100644 --- a/raul/Table.hpp +++ b/raul/Table.hpp @@ -36,10 +36,11 @@ public: Table<K, T>() {} void clear() { _entries.clear(); } + bool empty() const { return _entries.empty(); } struct const_iterator { const_iterator(const Table<K,T>& t, size_t i) : _table(t), _index(i) {} - inline const std::pair<const K, T>& operator*() const { return _table._entries[_index]; } + inline const std::pair<const K, T> operator*() const { return _table._entries[_index]; } inline const std::pair<const K, T>* operator->() const { return (std::pair<const K, T>*)&_table._entries[_index]; } inline const_iterator& operator++() { ++_index; return *this; } inline const_iterator& operator--() { --_index; return *this; } @@ -70,7 +71,8 @@ public: inline size_t size() const { return _entries.size(); } - void insert(const K& key, const T& value); + std::pair<iterator,bool> insert(const std::pair<K, T>& entry); + void erase(const K& key); void erase(iterator i); void erase(iterator begin, iterator end); diff --git a/raul/TableImpl.hpp b/raul/TableImpl.hpp index ab79b7f..35bf2f6 100644 --- a/raul/TableImpl.hpp +++ b/raul/TableImpl.hpp @@ -74,17 +74,27 @@ Table<K,T>::find(const K& key) } +/** Add an item to the table, using \a 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) + */ template <typename K, typename T> -void -Table<K,T>::insert(const K& key, const T& value) +std::pair<typename Table<K,T>::iterator,bool> +Table<K,T>::insert(const std::pair<K, T>& entry) { + const K& key = entry.first; + const T& value = entry.second; + if (size() == 0 || size() == 1 && key > _entries[0].first) { - _entries.push_back(make_pair(key, value)); - return; + _entries.push_back(entry); + return make_pair(iterator(*this, size()-1), true); } else if (size() == 1) { _entries.push_back(_entries[0]); - _entries[0] = make_pair(key, value); - return; + _entries[0] = entry; + return make_pair(begin(), true); } size_t lower = 0; @@ -103,7 +113,8 @@ Table<K,T>::insert(const K& key, const T& value) Entry& elem = _entries[i]; if (elem.first == key) { - break; + elem.second = value; + return make_pair(iterator(*this, i), false); } else if (elem.first > key) { if (i == 0 || _entries[i-1].first < key) break; @@ -123,9 +134,11 @@ Table<K,T>::insert(const K& key, const T& value) for (size_t j = size()-1; j > i; --j) _entries[j] = _entries[j-1]; - _entries[i] = make_pair(key, value); + _entries[i] = entry; assert(is_sorted()); + + return make_pair(iterator(*this, i), true); } |