[OMPT-svn-commit] OpenMPT r21436 - trunk/OpenMPT/src/mpt/base

[<sv...@op...>]

Author: manx
Date: Wed Aug 14 16:35:23 2024
New Revision: 21436
URL: https://source.openmpt.org/browse/openmpt/?op=revision&rev=21436

Log:
[Imp] mpt/base/algorithm.hpp: Use member find() instead of iterator find() when available. The reduces runtime complexity with associative containers.

Modified:
   trunk/OpenMPT/src/mpt/base/algorithm.hpp

Modified: trunk/OpenMPT/src/mpt/base/algorithm.hpp
==============================================================================
--- trunk/OpenMPT/src/mpt/base/algorithm.hpp	Wed Aug 14 11:25:40 2024	(r21435)
+++ trunk/OpenMPT/src/mpt/base/algorithm.hpp	Wed Aug 14 16:35:23 2024	(r21436)
@@ -12,6 +12,7 @@
 
 #include <algorithm>
 #include <limits>
+#include <type_traits>
 
 
 
@@ -47,11 +48,57 @@
 }
 
 
+namespace detail {
+namespace contains {
+
+template <typename Container, typename Signature>
+struct has_find : std::false_type {
+};
+
+template <typename Container, typename Ret, typename... Args>
+struct has_find<Container, Ret(Args...)> {
+private:
+	template <typename T>
+  static constexpr inline auto check(T *) -> typename std::is_same<decltype(std::declval<T>().find(std::declval<Args>()...)), Ret>::type {
+		return {};
+	}
+  template <typename T>
+	static constexpr inline std::false_type check(...) {
+		return {};
+	}
+public:
+  typedef decltype(check<Container>(nullptr)) type;
+  static constexpr inline bool value = type::value;
+};
+
+template <typename Tcontainer, typename Tval>
+MPT_CONSTEXPR20_FUN bool contains_class_find_impl(const Tcontainer & container, const Tval & value, std::true_type) noexcept(noexcept(container.find(value) != container.end())) {
+	return container.find(value) != container.end();
+}
+
+template <typename Tcontainer, typename Tval>
+MPT_CONSTEXPR20_FUN bool contains_class_find_impl(const Tcontainer & container, const Tval & value, std::false_type) noexcept(noexcept(std::find(std::begin(container), std::end(container), value))) {
+	return std::find(std::begin(container), std::end(container), value) != std::end(container);
+}
+
+template <typename Tcontainer, typename Tval>
+MPT_CONSTEXPR20_FUN bool contains_class_impl(const Tcontainer & container, const Tval & value, std::true_type) noexcept(noexcept(mpt::detail::contains::contains_class_find_impl<Tcontainer, Tval>(container, value, typename mpt::detail::contains::has_find<Tcontainer, typename Tcontainer::iterator(Tval)>::type{}))) {
+	return mpt::detail::contains::contains_class_find_impl<Tcontainer, Tval>(container, value, typename mpt::detail::contains::has_find<Tcontainer, typename Tcontainer::iterator(Tval)>::type{});
+}
+
 template <typename Tcontainer, typename Tval>
-MPT_CONSTEXPR20_FUN bool contains(const Tcontainer & container, const Tval & value) noexcept(noexcept(std::find(std::begin(container), std::end(container), value))) {
+MPT_CONSTEXPR20_FUN bool contains_class_impl(const Tcontainer & container, const Tval & value, std::false_type) noexcept(noexcept(std::find(std::begin(container), std::end(container), value))) {
 	return std::find(std::begin(container), std::end(container), value) != std::end(container);
 }
 
+} // namespace contains
+} // namespace detail
+
+template <typename Tcontainer, typename Tval>
+MPT_CONSTEXPR20_FUN bool contains(const Tcontainer & container, const Tval & value) noexcept(noexcept(mpt::detail::contains::contains_class_impl<Tcontainer, Tval>(container, value, typename std::is_class<Tcontainer>::type{}))) {
+	return mpt::detail::contains::contains_class_impl<Tcontainer, Tval>(container, value, typename std::is_class<Tcontainer>::type{});
+}
+
 
 } // namespace MPT_INLINE_NS
 } // namespace mpt