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