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_MAP_H_ 6 #define BASE_CONTAINERS_FIXED_FLAT_MAP_H_ 7 8 #include <algorithm> 9 #include <array> 10 #include <functional> 11 #include <utility> 12 13 #include "base/containers/flat_map.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 FixedFlatMapInputNotSortedOrNotUnique(); 21 } // namespace internal 22 23 // fixed_flat_map is a immutable container with a std::map-like interface that 24 // stores its contents in a sorted std::array. 25 // 26 // It is a special case of base::flat_map, 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_map(const fixed_flat_map&); 39 // fixed_flat_map(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 // iterator begin(); 50 // const_iterator begin() const; 51 // const_iterator cbegin() const; 52 // iterator end(); 53 // const_iterator end() const; 54 // const_iterator cend() const; 55 // reverse_iterator rbegin(); 56 // const reverse_iterator rbegin() const; 57 // const_reverse_iterator crbegin() const; 58 // reverse_iterator rend(); 59 // const_reverse_iterator rend() const; 60 // const_reverse_iterator crend() const; 61 // 62 // Insert and accessor functions: 63 // mapped_type& at(const K&); 64 // const mapped_type& at(const K&) const; 65 66 // Comparators (see std::map documentation). 67 // key_compare key_comp() const; 68 // value_compare value_comp() const; 69 // 70 // Search functions: 71 // template <typename K> size_t count(const K&) const; 72 // template <typename K> iterator find(const K&); 73 // template <typename K> const_iterator find(const K&) const; 74 // template <typename K> bool contains(const K&) const; 75 // template <typename K> 76 // pair<iterator, iterator> equal_range(const K&); 77 // template <typename K> 78 // pair<const_iterator, const_iterator> equal_range(K&) const; 79 // template <typename K> iterator lower_bound(const K&); 80 // template <typename K> const_iterator lower_bound(const K&) const; 81 // template <typename K> iterator upper_bound(const K&); 82 // template <typename K> const_iterator upper_bound(const K&) const; 83 // 84 // Non-member operators: 85 // bool operator==(const fixed_flat_map&, const fixed_flat_map&); 86 // bool operator!=(const fixed_flat_map&, const fixed_flat_map&); 87 // bool operator<(const fixed_flat_map&, const fixed_flat_map&); 88 // bool operator>(const fixed_flat_map&, const fixed_flat_map&); 89 // bool operator>=(const fixed_flat_map&, const fixed_flat_map&); 90 // bool operator<=(const fixed_flat_map&, const fixed_flat_map&); 91 // 92 template <class Key, class Mapped, size_t N, class Compare = std::less<>> 93 using fixed_flat_map = base:: 94 flat_map<Key, Mapped, Compare, std::array<std::pair<const Key, Mapped>, N>>; 95 96 // Utility function to simplify constructing a fixed_flat_map from a fixed list 97 // of keys and values. Requires that the passed in `data` contains unique keys. 98 // 99 // Large inputs will run into compiler limits, e.g. "constexpr evaluation hit 100 // maximum step limit", unless `data` is already sorted. 101 // 102 // Example usage: 103 // constexpr auto kMap = base::MakeFixedFlatMap<std::string_view, int>( 104 // {{"foo", 1}, {"bar", 2}, {"baz", 3}}); 105 template <class Key, class Mapped, size_t N, class Compare = std::less<>> 106 consteval fixed_flat_map<Key, Mapped, N, Compare> MakeFixedFlatMap( 107 std::pair<Key, Mapped> (&&data)[N], 108 const Compare& comp = Compare()) { 109 using FixedFlatMap = fixed_flat_map<Key, Mapped, N, Compare>; 110 typename FixedFlatMap::value_compare value_comp{comp}; 111 if (!internal::is_sorted_and_unique(data, value_comp)) { 112 std::ranges::sort(data, value_comp); 113 if (!internal::is_sorted_and_unique(data, value_comp)) { 114 internal::FixedFlatMapInputNotSortedOrNotUnique(); 115 } 116 } 117 return FixedFlatMap( 118 sorted_unique, internal::ToArray<typename FixedFlatMap::value_type>(data), 119 comp); 120 } 121 122 } // namespace base 123 124 #endif // BASE_CONTAINERS_FIXED_FLAT_MAP_H_ 125