| // 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. |
| // |
| // ----------------------------------------------------------------------------- |
| // File: algorithm.h |
| // ----------------------------------------------------------------------------- |
| // |
| // This header file contains Google extensions to the standard <algorithm> C++ |
| // header. |
| |
| #ifndef ABSL_ALGORITHM_ALGORITHM_H_ |
| #define ABSL_ALGORITHM_ALGORITHM_H_ |
| |
| #include <algorithm> |
| #include <iterator> |
| #include <type_traits> |
| |
| namespace absl { |
| |
| 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 |
| |
| // 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. |
| // |
| // 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{}); |
| } |
| |
| // 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{}); |
| } |
| |
| // Performs a linear search for `value` using the iterator `first` up to |
| // but not including `last`, returning true if [`first`, `last`) contains an |
| // element equal to `value`. |
| // |
| // A linear search is of O(n) complexity which is guaranteed to make at most |
| // n = (`last` - `first`) comparisons. A linear search over short containers |
| // may be faster than a binary search, even when the container is sorted. |
| template <typename InputIterator, typename EqualityComparable> |
| bool linear_search(InputIterator first, InputIterator last, |
| const EqualityComparable& value) { |
| return std::find(first, last, value) != last; |
| } |
| |
| // 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>()); |
| } |
| |
| } // namespace absl |
| |
| #endif // ABSL_ALGORITHM_ALGORITHM_H_ |