More C++11ification.
1. Replace HashMap and HashSet with std::unordered_map and
std::unordered_set respectively.
2. Extract the pair hasher into a struct pair_hash.
3. Delete collections_port.h
4. Convert explicit iterator based loops to auto based
loops where sensible.
Change-Id: Ib88bcd13a7463d18435639d3b771abaa52080efb
diff --git a/CMakeLists.txt b/CMakeLists.txt
index c78dc41..54e5e3a 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -440,10 +440,6 @@
# they are used when checking for compiler features.
set(CMAKE_REQUIRED_FLAGS ${CMAKE_CXX_FLAGS})
-# Set the Ceres option for C++11.
-# TODO(alex): Remove when #defines are removed from source & config.h
-list(APPEND CERES_COMPILE_OPTIONS CERES_STD_UNORDERED_MAP)
-
if (TBB)
find_package(TBB QUIET)
if (TBB_FOUND)
diff --git a/cmake/config.h.in b/cmake/config.h.in
index 76b853c..d031651 100644
--- a/cmake/config.h.in
+++ b/cmake/config.h.in
@@ -73,13 +73,6 @@
@CERES_HAVE_PTHREAD@
@CERES_HAVE_RWLOCK@
-// Which version of unordered map was used when Ceres was compiled. Exactly
-// one of these will be defined for any given build.
-@CERES_STD_UNORDERED_MAP@
-@CERES_STD_UNORDERED_MAP_IN_TR1_NAMESPACE@
-@CERES_TR1_UNORDERED_MAP@
-@CERES_NO_UNORDERED_MAP@
-
// If defined, the memory header is in <tr1/memory>, otherwise <memory>.
@CERES_TR1_MEMORY_HEADER@
diff --git a/internal/ceres/block_random_access_diagonal_matrix.h b/internal/ceres/block_random_access_diagonal_matrix.h
index 07ffc9d..2a8340b 100644
--- a/internal/ceres/block_random_access_diagonal_matrix.h
+++ b/internal/ceres/block_random_access_diagonal_matrix.h
@@ -36,7 +36,6 @@
#include <utility>
#include "ceres/mutex.h"
#include "ceres/block_random_access_matrix.h"
-#include "ceres/collections_port.h"
#include "ceres/triplet_sparse_matrix.h"
#include "ceres/integral_types.h"
#include "ceres/internal/macros.h"
diff --git a/internal/ceres/block_random_access_sparse_matrix.cc b/internal/ceres/block_random_access_sparse_matrix.cc
index 5432ec1..540a8b9 100644
--- a/internal/ceres/block_random_access_sparse_matrix.cc
+++ b/internal/ceres/block_random_access_sparse_matrix.cc
@@ -69,11 +69,9 @@
// object for looking into the values array of the
// TripletSparseMatrix.
int num_nonzeros = 0;
- for (set<pair<int, int> >::const_iterator it = block_pairs.begin();
- it != block_pairs.end();
- ++it) {
- const int row_block_size = blocks_[it->first];
- const int col_block_size = blocks_[it->second];
+ for (const auto& block_pair : block_pairs) {
+ const int row_block_size = blocks_[block_pair.first];
+ const int col_block_size = blocks_[block_pair.second];
num_nonzeros += row_block_size * col_block_size;
}
@@ -88,24 +86,19 @@
double* values = tsm_->mutable_values();
int pos = 0;
- for (set<pair<int, int> >::const_iterator it = block_pairs.begin();
- it != block_pairs.end();
- ++it) {
- const int row_block_size = blocks_[it->first];
- const int col_block_size = blocks_[it->second];
- cell_values_.push_back(make_pair(make_pair(it->first, it->second),
- values + pos));
- layout_[IntPairToLong(it->first, it->second)] =
+ for (const auto& block_pair : block_pairs) {
+ const int row_block_size = blocks_[block_pair.first];
+ const int col_block_size = blocks_[block_pair.second];
+ cell_values_.push_back(make_pair(block_pair, values + pos));
+ layout_[IntPairToLong(block_pair.first, block_pair.second)] =
new CellInfo(values + pos);
pos += row_block_size * col_block_size;
}
// Fill the sparsity pattern of the underlying matrix.
- for (set<pair<int, int> >::const_iterator it = block_pairs.begin();
- it != block_pairs.end();
- ++it) {
- const int row_block_id = it->first;
- const int col_block_id = it->second;
+ for (const auto& block_pair : block_pairs) {
+ const int row_block_id = block_pair.first;
+ const int col_block_id = block_pair.second;
const int row_block_size = blocks_[row_block_id];
const int col_block_size = blocks_[col_block_id];
int pos =
@@ -125,10 +118,8 @@
// Assume that the user does not hold any locks on any cell blocks
// when they are calling SetZero.
BlockRandomAccessSparseMatrix::~BlockRandomAccessSparseMatrix() {
- for (LayoutType::iterator it = layout_.begin();
- it != layout_.end();
- ++it) {
- delete it->second;
+ for (const auto& entry : layout_) {
+ delete entry.second;
}
}
@@ -163,19 +154,17 @@
void BlockRandomAccessSparseMatrix::SymmetricRightMultiply(const double* x,
double* y) const {
- vector< pair<pair<int, int>, double*> >::const_iterator it =
- cell_values_.begin();
- for (; it != cell_values_.end(); ++it) {
- const int row = it->first.first;
+ for (const auto& cell_position_and_data : cell_values_) {
+ const int row = cell_position_and_data.first.first;
const int row_block_size = blocks_[row];
const int row_block_pos = block_positions_[row];
- const int col = it->first.second;
+ const int col = cell_position_and_data.first.second;
const int col_block_size = blocks_[col];
const int col_block_pos = block_positions_[col];
MatrixVectorMultiply<Eigen::Dynamic, Eigen::Dynamic, 1>(
- it->second, row_block_size, col_block_size,
+ cell_position_and_data.second, row_block_size, col_block_size,
x + col_block_pos,
y + row_block_pos);
@@ -185,7 +174,7 @@
// triangular multiply also.
if (row != col) {
MatrixTransposeVectorMultiply<Eigen::Dynamic, Eigen::Dynamic, 1>(
- it->second, row_block_size, col_block_size,
+ cell_position_and_data.second, row_block_size, col_block_size,
x + row_block_pos,
y + col_block_pos);
}
diff --git a/internal/ceres/block_random_access_sparse_matrix.h b/internal/ceres/block_random_access_sparse_matrix.h
index 2b3c7fd..e79667b 100644
--- a/internal/ceres/block_random_access_sparse_matrix.h
+++ b/internal/ceres/block_random_access_sparse_matrix.h
@@ -32,11 +32,11 @@
#define CERES_INTERNAL_BLOCK_RANDOM_ACCESS_SPARSE_MATRIX_H_
#include <set>
+#include <unordered_map>
#include <vector>
#include <utility>
#include "ceres/mutex.h"
#include "ceres/block_random_access_matrix.h"
-#include "ceres/collections_port.h"
#include "ceres/triplet_sparse_matrix.h"
#include "ceres/integral_types.h"
#include "ceres/internal/macros.h"
@@ -109,7 +109,7 @@
// A mapping from <row_block_id, col_block_id> to the position in
// the values array of tsm_ where the block is stored.
- typedef HashMap<long int, CellInfo* > LayoutType;
+ typedef std::unordered_map<long int, CellInfo* > LayoutType;
LayoutType layout_;
// In order traversal of contents of the matrix. This allows us to
diff --git a/internal/ceres/block_random_access_sparse_matrix_test.cc b/internal/ceres/block_random_access_sparse_matrix_test.cc
index e4d82d0..688b09d 100644
--- a/internal/ceres/block_random_access_sparse_matrix_test.cc
+++ b/internal/ceres/block_random_access_sparse_matrix_test.cc
@@ -68,11 +68,9 @@
EXPECT_EQ(m.num_rows(), num_rows);
EXPECT_EQ(m.num_cols(), num_rows);
- for (set<pair<int, int> >::const_iterator it = block_pairs.begin();
- it != block_pairs.end();
- ++it) {
- const int row_block_id = it->first;
- const int col_block_id = it->second;
+ for (const auto& block_pair : block_pairs) {
+ const int row_block_id = block_pair.first;
+ const int col_block_id = block_pair.second;
int row;
int col;
int row_stride;
diff --git a/internal/ceres/canonical_views_clustering.cc b/internal/ceres/canonical_views_clustering.cc
index b3e9c22..ca8dff5 100644
--- a/internal/ceres/canonical_views_clustering.cc
+++ b/internal/ceres/canonical_views_clustering.cc
@@ -31,7 +31,9 @@
#include "ceres/canonical_views_clustering.h"
-#include "ceres/collections_port.h"
+#include <unordered_set>
+#include <unordered_map>
+
#include "ceres/graph.h"
#include "ceres/internal/macros.h"
#include "ceres/map_util.h"
@@ -42,8 +44,8 @@
using std::vector;
-typedef HashMap<int, int> IntMap;
-typedef HashSet<int> IntSet;
+typedef std::unordered_map<int, int> IntMap;
+typedef std::unordered_set<int> IntSet;
class CanonicalViewsClustering {
public:
@@ -76,7 +78,7 @@
// center).
IntMap view_to_canonical_view_;
// Maps a view to its similarity to its current cluster center.
- HashMap<int, double> view_to_canonical_view_similarity_;
+ std::unordered_map<int, double> view_to_canonical_view_similarity_;
CERES_DISALLOW_COPY_AND_ASSIGN(CanonicalViewsClustering);
};
@@ -111,14 +113,12 @@
int best_view = 0;
// TODO(sameeragarwal): Make this loop multi-threaded.
- for (IntSet::const_iterator view = valid_views.begin();
- view != valid_views.end();
- ++view) {
+ for (const auto& view : valid_views) {
const double difference =
- ComputeClusteringQualityDifference(*view, *centers);
+ ComputeClusteringQualityDifference(view, *centers);
if (difference > best_difference) {
best_difference = difference;
- best_view = *view;
+ best_view = view;
}
}
@@ -144,11 +144,9 @@
void CanonicalViewsClustering::FindValidViews(
IntSet* valid_views) const {
const IntSet& views = graph_->vertices();
- for (IntSet::const_iterator view = views.begin();
- view != views.end();
- ++view) {
- if (graph_->VertexWeight(*view) != WeightedGraph<int>::InvalidWeight()) {
- valid_views->insert(*view);
+ for (const auto& view : views) {
+ if (graph_->VertexWeight(view) != WeightedGraph<int>::InvalidWeight()) {
+ valid_views->insert(view);
}
}
}
@@ -166,12 +164,10 @@
// was added to the list of canonical views and its nearest
// neighbors became members of its cluster.
const IntSet& neighbors = graph_->Neighbors(candidate);
- for (IntSet::const_iterator neighbor = neighbors.begin();
- neighbor != neighbors.end();
- ++neighbor) {
+ for (const auto& neighbor : neighbors) {
const double old_similarity =
- FindWithDefault(view_to_canonical_view_similarity_, *neighbor, 0.0);
- const double new_similarity = graph_->EdgeWeight(*neighbor, candidate);
+ FindWithDefault(view_to_canonical_view_similarity_, neighbor, 0.0);
+ const double new_similarity = graph_->EdgeWeight(neighbor, candidate);
if (new_similarity > old_similarity) {
difference += new_similarity - old_similarity;
}
@@ -193,16 +189,14 @@
void CanonicalViewsClustering::UpdateCanonicalViewAssignments(
const int canonical_view) {
const IntSet& neighbors = graph_->Neighbors(canonical_view);
- for (IntSet::const_iterator neighbor = neighbors.begin();
- neighbor != neighbors.end();
- ++neighbor) {
+ for (const auto& neighbor : neighbors) {
const double old_similarity =
- FindWithDefault(view_to_canonical_view_similarity_, *neighbor, 0.0);
+ FindWithDefault(view_to_canonical_view_similarity_, neighbor, 0.0);
const double new_similarity =
- graph_->EdgeWeight(*neighbor, canonical_view);
+ graph_->EdgeWeight(neighbor, canonical_view);
if (new_similarity > old_similarity) {
- view_to_canonical_view_[*neighbor] = canonical_view;
- view_to_canonical_view_similarity_[*neighbor] = new_similarity;
+ view_to_canonical_view_[neighbor] = canonical_view;
+ view_to_canonical_view_similarity_[neighbor] = new_similarity;
}
}
}
@@ -222,17 +216,14 @@
static const int kInvalidClusterId = -1;
const IntSet& views = graph_->vertices();
- for (IntSet::const_iterator view = views.begin();
- view != views.end();
- ++view) {
- IntMap::const_iterator it =
- view_to_canonical_view_.find(*view);
+ for (const auto& view : views) {
+ auto it = view_to_canonical_view_.find(view);
int cluster_id = kInvalidClusterId;
if (it != view_to_canonical_view_.end()) {
cluster_id = FindOrDie(center_to_cluster_id, it->second);
}
- InsertOrDie(membership, *view, cluster_id);
+ InsertOrDie(membership, view, cluster_id);
}
}
diff --git a/internal/ceres/canonical_views_clustering.h b/internal/ceres/canonical_views_clustering.h
index 0847f48..6514827 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 "ceres/collections_port.h"
#include "ceres/graph.h"
namespace ceres {
@@ -98,7 +98,7 @@
const CanonicalViewsClusteringOptions& options,
const WeightedGraph<int>& graph,
std::vector<int>* centers,
- HashMap<int, int>* membership);
+ std::unordered_map<int, int>* membership);
struct CanonicalViewsClusteringOptions {
CanonicalViewsClusteringOptions()
diff --git a/internal/ceres/canonical_views_clustering_test.cc b/internal/ceres/canonical_views_clustering_test.cc
index 0c15fc7..a8db293 100644
--- a/internal/ceres/canonical_views_clustering_test.cc
+++ b/internal/ceres/canonical_views_clustering_test.cc
@@ -31,7 +31,7 @@
#include "ceres/canonical_views_clustering.h"
-#include "ceres/collections_port.h"
+#include <unordered_map>
#include "ceres/graph.h"
#include "gtest/gtest.h"
@@ -74,7 +74,7 @@
CanonicalViewsClusteringOptions options_;
std::vector<int> centers_;
- HashMap<int, int> membership_;
+ std::unordered_map<int, int> membership_;
};
TEST_F(CanonicalViewsTest, ComputeCanonicalViewsTest) {
diff --git a/internal/ceres/collections_port.h b/internal/ceres/collections_port.h
deleted file mode 100644
index e699a66..0000000
--- a/internal/ceres/collections_port.h
+++ /dev/null
@@ -1,196 +0,0 @@
-// Ceres Solver - A fast non-linear least squares minimizer
-// Copyright 2015 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)
-//
-// Portable HashMap and HashSet, and a specialized overload for hashing pairs.
-
-#ifndef CERES_INTERNAL_COLLECTIONS_PORT_H_
-#define CERES_INTERNAL_COLLECTIONS_PORT_H_
-
-#include "ceres/internal/port.h"
-
-#if defined(CERES_NO_UNORDERED_MAP)
-# include <map>
-# include <set>
-#endif
-
-#if defined(CERES_TR1_UNORDERED_MAP)
-# include <tr1/unordered_map>
-# include <tr1/unordered_set>
-# define CERES_HASH_NAMESPACE_START namespace std { namespace tr1 {
-# define CERES_HASH_NAMESPACE_END } }
-#endif
-
-#if defined(CERES_STD_UNORDERED_MAP)
-# include <unordered_map>
-# include <unordered_set>
-# define CERES_HASH_NAMESPACE_START namespace std {
-# define CERES_HASH_NAMESPACE_END }
-#endif
-
-#if defined(CERES_STD_UNORDERED_MAP_IN_TR1_NAMESPACE)
-# include <unordered_map>
-# include <unordered_set>
-# define CERES_HASH_NAMESPACE_START namespace std { namespace tr1 {
-# define CERES_HASH_NAMESPACE_END } }
-#endif
-
-#if !defined(CERES_NO_UNORDERED_MAP) && !defined(CERES_TR1_UNORDERED_MAP) && \
- !defined(CERES_STD_UNORDERED_MAP) && !defined(CERES_STD_UNORDERED_MAP_IN_TR1_NAMESPACE) // NOLINT
-# error One of: CERES_NO_UNORDERED_MAP, CERES_TR1_UNORDERED_MAP,\
- CERES_STD_UNORDERED_MAP, CERES_STD_UNORDERED_MAP_IN_TR1_NAMESPACE must be defined! // NOLINT
-#endif
-
-#include <utility>
-#include "ceres/integral_types.h"
-
-// Some systems don't have access to unordered_map/unordered_set. In
-// that case, substitute the hash map/set with normal map/set. The
-// price to pay is slower speed for some operations.
-#if defined(CERES_NO_UNORDERED_MAP)
-
-namespace ceres {
-namespace internal {
-
-template<typename K, typename V>
-struct HashMap : map<K, V> {};
-
-template<typename K>
-struct HashSet : set<K> {};
-
-} // namespace internal
-} // namespace ceres
-
-#else
-
-namespace ceres {
-namespace internal {
-
-#if defined(CERES_TR1_UNORDERED_MAP) || \
- defined(CERES_STD_UNORDERED_MAP_IN_TR1_NAMESPACE)
-template<typename K, typename V>
-struct HashMap : std::tr1::unordered_map<K, V> {};
-template<typename K>
-struct HashSet : std::tr1::unordered_set<K> {};
-#endif
-
-#if defined(CERES_STD_UNORDERED_MAP)
-template<typename K, typename V>
-struct HashMap : std::unordered_map<K, V> {};
-template<typename K>
-struct HashSet : std::unordered_set<K> {};
-#endif
-
-#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.
-//
-// 32bit version
-inline void hash_mix(uint32& a, uint32& b, uint32& 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& a, uint64& b, uint64& 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);
-}
-
-inline uint32 Hash32NumWithSeed(uint32 num, uint32 c) {
- // The golden ratio; an arbitrary value.
- uint32 b = 0x9e3779b9UL;
- hash_mix(num, b, c);
- return c;
-}
-
-inline uint64 Hash64NumWithSeed(uint64 num, uint64 c) {
- // More of the golden ratio.
- uint64 b = GG_ULONGLONG(0xe08c1d668b756f82);
- hash_mix(num, b, c);
- return c;
-}
-
-} // namespace internal
-} // namespace ceres
-
-// Since on some platforms this is a doubly-nested namespace (std::tr1) and
-// others it is not, the entire namespace line must be in a macro.
-CERES_HASH_NAMESPACE_START
-
-// The outrageously annoying specializations below are for portability reasons.
-// In short, it's not possible to have two overloads of hash<pair<T1, T2>
-
-// Hasher for STL pairs. Requires hashers for both members to be defined.
-template<typename T>
-struct hash<pair<T, T> > {
- size_t operator()(const pair<T, T>& p) const {
- size_t h1 = hash<T>()(p.first);
- size_t h2 = hash<T>()(p.second);
- // The decision below is at compile time
- return (sizeof(h1) <= sizeof(ceres::internal::uint32)) ?
- ceres::internal::Hash32NumWithSeed(h1, h2) :
- ceres::internal::Hash64NumWithSeed(h1, h2);
- }
- // Less than operator for MSVC.
- bool operator()(const pair<T, T>& a,
- const pair<T, T>& b) const {
- return a < b;
- }
- static const size_t bucket_size = 4; // These are required by MSVC
- static const size_t min_buckets = 8; // 4 and 8 are defaults.
-};
-
-CERES_HASH_NAMESPACE_END
-
-#endif // CERES_NO_UNORDERED_MAP
-#endif // CERES_INTERNAL_COLLECTIONS_PORT_H_
diff --git a/internal/ceres/coordinate_descent_minimizer.cc b/internal/ceres/coordinate_descent_minimizer.cc
index a334dde..e5569d4 100644
--- a/internal/ceres/coordinate_descent_minimizer.cc
+++ b/internal/ceres/coordinate_descent_minimizer.cc
@@ -80,18 +80,15 @@
// offsets for parallel access.
map<ParameterBlock*, int> parameter_block_index;
map<int, set<double*> > group_to_elements = ordering.group_to_elements();
- for (map<int, set<double*> >::const_iterator it = group_to_elements.begin();
- it != group_to_elements.end();
- ++it) {
- for (set<double*>::const_iterator ptr_it = it->second.begin();
- ptr_it != it->second.end();
- ++ptr_it) {
- parameter_blocks_.push_back(parameter_map.find(*ptr_it)->second);
+ for (const auto& g_t_e : group_to_elements) {
+ const auto& elements = g_t_e.second;
+ for (double* parameter_block: elements) {
+ parameter_blocks_.push_back(parameter_map.find(parameter_block)->second);
parameter_block_index[parameter_blocks_.back()] =
parameter_blocks_.size() - 1;
}
independent_set_offsets_.push_back(
- independent_set_offsets_.back() + it->second.size());
+ independent_set_offsets_.back() + elements.size());
}
// The ordering does not have to contain all parameter blocks, so
@@ -114,8 +111,7 @@
const int num_parameter_blocks = residual_block->NumParameterBlocks();
for (int j = 0; j < num_parameter_blocks; ++j) {
ParameterBlock* parameter_block = residual_block->parameter_blocks()[j];
- const map<ParameterBlock*, int>::const_iterator it =
- parameter_block_index.find(parameter_block);
+ const auto it = parameter_block_index.find(parameter_block);
if (it != parameter_block_index.end()) {
residual_blocks_[it->second].push_back(residual_block);
}
@@ -267,13 +263,12 @@
ordering.group_to_elements();
// Verify that each group is an independent set
- map<int, set<double*> >::const_iterator it = group_to_elements.begin();
- for (; it != group_to_elements.end(); ++it) {
- if (!program.IsParameterBlockSetIndependent(it->second)) {
+ for (const auto& g_t_e : group_to_elements) {
+ if (!program.IsParameterBlockSetIndependent(g_t_e.second)) {
*message =
StringPrintf("The user-provided "
"parameter_blocks_for_inner_iterations does not "
- "form an independent set. Group Id: %d", it->first);
+ "form an independent set. Group Id: %d", g_t_e.first);
return false;
}
}
diff --git a/internal/ceres/covariance_impl.cc b/internal/ceres/covariance_impl.cc
index c52866b..484c94f 100644
--- a/internal/ceres/covariance_impl.cc
+++ b/internal/ceres/covariance_impl.cc
@@ -38,6 +38,7 @@
#include <cstdlib>
#include <numeric>
#include <sstream>
+#include <unordered_set>
#include <utility>
#include <vector>
@@ -45,7 +46,6 @@
#include "Eigen/SparseQR"
#include "Eigen/SVD"
-#include "ceres/collections_port.h"
#include "ceres/compressed_col_sparse_matrix_utils.h"
#include "ceres/compressed_row_sparse_matrix.h"
#include "ceres/covariance.h"
@@ -412,7 +412,7 @@
vector<double*> all_parameter_blocks;
problem->GetParameterBlocks(&all_parameter_blocks);
const ProblemImpl::ParameterMap& parameter_map = problem->parameter_map();
- HashSet<ParameterBlock*> parameter_blocks_in_use;
+ std::unordered_set<ParameterBlock*> parameter_blocks_in_use;
vector<ResidualBlock*> residual_blocks;
problem->GetResidualBlocks(&residual_blocks);
@@ -511,13 +511,10 @@
// rows of the covariance matrix in order.
int i = 0; // index into covariance_blocks.
int cursor = 0; // index into the covariance matrix.
- for (map<const double*, int>::const_iterator it =
- parameter_block_to_row_index_.begin();
- it != parameter_block_to_row_index_.end();
- ++it) {
- const double* row_block = it->first;
+ for (const auto& entry : parameter_block_to_row_index_) {
+ const double* row_block = entry.first;
const int row_block_size = problem->ParameterBlockLocalSize(row_block);
- int row_begin = it->second;
+ int row_begin = entry.second;
// Iterate over the covariance blocks contained in this row block
// and count the number of columns in this row block.
diff --git a/internal/ceres/covariance_test.cc b/internal/ceres/covariance_test.cc
index 92a7626..96c962a 100644
--- a/internal/ceres/covariance_test.cc
+++ b/internal/ceres/covariance_test.cc
@@ -564,9 +564,8 @@
}
int dof = 0; // degrees of freedom = sum of LocalSize()s
- for (BoundsMap::const_iterator iter = column_bounds.begin();
- iter != column_bounds.end(); ++iter) {
- dof = std::max(dof, iter->second.second);
+ for (const auto& bound : column_bounds) {
+ dof = std::max(dof, bound.second.second);
}
ConstMatrixRef expected(expected_covariance, dof, dof);
double diff_norm = (expected.block(row_begin,
diff --git a/internal/ceres/graph.h b/internal/ceres/graph.h
index b96b672..25bb141 100644
--- a/internal/ceres/graph.h
+++ b/internal/ceres/graph.h
@@ -32,11 +32,12 @@
#define CERES_INTERNAL_GRAPH_H_
#include <limits>
+#include <unordered_set>
+#include <unordered_map>
#include <utility>
#include "ceres/integral_types.h"
#include "ceres/map_util.h"
-#include "ceres/collections_port.h"
-#include "ceres/internal/macros.h"
+#include "ceres/pair_hash.h"
#include "ceres/types.h"
#include "glog/logging.h"
@@ -53,7 +54,7 @@
// Add a vertex.
void AddVertex(const Vertex& vertex) {
if (vertices_.insert(vertex).second) {
- edges_[vertex] = HashSet<Vertex>();
+ edges_[vertex] = std::unordered_set<Vertex>();
}
}
@@ -63,10 +64,9 @@
}
vertices_.erase(vertex);
- const HashSet<Vertex>& sinks = edges_[vertex];
- for (typename HashSet<Vertex>::const_iterator it = sinks.begin();
- it != sinks.end(); ++it) {
- edges_[*it].erase(vertex);
+ const std::unordered_set<Vertex>& sinks = edges_[vertex];
+ for (const Vertex& s : sinks) {
+ edges_[s].erase(vertex);
}
edges_.erase(vertex);
@@ -90,19 +90,17 @@
// Calling Neighbors on a vertex not in the graph will result in
// undefined behaviour.
- const HashSet<Vertex>& Neighbors(const Vertex& vertex) const {
+ const std::unordered_set<Vertex>& Neighbors(const Vertex& vertex) const {
return FindOrDie(edges_, vertex);
}
- const HashSet<Vertex>& vertices() const {
+ const std::unordered_set<Vertex>& vertices() const {
return vertices_;
}
private:
- HashSet<Vertex> vertices_;
- HashMap<Vertex, HashSet<Vertex> > edges_;
-
- CERES_DISALLOW_COPY_AND_ASSIGN(Graph);
+ std::unordered_set<Vertex> vertices_;
+ std::unordered_map<Vertex, std::unordered_set<Vertex> > edges_;
};
// A weighted undirected graph templated over the vertex ids. Vertex
@@ -117,7 +115,7 @@
void AddVertex(const Vertex& vertex, double weight) {
if (vertices_.find(vertex) == vertices_.end()) {
vertices_.insert(vertex);
- edges_[vertex] = HashSet<Vertex>();
+ edges_[vertex] = std::unordered_set<Vertex>();
}
vertex_weights_[vertex] = weight;
}
@@ -135,15 +133,14 @@
vertices_.erase(vertex);
vertex_weights_.erase(vertex);
- const HashSet<Vertex>& sinks = edges_[vertex];
- for (typename HashSet<Vertex>::const_iterator it = sinks.begin();
- it != sinks.end(); ++it) {
- if (vertex < *it) {
- edge_weights_.erase(std::make_pair(vertex, *it));
+ const std::unordered_set<Vertex>& sinks = edges_[vertex];
+ for (const Vertex& s : sinks) {
+ if (vertex < s) {
+ edge_weights_.erase(std::make_pair(vertex, s));
} else {
- edge_weights_.erase(std::make_pair(*it, vertex));
+ edge_weights_.erase(std::make_pair(s, vertex));
}
- edges_[*it].erase(vertex);
+ edges_[s].erase(vertex);
}
edges_.erase(vertex);
@@ -198,11 +195,11 @@
// Calling Neighbors on a vertex not in the graph will result in
// undefined behaviour.
- const HashSet<Vertex>& Neighbors(const Vertex& vertex) const {
+ const std::unordered_set<Vertex>& Neighbors(const Vertex& vertex) const {
return FindOrDie(edges_, vertex);
}
- const HashSet<Vertex>& vertices() const {
+ const std::unordered_set<Vertex>& vertices() const {
return vertices_;
}
@@ -211,12 +208,11 @@
}
private:
- HashSet<Vertex> vertices_;
- HashMap<Vertex, double> vertex_weights_;
- HashMap<Vertex, HashSet<Vertex> > edges_;
- HashMap<std::pair<Vertex, Vertex>, double> edge_weights_;
-
- CERES_DISALLOW_COPY_AND_ASSIGN(WeightedGraph);
+ 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_;
};
} // namespace internal
diff --git a/internal/ceres/graph_algorithms.h b/internal/ceres/graph_algorithms.h
index d1d3f52..08837cf 100644
--- a/internal/ceres/graph_algorithms.h
+++ b/internal/ceres/graph_algorithms.h
@@ -34,9 +34,10 @@
#define CERES_INTERNAL_GRAPH_ALGORITHMS_H_
#include <algorithm>
+#include <unordered_map>
+#include <unordered_set>
#include <vector>
#include <utility>
-#include "ceres/collections_port.h"
#include "ceres/graph.h"
#include "ceres/wall_time.h"
#include "glog/logging.h"
@@ -96,7 +97,7 @@
template <typename Vertex>
int IndependentSetOrdering(const Graph<Vertex>& graph,
std::vector<Vertex>* ordering) {
- const HashSet<Vertex>& vertices = graph.vertices();
+ const std::unordered_set<Vertex>& vertices = graph.vertices();
const int num_vertices = vertices.size();
CHECK_NOTNULL(ordering);
@@ -109,34 +110,29 @@
const char kBlack = 2;
// Mark all vertices white.
- HashMap<Vertex, char> vertex_color;
+ std::unordered_map<Vertex, char> vertex_color;
std::vector<Vertex> vertex_queue;
- for (typename HashSet<Vertex>::const_iterator it = vertices.begin();
- it != vertices.end();
- ++it) {
- vertex_color[*it] = kWhite;
- vertex_queue.push_back(*it);
+ for (const Vertex& vertex : vertices) {
+ vertex_color[vertex] = kWhite;
+ vertex_queue.push_back(vertex);
}
-
- std::sort(vertex_queue.begin(), vertex_queue.end(),
+ std::sort(vertex_queue.begin(),
+ vertex_queue.end(),
VertexTotalOrdering<Vertex>(graph));
// Iterate over vertex_queue. Pick the first white vertex, add it
// to the independent set. Mark it black and its neighbors grey.
- for (int i = 0; i < vertex_queue.size(); ++i) {
- const Vertex& vertex = vertex_queue[i];
+ for (const Vertex& vertex : vertex_queue) {
if (vertex_color[vertex] != kWhite) {
continue;
}
ordering->push_back(vertex);
vertex_color[vertex] = kBlack;
- const HashSet<Vertex>& neighbors = graph.Neighbors(vertex);
- for (typename HashSet<Vertex>::const_iterator it = neighbors.begin();
- it != neighbors.end();
- ++it) {
- vertex_color[*it] = kGrey;
+ const std::unordered_set<Vertex>& neighbors = graph.Neighbors(vertex);
+ for (const Vertex& neighbor : neighbors) {
+ vertex_color[neighbor] = kGrey;
}
}
@@ -145,10 +141,7 @@
// Iterate over the vertices and add all the grey vertices to the
// ordering. At this stage there should only be black or grey
// vertices in the graph.
- for (typename std::vector<Vertex>::const_iterator it = vertex_queue.begin();
- it != vertex_queue.end();
- ++it) {
- const Vertex vertex = *it;
+ for (const Vertex& vertex : vertex_queue) {
DCHECK(vertex_color[vertex] != kWhite);
if (vertex_color[vertex] != kBlack) {
ordering->push_back(vertex);
@@ -173,7 +166,7 @@
int StableIndependentSetOrdering(const Graph<Vertex>& graph,
std::vector<Vertex>* ordering) {
CHECK_NOTNULL(ordering);
- const HashSet<Vertex>& vertices = graph.vertices();
+ const std::unordered_set<Vertex>& vertices = graph.vertices();
const int num_vertices = vertices.size();
CHECK_EQ(vertices.size(), ordering->size());
@@ -188,11 +181,9 @@
VertexDegreeLessThan<Vertex>(graph));
// Mark all vertices white.
- HashMap<Vertex, char> vertex_color;
- for (typename HashSet<Vertex>::const_iterator it = vertices.begin();
- it != vertices.end();
- ++it) {
- vertex_color[*it] = kWhite;
+ std::unordered_map<Vertex, char> vertex_color;
+ for (const Vertex& vertex : vertices) {
+ vertex_color[vertex] = kWhite;
}
ordering->clear();
@@ -207,11 +198,9 @@
ordering->push_back(vertex);
vertex_color[vertex] = kBlack;
- const HashSet<Vertex>& neighbors = graph.Neighbors(vertex);
- for (typename HashSet<Vertex>::const_iterator it = neighbors.begin();
- it != neighbors.end();
- ++it) {
- vertex_color[*it] = kGrey;
+ const std::unordered_set<Vertex>& neighbors = graph.Neighbors(vertex);
+ for (const Vertex& neighbor : neighbors) {
+ vertex_color[neighbor] = kGrey;
}
}
@@ -220,10 +209,7 @@
// Iterate over the vertices and add all the grey vertices to the
// ordering. At this stage there should only be black or grey
// vertices in the graph.
- for (typename std::vector<Vertex>::const_iterator it = vertex_queue.begin();
- it != vertex_queue.end();
- ++it) {
- const Vertex vertex = *it;
+ for (const Vertex& vertex : vertex_queue) {
DCHECK(vertex_color[vertex] != kWhite);
if (vertex_color[vertex] != kBlack) {
ordering->push_back(vertex);
@@ -242,8 +228,8 @@
// is what gives this data structure its efficiency.
template <typename Vertex>
Vertex FindConnectedComponent(const Vertex& vertex,
- HashMap<Vertex, Vertex>* union_find) {
- typename HashMap<Vertex, Vertex>::iterator it = union_find->find(vertex);
+ std::unordered_map<Vertex, Vertex>* union_find) {
+ auto it = union_find->find(vertex);
DCHECK(it != union_find->end());
if (it->second != vertex) {
it->second = FindConnectedComponent(it->second, union_find);
@@ -279,25 +265,19 @@
// Disjoint-set to keep track of the connected components in the
// maximum spanning tree.
- HashMap<Vertex, Vertex> disjoint_set;
+ std::unordered_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 HashSet<Vertex>& vertices = graph.vertices();
- for (typename HashSet<Vertex>::const_iterator it = vertices.begin();
- it != vertices.end();
- ++it) {
- const Vertex vertex1 = *it;
+ const std::unordered_set<Vertex>& vertices = graph.vertices();
+ for (const Vertex& vertex1 : vertices) {
forest->AddVertex(vertex1, graph.VertexWeight(vertex1));
disjoint_set[vertex1] = vertex1;
- const HashSet<Vertex>& neighbors = graph.Neighbors(vertex1);
- for (typename HashSet<Vertex>::const_iterator it2 = neighbors.begin();
- it2 != neighbors.end();
- ++it2) {
- const Vertex vertex2 = *it2;
+ const std::unordered_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 1071488..160ece1 100644
--- a/internal/ceres/graph_algorithms_test.cc
+++ b/internal/ceres/graph_algorithms_test.cc
@@ -31,8 +31,8 @@
#include "ceres/graph_algorithms.h"
#include <algorithm>
+#include <unordered_set>
#include "gtest/gtest.h"
-#include "ceres/collections_port.h"
#include "ceres/graph.h"
#include "ceres/internal/port.h"
#include "ceres/internal/scoped_ptr.h"
@@ -112,7 +112,7 @@
scoped_ptr<WeightedGraph<int> > forest(Degree2MaximumSpanningForest(graph));
- const HashSet<int>& vertices = forest->vertices();
+ const std::unordered_set<int>& vertices = forest->vertices();
EXPECT_EQ(vertices.size(), 2);
EXPECT_EQ(forest->VertexWeight(0), 1.0);
EXPECT_EQ(forest->VertexWeight(1), 2.0);
@@ -134,35 +134,35 @@
graph.AddEdge(0, 4, 4.0);
scoped_ptr<WeightedGraph<int> > forest(Degree2MaximumSpanningForest(graph));
- const HashSet<int>& vertices = forest->vertices();
+ const std::unordered_set<int>& vertices = forest->vertices();
EXPECT_EQ(vertices.size(), 5);
{
- const HashSet<int>& neighbors = forest->Neighbors(0);
+ const std::unordered_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 HashSet<int>& neighbors = forest->Neighbors(3);
+ const std::unordered_set<int>& neighbors = forest->Neighbors(3);
EXPECT_EQ(neighbors.size(), 1);
EXPECT_TRUE(neighbors.find(0) != neighbors.end());
}
{
- const HashSet<int>& neighbors = forest->Neighbors(4);
+ const std::unordered_set<int>& neighbors = forest->Neighbors(4);
EXPECT_EQ(neighbors.size(), 1);
EXPECT_TRUE(neighbors.find(0) != neighbors.end());
}
{
- const HashSet<int>& neighbors = forest->Neighbors(1);
+ const std::unordered_set<int>& neighbors = forest->Neighbors(1);
EXPECT_EQ(neighbors.size(), 0);
}
{
- const HashSet<int>& neighbors = forest->Neighbors(2);
+ const std::unordered_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 e9d4e1c..0907f86 100644
--- a/internal/ceres/graph_test.cc
+++ b/internal/ceres/graph_test.cc
@@ -30,8 +30,8 @@
#include "ceres/graph.h"
+#include <unordered_set>
#include "gtest/gtest.h"
-#include "ceres/collections_port.h"
#include "ceres/internal/scoped_ptr.h"
namespace ceres {
@@ -48,7 +48,7 @@
graph.AddVertex(1);
graph.AddEdge(0, 1);
- const HashSet<int>& vertices = graph.vertices();
+ const std::unordered_set<int>& vertices = graph.vertices();
EXPECT_EQ(vertices.size(), 2);
EXPECT_EQ(graph.Neighbors(0).size(), 1);
EXPECT_EQ(graph.Neighbors(1).size(), 1);
@@ -60,7 +60,7 @@
graph.AddVertex(1);
graph.AddEdge(0, 1);
- const HashSet<int>& vertices = graph.vertices();
+ const std::unordered_set<int>& vertices = graph.vertices();
EXPECT_EQ(vertices.size(), 2);
@@ -93,7 +93,7 @@
graph.AddVertex(1, 2.0);
graph.AddEdge(0, 1, 0.5);
- const HashSet<int>& vertices = graph.vertices();
+ const std::unordered_set<int>& vertices = graph.vertices();
EXPECT_EQ(vertices.size(), 2);
EXPECT_EQ(graph.VertexWeight(0), 1.0);
EXPECT_EQ(graph.VertexWeight(1), 2.0);
@@ -109,7 +109,7 @@
graph.AddVertex(1, 2.0);
graph.AddEdge(0, 1, 0.5);
- const HashSet<int>& vertices = graph.vertices();
+ const std::unordered_set<int>& vertices = graph.vertices();
EXPECT_EQ(vertices.size(), 2);
diff --git a/internal/ceres/low_rank_inverse_hessian.cc b/internal/ceres/low_rank_inverse_hessian.cc
index 1c6c992..f3953c4 100644
--- a/internal/ceres/low_rank_inverse_hessian.cc
+++ b/internal/ceres/low_rank_inverse_hessian.cc
@@ -175,12 +175,10 @@
<< "approximation.";
}
- for (list<int>::const_iterator it = indices_.begin();
- it != indices_.end();
- ++it) {
- const double beta = delta_gradient_history_.col(*it).dot(search_direction) /
- delta_x_dot_delta_gradient_(*it);
- search_direction += delta_x_history_.col(*it) * (alpha(*it) - beta);
+ for (const int i : indices_) {
+ const double beta = delta_gradient_history_.col(i).dot(search_direction) /
+ delta_x_dot_delta_gradient_(i);
+ search_direction += delta_x_history_.col(i) * (alpha(i) - beta);
}
}
diff --git a/internal/ceres/ordered_groups_test.cc b/internal/ceres/ordered_groups_test.cc
index 4510686..8cf4324 100644
--- a/internal/ceres/ordered_groups_test.cc
+++ b/internal/ceres/ordered_groups_test.cc
@@ -33,7 +33,6 @@
#include <cstddef>
#include <vector>
#include "gtest/gtest.h"
-#include "ceres/collections_port.h"
namespace ceres {
namespace internal {
diff --git a/internal/ceres/pair_hash.h b/internal/ceres/pair_hash.h
new file mode 100644
index 0000000..7fb32cf
--- /dev/null
+++ b/internal/ceres/pair_hash.h
@@ -0,0 +1,112 @@
+// Ceres Solver - A fast non-linear least squares minimizer
+// Copyright 2018 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 "ceres/internal/port.h"
+#include <utility>
+#include "ceres/integral_types.h"
+
+namespace ceres {
+namespace 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.
+//
+// 32bit version
+inline void hash_mix(uint32& a, uint32& b, uint32& 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& a, uint64& b, uint64& 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);
+}
+
+inline uint32 Hash32NumWithSeed(uint32 num, uint32 c) {
+ // The golden ratio; an arbitrary value.
+ uint32 b = 0x9e3779b9UL;
+ hash_mix(num, b, c);
+ return c;
+}
+
+inline uint64 Hash64NumWithSeed(uint64 num, uint64 c) {
+ // More of the golden ratio.
+ uint64 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)) ? Hash32NumWithSeed(h1, h2)
+ : Hash64NumWithSeed(h1, h2);
+ }
+};
+
+} // namespace internal
+} // namespace ceres
+
+#endif // CERES_INTERNAL_PAIR_HASH_H_
diff --git a/internal/ceres/parameter_block.h b/internal/ceres/parameter_block.h
index 8e21553..a41d9d1 100644
--- a/internal/ceres/parameter_block.h
+++ b/internal/ceres/parameter_block.h
@@ -35,8 +35,8 @@
#include <cstdlib>
#include <limits>
#include <string>
+#include <unordered_set>
#include "ceres/array_utils.h"
-#include "ceres/collections_port.h"
#include "ceres/integral_types.h"
#include "ceres/internal/eigen.h"
#include "ceres/internal/port.h"
@@ -71,7 +71,7 @@
// when it is small, but transitions to a hash set when it has more elements.
//
// For now, use a hash set.
- typedef HashSet<ResidualBlock*> ResidualBlockSet;
+ typedef std::unordered_set<ResidualBlock*> ResidualBlockSet;
// 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 efba339..649ce14 100644
--- a/internal/ceres/parameter_block_ordering.cc
+++ b/internal/ceres/parameter_block_ordering.cc
@@ -30,6 +30,7 @@
#include "ceres/parameter_block_ordering.h"
+#include <unordered_set>
#include "ceres/graph.h"
#include "ceres/graph_algorithms.h"
#include "ceres/internal/scoped_ptr.h"
@@ -55,7 +56,7 @@
event_logger.AddEvent("CreateHessianGraph");
const vector<ParameterBlock*>& parameter_blocks = program.parameter_blocks();
- const HashSet<ParameterBlock*>& vertices = graph->vertices();
+ const std::unordered_set<ParameterBlock*>& vertices = graph->vertices();
for (int i = 0; i < parameter_blocks.size(); ++i) {
if (vertices.count(parameter_blocks[i]) > 0) {
ordering->push_back(parameter_blocks[i]);
@@ -162,10 +163,8 @@
const map<int, set<double*> >& group_to_elements =
ordering->group_to_elements();
- for (map<int, set<double*> >::const_iterator it = group_to_elements.begin();
- it != group_to_elements.end();
- ++it) {
- group_sizes->push_back(it->second.size());
+ for (const auto& g_t_e : group_to_elements) {
+ group_sizes->push_back(g_t_e.second.size());
}
}
diff --git a/internal/ceres/parameter_block_ordering_test.cc b/internal/ceres/parameter_block_ordering_test.cc
index c98cdb5..41babff 100644
--- a/internal/ceres/parameter_block_ordering_test.cc
+++ b/internal/ceres/parameter_block_ordering_test.cc
@@ -31,9 +31,9 @@
#include "ceres/parameter_block_ordering.h"
#include <cstddef>
+#include <unordered_set>
#include <vector>
#include "gtest/gtest.h"
-#include "ceres/collections_port.h"
#include "ceres/graph.h"
#include "ceres/problem_impl.h"
#include "ceres/program.h"
@@ -48,7 +48,7 @@
using std::vector;
typedef Graph<ParameterBlock*> HessianGraph;
-typedef HashSet<ParameterBlock*> VertexSet;
+typedef std::unordered_set<ParameterBlock*> VertexSet;
template <int M, int N1 = 0, int N2 = 0, int N3 = 0>
class DummyCostFunction: public SizedCostFunction<M, N1, N2, N3> {
diff --git a/internal/ceres/problem_impl.cc b/internal/ceres/problem_impl.cc
index 3ed0efd..1f3c55b 100644
--- a/internal/ceres/problem_impl.cc
+++ b/internal/ceres/problem_impl.cc
@@ -63,7 +63,6 @@
using std::map;
using std::string;
using std::vector;
-typedef std::map<double*, internal::ParameterBlock*> ParameterMap;
namespace {
// Returns true if two regions of memory, a and b, with sizes size_a and size_b
@@ -90,7 +89,7 @@
template <typename KeyType>
void DecrementValueOrDeleteKey(const KeyType key,
std::map<KeyType, int>* container) {
- typename std::map<KeyType, int>::iterator it = container->find(key);
+ auto it = container->find(key);
if (it->second == 1) {
delete key;
container->erase(it);
@@ -936,10 +935,9 @@
void ProblemImpl::GetParameterBlocks(vector<double*>* parameter_blocks) const {
CHECK_NOTNULL(parameter_blocks);
parameter_blocks->resize(0);
- for (ParameterMap::const_iterator it = parameter_block_map_.begin();
- it != parameter_block_map_.end();
- ++it) {
- parameter_blocks->push_back(it->first);
+ parameter_blocks->reserve(parameter_block_map_.size());
+ for (const auto& entry : parameter_block_map_) {
+ parameter_blocks->push_back(entry.first);
}
}
diff --git a/internal/ceres/problem_impl.h b/internal/ceres/problem_impl.h
index 03e61d2..4c24e3b 100644
--- a/internal/ceres/problem_impl.h
+++ b/internal/ceres/problem_impl.h
@@ -40,9 +40,9 @@
#define CERES_PUBLIC_PROBLEM_IMPL_H_
#include <map>
+#include <unordered_set>
#include <vector>
-#include "ceres/collections_port.h"
#include "ceres/context_impl.h"
#include "ceres/internal/macros.h"
#include "ceres/internal/port.h"
@@ -65,7 +65,7 @@
class ProblemImpl {
public:
typedef std::map<double*, ParameterBlock*> ParameterMap;
- typedef HashSet<ResidualBlock*> ResidualBlockSet;
+ typedef std::unordered_set<ResidualBlock*> ResidualBlockSet;
typedef std::map<CostFunction*, int> CostFunctionRefCount;
typedef std::map<LossFunction*, int> LossFunctionRefCount;
@@ -203,7 +203,7 @@
ContextImpl* context_impl_;
// The mapping from user pointers to parameter blocks.
- std::map<double*, ParameterBlock*> parameter_block_map_;
+ ParameterMap parameter_block_map_;
// Iff enable_fast_removal is enabled, contains the current residual blocks.
ResidualBlockSet residual_block_set_;
diff --git a/internal/ceres/program.cc b/internal/ceres/program.cc
index 8e97f07..f6cd138 100644
--- a/internal/ceres/program.cc
+++ b/internal/ceres/program.cc
@@ -373,11 +373,10 @@
// blocks in the same residual block are part of
// parameter_block_ptrs as that would violate the assumption that it
// is an independent set in the Hessian matrix.
- for (vector<ResidualBlock*>::const_iterator it = residual_blocks_.begin();
- it != residual_blocks_.end();
- ++it) {
- ParameterBlock* const* parameter_blocks = (*it)->parameter_blocks();
- const int num_parameter_blocks = (*it)->NumParameterBlocks();
+ for (const ResidualBlock* residual_block : residual_blocks_) {
+ ParameterBlock* const* parameter_blocks =
+ residual_block->parameter_blocks();
+ const int num_parameter_blocks = residual_block->NumParameterBlocks();
int count = 0;
for (int i = 0; i < num_parameter_blocks; ++i) {
count += independent_set.count(
diff --git a/internal/ceres/reorder_program.cc b/internal/ceres/reorder_program.cc
index a7c3710..94a35bd 100644
--- a/internal/ceres/reorder_program.cc
+++ b/internal/ceres/reorder_program.cc
@@ -234,23 +234,18 @@
parameter_blocks->clear();
const map<int, set<double*> >& groups = ordering.group_to_elements();
- for (map<int, set<double*> >::const_iterator group_it = groups.begin();
- group_it != groups.end();
- ++group_it) {
- const set<double*>& group = group_it->second;
- for (set<double*>::const_iterator parameter_block_ptr_it = group.begin();
- parameter_block_ptr_it != group.end();
- ++parameter_block_ptr_it) {
- ProblemImpl::ParameterMap::const_iterator parameter_block_it =
- parameter_map.find(*parameter_block_ptr_it);
- if (parameter_block_it == parameter_map.end()) {
+ for (const auto& p : groups) {
+ const set<double*>& group = p.second;
+ for (double* parameter_block_ptr : group) {
+ auto it = parameter_map.find(parameter_block_ptr);
+ if (it == parameter_map.end()) {
*error = StringPrintf("User specified ordering contains a pointer "
"to a double that is not a parameter block in "
"the problem. The invalid double is in group: %d",
- group_it->first);
+ p.first);
return false;
}
- parameter_blocks->push_back(parameter_block_it->second);
+ parameter_blocks->push_back(it->second);
}
}
return true;
diff --git a/internal/ceres/schur_jacobi_preconditioner.cc b/internal/ceres/schur_jacobi_preconditioner.cc
index d7f6fe9..13e6463 100644
--- a/internal/ceres/schur_jacobi_preconditioner.cc
+++ b/internal/ceres/schur_jacobi_preconditioner.cc
@@ -34,7 +34,6 @@
#include <vector>
#include "ceres/block_random_access_diagonal_matrix.h"
#include "ceres/block_sparse_matrix.h"
-#include "ceres/collections_port.h"
#include "ceres/internal/scoped_ptr.h"
#include "ceres/linear_solver.h"
#include "ceres/schur_eliminator.h"
diff --git a/internal/ceres/schur_jacobi_preconditioner.h b/internal/ceres/schur_jacobi_preconditioner.h
index 5398f3f..fb7753b 100644
--- a/internal/ceres/schur_jacobi_preconditioner.h
+++ b/internal/ceres/schur_jacobi_preconditioner.h
@@ -41,7 +41,6 @@
#include <set>
#include <vector>
#include <utility>
-#include "ceres/collections_port.h"
#include "ceres/internal/macros.h"
#include "ceres/internal/scoped_ptr.h"
#include "ceres/preconditioner.h"
diff --git a/internal/ceres/single_linkage_clustering.cc b/internal/ceres/single_linkage_clustering.cc
index 9e9342a..2d3213a 100644
--- a/internal/ceres/single_linkage_clustering.cc
+++ b/internal/ceres/single_linkage_clustering.cc
@@ -30,8 +30,9 @@
#include "ceres/single_linkage_clustering.h"
+#include <unordered_set>
+#include <unordered_map>
#include "ceres/graph.h"
-#include "ceres/collections_port.h"
#include "ceres/graph_algorithms.h"
namespace ceres {
@@ -40,27 +41,18 @@
int ComputeSingleLinkageClustering(
const SingleLinkageClusteringOptions& options,
const WeightedGraph<int>& graph,
- HashMap<int, int>* membership) {
+ std::unordered_map<int, int>* membership) {
CHECK_NOTNULL(membership)->clear();
// Initially each vertex is in its own cluster.
- const HashSet<int>& vertices = graph.vertices();
- for (HashSet<int>::const_iterator it = vertices.begin();
- it != vertices.end();
- ++it) {
- (*membership)[*it] = *it;
+ const std::unordered_set<int>& vertices = graph.vertices();
+ for (const int v : vertices) {
+ (*membership)[v] = v;
}
- for (HashSet<int>::const_iterator it1 = vertices.begin();
- it1 != vertices.end();
- ++it1) {
- const int vertex1 = *it1;
- const HashSet<int>& neighbors = graph.Neighbors(vertex1);
- for (HashSet<int>::const_iterator it2 = neighbors.begin();
- it2 != neighbors.end();
- ++it2) {
- const int vertex2 = *it2;
-
+ for (const int vertex1 : vertices) {
+ const std::unordered_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.
if ((vertex1 > vertex2) ||
@@ -87,11 +79,9 @@
// Make sure that every vertex is connected directly to the vertex
// identifying the cluster.
int num_clusters = 0;
- for (HashMap<int, int>::iterator it = membership->begin();
- it != membership->end();
- ++it) {
- it->second = FindConnectedComponent(it->first, membership);
- if (it->first == it->second) {
+ for (auto& m : *membership) {
+ m.second = FindConnectedComponent(m.first, membership);
+ if (m.first == m.second) {
++num_clusters;
}
}
diff --git a/internal/ceres/single_linkage_clustering.h b/internal/ceres/single_linkage_clustering.h
index 8d1f02b..374125b 100644
--- a/internal/ceres/single_linkage_clustering.h
+++ b/internal/ceres/single_linkage_clustering.h
@@ -31,7 +31,7 @@
#ifndef CERES_INTERNAL_SINGLE_LINKAGE_CLUSTERING_H_
#define CERES_INTERNAL_SINGLE_LINKAGE_CLUSTERING_H_
-#include "ceres/collections_port.h"
+#include <unordered_map>
#include "ceres/graph.h"
namespace ceres {
@@ -60,7 +60,7 @@
int ComputeSingleLinkageClustering(
const SingleLinkageClusteringOptions& options,
const WeightedGraph<int>& graph,
- HashMap<int, int>* membership);
+ std::unordered_map<int, int>* membership);
} // namespace internal
} // namespace ceres
diff --git a/internal/ceres/single_linkage_clustering_test.cc b/internal/ceres/single_linkage_clustering_test.cc
index ca1a661..281c281 100644
--- a/internal/ceres/single_linkage_clustering_test.cc
+++ b/internal/ceres/single_linkage_clustering_test.cc
@@ -30,7 +30,7 @@
#include "ceres/single_linkage_clustering.h"
-#include "ceres/collections_port.h"
+#include <unordered_map>
#include "ceres/graph.h"
#include "gtest/gtest.h"
@@ -52,7 +52,7 @@
graph.AddEdge(4, 5, 1.0);
SingleLinkageClusteringOptions options;
- HashMap<int, int> membership;
+ std::unordered_map<int, int> membership;
ComputeSingleLinkageClustering(options, graph, &membership);
EXPECT_EQ(membership.size(), kNumVertices);
@@ -81,7 +81,7 @@
graph.AddEdge(4, 5, 0.5);
SingleLinkageClusteringOptions options;
- HashMap<int, int> membership;
+ std::unordered_map<int, int> membership;
ComputeSingleLinkageClustering(options, graph, &membership);
EXPECT_EQ(membership.size(), kNumVertices);
@@ -111,7 +111,7 @@
graph.AddEdge(4, 5, 1.0);
SingleLinkageClusteringOptions options;
- HashMap<int, int> membership;
+ std::unordered_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 cb962a6..a446b6b 100644
--- a/internal/ceres/visibility.cc
+++ b/internal/ceres/visibility.cc
@@ -35,10 +35,11 @@
#include <algorithm>
#include <set>
#include <vector>
+#include <unordered_map>
#include <utility>
#include "ceres/block_structure.h"
-#include "ceres/collections_port.h"
#include "ceres/graph.h"
+#include "ceres/pair_hash.h"
#include "glog/logging.h"
namespace ceres {
@@ -98,22 +99,17 @@
vector<set<int> > inverse_visibility(num_points);
for (int i = 0; i < visibility.size(); i++) {
const set<int>& visibility_set = visibility[i];
- for (set<int>::const_iterator it = visibility_set.begin();
- it != visibility_set.end();
- ++it) {
- inverse_visibility[*it].insert(i);
+ for (const int v : visibility_set) {
+ inverse_visibility[v].insert(i);
}
}
// Map from camera pairs to number of points visible to both cameras
// in the pair.
- HashMap<pair<int, int>, int > camera_pairs;
+ std::unordered_map<pair<int, int>, int, pair_hash> camera_pairs;
// Count the number of points visible to each camera/f_block pair.
- for (vector<set<int> >::const_iterator it = inverse_visibility.begin();
- it != inverse_visibility.end();
- ++it) {
- const set<int>& inverse_visibility_set = *it;
+ for (const auto& inverse_visibility_set : inverse_visibility) {
for (set<int>::const_iterator camera1 = inverse_visibility_set.begin();
camera1 != inverse_visibility_set.end();
++camera1) {
@@ -136,14 +132,11 @@
}
// Add an edge for each camera pair.
- for (HashMap<pair<int, int>, int>::const_iterator it = camera_pairs.begin();
- it != camera_pairs.end();
- ++it) {
- const int camera1 = it->first.first;
- const int camera2 = it->first.second;
- CHECK_NE(camera1, camera2);
-
- const int count = it->second;
+ for (const auto& camera_pair_count : camera_pairs) {
+ const int camera1 = camera_pair_count.first.first;
+ const int camera2 = camera_pair_count.first.second;
+ const int count = camera_pair_count.second;
+ DCHECK_NE(camera1, camera2);
// Static cast necessary for Windows.
const double weight = static_cast<double>(count) /
(sqrt(static_cast<double>(
diff --git a/internal/ceres/visibility_based_preconditioner.cc b/internal/ceres/visibility_based_preconditioner.cc
index 24563ae..31d2cc3 100644
--- a/internal/ceres/visibility_based_preconditioner.cc
+++ b/internal/ceres/visibility_based_preconditioner.cc
@@ -40,7 +40,6 @@
#include "ceres/block_random_access_sparse_matrix.h"
#include "ceres/block_sparse_matrix.h"
#include "ceres/canonical_views_clustering.h"
-#include "ceres/collections_port.h"
#include "ceres/graph.h"
#include "ceres/graph_algorithms.h"
#include "ceres/internal/scoped_ptr.h"
@@ -177,7 +176,7 @@
scoped_ptr<WeightedGraph<int> > schur_complement_graph(
CHECK_NOTNULL(CreateSchurComplementGraph(visibility)));
- HashMap<int, int> membership;
+ std::unordered_map<int, int> membership;
if (options_.visibility_clustering_type == CANONICAL_VIEWS) {
vector<int> centers;
@@ -382,11 +381,9 @@
// matrix. Scaling these off-diagonal entries by 1/2 forces this
// matrix to be positive definite.
void VisibilityBasedPreconditioner::ScaleOffDiagonalCells() {
- for (set<pair<int, int> >::const_iterator it = block_pairs_.begin();
- it != block_pairs_.end();
- ++it) {
- const int block1 = it->first;
- const int block2 = it->second;
+ for (const auto& block_pair : block_pairs_) {
+ const int block1 = block_pair.first;
+ const int block2 = block_pair.second;
if (!IsBlockPairOffDiagonal(block1, block2)) {
continue;
}
@@ -464,23 +461,17 @@
// each vertex.
void VisibilityBasedPreconditioner::ForestToClusterPairs(
const WeightedGraph<int>& forest,
- HashSet<pair<int, int> >* cluster_pairs) const {
+ std::unordered_set<pair<int, int>, pair_hash >* cluster_pairs) const {
CHECK_NOTNULL(cluster_pairs)->clear();
- const HashSet<int>& vertices = forest.vertices();
+ const std::unordered_set<int>& vertices = forest.vertices();
CHECK_EQ(vertices.size(), num_clusters_);
// Add all the cluster pairs corresponding to the edges in the
// forest.
- for (HashSet<int>::const_iterator it1 = vertices.begin();
- it1 != vertices.end();
- ++it1) {
- const int cluster1 = *it1;
+ for (const int cluster1 : vertices) {
cluster_pairs->insert(make_pair(cluster1, cluster1));
- const HashSet<int>& neighbors = forest.Neighbors(cluster1);
- for (HashSet<int>::const_iterator it2 = neighbors.begin();
- it2 != neighbors.end();
- ++it2) {
- const int cluster2 = *it2;
+ const std::unordered_set<int>& neighbors = forest.Neighbors(cluster1);
+ for (const int cluster2 : neighbors) {
if (cluster1 < cluster2) {
cluster_pairs->insert(make_pair(cluster1, cluster2));
}
@@ -538,7 +529,7 @@
return cluster_graph;
}
-// Canonical views clustering returns a HashMap from vertices to
+// Canonical views clustering returns a std::unordered_map 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.
@@ -547,20 +538,18 @@
// 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 HashMap<int, int>& membership_map,
+ const std::unordered_map<int, int>& membership_map,
vector<int>* membership_vector) const {
CHECK_NOTNULL(membership_vector)->resize(0);
membership_vector->resize(num_blocks_, -1);
- HashMap<int, int> cluster_id_to_index;
+ std::unordered_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.
- for (HashMap<int, int>::const_iterator it = membership_map.begin();
- it != membership_map.end();
- ++it) {
- const int camera_id = it->first;
- int cluster_id = it->second;
+ for (const auto& m : membership_map) {
+ const int camera_id = m.first;
+ int cluster_id = m.second;
// If the view was not clustered, randomly assign it to one of the
// clusters. This preserves the mathematical correctness of the
diff --git a/internal/ceres/visibility_based_preconditioner.h b/internal/ceres/visibility_based_preconditioner.h
index 40ce2c7..1c831d0 100644
--- a/internal/ceres/visibility_based_preconditioner.h
+++ b/internal/ceres/visibility_based_preconditioner.h
@@ -49,13 +49,15 @@
#define CERES_INTERNAL_VISIBILITY_BASED_PRECONDITIONER_H_
#include <set>
+#include <unordered_map>
+#include <unordered_set>
#include <utility>
#include <vector>
-#include "ceres/collections_port.h"
#include "ceres/graph.h"
#include "ceres/internal/macros.h"
#include "ceres/internal/scoped_ptr.h"
#include "ceres/linear_solver.h"
+#include "ceres/pair_hash.h"
#include "ceres/preconditioner.h"
#include "ceres/sparse_cholesky.h"
@@ -150,7 +152,7 @@
void ScaleOffDiagonalCells();
void ClusterCameras(const std::vector<std::set<int> >& visibility);
- void FlattenMembershipMap(const HashMap<int, int>& membership_map,
+ void FlattenMembershipMap(const std::unordered_map<int, int>& membership_map,
std::vector<int>* membership_vector) const;
void ComputeClusterVisibility(
const std::vector<std::set<int> >& visibility,
@@ -158,7 +160,7 @@
WeightedGraph<int>* CreateClusterGraph(
const std::vector<std::set<int> >& visibility) const;
void ForestToClusterPairs(const WeightedGraph<int>& forest,
- HashSet<std::pair<int, int> >* cluster_pairs) const;
+ std::unordered_set<std::pair<int, int>, pair_hash>* cluster_pairs) const;
void ComputeBlockPairsInPreconditioner(const CompressedRowBlockStructure& bs);
bool IsBlockPairInPreconditioner(int block1, int block2) const;
bool IsBlockPairOffDiagonal(int block1, int block2) const;
@@ -182,7 +184,7 @@
// Set of cluster pairs (including self pairs (i,i)) in the
// preconditioner.
- HashSet<std::pair<int, int> > cluster_pairs_;
+ std::unordered_set<std::pair<int, int>, pair_hash> cluster_pairs_;
scoped_ptr<SchurEliminatorBase> eliminator_;
// Preconditioner matrix.
diff --git a/internal/ceres/visibility_based_preconditioner_test.cc b/internal/ceres/visibility_based_preconditioner_test.cc
index d2f13bc..2227116 100644
--- a/internal/ceres/visibility_based_preconditioner_test.cc
+++ b/internal/ceres/visibility_based_preconditioner_test.cc
@@ -35,15 +35,14 @@
#include "ceres/block_random_access_sparse_matrix.h"
#include "ceres/block_sparse_matrix.h"
#include "ceres/casts.h"
-#include "ceres/collections_port.h"
#include "ceres/file.h"
#include "ceres/internal/eigen.h"
#include "ceres/internal/scoped_ptr.h"
#include "ceres/linear_least_squares_problems.h"
#include "ceres/schur_eliminator.h"
#include "ceres/stringprintf.h"
-#include "ceres/types.h"
#include "ceres/test_util.h"
+#include "ceres/types.h"
#include "glog/logging.h"
#include "gtest/gtest.h"
@@ -110,11 +109,11 @@
// schur_complement_.get(), rhs.data());
// }
-
// AssertionResult IsSparsityStructureValid() {
// preconditioner_->InitStorage(*A_->block_structure());
-// const HashSet<pair<int, int> >& cluster_pairs = get_cluster_pairs();
-// const vector<int>& cluster_membership = get_cluster_membership();
+// const std::unordered_set<pair<int, int>, pair_hash>& cluster_pairs =
+// get_cluster_pairs(); const vector<int>& cluster_membership =
+// get_cluster_membership();
// for (int i = 0; i < num_camera_blocks_; ++i) {
// for (int j = i; j < num_camera_blocks_; ++j) {
@@ -137,8 +136,8 @@
// AssertionResult PreconditionerValuesMatch() {
// preconditioner_->Update(*A_, D_.get());
-// const HashSet<pair<int, int> >& cluster_pairs = get_cluster_pairs();
-// const BlockRandomAccessSparseMatrix* m = get_m();
+// const std::unordered_set<pair<int, int>, pair_hash>& cluster_pairs =
+// get_cluster_pairs(); const BlockRandomAccessSparseMatrix* m = get_m();
// Matrix preconditioner_matrix;
// m->matrix()->ToDenseMatrix(&preconditioner_matrix);
// ConstMatrixRef full_schur_complement(schur_complement_->values(),
@@ -205,11 +204,12 @@
// return &preconditioner_->block_pairs_;
// }
-// const HashSet<pair<int, int> >& get_cluster_pairs() {
+// const std::unordered_set<pair<int, int>, pair_hash>& get_cluster_pairs() {
// return preconditioner_->cluster_pairs_;
// }
-// HashSet<pair<int, int> >* get_mutable_cluster_pairs() {
+// std::unordered_set<pair<int, int>, pair_hash>* get_mutable_cluster_pairs()
+// {
// return &preconditioner_->cluster_pairs_;
// }
@@ -253,8 +253,8 @@
// *get_mutable_num_clusters() = 1;
-// HashSet<pair<int, int> >& cluster_pairs = *get_mutable_cluster_pairs();
-// cluster_pairs.clear();
+// std::unordered_set<pair<int, int>, pair_hash>& cluster_pairs =
+// *get_mutable_cluster_pairs(); cluster_pairs.clear();
// cluster_pairs.insert(make_pair(0, 0));
// EXPECT_TRUE(IsSparsityStructureValid());
@@ -284,8 +284,6 @@
// }
// }
-
-
// TEST_F(VisibilityBasedPreconditionerTest, ClusterJacobi) {
// options_.type = CLUSTER_JACOBI;
// preconditioner_.reset(
@@ -301,9 +299,9 @@
// }
// *get_mutable_num_clusters() = kNumClusters;
-// HashSet<pair<int, int> >& cluster_pairs = *get_mutable_cluster_pairs();
-// cluster_pairs.clear();
-// for (int i = 0; i < kNumClusters; ++i) {
+// std::unordered_set<pair<int, int>, pair_hash>& cluster_pairs =
+// *get_mutable_cluster_pairs(); cluster_pairs.clear(); for (int i = 0; i <
+// kNumClusters; ++i) {
// cluster_pairs.insert(make_pair(i, i));
// }
@@ -311,7 +309,6 @@
// EXPECT_TRUE(PreconditionerValuesMatch());
// }
-
// TEST_F(VisibilityBasedPreconditionerTest, ClusterTridiagonal) {
// options_.type = CLUSTER_TRIDIAGONAL;
// preconditioner_.reset(
@@ -327,9 +324,9 @@
// *get_mutable_num_clusters() = kNumClusters;
// // Spanning forest has structure 0-1 2
-// HashSet<pair<int, int> >& cluster_pairs = *get_mutable_cluster_pairs();
-// cluster_pairs.clear();
-// for (int i = 0; i < kNumClusters; ++i) {
+// std::unordered_set<pair<int, int>, pair_hash>& cluster_pairs =
+// *get_mutable_cluster_pairs(); cluster_pairs.clear(); for (int i = 0; i <
+// kNumClusters; ++i) {
// cluster_pairs.insert(make_pair(i, i));
// }
// cluster_pairs.insert(make_pair(0, 1));