algorithm.h (2212B)
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 #include "absl/base/config.h" 30 31 namespace absl { 32 ABSL_NAMESPACE_BEGIN 33 34 // equal() 35 // rotate() 36 // 37 // Historical note: Abseil once provided implementations of these algorithms 38 // prior to their adoption in C++14. New code should prefer to use the std 39 // variants. 40 // 41 // See the documentation for the STL <algorithm> header for more information: 42 // https://en.cppreference.com/w/cpp/header/algorithm 43 using std::equal; 44 using std::rotate; 45 46 // linear_search() 47 // 48 // Performs a linear search for `value` using the iterator `first` up to 49 // but not including `last`, returning true if [`first`, `last`) contains an 50 // element equal to `value`. 51 // 52 // A linear search is of O(n) complexity which is guaranteed to make at most 53 // n = (`last` - `first`) comparisons. A linear search over short containers 54 // may be faster than a binary search, even when the container is sorted. 55 template <typename InputIterator, typename EqualityComparable> 56 ABSL_INTERNAL_CONSTEXPR_SINCE_CXX20 bool linear_search( 57 InputIterator first, InputIterator last, const EqualityComparable& value) { 58 return std::find(first, last, value) != last; 59 } 60 61 ABSL_NAMESPACE_END 62 } // namespace absl 63 64 #endif // ABSL_ALGORITHM_ALGORITHM_H_