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>
linear_search(InputIterator first,InputIterator last,const EqualityComparable & value)56 bool linear_search(InputIterator first, InputIterator last,
57 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_
65