diff options
Diffstat (limited to 'indra/llcommon/llsortedvector.h')
-rwxr-xr-x | indra/llcommon/llsortedvector.h | 152 |
1 files changed, 152 insertions, 0 deletions
diff --git a/indra/llcommon/llsortedvector.h b/indra/llcommon/llsortedvector.h new file mode 100755 index 0000000000..391b82ee44 --- /dev/null +++ b/indra/llcommon/llsortedvector.h @@ -0,0 +1,152 @@ +/** + * @file llsortedvector.h + * @author Nat Goodspeed + * @date 2012-04-08 + * @brief LLSortedVector class wraps a vector that we maintain in sorted + * order so we can perform binary-search lookups. + * + * $LicenseInfo:firstyear=2012&license=viewerlgpl$ + * Copyright (c) 2012, Linden Research, Inc. + * $/LicenseInfo$ + */ + +#if ! defined(LL_LLSORTEDVECTOR_H) +#define LL_LLSORTEDVECTOR_H + +#include <vector> +#include <algorithm> + +/** + * LLSortedVector contains a std::vector<std::pair> that we keep sorted on the + * first of the pair. This makes insertion somewhat more expensive than simple + * std::vector::push_back(), but allows us to use binary search for lookups. + * It's intended for small aggregates where lookup is far more performance- + * critical than insertion; in such cases a binary search on a small, sorted + * std::vector can be more performant than a std::map lookup. + */ +template <typename KEY, typename VALUE> +class LLSortedVector +{ +public: + typedef LLSortedVector<KEY, VALUE> self; + typedef KEY key_type; + typedef VALUE mapped_type; + typedef std::pair<key_type, mapped_type> value_type; + typedef std::vector<value_type> PairVector; + typedef typename PairVector::iterator iterator; + typedef typename PairVector::const_iterator const_iterator; + + /// Empty + LLSortedVector() {} + + /// Fixed initial size + LLSortedVector(std::size_t size): + mVector(size) + {} + + /// Bulk load + template <typename ITER> + LLSortedVector(ITER begin, ITER end): + mVector(begin, end) + { + // Allow caller to dump in a bunch of (pairs convertible to) + // value_type if desired, but make sure we sort afterwards. + std::sort(mVector.begin(), mVector.end()); + } + + /// insert(key, value) + std::pair<iterator, bool> insert(const key_type& key, const mapped_type& value) + { + return insert(value_type(key, value)); + } + + /// insert(value_type) + std::pair<iterator, bool> insert(const value_type& pair) + { + typedef std::pair<iterator, bool> iterbool; + iterator found = std::lower_bound(mVector.begin(), mVector.end(), pair, + less<value_type>()); + // have to check for end() before it's even valid to dereference + if (found == mVector.end()) + { + std::size_t index(mVector.size()); + mVector.push_back(pair); + // don't forget that push_back() invalidates 'found' + return iterbool(mVector.begin() + index, true); + } + if (found->first == pair.first) + { + return iterbool(found, false); + } + // remember that insert() invalidates 'found' -- save index + std::size_t index(found - mVector.begin()); + mVector.insert(found, pair); + // okay, convert from index back to iterator + return iterbool(mVector.begin() + index, true); + } + + iterator begin() { return mVector.begin(); } + iterator end() { return mVector.end(); } + const_iterator begin() const { return mVector.begin(); } + const_iterator end() const { return mVector.end(); } + + bool empty() const { return mVector.empty(); } + std::size_t size() const { return mVector.size(); } + + /// find + iterator find(const key_type& key) + { + iterator found = std::lower_bound(mVector.begin(), mVector.end(), + value_type(key, mapped_type()), + less<value_type>()); + if (found == mVector.end() || found->first != key) + return mVector.end(); + return found; + } + + const_iterator find(const key_type& key) const + { + return const_cast<self*>(this)->find(key); + } + +private: + // Define our own 'less' comparator so we can specialize without messing + // with std::less. + template <typename T> + struct less: public std::less<T> {}; + + // Specialize 'less' for an LLSortedVector::value_type involving + // std::type_info*. This is one of LLSortedVector's foremost use cases. We + // specialize 'less' rather than just defining a specific comparator + // because LLSortedVector should be usable for other key_types as well. + template <typename T> + struct less< std::pair<std::type_info*, T> >: + public std::binary_function<std::pair<std::type_info*, T>, + std::pair<std::type_info*, T>, + bool> + { + bool operator()(const std::pair<std::type_info*, T>& lhs, + const std::pair<std::type_info*, T>& rhs) const + { + return lhs.first->before(*rhs.first); + } + }; + + // Same as above, but with const std::type_info*. + template <typename T> + struct less< std::pair<const std::type_info*, T> >: + public std::binary_function<std::pair<const std::type_info*, T>, + std::pair<const std::type_info*, T>, + bool> + { + bool operator()(const std::pair<const std::type_info*, T>& lhs, + const std::pair<const std::type_info*, T>& rhs) const + { + return lhs.first->before(*rhs.first); + } + }; + + PairVector mVector; +}; + +#endif /* ! defined(LL_LLSORTEDVECTOR_H) */ |