upd

kisasexypantera94 · Apr 17, 2024 · 2e93d24 · 2e93d24
1 parent 82ea823
commit 2e93d24
Show file tree

Hide file tree

Showing 3 changed files with 40 additions and 18 deletions.
diff --git a/src/flat_map.hpp b/src/flat_map.hpp
@@ -0,0 +1,35 @@
+#pragma once
+
+#include <cstddef>
+#include <vector>
+
+template <typename K, typename V>
+class BoundedFlatMap {
+public:
+    BoundedFlatMap(size_t limit): m_limit(limit) {}
+
+public:
+    void emplace(const K& key, const V& val)
+    {
+        if (m_data.size() > m_limit and m_data.back().first < key) {
+            return;
+        }
+
+        const auto element = std::make_pair(key, val);
+        m_data.insert(std::lower_bound(m_data.begin(), m_data.end(), element), element);
+
+        if (m_data.size() > m_limit) {
+            m_data.pop_back();
+        }
+    }
+
+    void reserve(size_t num) { m_data.reserve(num); }
+    auto begin() { return m_data.begin(); }
+    auto end() { return m_data.end(); }
+
+    operator std::vector<std::pair<K, V>>() && { return std::move(m_data); }
+
+private:
+    size_t m_limit;
+    std::vector<std::pair<K, V>> m_data;
+};
diff --git a/src/graph.cpp b/src/graph.cpp
@@ -1,5 +1,6 @@
 #include "graph.hpp"
 
+#include "flat_map.hpp"
 #include "types.hpp"
 
 #include <algorithm>
@@ -102,8 +103,9 @@ GraphConstructor<T>::GreedySearchResult GraphConstructor<T>::GreedySearch(size_t
     std::vector<std::pair<T, size_t>> visited;
     visited.reserve(m_L * 2);
 
-    std::vector<std::pair<T, size_t>> candidates{{Distance(m_points[s_idx], query), s_idx}};
+    BoundedFlatMap<T, size_t> candidates(m_L);
     candidates.reserve(m_L + 1);
+    candidates.emplace(Distance(m_points[s_idx], query), s_idx);
 
     while (true) {
         auto it = std::find_if(candidates.begin(), candidates.end(), [&](const auto& c) {
@@ -121,18 +123,7 @@ GraphConstructor<T>::GreedySearchResult GraphConstructor<T>::GreedySearch(size_t
 
         for (const auto n_idx: m_n_out[p_star_idx]) {
             if (not fast_visited.contains(n_idx)) {
-                const T distance = Distance(m_points[n_idx], query);
-
-                if (candidates.size() > m_L and candidates.back().first < distance) {
-                    continue;
-                }
-
-                const auto value = std::make_pair(distance, n_idx);
-                candidates.insert(std::lower_bound(candidates.begin(), candidates.end(), value), value);
-
-                if (candidates.size() > m_L) {
-                    candidates.pop_back();
-                }
+                candidates.emplace(Distance(m_points[n_idx], query), n_idx);
             }
         }
     }

diff --git a/src/graph.hpp b/src/graph.hpp
@@ -4,7 +4,6 @@
 
 #include <tsl/robin_map.h>
 #include <tsl/robin_set.h>
-#include <boost/container/flat_map.hpp>
 
 #include <span>
 
@@ -24,9 +23,6 @@ class GraphConstructor {
     ~GraphConstructor() = default;
 
 private:
-    template <typename K, typename V>
-    using FlatMap = boost::container::flat_map<K, V>;
-
     template <typename K>
     using HashSet = tsl::robin_set<K>;
 
@@ -48,7 +44,7 @@ class GraphConstructor {
     const size_t m_L;
     const size_t m_dimension;
     const std::span<const Point<T>> m_points;
-    HashMap<size_t, HashSet<size_t>> m_n_out;  // TODO: robin_map
+    HashMap<size_t, HashSet<size_t>> m_n_out;
 };
 
 }  // namespace urukrama