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 <ranges>
9 #include <type_traits>
10 #include <utility>
11
12 #include "base/ranges/algorithm.h"
13 // TODO(dcheng): Remove this after fixing any IWYU errors.
14 #include "base/ranges/ranges.h"
15
16 namespace base {
17
18 namespace internal {
19
20 // Small helper to detect whether a given type has a nested `key_type` typedef.
21 // Used below to catch misuses of the API for associative containers.
22 template <typename T>
23 concept HasKeyType = requires { typename T::key_type; };
24
25 } // namespace internal
26
27 // A general purpose utility to check whether `container` contains `value`. This
28 // will probe whether a `contains` or `find` member function on `container`
29 // exists, and fall back to a generic linear search over `container`.
30 template <typename Container, typename Value>
Contains(const Container & container,const Value & value)31 constexpr bool Contains(const Container& container, const Value& value) {
32 if constexpr (requires {
33 { container.contains(value) } -> std::same_as<bool>;
34 }) {
35 return container.contains(value);
36 } else if constexpr (requires { container.find(value) != Container::npos; }) {
37 return container.find(value) != Container::npos;
38 } else if constexpr (requires { container.find(value) != container.end(); }) {
39 return container.find(value) != container.end();
40 } else {
41 static_assert(
42 !internal::HasKeyType<Container>,
43 "Error: About to perform linear search on an associative container. "
44 "Either use a more generic comparator (e.g. std::less<>) or, if a "
45 "linear search is desired, provide an explicit projection parameter.");
46 return ranges::find(container, value) != std::ranges::end(container);
47 }
48 }
49
50 // Overload that allows to provide an additional projection invocable. This
51 // projection will be applied to every element in `container` before comparing
52 // it with `value`. This will always perform a linear search.
53 template <typename Container, typename Value, typename Proj>
Contains(const Container & container,const Value & value,Proj proj)54 constexpr bool Contains(const Container& container,
55 const Value& value,
56 Proj proj) {
57 return ranges::find(container, value, std::move(proj)) !=
58 std::ranges::end(container);
59 }
60
61 } // namespace base
62
63 #endif // BASE_CONTAINERS_CONTAINS_H_
64