Use absl::btree_map instead of std::map
Change-Id: Iece280a6cb0f37fa0bc572046b9d7f79ca825ebc
diff --git a/internal/ceres/CMakeLists.txt b/internal/ceres/CMakeLists.txt
index 4c501a5..1355a38 100644
--- a/internal/ceres/CMakeLists.txt
+++ b/internal/ceres/CMakeLists.txt
@@ -49,6 +49,7 @@
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_PRIVATE_DEPENDENCIES absl::btree)
list(APPEND CERES_LIBRARY_PUBLIC_DEPENDENCIES absl::log)
list(APPEND CERES_LIBRARY_PUBLIC_DEPENDENCIES absl::check)
diff --git a/internal/ceres/block_random_access_sparse_matrix.cc b/internal/ceres/block_random_access_sparse_matrix.cc
index 6694d06..4d12044 100644
--- a/internal/ceres/block_random_access_sparse_matrix.cc
+++ b/internal/ceres/block_random_access_sparse_matrix.cc
@@ -32,10 +32,10 @@
#include <algorithm>
#include <memory>
-#include <set>
#include <utility>
#include <vector>
+#include "absl/container/btree_set.h"
#include "absl/log/check.h"
#include "absl/log/log.h"
#include "ceres/internal/export.h"
@@ -47,7 +47,7 @@
BlockRandomAccessSparseMatrix::BlockRandomAccessSparseMatrix(
const std::vector<Block>& blocks,
- const std::set<std::pair<int, int>>& block_pairs,
+ const absl::btree_set<std::pair<int, int>>& block_pairs,
ContextImpl* context,
int num_threads)
: blocks_(blocks), context_(context), num_threads_(num_threads) {
diff --git a/internal/ceres/block_random_access_sparse_matrix.h b/internal/ceres/block_random_access_sparse_matrix.h
index 5121832..b4bfe44 100644
--- a/internal/ceres/block_random_access_sparse_matrix.h
+++ b/internal/ceres/block_random_access_sparse_matrix.h
@@ -33,11 +33,11 @@
#include <cstdint>
#include <memory>
-#include <set>
#include <unordered_map>
#include <utility>
#include <vector>
+#include "absl/container/btree_set.h"
#include "ceres/block_random_access_matrix.h"
#include "ceres/block_sparse_matrix.h"
#include "ceres/block_structure.h"
@@ -61,7 +61,7 @@
// of this matrix.
BlockRandomAccessSparseMatrix(
const std::vector<Block>& blocks,
- const std::set<std::pair<int, int>>& block_pairs,
+ const absl::btree_set<std::pair<int, int>>& block_pairs,
ContextImpl* context,
int num_threads);
diff --git a/internal/ceres/block_random_access_sparse_matrix_test.cc b/internal/ceres/block_random_access_sparse_matrix_test.cc
index 3740682..23f2527 100644
--- a/internal/ceres/block_random_access_sparse_matrix_test.cc
+++ b/internal/ceres/block_random_access_sparse_matrix_test.cc
@@ -32,10 +32,10 @@
#include <limits>
#include <memory>
-#include <set>
#include <utility>
#include <vector>
+#include "absl/container/btree_set.h"
#include "ceres/internal/eigen.h"
#include "gtest/gtest.h"
@@ -50,7 +50,7 @@
blocks.emplace_back(5, 7);
constexpr int num_rows = 3 + 4 + 5;
- std::set<std::pair<int, int>> block_pairs;
+ absl::btree_set<std::pair<int, int>> block_pairs;
int num_nonzeros = 0;
block_pairs.emplace(0, 0);
num_nonzeros += blocks[0].size * blocks[0].size;
@@ -136,7 +136,7 @@
void SetUp() final {
std::vector<Block> blocks;
blocks.emplace_back(1, 0);
- std::set<std::pair<int, int>> block_pairs;
+ absl::btree_set<std::pair<int, int>> block_pairs;
block_pairs.emplace(0, 0);
m_ = std::make_unique<BlockRandomAccessSparseMatrix>(
blocks, block_pairs, &context_, 1);
diff --git a/internal/ceres/covariance_impl.h b/internal/ceres/covariance_impl.h
index 9ff7982..cb35029 100644
--- a/internal/ceres/covariance_impl.h
+++ b/internal/ceres/covariance_impl.h
@@ -31,12 +31,12 @@
#ifndef CERES_INTERNAL_COVARIANCE_IMPL_H_
#define CERES_INTERNAL_COVARIANCE_IMPL_H_
-#include <map>
#include <memory>
-#include <set>
#include <utility>
#include <vector>
+#include "absl/container/btree_map.h"
+#include "absl/container/btree_set.h"
#include "ceres/covariance.h"
#include "ceres/internal/disable_warnings.h"
#include "ceres/internal/export.h"
@@ -90,8 +90,8 @@
Problem::EvaluateOptions evaluate_options_;
bool is_computed_;
bool is_valid_;
- std::map<const double*, int> parameter_block_to_row_index_;
- std::set<const double*> constant_parameter_blocks_;
+ absl::btree_map<const double*, int> parameter_block_to_row_index_;
+ absl::btree_set<const double*> constant_parameter_blocks_;
std::unique_ptr<CompressedRowSparseMatrix> covariance_matrix_;
};
diff --git a/internal/ceres/problem_impl.cc b/internal/ceres/problem_impl.cc
index b60a7cf..fb6f254 100644
--- a/internal/ceres/problem_impl.cc
+++ b/internal/ceres/problem_impl.cc
@@ -36,7 +36,6 @@
#include <cstdint>
#include <iterator>
#include <memory>
-#include <set>
#include <string>
#include <utility>
#include <vector>
@@ -87,7 +86,7 @@
template <typename KeyType>
void DecrementValueOrDeleteKey(const KeyType key,
- std::map<KeyType, int>* container) {
+ absl::btree_map<KeyType, int>* container) {
auto it = container->find(key);
if (it->second == 1) {
delete key;
diff --git a/internal/ceres/problem_impl.h b/internal/ceres/problem_impl.h
index f5bf4d0..0932468 100644
--- a/internal/ceres/problem_impl.h
+++ b/internal/ceres/problem_impl.h
@@ -44,6 +44,7 @@
#include <memory>
#include <vector>
+#include "absl/container/btree_map.h"
#include "absl/container/flat_hash_set.h"
#include "absl/log/check.h"
#include "ceres/context_impl.h"
@@ -68,10 +69,10 @@
class CERES_NO_EXPORT ProblemImpl {
public:
- using ParameterMap = std::map<double*, ParameterBlock*>;
+ using ParameterMap = absl::btree_map<double*, ParameterBlock*>;
using ResidualBlockSet = absl::flat_hash_set<ResidualBlock*>;
- using CostFunctionRefCount = std::map<CostFunction*, int>;
- using LossFunctionRefCount = std::map<LossFunction*, int>;
+ using CostFunctionRefCount = absl::btree_map<CostFunction*, int>;
+ using LossFunctionRefCount = absl::btree_map<LossFunction*, int>;
ProblemImpl();
explicit ProblemImpl(const Problem::Options& options);
diff --git a/internal/ceres/schur_complement_solver.cc b/internal/ceres/schur_complement_solver.cc
index ce0af45..4a2fbba 100644
--- a/internal/ceres/schur_complement_solver.cc
+++ b/internal/ceres/schur_complement_solver.cc
@@ -33,12 +33,12 @@
#include <algorithm>
#include <ctime>
#include <memory>
-#include <set>
#include <utility>
#include <vector>
#include "Eigen/Dense"
#include "Eigen/SparseCore"
+#include "absl/container/btree_set.h"
#include "absl/log/check.h"
#include "ceres/block_random_access_dense_matrix.h"
#include "ceres/block_random_access_matrix.h"
@@ -229,7 +229,7 @@
blocks_ = Tail(bs->cols, num_col_blocks - num_eliminate_blocks);
- std::set<std::pair<int, int>> block_pairs;
+ absl::btree_set<std::pair<int, int>> block_pairs;
for (int i = 0; i < blocks_.size(); ++i) {
block_pairs.emplace(i, i);
}
diff --git a/internal/ceres/schur_eliminator.h b/internal/ceres/schur_eliminator.h
index 77bca54..8fd396d 100644
--- a/internal/ceres/schur_eliminator.h
+++ b/internal/ceres/schur_eliminator.h
@@ -31,12 +31,12 @@
#ifndef CERES_INTERNAL_SCHUR_ELIMINATOR_H_
#define CERES_INTERNAL_SCHUR_ELIMINATOR_H_
-#include <map>
#include <memory>
#include <mutex>
#include <vector>
#include "Eigen/Dense"
+#include "absl/container/btree_map.h"
#include "absl/log/check.h"
#include "ceres/block_random_access_matrix.h"
#include "ceres/block_sparse_matrix.h"
@@ -274,7 +274,7 @@
// buffer_layout[z1] = 0
// buffer_layout[z5] = y1 * z1
// buffer_layout[z2] = y1 * z1 + y1 * z5
- using BufferLayoutType = std::map<int, int>;
+ using BufferLayoutType = absl::btree_map<int, int>;
struct Chunk {
explicit Chunk(int start) : size(0), start(start) {}
int size;
diff --git a/internal/ceres/visibility.cc b/internal/ceres/visibility.cc
index ca0853f..38fc6d9 100644
--- a/internal/ceres/visibility.cc
+++ b/internal/ceres/visibility.cc
@@ -34,10 +34,10 @@
#include <cmath>
#include <ctime>
#include <memory>
-#include <set>
#include <utility>
#include <vector>
+#include "absl/container/btree_set.h"
#include "absl/log/check.h"
#include "absl/log/log.h"
#include "ceres/block_structure.h"
@@ -47,7 +47,7 @@
void ComputeVisibility(const CompressedRowBlockStructure& block_structure,
const int num_eliminate_blocks,
- std::vector<std::set<int>>* visibility) {
+ std::vector<absl::btree_set<int>>* visibility) {
CHECK(visibility != nullptr);
// Clear the visibility vector and resize it to hold a
@@ -73,7 +73,7 @@
}
std::unique_ptr<WeightedGraph<int>> CreateSchurComplementGraph(
- const std::vector<std::set<int>>& visibility) {
+ const std::vector<absl::btree_set<int>>& visibility) {
const time_t start_time = time(nullptr);
// Compute the number of e_blocks/point blocks. Since the visibility
// set for each e_block/camera contains the set of e_blocks/points
@@ -90,9 +90,9 @@
// cameras. However, to compute the sparsity structure of the Schur
// Complement efficiently, its better to have the point->camera
// mapping.
- std::vector<std::set<int>> inverse_visibility(num_points);
+ std::vector<absl::btree_set<int>> inverse_visibility(num_points);
for (int i = 0; i < visibility.size(); i++) {
- const std::set<int>& visibility_set = visibility[i];
+ const absl::btree_set<int>& visibility_set = visibility[i];
for (int v : visibility_set) {
inverse_visibility[v].insert(i);
}
diff --git a/internal/ceres/visibility.h b/internal/ceres/visibility.h
index 2e5f4fc..c93f5f8 100644
--- a/internal/ceres/visibility.h
+++ b/internal/ceres/visibility.h
@@ -36,9 +36,9 @@
#define CERES_INTERNAL_VISIBILITY_H_
#include <memory>
-#include <set>
#include <vector>
+#include "absl/container/btree_set.h"
#include "ceres/graph.h"
#include "ceres/internal/disable_warnings.h"
#include "ceres/internal/export.h"
@@ -58,7 +58,7 @@
CERES_NO_EXPORT void ComputeVisibility(
const CompressedRowBlockStructure& block_structure,
int num_eliminate_blocks,
- std::vector<std::set<int>>* visibility);
+ std::vector<absl::btree_set<int>>* visibility);
// Given f_block visibility as computed by the ComputeVisibility
// function above, construct and return a graph whose vertices are
@@ -74,7 +74,7 @@
// Caller acquires ownership of the returned WeightedGraph pointer
// (heap-allocated).
CERES_NO_EXPORT std::unique_ptr<WeightedGraph<int>> CreateSchurComplementGraph(
- const std::vector<std::set<int>>& visibility);
+ const std::vector<absl::btree_set<int>>& visibility);
} // namespace ceres::internal
diff --git a/internal/ceres/visibility_based_preconditioner.cc b/internal/ceres/visibility_based_preconditioner.cc
index 0062e1a..f245da9 100644
--- a/internal/ceres/visibility_based_preconditioner.cc
+++ b/internal/ceres/visibility_based_preconditioner.cc
@@ -34,12 +34,12 @@
#include <functional>
#include <iterator>
#include <memory>
-#include <set>
#include <string>
#include <utility>
#include <vector>
#include "Eigen/Dense"
+#include "absl/container/btree_set.h"
#include "absl/container/flat_hash_map.h"
#include "absl/container/flat_hash_set.h"
#include "absl/log/check.h"
@@ -121,7 +121,7 @@
// preconditioner matrix.
void VisibilityBasedPreconditioner::ComputeClusterJacobiSparsity(
const CompressedRowBlockStructure& bs) {
- std::vector<std::set<int>> visibility;
+ std::vector<absl::btree_set<int>> visibility;
ComputeVisibility(bs, options_.elimination_groups[0], &visibility);
CHECK_EQ(num_blocks_, visibility.size());
ClusterCameras(visibility);
@@ -139,7 +139,7 @@
// of edges in this forest are the cluster pairs.
void VisibilityBasedPreconditioner::ComputeClusterTridiagonalSparsity(
const CompressedRowBlockStructure& bs) {
- std::vector<std::set<int>> visibility;
+ std::vector<absl::btree_set<int>> visibility;
ComputeVisibility(bs, options_.elimination_groups[0], &visibility);
CHECK_EQ(num_blocks_, visibility.size());
ClusterCameras(visibility);
@@ -148,7 +148,7 @@
// edges are the number of 3D points/e_blocks visible in both the
// clusters at the ends of the edge. Return an approximate degree-2
// maximum spanning forest of this graph.
- std::vector<std::set<int>> cluster_visibility;
+ std::vector<absl::btree_set<int>> cluster_visibility;
ComputeClusterVisibility(visibility, &cluster_visibility);
auto cluster_graph = CreateClusterGraph(cluster_visibility);
CHECK(cluster_graph != nullptr);
@@ -172,7 +172,7 @@
// The cluster_membership_ vector is updated to indicate cluster
// memberships for each camera block.
void VisibilityBasedPreconditioner::ClusterCameras(
- const std::vector<std::set<int>>& visibility) {
+ const std::vector<absl::btree_set<int>>& visibility) {
auto schur_complement_graph = CreateSchurComplementGraph(visibility);
CHECK(schur_complement_graph != nullptr);
@@ -253,7 +253,7 @@
break;
}
- std::set<int> f_blocks;
+ absl::btree_set<int> f_blocks;
for (; r < num_row_blocks; ++r) {
const CompressedRow& row = bs.rows[r];
if (row.cells.front().block_id != e_block_id) {
@@ -481,8 +481,8 @@
// of all its cameras. In other words, the set of points visible to
// any camera in the cluster.
void VisibilityBasedPreconditioner::ComputeClusterVisibility(
- const std::vector<std::set<int>>& visibility,
- std::vector<std::set<int>>* cluster_visibility) const {
+ const std::vector<absl::btree_set<int>>& visibility,
+ std::vector<absl::btree_set<int>>* cluster_visibility) const {
CHECK(cluster_visibility != nullptr);
cluster_visibility->resize(0);
cluster_visibility->resize(num_clusters_);
@@ -498,7 +498,7 @@
// vertices.
std::unique_ptr<WeightedGraph<int>>
VisibilityBasedPreconditioner::CreateClusterGraph(
- const std::vector<std::set<int>>& cluster_visibility) const {
+ const std::vector<absl::btree_set<int>>& cluster_visibility) const {
auto cluster_graph = std::make_unique<WeightedGraph<int>>();
for (int i = 0; i < num_clusters_; ++i) {
@@ -506,10 +506,10 @@
}
for (int i = 0; i < num_clusters_; ++i) {
- const std::set<int>& cluster_i = cluster_visibility[i];
+ const absl::btree_set<int>& cluster_i = cluster_visibility[i];
for (int j = i + 1; j < num_clusters_; ++j) {
std::vector<int> intersection;
- const std::set<int>& cluster_j = cluster_visibility[j];
+ const absl::btree_set<int>& cluster_j = cluster_visibility[j];
std::set_intersection(cluster_i.begin(),
cluster_i.end(),
cluster_j.begin(),
diff --git a/internal/ceres/visibility_based_preconditioner.h b/internal/ceres/visibility_based_preconditioner.h
index 68827b3..159cc69 100644
--- a/internal/ceres/visibility_based_preconditioner.h
+++ b/internal/ceres/visibility_based_preconditioner.h
@@ -49,10 +49,10 @@
#define CERES_INTERNAL_VISIBILITY_BASED_PRECONDITIONER_H_
#include <memory>
-#include <set>
#include <utility>
#include <vector>
+#include "absl/container/btree_set.h"
#include "absl/container/flat_hash_map.h"
#include "absl/container/flat_hash_set.h"
#include "ceres/block_structure.h"
@@ -154,14 +154,14 @@
LinearSolverTerminationType Factorize();
void ScaleOffDiagonalCells();
- void ClusterCameras(const std::vector<std::set<int>>& visibility);
+ void ClusterCameras(const std::vector<absl::btree_set<int>>& visibility);
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,
- std::vector<std::set<int>>* cluster_visibility) const;
+ const std::vector<absl::btree_set<int>>& visibility,
+ std::vector<absl::btree_set<int>>* cluster_visibility) const;
std::unique_ptr<WeightedGraph<int>> CreateClusterGraph(
- const std::vector<std::set<int>>& visibility) const;
+ const std::vector<absl::btree_set<int>>& visibility) const;
void ForestToClusterPairs(
const WeightedGraph<int>& forest,
absl::flat_hash_set<std::pair<int, int>>* cluster_pairs) const;
@@ -184,7 +184,7 @@
// Non-zero camera pairs from the schur complement matrix that are
// present in the preconditioner, sorted by row (first element of
// each pair), then column (second).
- std::set<std::pair<int, int>> block_pairs_;
+ absl::btree_set<std::pair<int, int>> block_pairs_;
// Set of cluster pairs (including self pairs (i,i)) in the
// preconditioner.
diff --git a/internal/ceres/visibility_test.cc b/internal/ceres/visibility_test.cc
index 871ab56..819c5ee 100644
--- a/internal/ceres/visibility_test.cc
+++ b/internal/ceres/visibility_test.cc
@@ -32,9 +32,9 @@
#include "ceres/visibility.h"
#include <memory>
-#include <set>
#include <vector>
+#include "absl/container/btree_set.h"
#include "ceres/block_structure.h"
#include "ceres/graph.h"
#include "gtest/gtest.h"
@@ -94,7 +94,7 @@
}
bs.cols.resize(num_cols);
- std::vector<std::set<int>> visibility;
+ std::vector<absl::btree_set<int>> visibility;
ComputeVisibility(bs, num_eliminate_blocks, &visibility);
ASSERT_EQ(visibility.size(), num_cols - num_eliminate_blocks);
for (const auto& visible : visibility) {
@@ -169,7 +169,7 @@
}
bs.cols.resize(num_cols);
- std::vector<std::set<int>> visibility;
+ std::vector<absl::btree_set<int>> visibility;
ComputeVisibility(bs, num_eliminate_blocks, &visibility);
ASSERT_EQ(visibility.size(), num_cols - num_eliminate_blocks);
for (const auto& visible : visibility) {
