Use STL algorithms available since C++14 to implement absl::equal and

absl::rotate.

Prior to C++14 these were either polyfills or fixes for bugs in
standard libraries.

PiperOrigin-RevId: 575295101
Change-Id: Ie01e77fedadc879c73203d71babd40c87a419af3

4 files changed, 8 insertions, 384 deletions

diff --git a/absl/algorithm/BUILD.bazel b/absl/algorithm/BUILD.bazel
index 0ae77a5d..a339dc13 100644
--- a/absl/algorithm/BUILD.bazel
+++ b/absl/algorithm/BUILD.bazel
@@ -56,20 +56,6 @@ cc_test(
     ],
 )
 
-cc_binary(
-    name = "algorithm_benchmark",
-    testonly = 1,
-    srcs = ["equal_benchmark.cc"],
-    copts = ABSL_TEST_COPTS,
-    linkopts = ABSL_DEFAULT_LINKOPTS,
-    tags = ["benchmark"],
-    deps = [
-        ":algorithm",
-        "//absl/base:core_headers",
-        "@com_github_google_benchmark//:benchmark_main",
-    ],
-)
-
 cc_library(
     name = "container",
     hdrs = [
diff --git a/absl/algorithm/algorithm.h b/absl/algorithm/algorithm.h
index e9b47338..59aeed7d 100644
--- a/absl/algorithm/algorithm.h
+++ b/absl/algorithm/algorithm.h
@@ -31,92 +31,17 @@
 namespace absl {
 ABSL_NAMESPACE_BEGIN
 
-namespace algorithm_internal {
-
-// Performs comparisons with operator==, similar to C++14's `std::equal_to<>`.
-struct EqualTo {
-  template <typename T, typename U>
-  bool operator()(const T& a, const U& b) const {
-    return a == b;
-  }
-};
-
-template <typename InputIter1, typename InputIter2, typename Pred>
-bool EqualImpl(InputIter1 first1, InputIter1 last1, InputIter2 first2,
-               InputIter2 last2, Pred pred, std::input_iterator_tag,
-               std::input_iterator_tag) {
-  while (true) {
-    if (first1 == last1) return first2 == last2;
-    if (first2 == last2) return false;
-    if (!pred(*first1, *first2)) return false;
-    ++first1;
-    ++first2;
-  }
-}
-
-template <typename InputIter1, typename InputIter2, typename Pred>
-bool EqualImpl(InputIter1 first1, InputIter1 last1, InputIter2 first2,
-               InputIter2 last2, Pred&& pred, std::random_access_iterator_tag,
-               std::random_access_iterator_tag) {
-  return (last1 - first1 == last2 - first2) &&
-         std::equal(first1, last1, first2, std::forward<Pred>(pred));
-}
-
-// When we are using our own internal predicate that just applies operator==, we
-// forward to the non-predicate form of std::equal. This enables an optimization
-// in libstdc++ that can result in std::memcmp being used for integer types.
-template <typename InputIter1, typename InputIter2>
-bool EqualImpl(InputIter1 first1, InputIter1 last1, InputIter2 first2,
-               InputIter2 last2, algorithm_internal::EqualTo /* unused */,
-               std::random_access_iterator_tag,
-               std::random_access_iterator_tag) {
-  return (last1 - first1 == last2 - first2) &&
-         std::equal(first1, last1, first2);
-}
-
-template <typename It>
-It RotateImpl(It first, It middle, It last, std::true_type) {
-  return std::rotate(first, middle, last);
-}
-
-template <typename It>
-It RotateImpl(It first, It middle, It last, std::false_type) {
-  std::rotate(first, middle, last);
-  return std::next(first, std::distance(middle, last));
-}
-
-}  // namespace algorithm_internal
-
 // equal()
+// rotate()
 //
-// Compares the equality of two ranges specified by pairs of iterators, using
-// the given predicate, returning true iff for each corresponding iterator i1
-// and i2 in the first and second range respectively, pred(*i1, *i2) == true
-//
-// This comparison takes at most min(`last1` - `first1`, `last2` - `first2`)
-// invocations of the predicate. Additionally, if InputIter1 and InputIter2 are
-// both random-access iterators, and `last1` - `first1` != `last2` - `first2`,
-// then the predicate is never invoked and the function returns false.
+// Historical note: Abseil once provided implementations of these algorithms
+// prior to their adoption in C++14. New code should prefer to use the std
+// variants.
 //
-// This is a C++11-compatible implementation of C++14 `std::equal`.  See
-// https://en.cppreference.com/w/cpp/algorithm/equal for more information.
-template <typename InputIter1, typename InputIter2, typename Pred>
-bool equal(InputIter1 first1, InputIter1 last1, InputIter2 first2,
-           InputIter2 last2, Pred&& pred) {
-  return algorithm_internal::EqualImpl(
-      first1, last1, first2, last2, std::forward<Pred>(pred),
-      typename std::iterator_traits<InputIter1>::iterator_category{},
-      typename std::iterator_traits<InputIter2>::iterator_category{});
-}
-
-// Overload of equal() that performs comparison of two ranges specified by pairs
-// of iterators using operator==.
-template <typename InputIter1, typename InputIter2>
-bool equal(InputIter1 first1, InputIter1 last1, InputIter2 first2,
-           InputIter2 last2) {
-  return absl::equal(first1, last1, first2, last2,
-                     algorithm_internal::EqualTo{});
-}
+// See the documentation for the STL <algorithm> header for more information:
+// https://en.cppreference.com/w/cpp/header/algorithm
+using std::equal;
+using std::rotate;
 
 // linear_search()
 //
@@ -133,26 +58,6 @@ bool linear_search(InputIterator first, InputIterator last,
   return std::find(first, last, value) != last;
 }
 
-// rotate()
-//
-// Performs a left rotation on a range of elements (`first`, `last`) such that
-// `middle` is now the first element. `rotate()` returns an iterator pointing to
-// the first element before rotation. This function is exactly the same as
-// `std::rotate`, but fixes a bug in gcc
-// <= 4.9 where `std::rotate` returns `void` instead of an iterator.
-//
-// The complexity of this algorithm is the same as that of `std::rotate`, but if
-// `ForwardIterator` is not a random-access iterator, then `absl::rotate`
-// performs an additional pass over the range to construct the return value.
-template <typename ForwardIterator>
-ForwardIterator rotate(ForwardIterator first, ForwardIterator middle,
-                       ForwardIterator last) {
-  return algorithm_internal::RotateImpl(
-      first, middle, last,
-      std::is_same<decltype(std::rotate(first, middle, last)),
-                   ForwardIterator>());
-}
-
 ABSL_NAMESPACE_END
 }  // namespace absl
 
diff --git a/absl/algorithm/algorithm_test.cc b/absl/algorithm/algorithm_test.cc
index d18df024..e6ee4695 100644
--- a/absl/algorithm/algorithm_test.cc
+++ b/absl/algorithm/algorithm_test.cc
@@ -24,137 +24,6 @@
 
 namespace {
 
-TEST(EqualTest, DefaultComparisonRandomAccess) {
-  std::vector<int> v1{1, 2, 3};
-  std::vector<int> v2 = v1;
-  std::vector<int> v3 = {1, 2};
-  std::vector<int> v4 = {1, 2, 4};
-
-  EXPECT_TRUE(absl::equal(v1.begin(), v1.end(), v2.begin(), v2.end()));
-  EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), v3.begin(), v3.end()));
-  EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), v4.begin(), v4.end()));
-}
-
-TEST(EqualTest, DefaultComparison) {
-  std::list<int> lst1{1, 2, 3};
-  std::list<int> lst2 = lst1;
-  std::list<int> lst3{1, 2};
-  std::list<int> lst4{1, 2, 4};
-
-  EXPECT_TRUE(absl::equal(lst1.begin(), lst1.end(), lst2.begin(), lst2.end()));
-  EXPECT_FALSE(absl::equal(lst1.begin(), lst1.end(), lst3.begin(), lst3.end()));
-  EXPECT_FALSE(absl::equal(lst1.begin(), lst1.end(), lst4.begin(), lst4.end()));
-}
-
-TEST(EqualTest, EmptyRange) {
-  std::vector<int> v1{1, 2, 3};
-  std::vector<int> empty1;
-  std::vector<int> empty2;
-
-  // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105705
-#if ABSL_INTERNAL_HAVE_MIN_GNUC_VERSION(12, 0)
-#pragma GCC diagnostic push
-#pragma GCC diagnostic ignored "-Wnonnull"
-#endif
-  EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), empty1.begin(), empty1.end()));
-#if ABSL_INTERNAL_HAVE_MIN_GNUC_VERSION(12, 0)
-#pragma GCC diagnostic pop
-#endif
-  EXPECT_FALSE(absl::equal(empty1.begin(), empty1.end(), v1.begin(), v1.end()));
-  EXPECT_TRUE(
-      absl::equal(empty1.begin(), empty1.end(), empty2.begin(), empty2.end()));
-}
-
-TEST(EqualTest, MixedIterTypes) {
-  std::vector<int> v1{1, 2, 3};
-  std::list<int> lst1{v1.begin(), v1.end()};
-  std::list<int> lst2{1, 2, 4};
-  std::list<int> lst3{1, 2};
-
-  EXPECT_TRUE(absl::equal(v1.begin(), v1.end(), lst1.begin(), lst1.end()));
-  EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), lst2.begin(), lst2.end()));
-  EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), lst3.begin(), lst3.end()));
-}
-
-TEST(EqualTest, MixedValueTypes) {
-  std::vector<int> v1{1, 2, 3};
-  std::vector<char> v2{1, 2, 3};
-  std::vector<char> v3{1, 2};
-  std::vector<char> v4{1, 2, 4};
-
-  EXPECT_TRUE(absl::equal(v1.begin(), v1.end(), v2.begin(), v2.end()));
-  EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), v3.begin(), v3.end()));
-  EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), v4.begin(), v4.end()));
-}
-
-TEST(EqualTest, WeirdIterators) {
-  std::vector<bool> v1{true, false};
-  std::vector<bool> v2 = v1;
-  std::vector<bool> v3{true};
-  std::vector<bool> v4{true, true, true};
-
-  EXPECT_TRUE(absl::equal(v1.begin(), v1.end(), v2.begin(), v2.end()));
-  EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), v3.begin(), v3.end()));
-  EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), v4.begin(), v4.end()));
-}
-
-TEST(EqualTest, CustomComparison) {
-  int n[] = {1, 2, 3, 4};
-  std::vector<int*> v1{&n[0], &n[1], &n[2]};
-  std::vector<int*> v2 = v1;
-  std::vector<int*> v3{&n[0], &n[1], &n[3]};
-  std::vector<int*> v4{&n[0], &n[1]};
-
-  auto eq = [](int* a, int* b) { return *a == *b; };
-
-  EXPECT_TRUE(absl::equal(v1.begin(), v1.end(), v2.begin(), v2.end(), eq));
-  EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), v3.begin(), v3.end(), eq));
-  EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), v4.begin(), v4.end(), eq));
-}
-
-TEST(EqualTest, MoveOnlyPredicate) {
-  std::vector<int> v1{1, 2, 3};
-  std::vector<int> v2{4, 5, 6};
-
-  // move-only equality predicate
-  struct Eq {
-    Eq() = default;
-    Eq(Eq &&) = default;
-    Eq(const Eq &) = delete;
-    Eq &operator=(const Eq &) = delete;
-    bool operator()(const int a, const int b) const { return a == b; }
-  };
-
-  EXPECT_TRUE(absl::equal(v1.begin(), v1.end(), v1.begin(), v1.end(), Eq()));
-  EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), v2.begin(), v2.end(), Eq()));
-}
-
-struct CountingTrivialPred {
-  int* count;
-  bool operator()(int, int) const {
-    ++*count;
-    return true;
-  }
-};
-
-TEST(EqualTest, RandomAccessComplexity) {
-  std::vector<int> v1{1, 1, 3};
-  std::vector<int> v2 = v1;
-  std::vector<int> v3{1, 2};
-
-  do {
-    int count = 0;
-    absl::equal(v1.begin(), v1.end(), v2.begin(), v2.end(),
-                CountingTrivialPred{&count});
-    EXPECT_LE(count, 3);
-  } while (std::next_permutation(v2.begin(), v2.end()));
-
-  int count = 0;
-  absl::equal(v1.begin(), v1.end(), v3.begin(), v3.end(),
-              CountingTrivialPred{&count});
-  EXPECT_EQ(count, 0);
-}
-
 class LinearSearchTest : public testing::Test {
  protected:
   LinearSearchTest() : container_{1, 2, 3} {}
@@ -178,14 +47,4 @@ TEST_F(LinearSearchTest, linear_searchConst) {
       absl::linear_search(const_container->begin(), const_container->end(), 4));
 }
 
-TEST(RotateTest, Rotate) {
-  std::vector<int> v{0, 1, 2, 3, 4};
-  EXPECT_EQ(*absl::rotate(v.begin(), v.begin() + 2, v.end()), 0);
-  EXPECT_THAT(v, testing::ElementsAreArray({2, 3, 4, 0, 1}));
-
-  std::list<int> l{0, 1, 2, 3, 4};
-  EXPECT_EQ(*absl::rotate(l.begin(), std::next(l.begin(), 3), l.end()), 0);
-  EXPECT_THAT(l, testing::ElementsAreArray({3, 4, 0, 1, 2}));
-}
-
 }  // namespace
diff --git a/absl/algorithm/equal_benchmark.cc b/absl/algorithm/equal_benchmark.cc
deleted file mode 100644
index 948cd65c..00000000
--- a/absl/algorithm/equal_benchmark.cc
+++ /dev/null
@@ -1,126 +0,0 @@
-// Copyright 2017 The Abseil Authors.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-//      https://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-
-#include <cstdint>
-#include <cstring>
-
-#include "absl/algorithm/algorithm.h"
-#include "benchmark/benchmark.h"
-
-namespace {
-
-// The range of sequence sizes to benchmark.
-constexpr int kMinBenchmarkSize = 1024;
-constexpr int kMaxBenchmarkSize = 8 * 1024 * 1024;
-
-// A user-defined type for use in equality benchmarks. Note that we expect
-// std::memcmp to win for this type: libstdc++'s std::equal only defers to
-// memcmp for integral types. This is because it is not straightforward to
-// guarantee that std::memcmp would produce a result "as-if" compared by
-// operator== for other types (example gotchas: NaN floats, structs with
-// padding).
-struct EightBits {
-  explicit EightBits(int /* unused */) : data(0) {}
-  bool operator==(const EightBits& rhs) const { return data == rhs.data; }
-  uint8_t data;
-};
-
-template <typename T>
-void BM_absl_equal_benchmark(benchmark::State& state) {
-  std::vector<T> xs(state.range(0), T(0));
-  std::vector<T> ys = xs;
-  while (state.KeepRunning()) {
-    const bool same = absl::equal(xs.begin(), xs.end(), ys.begin(), ys.end());
-    benchmark::DoNotOptimize(same);
-  }
-}
-
-template <typename T>
-void BM_std_equal_benchmark(benchmark::State& state) {
-  std::vector<T> xs(state.range(0), T(0));
-  std::vector<T> ys = xs;
-  while (state.KeepRunning()) {
-    const bool same = std::equal(xs.begin(), xs.end(), ys.begin());
-    benchmark::DoNotOptimize(same);
-  }
-}
-
-template <typename T>
-void BM_memcmp_benchmark(benchmark::State& state) {
-  std::vector<T> xs(state.range(0), T(0));
-  std::vector<T> ys = xs;
-  while (state.KeepRunning()) {
-    const bool same =
-        std::memcmp(xs.data(), ys.data(), xs.size() * sizeof(T)) == 0;
-    benchmark::DoNotOptimize(same);
-  }
-}
-
-// The expectation is that the compiler should be able to elide the equality
-// comparison altogether for sufficiently simple types.
-template <typename T>
-void BM_absl_equal_self_benchmark(benchmark::State& state) {
-  std::vector<T> xs(state.range(0), T(0));
-  while (state.KeepRunning()) {
-    const bool same = absl::equal(xs.begin(), xs.end(), xs.begin(), xs.end());
-    benchmark::DoNotOptimize(same);
-  }
-}
-
-BENCHMARK_TEMPLATE(BM_absl_equal_benchmark, uint8_t)
-    ->Range(kMinBenchmarkSize, kMaxBenchmarkSize);
-BENCHMARK_TEMPLATE(BM_std_equal_benchmark, uint8_t)
-    ->Range(kMinBenchmarkSize, kMaxBenchmarkSize);
-BENCHMARK_TEMPLATE(BM_memcmp_benchmark, uint8_t)
-    ->Range(kMinBenchmarkSize, kMaxBenchmarkSize);
-BENCHMARK_TEMPLATE(BM_absl_equal_self_benchmark, uint8_t)
-    ->Range(kMinBenchmarkSize, kMaxBenchmarkSize);
-
-BENCHMARK_TEMPLATE(BM_absl_equal_benchmark, uint16_t)
-    ->Range(kMinBenchmarkSize, kMaxBenchmarkSize);
-BENCHMARK_TEMPLATE(BM_std_equal_benchmark, uint16_t)
-    ->Range(kMinBenchmarkSize, kMaxBenchmarkSize);
-BENCHMARK_TEMPLATE(BM_memcmp_benchmark, uint16_t)
-    ->Range(kMinBenchmarkSize, kMaxBenchmarkSize);
-BENCHMARK_TEMPLATE(BM_absl_equal_self_benchmark, uint16_t)
-    ->Range(kMinBenchmarkSize, kMaxBenchmarkSize);
-
-BENCHMARK_TEMPLATE(BM_absl_equal_benchmark, uint32_t)
-    ->Range(kMinBenchmarkSize, kMaxBenchmarkSize);
-BENCHMARK_TEMPLATE(BM_std_equal_benchmark, uint32_t)
-    ->Range(kMinBenchmarkSize, kMaxBenchmarkSize);
-BENCHMARK_TEMPLATE(BM_memcmp_benchmark, uint32_t)
-    ->Range(kMinBenchmarkSize, kMaxBenchmarkSize);
-BENCHMARK_TEMPLATE(BM_absl_equal_self_benchmark, uint32_t)
-    ->Range(kMinBenchmarkSize, kMaxBenchmarkSize);
-
-BENCHMARK_TEMPLATE(BM_absl_equal_benchmark, uint64_t)
-    ->Range(kMinBenchmarkSize, kMaxBenchmarkSize);
-BENCHMARK_TEMPLATE(BM_std_equal_benchmark, uint64_t)
-    ->Range(kMinBenchmarkSize, kMaxBenchmarkSize);
-BENCHMARK_TEMPLATE(BM_memcmp_benchmark, uint64_t)
-    ->Range(kMinBenchmarkSize, kMaxBenchmarkSize);
-BENCHMARK_TEMPLATE(BM_absl_equal_self_benchmark, uint64_t)
-    ->Range(kMinBenchmarkSize, kMaxBenchmarkSize);
-
-BENCHMARK_TEMPLATE(BM_absl_equal_benchmark, EightBits)
-    ->Range(kMinBenchmarkSize, kMaxBenchmarkSize);
-BENCHMARK_TEMPLATE(BM_std_equal_benchmark, EightBits)
-    ->Range(kMinBenchmarkSize, kMaxBenchmarkSize);
-BENCHMARK_TEMPLATE(BM_memcmp_benchmark, EightBits)
-    ->Range(kMinBenchmarkSize, kMaxBenchmarkSize);
-BENCHMARK_TEMPLATE(BM_absl_equal_self_benchmark, EightBits)
-    ->Range(kMinBenchmarkSize, kMaxBenchmarkSize);
-
-}  // namespace