Updated external benchmark hash maps to latest, and improved example lower_bound.c

1 files changed, 39 insertions, 17 deletions

diff --git a/misc/benchmarks/external/ankerl/unordered_dense.h b/misc/benchmarks/external/ankerl/unordered_dense.h
index ff902ad4..05c7e928 100644
--- a/misc/benchmarks/external/ankerl/unordered_dense.h
+++ b/misc/benchmarks/external/ankerl/unordered_dense.h
@@ -1,7 +1,7 @@
 ///////////////////////// ankerl::unordered_dense::{map, set} /////////////////////////
 
 // A fast & densely stored hashmap and hashset based on robin-hood backward shift deletion.
-// Version 2.0.0
+// Version 3.0.0
 // https://github.com/martinus/unordered_dense
 //
 // Licensed under the MIT License <http://opensource.org/licenses/MIT>.
@@ -30,7 +30,7 @@
 #define ANKERL_UNORDERED_DENSE_H
 
 // see https://semver.org/spec/v2.0.0.html
-#define ANKERL_UNORDERED_DENSE_VERSION_MAJOR 2 // NOLINT(cppcoreguidelines-macro-usage) incompatible API changes
+#define ANKERL_UNORDERED_DENSE_VERSION_MAJOR 3 // NOLINT(cppcoreguidelines-macro-usage) incompatible API changes
 #define ANKERL_UNORDERED_DENSE_VERSION_MINOR 0 // NOLINT(cppcoreguidelines-macro-usage) backwards compatible functionality
 #define ANKERL_UNORDERED_DENSE_VERSION_PATCH 0 // NOLINT(cppcoreguidelines-macro-usage) backwards compatible bug fixes
 
@@ -363,6 +363,9 @@ using detect_is_transparent = typename T::is_transparent;
 template <typename T>
 using detect_iterator = typename T::iterator;
 
+template <typename T>
+using detect_reserve = decltype(std::declval<T&>().reserve(size_t{}));
+
 // enable_if helpers
 
 template <typename Mapped>
@@ -374,6 +377,18 @@ constexpr bool is_transparent_v = is_detected_v<detect_is_transparent, Hash>&& i
 template <typename From, typename To1, typename To2>
 constexpr bool is_neither_convertible_v = !std::is_convertible_v<From, To1> && !std::is_convertible_v<From, To2>;
 
+template <typename T>
+constexpr bool has_reserve = is_detected_v<detect_reserve, T>;
+
+// base type for map has mapped_type
+template <class T>
+struct base_table_type_map {
+    using mapped_type = T;
+};
+
+// base type for set doesn't have mapped_type
+struct base_table_type_set {};
+
 // This is it, the table. Doubles as map and set, and uses `void` for T when its used as a set.
 template <class Key,
           class T, // when void, treat it as a set.
@@ -381,12 +396,12 @@ template <class Key,
           class KeyEqual,
           class AllocatorOrContainer,
           class Bucket>
-class table {
+class table : public std::conditional_t<is_map_v<T>, base_table_type_map<T>, base_table_type_set> {
 public:
     using value_container_type = std::conditional_t<
         is_detected_v<detect_iterator, AllocatorOrContainer>,
         AllocatorOrContainer,
-        typename std::vector<typename std::conditional_t<std::is_void_v<T>, Key, std::pair<Key, T>>, AllocatorOrContainer>>;
+        typename std::vector<typename std::conditional_t<is_map_v<T>, std::pair<Key, T>, Key>, AllocatorOrContainer>>;
 
 private:
     using bucket_alloc =
@@ -398,7 +413,6 @@ private:
 
 public:
     using key_type = Key;
-    using mapped_type = T;
     using value_type = typename value_container_type::value_type;
     using size_type = typename value_container_type::size_type;
     using difference_type = typename value_container_type::difference_type;
@@ -409,8 +423,8 @@ public:
     using const_reference = typename value_container_type::const_reference;
     using pointer = typename value_container_type::pointer;
     using const_pointer = typename value_container_type::const_pointer;
-    using iterator = typename value_container_type::iterator;
     using const_iterator = typename value_container_type::const_iterator;
+    using iterator = std::conditional_t<is_map_v<T>, typename value_container_type::iterator, const_iterator>;
     using bucket_type = Bucket;
 
 private:
@@ -477,10 +491,10 @@ private:
     }
 
     [[nodiscard]] static constexpr auto get_key(value_type const& vt) -> key_type const& {
-        if constexpr (std::is_void_v<T>) {
-            return vt;
-        } else {
+        if constexpr (is_map_v<T>) {
             return vt.first;
+        } else {
+            return vt;
         }
     }
 
@@ -746,13 +760,17 @@ public:
     table()
         : table(0) {}
 
-    explicit table(size_t /*bucket_count*/,
+    explicit table(size_t bucket_count,
                    Hash const& hash = Hash(),
                    KeyEqual const& equal = KeyEqual(),
                    allocator_type const& alloc_or_container = allocator_type())
         : m_values(alloc_or_container)
         , m_hash(hash)
-        , m_equal(equal) {}
+        , m_equal(equal) {
+        if (0 != bucket_count) {
+            reserve(bucket_count);
+        }
+    }
 
     table(size_t bucket_count, allocator_type const& alloc)
         : table(bucket_count, Hash(), KeyEqual(), alloc) {}
@@ -1184,6 +1202,7 @@ public:
         return begin() + static_cast<difference_type>(value_idx_to_remove);
     }
 
+    template <typename Q = T, std::enable_if_t<is_map_v<Q>, bool> = true>
     auto erase(const_iterator it) -> iterator {
         return erase(begin() + (it - cbegin()));
     }
@@ -1375,7 +1394,10 @@ public:
 
     void reserve(size_t capa) {
         capa = std::min(capa, max_size());
-        m_values.reserve(capa);
+        if constexpr (has_reserve<value_container_type>) {
+            // std::deque doesn't have reserve(). Make sure we only call when available
+            m_values.reserve(capa);
+        }
         auto shifts = calc_shifts_for_size(std::max(capa, size()));
         if (0 == m_num_buckets || shifts < m_shifts) {
             m_shifts = shifts;
@@ -1411,14 +1433,14 @@ public:
         }
         for (auto const& b_entry : b) {
             auto it = a.find(get_key(b_entry));
-            if constexpr (std::is_void_v<T>) {
-                // set: only check that the key is here
-                if (a.end() == it) {
+            if constexpr (is_map_v<T>) {
+                // map: check that key is here, then also check that value is the same
+                if (a.end() == it || !(b_entry.second == it->second)) {
                     return false;
                 }
             } else {
-                // map: check that key is here, then also check that value is the same
-                if (a.end() == it || !(b_entry.second == it->second)) {
+                // set: only check that the key is here
+                if (a.end() == it) {
                     return false;
                 }
             }