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_FIXED_FLAT_SET_H_ 6 #define BASE_CONTAINERS_FIXED_FLAT_SET_H_ 7 8 #include <algorithm> 9 #include <array> 10 #include <functional> 11 #include <type_traits> 12 13 #include "base/containers/flat_set.h" 14 #include "base/containers/flat_tree.h" 15 16 namespace base { 17 18 namespace internal { 19 // Not constexpr to trigger a compile error. 20 void FixedFlatSetInputNotSortedOrNotUnique(); 21 } // namespace internal 22 23 // fixed_flat_set is a immutable container with a std::set-like interface that 24 // stores its contents in a sorted std::array. 25 // 26 // It is a special case of base::flat_set, and mostly useful as a look-up table. 27 // 28 // Please see //base/containers/README.md for an overview of which container 29 // to select. 30 // 31 // QUICK REFERENCE 32 // 33 // Most of the core functionality is inherited from flat_tree. Please see 34 // flat_tree.h for more details for most of these functions. As a quick 35 // reference, the functions available are: 36 // 37 // Constructors (inputs need to be sorted): 38 // fixed_flat_set(const fixed_flat_set&); 39 // fixed_flat_set(sorted_unique_t, 40 // const container_type& items, 41 // const Compare& compare = Compare()); 42 // 43 // Size management functions: 44 // size_t size() const; 45 // size_t max_size() const; 46 // bool empty() const; 47 // 48 // Iterator functions: 49 // const_iterator begin() const; 50 // const_iterator cbegin() const; 51 // const_iterator end() const; 52 // const_iterator cend() const; 53 // const reverse_iterator rbegin() const; 54 // const_reverse_iterator crbegin() const; 55 // const_reverse_iterator rend() const; 56 // const_reverse_iterator crend() const; 57 // 58 // Comparators (see std::set documentation). 59 // key_compare key_comp() const; 60 // value_compare value_comp() const; 61 // 62 // Search functions: 63 // template <typename K> size_t count(const K&) const; 64 // template <typename K> const_iterator find(const K&) const; 65 // template <typename K> bool contains(const K&) const; 66 // template <typename K> 67 // pair<const_iterator, const_iterator> equal_range(K&) const; 68 // template <typename K> const_iterator lower_bound(const K&) const; 69 // template <typename K> const_iterator upper_bound(const K&) const; 70 // 71 // Non-member operators: 72 // bool operator==(const fixed_flat_set&, const fixed_flat_set&); 73 // bool operator!=(const fixed_flat_set&, const fixed_flat_set&); 74 // bool operator<(const fixed_flat_set&, const fixed_flat_set&); 75 // bool operator>(const fixed_flat_set&, const fixed_flat_set&); 76 // bool operator>=(const fixed_flat_set&, const fixed_flat_set&); 77 // bool operator<=(const fixed_flat_set&, const fixed_flat_set&); 78 // 79 template <class Key, size_t N, class Compare = std::less<>> 80 using fixed_flat_set = base::flat_set<Key, Compare, std::array<const Key, N>>; 81 82 // Utility function to simplify constructing a fixed_flat_set from a fixed list 83 // of keys and values. Requires that the passed in `data` contains unique keys 84 // and be sorted by key. See `MakeFixedFlatSet` for a variant that sorts the 85 // input automatically. 86 // 87 // Example usage: 88 // constexpr auto kSet = base::MakeFixedFlatSet<std::string_view>( 89 // base::sorted_unique, {"bar", "baz", "foo", "qux"}); 90 template <class Key, size_t N, class Compare = std::less<>> 91 consteval fixed_flat_set<Key, N, Compare> MakeFixedFlatSet( 92 sorted_unique_t, 93 std::common_type_t<Key> (&&data)[N], 94 const Compare& comp = Compare()) { 95 if (!internal::is_sorted_and_unique(data, comp)) { 96 internal::FixedFlatSetInputNotSortedOrNotUnique(); 97 } 98 // Specify the value_type explicitly to ensure that the returned array has 99 // immutable keys. 100 return fixed_flat_set<Key, N, Compare>( 101 sorted_unique, internal::ToArray<const Key>(data), comp); 102 } 103 104 // Utility function to simplify constructing a fixed_flat_set from a fixed list 105 // of keys. Requires that the passed in `data` contains unique keys. 106 // 107 // Large inputs will run into compiler limits, e.g. "constexpr evaluation hit 108 // maximum step limit". In that case, use `MakeFixedFlatSet(sorted_unique)`. 109 // 110 // Example usage: 111 // constexpr auto kIntSet = base::MakeFixedFlatSet<int>({1, 2, 3, 4}); 112 // 113 // Data needs not to be sorted: 114 // constexpr auto kStringSet = base::MakeFixedFlatSet<std::string_view>( 115 // {"foo", "bar", "baz", "qux"}); 116 // 117 // Note: Wrapping `Key` in `std::common_type_t` below requires callers to 118 // explicitly specify `Key`, which is desired here. 119 template <class Key, size_t N, class Compare = std::less<>> 120 consteval fixed_flat_set<Key, N, Compare> MakeFixedFlatSet( 121 std::common_type_t<Key> (&&data)[N], 122 const Compare& comp = Compare()) { 123 std::ranges::sort(data, comp); 124 return MakeFixedFlatSet<Key>(sorted_unique, std::move(data), comp); 125 } 126 127 } // namespace base 128 129 #endif // BASE_CONTAINERS_FIXED_FLAT_SET_H_ 130