contains.h (3953B)
1 // Copyright 2020 The Chromium Authors 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef BASE_CONTAINERS_CONTAINS_H_ 6 #define BASE_CONTAINERS_CONTAINS_H_ 7 8 #include <type_traits> 9 #include <utility> 10 11 #include "base/ranges/algorithm.h" 12 #include "base/ranges/ranges.h" 13 14 namespace base { 15 16 namespace internal { 17 18 // Small helper to detect whether a given type has a nested `key_type` typedef. 19 // Used below to catch misuses of the API for associative containers. 20 template <typename T, typename SFINAE = void> 21 struct HasKeyType : std::false_type {}; 22 23 template <typename T> 24 struct HasKeyType<T, std::void_t<typename T::key_type>> : std::true_type {}; 25 26 // Probe whether a `contains` member function exists and return the result of 27 // `container.contains(value)` if this is a valid expression. This is the 28 // highest priority option. 29 template <typename Container, typename Value> 30 constexpr auto ContainsImpl(const Container& container, 31 const Value& value, 32 priority_tag<2>) 33 -> decltype(container.contains(value)) { 34 return container.contains(value); 35 } 36 37 // Probe whether a `find` member function exists and whether its return value 38 // can be compared with `container.end()`. Intended for STL style maps and sets 39 // that lack a `contains` member function. 40 template <typename Container, typename Value> 41 constexpr auto ContainsImpl(const Container& container, 42 const Value& value, 43 priority_tag<1>) 44 -> decltype(container.find(value) != container.end()) { 45 return container.find(value) != container.end(); 46 } 47 48 // Probe whether a `find` member function exists and whether its return value 49 // can be compared with `Container::npos`. Intended for STL style strings that 50 // lack a `contains` member function. 51 template <typename Container, typename Value> 52 constexpr auto ContainsImpl(const Container& container, 53 const Value& value, 54 priority_tag<1>) 55 -> decltype(container.find(value) != Container::npos) { 56 return container.find(value) != Container::npos; 57 } 58 59 // Generic fallback option, using a linear search over `container` to find 60 // `value`. Has the lowest priority. This will not compile for associative 61 // containers, as this likely is a performance bug. 62 template <typename Container, typename Value> 63 constexpr bool ContainsImpl(const Container& container, 64 const Value& value, 65 priority_tag<0>) { 66 static_assert( 67 !HasKeyType<Container>::value, 68 "Error: About to perform linear search on an associative container. " 69 "Either use a more generic comparator (e.g. std::less<>) or, if a linear " 70 "search is desired, provide an explicit projection parameter."); 71 return ranges::find(container, value) != ranges::end(container); 72 } 73 74 } // namespace internal 75 76 // A general purpose utility to check whether `container` contains `value`. This 77 // will probe whether a `contains` or `find` member function on `container` 78 // exists, and fall back to a generic linear search over `container`. 79 template <typename Container, typename Value> 80 constexpr bool Contains(const Container& container, const Value& value) { 81 return internal::ContainsImpl(container, value, internal::priority_tag<2>()); 82 } 83 84 // Overload that allows to provide an additional projection invocable. This 85 // projection will be applied to every element in `container` before comparing 86 // it with `value`. This will always perform a linear search. 87 template <typename Container, typename Value, typename Proj> 88 constexpr bool Contains(const Container& container, 89 const Value& value, 90 Proj proj) { 91 return ranges::find(container, value, std::move(proj)) != 92 ranges::end(container); 93 } 94 95 } // namespace base 96 97 #endif // BASE_CONTAINERS_CONTAINS_H_