From e95f207ecf1de5eed44744b6d84691c00b6f1e1c Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Markus=20H=C3=A4rer?= Date: Sun, 7 Jul 2024 18:34:11 +0200 Subject: Map: Make access log(n) if keys can be sorted --- xbmc/utils/Map.h | 26 +++++++++++++++++++++++--- 1 file 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 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; } -- cgit v1.2.3