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