Use absl::btree_map instead of std::map

Change-Id: Iece280a6cb0f37fa0bc572046b9d7f79ca825ebc

internal/ceres/CMakeLists.txt

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)

internal/ceres/block_random_access_sparse_matrix.cc

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) {

internal/ceres/block_random_access_sparse_matrix.h

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);
 

internal/ceres/block_random_access_sparse_matrix_test.cc

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);

internal/ceres/covariance_impl.h

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_;
 };
 

internal/ceres/problem_impl.cc

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;

internal/ceres/problem_impl.h

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);

internal/ceres/schur_complement_solver.cc

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);
   }

internal/ceres/schur_eliminator.h

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;

internal/ceres/visibility.cc

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);
     }

internal/ceres/visibility.h

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
 

internal/ceres/visibility_based_preconditioner.cc

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(),

internal/ceres/visibility_based_preconditioner.h

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.

internal/ceres/visibility_test.cc

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) {