diff options
| -rw-r--r-- | raul/Table.hpp | 3 | ||||
| -rw-r--r-- | raul/TableImpl.hpp | 13 |
2 files changed, 14 insertions, 2 deletions
diff --git a/raul/Table.hpp b/raul/Table.hpp index 1d20a9c..fa3848c 100644 --- a/raul/Table.hpp +++ b/raul/Table.hpp @@ -86,7 +86,10 @@ public: std::pair<iterator, bool> cram(const Table<K, T>& range); + const_iterator find(const_iterator start, const_iterator end, const K& key) const; const_iterator find(const K& key) const; + + iterator find(iterator start, iterator end, const K& key); iterator find(const K& key); const_iterator find_range_end(const_iterator left, bool (*comp)(const K&,const K&)) const; diff --git a/raul/TableImpl.hpp b/raul/TableImpl.hpp index 1bb4699..d01c0ca 100644 --- a/raul/TableImpl.hpp +++ b/raul/TableImpl.hpp @@ -66,11 +66,20 @@ template <typename K, typename T> typename Table<K,T>::iterator Table<K,T>::find(const K& key) { + return find(begin(), end(), key); +} + + +/** Binary search (O(log(end - start))) */ +template <typename K, typename T> +typename Table<K,T>::iterator +Table<K,T>::find(iterator start, iterator finish, const K& key) +{ if (size() == 0) return end(); - size_t lower = 0; - size_t upper = size() - 1; + size_t lower = start._index; + size_t upper = finish._index - 1; size_t i; while (upper >= lower) { |