Use absl hash containers for graph algorithms
This reduces pre-processor time when finding an
ordering automatically substantially.
Before:
ComputeStableSchurOrdering
Delta Cumulative
CreateHessianGraph : 0.50324 0.50324
Preordering : 0.00692 0.51017
StableIndependentSet : 0.26341 0.77358
ConstantParameterBlocks : 0.00095 0.77453
Total : 0.23978 1.01431
After:
ComputeStableSchurOrdering
Delta Cumulative
CreateHessianGraph : 0.17183 0.17183
Preordering : 0.00226 0.17409
StableIndependentSet : 0.12510 0.29919
ConstantParameterBlocks : 0.00073 0.29991
Total : 0.01638 0.31629
Change-Id: I50bbac69f8b3f19240a61a218913cebf34da0db5
diff --git a/internal/ceres/CMakeLists.txt b/internal/ceres/CMakeLists.txt
index ed30c7d..4c501a5 100644
--- a/internal/ceres/CMakeLists.txt
+++ b/internal/ceres/CMakeLists.txt
@@ -47,6 +47,8 @@
list(APPEND CERES_LIBRARY_PRIVATE_DEPENDENCIES absl::strings)
list(APPEND CERES_LIBRARY_PRIVATE_DEPENDENCIES absl::time)
+list(APPEND CERES_LIBRARY_PRIVATE_DEPENDENCIES absl::flat_hash_map)
+list(APPEND CERES_LIBRARY_PRIVATE_DEPENDENCIES absl::flat_hash_set)
list(APPEND CERES_LIBRARY_PUBLIC_DEPENDENCIES absl::log)
list(APPEND CERES_LIBRARY_PUBLIC_DEPENDENCIES absl::check)
diff --git a/internal/ceres/canonical_views_clustering.cc b/internal/ceres/canonical_views_clustering.cc
index 15459e1..a41e5f8 100644
--- a/internal/ceres/canonical_views_clustering.cc
+++ b/internal/ceres/canonical_views_clustering.cc
@@ -31,10 +31,10 @@
#include "ceres/canonical_views_clustering.h"
-#include <unordered_map>
-#include <unordered_set>
#include <vector>
+#include "absl/container/flat_hash_map.h"
+#include "absl/container/flat_hash_set.h"
#include "absl/log/check.h"
#include "absl/log/log.h"
#include "ceres/graph.h"
@@ -43,8 +43,8 @@
namespace ceres::internal {
-using IntMap = std::unordered_map<int, int>;
-using IntSet = std::unordered_set<int>;
+using IntMap = absl::flat_hash_map<int, int>;
+using IntSet = absl::flat_hash_set<int>;
class CERES_NO_EXPORT CanonicalViewsClustering {
public:
@@ -75,7 +75,7 @@
// center).
IntMap view_to_canonical_view_;
// Maps a view to its similarity to its current cluster center.
- std::unordered_map<int, double> view_to_canonical_view_similarity_;
+ absl::flat_hash_map<int, double> view_to_canonical_view_similarity_;
};
void ComputeCanonicalViewsClustering(
diff --git a/internal/ceres/canonical_views_clustering.h b/internal/ceres/canonical_views_clustering.h
index eb05a91..c7c4d2f 100644
--- a/internal/ceres/canonical_views_clustering.h
+++ b/internal/ceres/canonical_views_clustering.h
@@ -41,9 +41,9 @@
#ifndef CERES_INTERNAL_CANONICAL_VIEWS_CLUSTERING_H_
#define CERES_INTERNAL_CANONICAL_VIEWS_CLUSTERING_H_
-#include <unordered_map>
#include <vector>
+#include "absl/container/flat_hash_map.h"
#include "ceres/graph.h"
#include "ceres/internal/disable_warnings.h"
#include "ceres/internal/export.h"
@@ -99,7 +99,7 @@
const CanonicalViewsClusteringOptions& options,
const WeightedGraph<int>& graph,
std::vector<int>* centers,
- std::unordered_map<int, int>* membership);
+ absl::flat_hash_map<int, int>* membership);
struct CERES_NO_EXPORT CanonicalViewsClusteringOptions {
// The minimum number of canonical views to compute.
diff --git a/internal/ceres/canonical_views_clustering_test.cc b/internal/ceres/canonical_views_clustering_test.cc
index fa79582..634eed7 100644
--- a/internal/ceres/canonical_views_clustering_test.cc
+++ b/internal/ceres/canonical_views_clustering_test.cc
@@ -31,8 +31,7 @@
#include "ceres/canonical_views_clustering.h"
-#include <unordered_map>
-
+#include "absl/container/flat_hash_map.h"
#include "ceres/graph.h"
#include "gtest/gtest.h"
@@ -74,7 +73,7 @@
CanonicalViewsClusteringOptions options_;
std::vector<int> centers_;
- std::unordered_map<int, int> membership_;
+ absl::flat_hash_map<int, int> membership_;
};
TEST_F(CanonicalViewsTest, ComputeCanonicalViewsTest) {
diff --git a/internal/ceres/covariance_impl.cc b/internal/ceres/covariance_impl.cc
index bdbb590..8da6d89 100644
--- a/internal/ceres/covariance_impl.cc
+++ b/internal/ceres/covariance_impl.cc
@@ -35,13 +35,13 @@
#include <memory>
#include <numeric>
#include <sstream>
-#include <unordered_set>
#include <utility>
#include <vector>
#include "Eigen/SVD"
#include "Eigen/SparseCore"
#include "Eigen/SparseQR"
+#include "absl/container/flat_hash_set.h"
#include "absl/log/check.h"
#include "absl/log/log.h"
#include "ceres/compressed_col_sparse_matrix_utils.h"
@@ -367,7 +367,7 @@
std::vector<double*> all_parameter_blocks;
problem->GetParameterBlocks(&all_parameter_blocks);
const ProblemImpl::ParameterMap& parameter_map = problem->parameter_map();
- std::unordered_set<ParameterBlock*> parameter_blocks_in_use;
+ absl::flat_hash_set<ParameterBlock*> parameter_blocks_in_use;
std::vector<ResidualBlock*> residual_blocks;
problem->GetResidualBlocks(&residual_blocks);
diff --git a/internal/ceres/graph.h b/internal/ceres/graph.h
index 9b28b06..f683d37 100644
--- a/internal/ceres/graph.h
+++ b/internal/ceres/graph.h
@@ -32,14 +32,13 @@
#define CERES_INTERNAL_GRAPH_H_
#include <limits>
-#include <unordered_map>
-#include <unordered_set>
#include <utility>
+#include "absl/container/flat_hash_map.h"
+#include "absl/container/flat_hash_set.h"
#include "absl/log/check.h"
#include "ceres/internal/export.h"
#include "ceres/map_util.h"
-#include "ceres/pair_hash.h"
#include "ceres/types.h"
namespace ceres::internal {
@@ -52,7 +51,7 @@
// Add a vertex.
void AddVertex(const Vertex& vertex) {
if (vertices_.insert(vertex).second) {
- edges_[vertex] = std::unordered_set<Vertex>();
+ edges_[vertex] = absl::flat_hash_set<Vertex>();
}
}
@@ -62,7 +61,7 @@
}
vertices_.erase(vertex);
- const std::unordered_set<Vertex>& sinks = edges_[vertex];
+ const absl::flat_hash_set<Vertex>& sinks = edges_[vertex];
for (const Vertex& s : sinks) {
edges_[s].erase(vertex);
}
@@ -88,15 +87,15 @@
// Calling Neighbors on a vertex not in the graph will result in
// undefined behaviour.
- const std::unordered_set<Vertex>& Neighbors(const Vertex& vertex) const {
+ const absl::flat_hash_set<Vertex>& Neighbors(const Vertex& vertex) const {
return FindOrDie(edges_, vertex);
}
- const std::unordered_set<Vertex>& vertices() const { return vertices_; }
+ const absl::flat_hash_set<Vertex>& vertices() const { return vertices_; }
private:
- std::unordered_set<Vertex> vertices_;
- std::unordered_map<Vertex, std::unordered_set<Vertex>> edges_;
+ absl::flat_hash_set<Vertex> vertices_;
+ absl::flat_hash_map<Vertex, absl::flat_hash_set<Vertex>> edges_;
};
// A weighted undirected graph templated over the vertex ids. Vertex
@@ -109,7 +108,7 @@
void AddVertex(const Vertex& vertex, double weight) {
if (vertices_.find(vertex) == vertices_.end()) {
vertices_.insert(vertex);
- edges_[vertex] = std::unordered_set<Vertex>();
+ edges_[vertex] = absl::flat_hash_set<Vertex>();
}
vertex_weights_[vertex] = weight;
}
@@ -125,7 +124,7 @@
vertices_.erase(vertex);
vertex_weights_.erase(vertex);
- const std::unordered_set<Vertex>& sinks = edges_[vertex];
+ const absl::flat_hash_set<Vertex>& sinks = edges_[vertex];
for (const Vertex& s : sinks) {
if (vertex < s) {
edge_weights_.erase(std::make_pair(vertex, s));
@@ -187,22 +186,21 @@
// Calling Neighbors on a vertex not in the graph will result in
// undefined behaviour.
- const std::unordered_set<Vertex>& Neighbors(const Vertex& vertex) const {
+ const absl::flat_hash_set<Vertex>& Neighbors(const Vertex& vertex) const {
return FindOrDie(edges_, vertex);
}
- const std::unordered_set<Vertex>& vertices() const { return vertices_; }
+ const absl::flat_hash_set<Vertex>& vertices() const { return vertices_; }
static double InvalidWeight() {
return std::numeric_limits<double>::quiet_NaN();
}
private:
- std::unordered_set<Vertex> vertices_;
- std::unordered_map<Vertex, double> vertex_weights_;
- std::unordered_map<Vertex, std::unordered_set<Vertex>> edges_;
- std::unordered_map<std::pair<Vertex, Vertex>, double, pair_hash>
- edge_weights_;
+ absl::flat_hash_set<Vertex> vertices_;
+ absl::flat_hash_map<Vertex, double> vertex_weights_;
+ absl::flat_hash_map<Vertex, absl::flat_hash_set<Vertex>> edges_;
+ absl::flat_hash_map<std::pair<Vertex, Vertex>, double> edge_weights_;
};
} // namespace ceres::internal
diff --git a/internal/ceres/graph_algorithms.h b/internal/ceres/graph_algorithms.h
index 60520d5..fd395f8 100644
--- a/internal/ceres/graph_algorithms.h
+++ b/internal/ceres/graph_algorithms.h
@@ -35,11 +35,11 @@
#include <algorithm>
#include <memory>
-#include <unordered_map>
-#include <unordered_set>
#include <utility>
#include <vector>
+#include "absl/container/flat_hash_map.h"
+#include "absl/container/flat_hash_set.h"
#include "absl/log/check.h"
#include "ceres/graph.h"
#include "ceres/internal/export.h"
@@ -96,7 +96,7 @@
template <typename Vertex>
int IndependentSetOrdering(const Graph<Vertex>& graph,
std::vector<Vertex>* ordering) {
- const std::unordered_set<Vertex>& vertices = graph.vertices();
+ const absl::flat_hash_set<Vertex>& vertices = graph.vertices();
const int num_vertices = vertices.size();
CHECK(ordering != nullptr);
@@ -109,7 +109,7 @@
const char kBlack = 2;
// Mark all vertices white.
- std::unordered_map<Vertex, char> vertex_color;
+ absl::flat_hash_map<Vertex, char> vertex_color;
std::vector<Vertex> vertex_queue;
for (const Vertex& vertex : vertices) {
vertex_color[vertex] = kWhite;
@@ -129,7 +129,7 @@
ordering->push_back(vertex);
vertex_color[vertex] = kBlack;
- const std::unordered_set<Vertex>& neighbors = graph.Neighbors(vertex);
+ const absl::flat_hash_set<Vertex>& neighbors = graph.Neighbors(vertex);
for (const Vertex& neighbor : neighbors) {
vertex_color[neighbor] = kGrey;
}
@@ -165,7 +165,7 @@
int StableIndependentSetOrdering(const Graph<Vertex>& graph,
std::vector<Vertex>* ordering) {
CHECK(ordering != nullptr);
- const std::unordered_set<Vertex>& vertices = graph.vertices();
+ const absl::flat_hash_set<Vertex>& vertices = graph.vertices();
const int num_vertices = vertices.size();
CHECK_EQ(vertices.size(), ordering->size());
@@ -181,7 +181,7 @@
VertexDegreeLessThan<Vertex>(graph));
// Mark all vertices white.
- std::unordered_map<Vertex, char> vertex_color;
+ absl::flat_hash_map<Vertex, char> vertex_color;
for (const Vertex& vertex : vertices) {
vertex_color[vertex] = kWhite;
}
@@ -198,7 +198,7 @@
ordering->push_back(vertex);
vertex_color[vertex] = kBlack;
- const std::unordered_set<Vertex>& neighbors = graph.Neighbors(vertex);
+ const absl::flat_hash_set<Vertex>& neighbors = graph.Neighbors(vertex);
for (const Vertex& neighbor : neighbors) {
vertex_color[neighbor] = kGrey;
}
@@ -228,7 +228,7 @@
// is what gives this data structure its efficiency.
template <typename Vertex>
Vertex FindConnectedComponent(const Vertex& vertex,
- std::unordered_map<Vertex, Vertex>* union_find) {
+ absl::flat_hash_map<Vertex, Vertex>* union_find) {
auto it = union_find->find(vertex);
DCHECK(it != union_find->end());
if (it->second != vertex) {
@@ -265,18 +265,18 @@
// Disjoint-set to keep track of the connected components in the
// maximum spanning tree.
- std::unordered_map<Vertex, Vertex> disjoint_set;
+ absl::flat_hash_map<Vertex, Vertex> disjoint_set;
// Sort of the edges in the graph in decreasing order of their
// weight. Also add the vertices of the graph to the Maximum
// Spanning Tree graph and set each vertex to be its own connected
// component in the disjoint_set structure.
- const std::unordered_set<Vertex>& vertices = graph.vertices();
+ const absl::flat_hash_set<Vertex>& vertices = graph.vertices();
for (const Vertex& vertex1 : vertices) {
forest->AddVertex(vertex1, graph.VertexWeight(vertex1));
disjoint_set[vertex1] = vertex1;
- const std::unordered_set<Vertex>& neighbors = graph.Neighbors(vertex1);
+ const absl::flat_hash_set<Vertex>& neighbors = graph.Neighbors(vertex1);
for (const Vertex& vertex2 : neighbors) {
if (vertex1 >= vertex2) {
continue;
diff --git a/internal/ceres/graph_algorithms_test.cc b/internal/ceres/graph_algorithms_test.cc
index 6c86668..aa1d759 100644
--- a/internal/ceres/graph_algorithms_test.cc
+++ b/internal/ceres/graph_algorithms_test.cc
@@ -32,9 +32,9 @@
#include <algorithm>
#include <memory>
-#include <unordered_set>
#include <vector>
+#include "absl/container/flat_hash_set.h"
#include "ceres/graph.h"
#include "ceres/internal/export.h"
#include "gtest/gtest.h"
@@ -112,7 +112,7 @@
std::unique_ptr<WeightedGraph<int>> forest(
Degree2MaximumSpanningForest(graph));
- const std::unordered_set<int>& vertices = forest->vertices();
+ const absl::flat_hash_set<int>& vertices = forest->vertices();
EXPECT_EQ(vertices.size(), 2);
EXPECT_EQ(forest->VertexWeight(0), 1.0);
EXPECT_EQ(forest->VertexWeight(1), 2.0);
@@ -135,35 +135,35 @@
std::unique_ptr<WeightedGraph<int>> forest(
Degree2MaximumSpanningForest(graph));
- const std::unordered_set<int>& vertices = forest->vertices();
+ const absl::flat_hash_set<int>& vertices = forest->vertices();
EXPECT_EQ(vertices.size(), 5);
{
- const std::unordered_set<int>& neighbors = forest->Neighbors(0);
+ const absl::flat_hash_set<int>& neighbors = forest->Neighbors(0);
EXPECT_EQ(neighbors.size(), 2);
EXPECT_TRUE(neighbors.find(4) != neighbors.end());
EXPECT_TRUE(neighbors.find(3) != neighbors.end());
}
{
- const std::unordered_set<int>& neighbors = forest->Neighbors(3);
+ const absl::flat_hash_set<int>& neighbors = forest->Neighbors(3);
EXPECT_EQ(neighbors.size(), 1);
EXPECT_TRUE(neighbors.find(0) != neighbors.end());
}
{
- const std::unordered_set<int>& neighbors = forest->Neighbors(4);
+ const absl::flat_hash_set<int>& neighbors = forest->Neighbors(4);
EXPECT_EQ(neighbors.size(), 1);
EXPECT_TRUE(neighbors.find(0) != neighbors.end());
}
{
- const std::unordered_set<int>& neighbors = forest->Neighbors(1);
+ const absl::flat_hash_set<int>& neighbors = forest->Neighbors(1);
EXPECT_EQ(neighbors.size(), 0);
}
{
- const std::unordered_set<int>& neighbors = forest->Neighbors(2);
+ const absl::flat_hash_set<int>& neighbors = forest->Neighbors(2);
EXPECT_EQ(neighbors.size(), 0);
}
}
diff --git a/internal/ceres/graph_test.cc b/internal/ceres/graph_test.cc
index 8c8afc6..4801646 100644
--- a/internal/ceres/graph_test.cc
+++ b/internal/ceres/graph_test.cc
@@ -30,8 +30,7 @@
#include "ceres/graph.h"
-#include <unordered_set>
-
+#include "absl/container/flat_hash_set.h"
#include "gtest/gtest.h"
namespace ceres::internal {
@@ -47,7 +46,7 @@
graph.AddVertex(1);
graph.AddEdge(0, 1);
- const std::unordered_set<int>& vertices = graph.vertices();
+ const absl::flat_hash_set<int>& vertices = graph.vertices();
EXPECT_EQ(vertices.size(), 2);
EXPECT_EQ(graph.Neighbors(0).size(), 1);
EXPECT_EQ(graph.Neighbors(1).size(), 1);
@@ -59,7 +58,7 @@
graph.AddVertex(1);
graph.AddEdge(0, 1);
- const std::unordered_set<int>& vertices = graph.vertices();
+ const absl::flat_hash_set<int>& vertices = graph.vertices();
EXPECT_EQ(vertices.size(), 2);
@@ -92,7 +91,7 @@
graph.AddVertex(1, 2.0);
graph.AddEdge(0, 1, 0.5);
- const std::unordered_set<int>& vertices = graph.vertices();
+ const absl::flat_hash_set<int>& vertices = graph.vertices();
EXPECT_EQ(vertices.size(), 2);
EXPECT_EQ(graph.VertexWeight(0), 1.0);
EXPECT_EQ(graph.VertexWeight(1), 2.0);
@@ -108,7 +107,7 @@
graph.AddVertex(1, 2.0);
graph.AddEdge(0, 1, 0.5);
- const std::unordered_set<int>& vertices = graph.vertices();
+ const absl::flat_hash_set<int>& vertices = graph.vertices();
EXPECT_EQ(vertices.size(), 2);
diff --git a/internal/ceres/pair_hash.h b/internal/ceres/pair_hash.h
deleted file mode 100644
index 64882cd..0000000
--- a/internal/ceres/pair_hash.h
+++ /dev/null
@@ -1,116 +0,0 @@
-// Ceres Solver - A fast non-linear least squares minimizer
-// Copyright 2023 Google Inc. All rights reserved.
-// http://ceres-solver.org/
-//
-// Redistribution and use in source and binary forms, with or without
-// modification, are permitted provided that the following conditions are met:
-//
-// * Redistributions of source code must retain the above copyright notice,
-// this list of conditions and the following disclaimer.
-// * Redistributions in binary form must reproduce the above copyright notice,
-// this list of conditions and the following disclaimer in the documentation
-// and/or other materials provided with the distribution.
-// * Neither the name of Google Inc. nor the names of its contributors may be
-// used to endorse or promote products derived from this software without
-// specific prior written permission.
-//
-// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
-// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
-// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
-// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
-// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
-// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
-// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
-// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
-// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
-// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
-// POSSIBILITY OF SUCH DAMAGE.
-//
-// Author: keir@google.com (Keir Mierle)
-//
-// A hasher for std::pair<T, T>.
-
-#ifndef CERES_INTERNAL_PAIR_HASH_H_
-#define CERES_INTERNAL_PAIR_HASH_H_
-
-#include <cstddef>
-#include <cstdint>
-#include <functional>
-#include <utility>
-
-#include "ceres/internal/export.h"
-
-namespace ceres::internal {
-
-#if defined(_WIN32) && !defined(__MINGW64__) && !defined(__MINGW32__)
-#define GG_LONGLONG(x) x##I64
-#define GG_ULONGLONG(x) x##UI64
-#else
-#define GG_LONGLONG(x) x##LL
-#define GG_ULONGLONG(x) x##ULL
-#endif
-
-// The hash function is due to Bob Jenkins (see
-// http://burtleburtle.net/bob/hash/index.html). Each mix takes 36 instructions,
-// in 18 cycles if you're lucky. On x86 architectures, this requires 45
-// instructions in 27 cycles, if you're lucky.
-//
-// clang-format off
-//
-// 32bit version
-inline void hash_mix(uint32_t& a, uint32_t& b, uint32_t& c) {
- a -= b; a -= c; a ^= (c>>13);
- b -= c; b -= a; b ^= (a<<8);
- c -= a; c -= b; c ^= (b>>13);
- a -= b; a -= c; a ^= (c>>12);
- b -= c; b -= a; b ^= (a<<16);
- c -= a; c -= b; c ^= (b>>5);
- a -= b; a -= c; a ^= (c>>3);
- b -= c; b -= a; b ^= (a<<10);
- c -= a; c -= b; c ^= (b>>15);
-}
-
-// 64bit version
-inline void hash_mix(uint64_t& a, uint64_t& b, uint64_t& c) {
- a -= b; a -= c; a ^= (c>>43);
- b -= c; b -= a; b ^= (a<<9);
- c -= a; c -= b; c ^= (b>>8);
- a -= b; a -= c; a ^= (c>>38);
- b -= c; b -= a; b ^= (a<<23);
- c -= a; c -= b; c ^= (b>>5);
- a -= b; a -= c; a ^= (c>>35);
- b -= c; b -= a; b ^= (a<<49);
- c -= a; c -= b; c ^= (b>>11);
-}
-// clang-format on
-
-inline uint32_t Hash32NumWithSeed(uint32_t num, uint32_t c) {
- // The golden ratio; an arbitrary value.
- uint32_t b = 0x9e3779b9UL;
- hash_mix(num, b, c);
- return c;
-}
-
-inline uint64_t Hash64NumWithSeed(uint64_t num, uint64_t c) {
- // More of the golden ratio.
- uint64_t b = GG_ULONGLONG(0xe08c1d668b756f82);
- hash_mix(num, b, c);
- return c;
-}
-
-// Hasher for STL pairs. Requires hashers for both members to be defined.
-struct pair_hash {
- public:
- template <typename T>
- std::size_t operator()(const std::pair<T, T>& p) const {
- const std::size_t h1 = std::hash<T>()(p.first);
- const std::size_t h2 = std::hash<T>()(p.second);
- // The decision below is at compile time
- return (sizeof(h1) <= sizeof(uint32_t)) ? Hash32NumWithSeed(h1, h2)
- : Hash64NumWithSeed(h1, h2);
- }
-};
-
-} // namespace ceres::internal
-
-#endif // CERES_INTERNAL_PAIR_HASH_H_
diff --git a/internal/ceres/parameter_block.h b/internal/ceres/parameter_block.h
index a76192c..96dd9de 100644
--- a/internal/ceres/parameter_block.h
+++ b/internal/ceres/parameter_block.h
@@ -37,8 +37,8 @@
#include <limits>
#include <memory>
#include <string>
-#include <unordered_set>
+#include "absl/container/flat_hash_set.h"
#include "absl/log/check.h"
#include "absl/log/log.h"
#include "absl/strings/str_format.h"
@@ -64,7 +64,7 @@
// proper disposal of the manifold.
class CERES_NO_EXPORT ParameterBlock {
public:
- using ResidualBlockSet = std::unordered_set<ResidualBlock*>;
+ using ResidualBlockSet = absl::flat_hash_set<ResidualBlock*>;
// Create a parameter block with the user state, size, and index specified.
// The size is the size of the parameter block and the index is the position
diff --git a/internal/ceres/parameter_block_ordering.cc b/internal/ceres/parameter_block_ordering.cc
index 68dfb05..6db8a60 100644
--- a/internal/ceres/parameter_block_ordering.cc
+++ b/internal/ceres/parameter_block_ordering.cc
@@ -33,7 +33,6 @@
#include <map>
#include <memory>
#include <set>
-#include <unordered_set>
#include <vector>
#include "absl/log/check.h"
@@ -57,7 +56,7 @@
const std::vector<ParameterBlock*>& parameter_blocks =
program.parameter_blocks();
- const std::unordered_set<ParameterBlock*>& vertices = graph->vertices();
+ const auto& vertices = graph->vertices();
for (auto* parameter_block : parameter_blocks) {
if (vertices.count(parameter_block) > 0) {
ordering->push_back(parameter_block);
diff --git a/internal/ceres/parameter_block_ordering_test.cc b/internal/ceres/parameter_block_ordering_test.cc
index 459a055..feb5f6d 100644
--- a/internal/ceres/parameter_block_ordering_test.cc
+++ b/internal/ceres/parameter_block_ordering_test.cc
@@ -32,9 +32,9 @@
#include <cstddef>
#include <memory>
-#include <unordered_set>
#include <vector>
+#include "absl/container/flat_hash_set.h"
#include "ceres/cost_function.h"
#include "ceres/graph.h"
#include "ceres/problem_impl.h"
@@ -45,7 +45,7 @@
namespace ceres::internal {
-using VertexSet = std::unordered_set<ParameterBlock*>;
+using VertexSet = absl::flat_hash_set<ParameterBlock*>;
template <int M, int... Ns>
class DummyCostFunction : public SizedCostFunction<M, Ns...> {
diff --git a/internal/ceres/problem_impl.h b/internal/ceres/problem_impl.h
index 73a4a05..f5bf4d0 100644
--- a/internal/ceres/problem_impl.h
+++ b/internal/ceres/problem_impl.h
@@ -42,10 +42,9 @@
#include <array>
#include <map>
#include <memory>
-#include <unordered_map>
-#include <unordered_set>
#include <vector>
+#include "absl/container/flat_hash_set.h"
#include "absl/log/check.h"
#include "ceres/context_impl.h"
#include "ceres/internal/disable_warnings.h"
@@ -70,7 +69,7 @@
class CERES_NO_EXPORT ProblemImpl {
public:
using ParameterMap = std::map<double*, ParameterBlock*>;
- using ResidualBlockSet = std::unordered_set<ResidualBlock*>;
+ using ResidualBlockSet = absl::flat_hash_set<ResidualBlock*>;
using CostFunctionRefCount = std::map<CostFunction*, int>;
using LossFunctionRefCount = std::map<LossFunction*, int>;
diff --git a/internal/ceres/single_linkage_clustering.cc b/internal/ceres/single_linkage_clustering.cc
index 8ebbbb9..5545405 100644
--- a/internal/ceres/single_linkage_clustering.cc
+++ b/internal/ceres/single_linkage_clustering.cc
@@ -30,9 +30,8 @@
#include "ceres/single_linkage_clustering.h"
-#include <unordered_map>
-#include <unordered_set>
-
+#include "absl/container/flat_hash_map.h"
+#include "absl/container/flat_hash_set.h"
#include "absl/log/check.h"
#include "ceres/graph.h"
#include "ceres/graph_algorithms.h"
@@ -42,18 +41,18 @@
int ComputeSingleLinkageClustering(
const SingleLinkageClusteringOptions& options,
const WeightedGraph<int>& graph,
- std::unordered_map<int, int>* membership) {
+ absl::flat_hash_map<int, int>* membership) {
CHECK(membership != nullptr);
membership->clear();
// Initially each vertex is in its own cluster.
- const std::unordered_set<int>& vertices = graph.vertices();
+ const absl::flat_hash_set<int>& vertices = graph.vertices();
for (const int v : vertices) {
(*membership)[v] = v;
}
for (const int vertex1 : vertices) {
- const std::unordered_set<int>& neighbors = graph.Neighbors(vertex1);
+ const absl::flat_hash_set<int>& neighbors = graph.Neighbors(vertex1);
for (const int vertex2 : neighbors) {
// Since the graph is undirected, only pay attention to one side
// of the edge and ignore weak edges.
diff --git a/internal/ceres/single_linkage_clustering.h b/internal/ceres/single_linkage_clustering.h
index 3f49540..46a5fb8 100644
--- a/internal/ceres/single_linkage_clustering.h
+++ b/internal/ceres/single_linkage_clustering.h
@@ -31,8 +31,7 @@
#ifndef CERES_INTERNAL_SINGLE_LINKAGE_CLUSTERING_H_
#define CERES_INTERNAL_SINGLE_LINKAGE_CLUSTERING_H_
-#include <unordered_map>
-
+#include "absl/container/flat_hash_map.h"
#include "ceres/graph.h"
#include "ceres/internal/disable_warnings.h"
#include "ceres/internal/export.h"
@@ -58,7 +57,7 @@
CERES_NO_EXPORT int ComputeSingleLinkageClustering(
const SingleLinkageClusteringOptions& options,
const WeightedGraph<int>& graph,
- std::unordered_map<int, int>* membership);
+ absl::flat_hash_map<int, int>* membership);
} // namespace ceres::internal
diff --git a/internal/ceres/single_linkage_clustering_test.cc b/internal/ceres/single_linkage_clustering_test.cc
index cc16cb4..6cb7e59 100644
--- a/internal/ceres/single_linkage_clustering_test.cc
+++ b/internal/ceres/single_linkage_clustering_test.cc
@@ -30,8 +30,7 @@
#include "ceres/single_linkage_clustering.h"
-#include <unordered_map>
-
+#include "absl/container/flat_hash_map.h"
#include "ceres/graph.h"
#include "gtest/gtest.h"
@@ -52,7 +51,7 @@
graph.AddEdge(4, 5, 1.0);
SingleLinkageClusteringOptions options;
- std::unordered_map<int, int> membership;
+ absl::flat_hash_map<int, int> membership;
ComputeSingleLinkageClustering(options, graph, &membership);
EXPECT_EQ(membership.size(), kNumVertices);
@@ -81,7 +80,7 @@
graph.AddEdge(4, 5, 0.5);
SingleLinkageClusteringOptions options;
- std::unordered_map<int, int> membership;
+ absl::flat_hash_map<int, int> membership;
ComputeSingleLinkageClustering(options, graph, &membership);
EXPECT_EQ(membership.size(), kNumVertices);
@@ -111,7 +110,7 @@
graph.AddEdge(4, 5, 1.0);
SingleLinkageClusteringOptions options;
- std::unordered_map<int, int> membership;
+ absl::flat_hash_map<int, int> membership;
ComputeSingleLinkageClustering(options, graph, &membership);
EXPECT_EQ(membership.size(), kNumVertices);
diff --git a/internal/ceres/visibility.cc b/internal/ceres/visibility.cc
index 05ac8b0..ca0853f 100644
--- a/internal/ceres/visibility.cc
+++ b/internal/ceres/visibility.cc
@@ -35,7 +35,6 @@
#include <ctime>
#include <memory>
#include <set>
-#include <unordered_map>
#include <utility>
#include <vector>
@@ -43,7 +42,6 @@
#include "absl/log/log.h"
#include "ceres/block_structure.h"
#include "ceres/graph.h"
-#include "ceres/pair_hash.h"
namespace ceres::internal {
@@ -102,7 +100,7 @@
// Map from camera pairs to number of points visible to both cameras
// in the pair.
- std::unordered_map<std::pair<int, int>, int, pair_hash> camera_pairs;
+ absl::flat_hash_map<std::pair<int, int>, int> camera_pairs;
// Count the number of points visible to each camera/f_block pair.
for (const auto& inverse_visibility_set : inverse_visibility) {
diff --git a/internal/ceres/visibility_based_preconditioner.cc b/internal/ceres/visibility_based_preconditioner.cc
index 0f46a87..0062e1a 100644
--- a/internal/ceres/visibility_based_preconditioner.cc
+++ b/internal/ceres/visibility_based_preconditioner.cc
@@ -36,11 +36,12 @@
#include <memory>
#include <set>
#include <string>
-#include <unordered_set>
#include <utility>
#include <vector>
#include "Eigen/Dense"
+#include "absl/container/flat_hash_map.h"
+#include "absl/container/flat_hash_set.h"
#include "absl/log/check.h"
#include "absl/log/log.h"
#include "ceres/block_random_access_sparse_matrix.h"
@@ -175,7 +176,7 @@
auto schur_complement_graph = CreateSchurComplementGraph(visibility);
CHECK(schur_complement_graph != nullptr);
- std::unordered_map<int, int> membership;
+ absl::flat_hash_map<int, int> membership;
if (options_.visibility_clustering_type == CANONICAL_VIEWS) {
std::vector<int> centers;
@@ -457,17 +458,17 @@
// each vertex.
void VisibilityBasedPreconditioner::ForestToClusterPairs(
const WeightedGraph<int>& forest,
- std::unordered_set<std::pair<int, int>, pair_hash>* cluster_pairs) const {
+ absl::flat_hash_set<std::pair<int, int>>* cluster_pairs) const {
CHECK(cluster_pairs != nullptr);
cluster_pairs->clear();
- const std::unordered_set<int>& vertices = forest.vertices();
+ const absl::flat_hash_set<int>& vertices = forest.vertices();
CHECK_EQ(vertices.size(), num_clusters_);
// Add all the cluster pairs corresponding to the edges in the
// forest.
for (const int cluster1 : vertices) {
cluster_pairs->insert(std::make_pair(cluster1, cluster1));
- const std::unordered_set<int>& neighbors = forest.Neighbors(cluster1);
+ const absl::flat_hash_set<int>& neighbors = forest.Neighbors(cluster1);
for (const int cluster2 : neighbors) {
if (cluster1 < cluster2) {
cluster_pairs->insert(std::make_pair(cluster1, cluster2));
@@ -528,7 +529,7 @@
return cluster_graph;
}
-// Canonical views clustering returns a std::unordered_map from vertices to
+// Canonical views clustering returns a absl::flat_hash_set from vertices to
// cluster ids. Convert this into a flat array for quick lookup. It is
// possible that some of the vertices may not be associated with any
// cluster. In that case, randomly assign them to one of the clusters.
@@ -537,13 +538,13 @@
// the membership_map, we also map the cluster ids to a contiguous set
// of integers so that the cluster ids are in [0, num_clusters_).
void VisibilityBasedPreconditioner::FlattenMembershipMap(
- const std::unordered_map<int, int>& membership_map,
+ const absl::flat_hash_map<int, int>& membership_map,
std::vector<int>* membership_vector) const {
CHECK(membership_vector != nullptr);
membership_vector->resize(0);
membership_vector->resize(num_blocks_, -1);
- std::unordered_map<int, int> cluster_id_to_index;
+ absl::flat_hash_map<int, int> cluster_id_to_index;
// Iterate over the cluster membership map and update the
// cluster_membership_ vector assigning arbitrary cluster ids to
// the few cameras that have not been clustered.
diff --git a/internal/ceres/visibility_based_preconditioner.h b/internal/ceres/visibility_based_preconditioner.h
index d2d4aad..68827b3 100644
--- a/internal/ceres/visibility_based_preconditioner.h
+++ b/internal/ceres/visibility_based_preconditioner.h
@@ -50,15 +50,14 @@
#include <memory>
#include <set>
-#include <unordered_map>
-#include <unordered_set>
#include <utility>
#include <vector>
+#include "absl/container/flat_hash_map.h"
+#include "absl/container/flat_hash_set.h"
#include "ceres/block_structure.h"
#include "ceres/graph.h"
#include "ceres/linear_solver.h"
-#include "ceres/pair_hash.h"
#include "ceres/preconditioner.h"
#include "ceres/sparse_cholesky.h"
@@ -156,7 +155,7 @@
void ScaleOffDiagonalCells();
void ClusterCameras(const std::vector<std::set<int>>& visibility);
- void FlattenMembershipMap(const std::unordered_map<int, int>& membership_map,
+ void FlattenMembershipMap(const absl::flat_hash_map<int, int>& membership_map,
std::vector<int>* membership_vector) const;
void ComputeClusterVisibility(
const std::vector<std::set<int>>& visibility,
@@ -165,7 +164,7 @@
const std::vector<std::set<int>>& visibility) const;
void ForestToClusterPairs(
const WeightedGraph<int>& forest,
- std::unordered_set<std::pair<int, int>, pair_hash>* cluster_pairs) const;
+ absl::flat_hash_set<std::pair<int, int>>* cluster_pairs) const;
void ComputeBlockPairsInPreconditioner(const CompressedRowBlockStructure& bs);
bool IsBlockPairInPreconditioner(int block1, int block2) const;
bool IsBlockPairOffDiagonal(int block1, int block2) const;
@@ -189,7 +188,7 @@
// Set of cluster pairs (including self pairs (i,i)) in the
// preconditioner.
- std::unordered_set<std::pair<int, int>, pair_hash> cluster_pairs_;
+ absl::flat_hash_set<std::pair<int, int>> cluster_pairs_;
std::unique_ptr<SchurEliminatorBase> eliminator_;
// Preconditioner matrix.
diff --git a/internal/ceres/visibility_based_preconditioner_test.cc b/internal/ceres/visibility_based_preconditioner_test.cc
index 4558964..acc7da0 100644
--- a/internal/ceres/visibility_based_preconditioner_test.cc
+++ b/internal/ceres/visibility_based_preconditioner_test.cc
@@ -110,7 +110,7 @@
// AssertionResult IsSparsityStructureValid() {
// preconditioner_->InitStorage(*A_->block_structure());
-// const std::unordered_set<pair<int, int>, pair_hash>& cluster_pairs =
+// const absl::flat_hash_set<pair<int, int>>& cluster_pairs =
// get_cluster_pairs(); const vector<int>& cluster_membership =
// get_cluster_membership();
@@ -135,7 +135,7 @@
// AssertionResult PreconditionerValuesMatch() {
// preconditioner_->Update(*A_, D_.get());
-// const std::unordered_set<pair<int, int>, pair_hash>& cluster_pairs =
+// const absl::flat_hash_set<pair<int, int>>& cluster_pairs =
// get_cluster_pairs(); const BlockRandomAccessSparseMatrix* m = get_m();
// Matrix preconditioner_matrix;
// m->matrix()->ToDenseMatrix(&preconditioner_matrix);
@@ -203,11 +203,11 @@
// return &preconditioner_->block_pairs_;
// }
-// const std::unordered_set<pair<int, int>, pair_hash>& get_cluster_pairs() {
+// const absl::flat_hash_set<pair<int, int>>& get_cluster_pairs() {
// return preconditioner_->cluster_pairs_;
// }
-// std::unordered_set<pair<int, int>, pair_hash>* get_mutable_cluster_pairs()
+// absl::flat_hash_set<pair<int, int>>* get_mutable_cluster_pairs()
// {
// return &preconditioner_->cluster_pairs_;
// }
@@ -253,7 +253,7 @@
// *get_mutable_num_clusters() = 1;
-// std::unordered_set<pair<int, int>, pair_hash>& cluster_pairs =
+// absl::flat_hash_set<pair<int, int>>& cluster_pairs =
// *get_mutable_cluster_pairs(); cluster_pairs.clear();
// cluster_pairs.insert(make_pair(0, 0));
@@ -300,7 +300,7 @@
// }
// *get_mutable_num_clusters() = kNumClusters;
-// std::unordered_set<pair<int, int>, pair_hash>& cluster_pairs =
+// absl::flat_hash_set<pair<int, int>>& cluster_pairs =
// *get_mutable_cluster_pairs(); cluster_pairs.clear(); for (int i = 0; i <
// kNumClusters; ++i) {
// cluster_pairs.insert(make_pair(i, i));
@@ -326,7 +326,7 @@
// *get_mutable_num_clusters() = kNumClusters;
// // Spanning forest has structure 0-1 2
-// std::unordered_set<pair<int, int>, pair_hash>& cluster_pairs =
+// absl::flat_hash_set<pair<int, int>>& cluster_pairs =
// *get_mutable_cluster_pairs(); cluster_pairs.clear(); for (int i = 0; i <
// kNumClusters; ++i) {
// cluster_pairs.insert(make_pair(i, i));
