diff options
author | Markus Härer <markus.haerer@gmx.net> | 2024-07-07 18:34:11 +0200 |
---|---|---|
committer | Markus Härer <markus.haerer@gmx.net> | 2024-07-10 01:39:53 +0200 |
commit | e95f207ecf1de5eed44744b6d84691c00b6f1e1c (patch) | |
tree | 060373b2421c261cb0704cc98488f7a0d855d9b6 | |
parent | d7876de3e6d9045941cc12eb4150248e01c1ea64 (diff) |
Map: Make access log(n) if keys can be sorted
-rw-r--r-- | xbmc/utils/Map.h | 26 |
1 files changed, 23 insertions, 3 deletions
diff --git a/xbmc/utils/Map.h b/xbmc/utils/Map.h index 17af54548f..f4a1c872c4 100644 --- a/xbmc/utils/Map.h +++ b/xbmc/utils/Map.h @@ -26,7 +26,8 @@ * This class is useful for mapping enum values to strings that can be * compile time checked. This also helps with heap usage. * - * Lookups have linear complexity, so should not be used for "big" maps. + * Lookups have log(n) complexity if Key is comparable using std::less<>, + * otherwise it's linear. */ template<typename Key, typename Value, size_t Size> class CMap @@ -55,6 +56,12 @@ public: // ++begin; // } + + if constexpr (requires(Key k) { std::less<>{}(k, k); }) + { + std::sort(m_map.begin(), m_map.end(), + [](const auto& a, const auto& b) { return std::less<>{}(a.first, b.first); }); + } } ~CMap() = default; @@ -74,8 +81,21 @@ public: constexpr auto find(const Key& key) const { - return std::find_if(m_map.cbegin(), m_map.cend(), - [&key](const auto& pair) { return pair.first == key; }); + if constexpr (requires(Key k) { std::less<>{}(k, k); }) + { + const auto iter = + std::lower_bound(m_map.cbegin(), m_map.cend(), key, + [](const auto& a, const auto& b) { return std::less<>{}(a.first, b); }); + if (iter != m_map.end() && !(key < iter->first)) + return iter; + else + return m_map.end(); + } + else + { + return std::find_if(m_map.cbegin(), m_map.cend(), + [&key](const auto& pair) { return pair.first == key; }); + } } constexpr size_t size() const { return Size; } |