algorithm.h
Go to the documentation of this file.
1 // Copyright 2017 The Abseil Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 //
15 // -----------------------------------------------------------------------------
16 // File: algorithm.h
17 // -----------------------------------------------------------------------------
18 //
19 // This header file contains Google extensions to the standard <algorithm> C++
20 // header.
21 
22 #ifndef ABSL_ALGORITHM_ALGORITHM_H_
23 #define ABSL_ALGORITHM_ALGORITHM_H_
24 
25 #include <algorithm>
26 #include <iterator>
27 #include <type_traits>
28 
29 namespace absl {
30 
31 namespace algorithm_internal {
32 
33 // Performs comparisons with operator==, similar to C++14's `std::equal_to<>`.
34 struct EqualTo {
35  template <typename T, typename U>
36  bool operator()(const T& a, const U& b) const {
37  return a == b;
38  }
39 };
40 
41 template <typename InputIter1, typename InputIter2, typename Pred>
42 bool EqualImpl(InputIter1 first1, InputIter1 last1, InputIter2 first2,
43  InputIter2 last2, Pred pred, std::input_iterator_tag,
44  std::input_iterator_tag) {
45  while (true) {
46  if (first1 == last1) return first2 == last2;
47  if (first2 == last2) return false;
48  if (!pred(*first1, *first2)) return false;
49  ++first1;
50  ++first2;
51  }
52 }
53 
54 template <typename InputIter1, typename InputIter2, typename Pred>
55 bool EqualImpl(InputIter1 first1, InputIter1 last1, InputIter2 first2,
56  InputIter2 last2, Pred&& pred, std::random_access_iterator_tag,
57  std::random_access_iterator_tag) {
58  return (last1 - first1 == last2 - first2) &&
59  std::equal(first1, last1, first2, std::forward<Pred>(pred));
60 }
61 
62 // When we are using our own internal predicate that just applies operator==, we
63 // forward to the non-predicate form of std::equal. This enables an optimization
64 // in libstdc++ that can result in std::memcmp being used for integer types.
65 template <typename InputIter1, typename InputIter2>
66 bool EqualImpl(InputIter1 first1, InputIter1 last1, InputIter2 first2,
67  InputIter2 last2, algorithm_internal::EqualTo /* unused */,
68  std::random_access_iterator_tag,
69  std::random_access_iterator_tag) {
70  return (last1 - first1 == last2 - first2) &&
71  std::equal(first1, last1, first2);
72 }
73 
74 template <typename It>
75 It RotateImpl(It first, It middle, It last, std::true_type) {
76  return std::rotate(first, middle, last);
77 }
78 
79 template <typename It>
80 It RotateImpl(It first, It middle, It last, std::false_type) {
81  std::rotate(first, middle, last);
82  return std::next(first, std::distance(middle, last));
83 }
84 
85 } // namespace algorithm_internal
86 
87 // Compares the equality of two ranges specified by pairs of iterators, using
88 // the given predicate, returning true iff for each corresponding iterator i1
89 // and i2 in the first and second range respectively, pred(*i1, *i2) == true
90 //
91 // This comparison takes at most min(`last1` - `first1`, `last2` - `first2`)
92 // invocations of the predicate. Additionally, if InputIter1 and InputIter2 are
93 // both random-access iterators, and `last1` - `first1` != `last2` - `first2`,
94 // then the predicate is never invoked and the function returns false.
95 //
96 // This is a C++11-compatible implementation of C++14 `std::equal`. See
97 // https://en.cppreference.com/w/cpp/algorithm/equal for more information.
98 template <typename InputIter1, typename InputIter2, typename Pred>
99 bool equal(InputIter1 first1, InputIter1 last1, InputIter2 first2,
100  InputIter2 last2, Pred&& pred) {
102  first1, last1, first2, last2, std::forward<Pred>(pred),
103  typename std::iterator_traits<InputIter1>::iterator_category{},
104  typename std::iterator_traits<InputIter2>::iterator_category{});
105 }
106 
107 // Performs comparison of two ranges specified by pairs of iterators using
108 // operator==.
109 template <typename InputIter1, typename InputIter2>
110 bool equal(InputIter1 first1, InputIter1 last1, InputIter2 first2,
111  InputIter2 last2) {
112  return absl::equal(first1, last1, first2, last2,
114 }
115 
116 // Performs a linear search for `value` using the iterator `first` up to
117 // but not including `last`, returning true if [`first`, `last`) contains an
118 // element equal to `value`.
119 //
120 // A linear search is of O(n) complexity which is guaranteed to make at most
121 // n = (`last` - `first`) comparisons. A linear search over short containers
122 // may be faster than a binary search, even when the container is sorted.
123 template <typename InputIterator, typename EqualityComparable>
124 bool linear_search(InputIterator first, InputIterator last,
125  const EqualityComparable& value) {
126  return std::find(first, last, value) != last;
127 }
128 
129 // Performs a left rotation on a range of elements (`first`, `last`) such that
130 // `middle` is now the first element. `rotate()` returns an iterator pointing to
131 // the first element before rotation. This function is exactly the same as
132 // `std::rotate`, but fixes a bug in gcc
133 // <= 4.9 where `std::rotate` returns `void` instead of an iterator.
134 //
135 // The complexity of this algorithm is the same as that of `std::rotate`, but if
136 // `ForwardIterator` is not a random-access iterator, then `absl::rotate`
137 // performs an additional pass over the range to construct the return value.
138 
139 template <typename ForwardIterator>
140 ForwardIterator rotate(ForwardIterator first, ForwardIterator middle,
141  ForwardIterator last) {
143  first, middle, last,
144  std::is_same<decltype(std::rotate(first, middle, last)),
145  ForwardIterator>());
146 }
147 
148 } // namespace absl
149 
150 #endif // ABSL_ALGORITHM_ALGORITHM_H_
It RotateImpl(It first, It middle, It last, std::true_type)
Definition: algorithm.h:75
Definition: algorithm.h:29
AllocList * next[kMaxLevel]
size_t value
bool linear_search(InputIterator first, InputIterator last, const EqualityComparable &value)
Definition: algorithm.h:124
bool equal(InputIter1 first1, InputIter1 last1, InputIter2 first2, InputIter2 last2, Pred &&pred)
Definition: algorithm.h:99
bool EqualImpl(InputIter1 first1, InputIter1 last1, InputIter2 first2, InputIter2 last2, Pred pred, std::input_iterator_tag, std::input_iterator_tag)
Definition: algorithm.h:42
ForwardIterator rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last)
Definition: algorithm.h:140
bool operator()(const T &a, const U &b) const
Definition: algorithm.h:36
uint64_t b
Definition: layout_test.cc:50


abseil_cpp
Author(s):
autogenerated on Mon Feb 28 2022 21:31:17