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