aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMarkus Härer <markus.haerer@gmx.net>2024-07-07 18:34:11 +0200
committerMarkus Härer <markus.haerer@gmx.net>2024-07-10 01:39:53 +0200
commite95f207ecf1de5eed44744b6d84691c00b6f1e1c (patch)
tree060373b2421c261cb0704cc98488f7a0d855d9b6
parentd7876de3e6d9045941cc12eb4150248e01c1ea64 (diff)
Map: Make access log(n) if keys can be sorted
-rw-r--r--xbmc/utils/Map.h26
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; }