1 // Copyright 2017 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_FLAT_SET_H_ 6 #define BASE_CONTAINERS_FLAT_SET_H_ 7 8 #include <functional> 9 #include <vector> 10 11 #include "base/containers/flat_tree.h" 12 #include "base/ranges/algorithm.h" 13 #include "base/template_util.h" 14 15 namespace base { 16 17 // flat_set is a container with a std::set-like interface that stores its 18 // contents in a sorted container, by default a vector. 19 // 20 // Its implementation mostly tracks the corresponding standardization proposal 21 // https://wg21.link/P1222. 22 // 23 // Please see //base/containers/README.md for an overview of which container 24 // to select. 25 // 26 // PROS 27 // 28 // - Good memory locality. 29 // - Low overhead, especially for smaller sets. 30 // - Performance is good for more workloads than you might expect (see 31 // overview link above). 32 // - Supports C++14 set interface. 33 // 34 // CONS 35 // 36 // - Inserts and removals are O(n). 37 // 38 // IMPORTANT NOTES 39 // 40 // - Iterators are invalidated across mutations. 41 // - If possible, construct a flat_set in one operation by inserting into 42 // a container and moving that container into the flat_set constructor. 43 // - For multiple removals use base::EraseIf() which is O(n) rather than 44 // O(n * removed_items). 45 // 46 // QUICK REFERENCE 47 // 48 // Most of the core functionality is inherited from flat_tree. Please see 49 // flat_tree.h for more details for most of these functions. As a quick 50 // reference, the functions available are: 51 // 52 // Constructors (inputs need not be sorted): 53 // flat_set(const flat_set&); 54 // flat_set(flat_set&&); 55 // flat_set(InputIterator first, InputIterator last, 56 // const Compare& compare = Compare()); 57 // flat_set(const container_type& items, 58 // const Compare& compare = Compare()); 59 // flat_set(container_type&& items, 60 // const Compare& compare = Compare()); // Re-use storage. 61 // flat_set(std::initializer_list<value_type> ilist, 62 // const Compare& comp = Compare()); 63 // 64 // Constructors (inputs need to be sorted): 65 // flat_set(sorted_unique_t, 66 // InputIterator first, InputIterator last, 67 // const Compare& compare = Compare()); 68 // flat_set(sorted_unique_t, 69 // const container_type& items, 70 // const Compare& compare = Compare()); 71 // flat_set(sorted_unique_t, 72 // container_type&& items, 73 // const Compare& compare = Compare()); // Re-use storage. 74 // flat_set(sorted_unique_t, 75 // std::initializer_list<value_type> ilist, 76 // const Compare& comp = Compare()); 77 // 78 // Assignment functions: 79 // flat_set& operator=(const flat_set&); 80 // flat_set& operator=(flat_set&&); 81 // flat_set& operator=(initializer_list<Key>); 82 // 83 // Memory management functions: 84 // void reserve(size_t); 85 // size_t capacity() const; 86 // void shrink_to_fit(); 87 // 88 // Size management functions: 89 // void clear(); 90 // size_t size() const; 91 // size_t max_size() const; 92 // bool empty() const; 93 // 94 // Iterator functions: 95 // iterator begin(); 96 // const_iterator begin() const; 97 // const_iterator cbegin() const; 98 // iterator end(); 99 // const_iterator end() const; 100 // const_iterator cend() const; 101 // reverse_iterator rbegin(); 102 // const reverse_iterator rbegin() const; 103 // const_reverse_iterator crbegin() const; 104 // reverse_iterator rend(); 105 // const_reverse_iterator rend() const; 106 // const_reverse_iterator crend() const; 107 // 108 // Insert and accessor functions: 109 // pair<iterator, bool> insert(const key_type&); 110 // pair<iterator, bool> insert(key_type&&); 111 // void insert(InputIterator first, InputIterator last); 112 // iterator insert(const_iterator hint, const key_type&); 113 // iterator insert(const_iterator hint, key_type&&); 114 // pair<iterator, bool> emplace(Args&&...); 115 // iterator emplace_hint(const_iterator, Args&&...); 116 // 117 // Underlying type functions: 118 // container_type extract() &&; 119 // void replace(container_type&&); 120 // 121 // Erase functions: 122 // iterator erase(iterator); 123 // iterator erase(const_iterator); 124 // iterator erase(const_iterator first, const_iterator& last); 125 // template <typename K> size_t erase(const K& key); 126 // 127 // Comparators (see std::set documentation). 128 // key_compare key_comp() const; 129 // value_compare value_comp() const; 130 // 131 // Search functions: 132 // template <typename K> size_t count(const K&) const; 133 // template <typename K> iterator find(const K&); 134 // template <typename K> const_iterator find(const K&) const; 135 // template <typename K> bool contains(const K&) const; 136 // template <typename K> pair<iterator, iterator> equal_range(K&); 137 // template <typename K> iterator lower_bound(const K&); 138 // template <typename K> const_iterator lower_bound(const K&) const; 139 // template <typename K> iterator upper_bound(const K&); 140 // template <typename K> const_iterator upper_bound(const K&) const; 141 // 142 // General functions: 143 // void swap(flat_set&); 144 // 145 // Non-member operators: 146 // bool operator==(const flat_set&, const flat_set); 147 // bool operator!=(const flat_set&, const flat_set); 148 // bool operator<(const flat_set&, const flat_set); 149 // bool operator>(const flat_set&, const flat_set); 150 // bool operator>=(const flat_set&, const flat_set); 151 // bool operator<=(const flat_set&, const flat_set); 152 // 153 template <class Key, 154 class Compare = std::less<>, 155 class Container = std::vector<Key>> 156 using flat_set = typename ::base::internal:: 157 flat_tree<Key, std::identity, Compare, Container>; 158 159 // Utility function to simplify constructing a flat_set from a fixed list 160 // of keys. The keys are obtained by applying the projection |proj| to the 161 // |unprojected_elements|. The set's keys are sorted by |comp|. 162 // 163 // Example usage (creates a set {16, 9, 4, 1}): 164 // auto set = base::MakeFlatSet<int>( 165 // std::vector<int>{1, 2, 3, 4}, [](int i, int j) { return i > j; }, 166 // [](int i) { return i * i; }); 167 template <class Key, 168 class Compare = std::less<>, 169 class Container = std::vector<Key>, 170 class InputContainer, 171 class Projection = std::identity> 172 constexpr flat_set<Key, Compare, Container> MakeFlatSet( 173 const InputContainer& unprojected_elements, 174 const Compare& comp = Compare(), 175 const Projection& proj = Projection()) { 176 Container elements; 177 internal::ReserveIfSupported(elements, unprojected_elements); 178 base::ranges::transform(unprojected_elements, std::back_inserter(elements), 179 proj); 180 return flat_set<Key, Compare, Container>(std::move(elements), comp); 181 } 182 183 } // namespace base 184 185 #endif // BASE_CONTAINERS_FLAT_SET_H_ 186