absl/algorithm/algorithm.h

0001 // Copyright 2017 The Abseil Authors.
0002 //
0003 // Licensed under the Apache License, Version 2.0 (the "License");
0004 // you may not use this file except in compliance with the License.
0005 // You may obtain a copy of the License at
0006 //
0007 //      https://www.apache.org/licenses/LICENSE-2.0
0008 //
0009 // Unless required by applicable law or agreed to in writing, software
0010 // distributed under the License is distributed on an "AS IS" BASIS,
0011 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0012 // See the License for the specific language governing permissions and
0013 // limitations under the License.
0014 //
0015 // -----------------------------------------------------------------------------
0016 // File: algorithm.h
0017 // -----------------------------------------------------------------------------
0018 //
0019 // This header file contains Google extensions to the standard <algorithm> C++
0020 // header.
0021
0022 #ifndef ABSL_ALGORITHM_ALGORITHM_H_
0023 #define ABSL_ALGORITHM_ALGORITHM_H_
0024
0025 #include <algorithm>
0026 #include <iterator>
0027 #include <type_traits>
0028
0029 #include "absl/base/config.h"
0030
0031 namespace absl {
0032 ABSL_NAMESPACE_BEGIN
0033
0034 // equal()
0035 // rotate()
0036 //
0037 // Historical note: Abseil once provided implementations of these algorithms
0038 // prior to their adoption in C++14. New code should prefer to use the std
0039 // variants.
0040 //
0041 // See the documentation for the STL <algorithm> header for more information:
0042 // https://en.cppreference.com/w/cpp/header/algorithm
0043 using std::equal;
0044 using std::rotate;
0045
0046 // linear_search()
0047 //
0048 // Performs a linear search for `value` using the iterator `first` up to
0049 // but not including `last`, returning true if [`first`, `last`) contains an
0050 // element equal to `value`.
0051 //
0052 // A linear search is of O(n) complexity which is guaranteed to make at most
0053 // n = (`last` - `first`) comparisons. A linear search over short containers
0054 // may be faster than a binary search, even when the container is sorted.
0055 template <typename InputIterator, typename EqualityComparable>
0056 bool linear_search(InputIterator first, InputIterator last,
0057                    const EqualityComparable& value) {
0058   return std::find(first, last, value) != last;
0059 }
0060
0061 ABSL_NAMESPACE_END
0062 }  // namespace absl
0063
0064 #endif  // ABSL_ALGORITHM_ALGORITHM_H_