algorithm.h
Go to the documentation of this file.
```00001 // Copyright 2017 The Abseil Authors.
00002 //
00004 // you may not use this file except in compliance with the License.
00005 // You may obtain a copy of the License at
00006 //
00008 //
00009 // Unless required by applicable law or agreed to in writing, software
00011 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00012 // See the License for the specific language governing permissions and
00013 // limitations under the License.
00014 //
00015 // -----------------------------------------------------------------------------
00016 // File: algorithm.h
00017 // -----------------------------------------------------------------------------
00018 //
00019 // This header file contains Google extensions to the standard <algorithm> C++
00021
00022 #ifndef ABSL_ALGORITHM_ALGORITHM_H_
00023 #define ABSL_ALGORITHM_ALGORITHM_H_
00024
00025 #include <algorithm>
00026 #include <iterator>
00027 #include <type_traits>
00028
00029 namespace absl {
00030
00031 namespace algorithm_internal {
00032
00033 // Performs comparisons with operator==, similar to C++14's `std::equal_to<>`.
00034 struct EqualTo {
00035   template <typename T, typename U>
00036   bool operator()(const T& a, const U& b) const {
00037     return a == b;
00038   }
00039 };
00040
00041 template <typename InputIter1, typename InputIter2, typename Pred>
00042 bool EqualImpl(InputIter1 first1, InputIter1 last1, InputIter2 first2,
00043                InputIter2 last2, Pred pred, std::input_iterator_tag,
00044                std::input_iterator_tag) {
00045   while (true) {
00046     if (first1 == last1) return first2 == last2;
00047     if (first2 == last2) return false;
00048     if (!pred(*first1, *first2)) return false;
00049     ++first1;
00050     ++first2;
00051   }
00052 }
00053
00054 template <typename InputIter1, typename InputIter2, typename Pred>
00055 bool EqualImpl(InputIter1 first1, InputIter1 last1, InputIter2 first2,
00056                InputIter2 last2, Pred&& pred, std::random_access_iterator_tag,
00057                std::random_access_iterator_tag) {
00058   return (last1 - first1 == last2 - first2) &&
00059          std::equal(first1, last1, first2, std::forward<Pred>(pred));
00060 }
00061
00062 // When we are using our own internal predicate that just applies operator==, we
00063 // forward to the non-predicate form of std::equal. This enables an optimization
00064 // in libstdc++ that can result in std::memcmp being used for integer types.
00065 template <typename InputIter1, typename InputIter2>
00066 bool EqualImpl(InputIter1 first1, InputIter1 last1, InputIter2 first2,
00067                InputIter2 last2, algorithm_internal::EqualTo /* unused */,
00068                std::random_access_iterator_tag,
00069                std::random_access_iterator_tag) {
00070   return (last1 - first1 == last2 - first2) &&
00071          std::equal(first1, last1, first2);
00072 }
00073
00074 template <typename It>
00075 It RotateImpl(It first, It middle, It last, std::true_type) {
00076   return std::rotate(first, middle, last);
00077 }
00078
00079 template <typename It>
00080 It RotateImpl(It first, It middle, It last, std::false_type) {
00081   std::rotate(first, middle, last);
00082   return std::next(first, std::distance(middle, last));
00083 }
00084
00085 }  // namespace algorithm_internal
00086
00087 // Compares the equality of two ranges specified by pairs of iterators, using
00088 // the given predicate, returning true iff for each corresponding iterator i1
00089 // and i2 in the first and second range respectively, pred(*i1, *i2) == true
00090 //
00091 // This comparison takes at most min(`last1` - `first1`, `last2` - `first2`)
00092 // invocations of the predicate. Additionally, if InputIter1 and InputIter2 are
00093 // both random-access iterators, and `last1` - `first1` != `last2` - `first2`,
00094 // then the predicate is never invoked and the function returns false.
00095 //
00096 // This is a C++11-compatible implementation of C++14 `std::equal`.  See
00098 template <typename InputIter1, typename InputIter2, typename Pred>
00099 bool equal(InputIter1 first1, InputIter1 last1, InputIter2 first2,
00100            InputIter2 last2, Pred&& pred) {
00101   return algorithm_internal::EqualImpl(
00102       first1, last1, first2, last2, std::forward<Pred>(pred),
00103       typename std::iterator_traits<InputIter1>::iterator_category{},
00104       typename std::iterator_traits<InputIter2>::iterator_category{});
00105 }
00106
00107 // Performs comparison of two ranges specified by pairs of iterators using
00108 // operator==.
00109 template <typename InputIter1, typename InputIter2>
00110 bool equal(InputIter1 first1, InputIter1 last1, InputIter2 first2,
00111            InputIter2 last2) {
00112   return absl::equal(first1, last1, first2, last2,
00113                      algorithm_internal::EqualTo{});
00114 }
00115
00116 // Performs a linear search for `value` using the iterator `first` up to
00117 // but not including `last`, returning true if [`first`, `last`) contains an
00118 // element equal to `value`.
00119 //
00120 // A linear search is of O(n) complexity which is guaranteed to make at most
00121 // n = (`last` - `first`) comparisons. A linear search over short containers
00122 // may be faster than a binary search, even when the container is sorted.
00123 template <typename InputIterator, typename EqualityComparable>
00124 bool linear_search(InputIterator first, InputIterator last,
00125                    const EqualityComparable& value) {
00126   return std::find(first, last, value) != last;
00127 }
00128
00129 // Performs a left rotation on a range of elements (`first`, `last`) such that
00130 // `middle` is now the first element. `rotate()` returns an iterator pointing to
00131 // the first element before rotation. This function is exactly the same as
00132 // `std::rotate`, but fixes a bug in gcc
00133 // <= 4.9 where `std::rotate` returns `void` instead of an iterator.
00134 //
00135 // The complexity of this algorithm is the same as that of `std::rotate`, but if
00136 // `ForwardIterator` is not a random-access iterator, then `absl::rotate`
00137 // performs an additional pass over the range to construct the return value.
00138
00139 template <typename ForwardIterator>
00140 ForwardIterator rotate(ForwardIterator first, ForwardIterator middle,
00141                        ForwardIterator last) {
00142   return algorithm_internal::RotateImpl(
00143       first, middle, last,
00144       std::is_same<decltype(std::rotate(first, middle, last)),
00145                    ForwardIterator>());
00146 }
00147
00148 }  // namespace absl
00149
00150 #endif  // ABSL_ALGORITHM_ALGORITHM_H_
```

abseil_cpp
Author(s):
autogenerated on Wed Jun 19 2019 19:42:14