1 /* 2 * Copyright (c) 2021 The WebRTC project authors. All Rights Reserved. 3 * 4 * Use of this source code is governed by a BSD-style license 5 * that can be found in the LICENSE file in the root of the source 6 * tree. An additional intellectual property rights grant can be found 7 * in the file PATENTS. All contributing project authors may 8 * be found in the AUTHORS file in the root of the source tree. 9 */ 10 11 // This implementation is borrowed from Chromium. 12 13 #ifndef RTC_BASE_CONTAINERS_FLAT_SET_H_ 14 #define RTC_BASE_CONTAINERS_FLAT_SET_H_ 15 16 #include <functional> 17 #include <vector> 18 19 #include "rtc_base/containers/flat_tree.h" // IWYU pragma: export 20 #include "rtc_base/containers/identity.h" 21 22 namespace webrtc { 23 24 // flat_set is a container with a std::set-like interface that stores its 25 // contents in a sorted container, by default a vector. 26 // 27 // Its implementation mostly tracks the corresponding standardization proposal 28 // https://wg21.link/P1222. 29 // 30 // 31 // PROS 32 // 33 // - Good memory locality. 34 // - Low overhead, especially for smaller sets. 35 // - Performance is good for more workloads than you might expect (see 36 // //base/containers/README.md in Chromium repository) 37 // - Supports C++14 set interface. 38 // 39 // CONS 40 // 41 // - Inserts and removals are O(n). 42 // 43 // IMPORTANT NOTES 44 // 45 // - Iterators are invalidated across mutations. 46 // - If possible, construct a flat_set in one operation by inserting into 47 // a container and moving that container into the flat_set constructor. 48 // - For multiple removals use base::EraseIf() which is O(n) rather than 49 // O(n * removed_items). 50 // 51 // QUICK REFERENCE 52 // 53 // Most of the core functionality is inherited from flat_tree. Please see 54 // flat_tree.h for more details for most of these functions. As a quick 55 // reference, the functions available are: 56 // 57 // Constructors (inputs need not be sorted): 58 // flat_set(const flat_set&); 59 // flat_set(flat_set&&); 60 // flat_set(InputIterator first, InputIterator last, 61 // const Compare& compare = Compare()); 62 // flat_set(const container_type& items, 63 // const Compare& compare = Compare()); 64 // flat_set(container_type&& items, 65 // const Compare& compare = Compare()); // Re-use storage. 66 // flat_set(std::initializer_list<value_type> ilist, 67 // const Compare& comp = Compare()); 68 // 69 // Constructors (inputs need to be sorted): 70 // flat_set(sorted_unique_t, 71 // InputIterator first, InputIterator last, 72 // const Compare& compare = Compare()); 73 // flat_set(sorted_unique_t, 74 // const container_type& items, 75 // const Compare& compare = Compare()); 76 // flat_set(sorted_unique_t, 77 // container_type&& items, 78 // const Compare& compare = Compare()); // Re-use storage. 79 // flat_set(sorted_unique_t, 80 // std::initializer_list<value_type> ilist, 81 // const Compare& comp = Compare()); 82 // 83 // Assignment functions: 84 // flat_set& operator=(const flat_set&); 85 // flat_set& operator=(flat_set&&); 86 // flat_set& operator=(initializer_list<Key>); 87 // 88 // Memory management functions: 89 // void reserve(size_t); 90 // size_t capacity() const; 91 // void shrink_to_fit(); 92 // 93 // Size management functions: 94 // void clear(); 95 // size_t size() const; 96 // size_t max_size() const; 97 // bool empty() const; 98 // 99 // Iterator functions: 100 // iterator begin(); 101 // const_iterator begin() const; 102 // const_iterator cbegin() const; 103 // iterator end(); 104 // const_iterator end() const; 105 // const_iterator cend() const; 106 // reverse_iterator rbegin(); 107 // const reverse_iterator rbegin() const; 108 // const_reverse_iterator crbegin() const; 109 // reverse_iterator rend(); 110 // const_reverse_iterator rend() const; 111 // const_reverse_iterator crend() const; 112 // 113 // Insert and accessor functions: 114 // pair<iterator, bool> insert(const key_type&); 115 // pair<iterator, bool> insert(key_type&&); 116 // void insert(InputIterator first, InputIterator last); 117 // iterator insert(const_iterator hint, const key_type&); 118 // iterator insert(const_iterator hint, key_type&&); 119 // pair<iterator, bool> emplace(Args&&...); 120 // iterator emplace_hint(const_iterator, Args&&...); 121 // 122 // Underlying type functions: 123 // container_type extract() &&; 124 // void replace(container_type&&); 125 // 126 // Erase functions: 127 // iterator erase(iterator); 128 // iterator erase(const_iterator); 129 // iterator erase(const_iterator first, const_iterator& last); 130 // template <typename K> size_t erase(const K& key); 131 // 132 // Comparators (see std::set documentation). 133 // key_compare key_comp() const; 134 // value_compare value_comp() const; 135 // 136 // Search functions: 137 // template <typename K> size_t count(const K&) const; 138 // template <typename K> iterator find(const K&); 139 // template <typename K> const_iterator find(const K&) const; 140 // template <typename K> bool contains(const K&) const; 141 // template <typename K> pair<iterator, iterator> equal_range(K&); 142 // template <typename K> iterator lower_bound(const K&); 143 // template <typename K> const_iterator lower_bound(const K&) const; 144 // template <typename K> iterator upper_bound(const K&); 145 // template <typename K> const_iterator upper_bound(const K&) const; 146 // 147 // General functions: 148 // void swap(flat_set&); 149 // 150 // Non-member operators: 151 // bool operator==(const flat_set&, const flat_set); 152 // bool operator!=(const flat_set&, const flat_set); 153 // bool operator<(const flat_set&, const flat_set); 154 // bool operator>(const flat_set&, const flat_set); 155 // bool operator>=(const flat_set&, const flat_set); 156 // bool operator<=(const flat_set&, const flat_set); 157 // 158 template <class Key, 159 class Compare = std::less<>, 160 class Container = std::vector<Key>> 161 using flat_set = typename ::webrtc::flat_containers_internal:: 162 flat_tree<Key, webrtc::identity, Compare, Container>; 163 164 // ---------------------------------------------------------------------------- 165 // General operations. 166 167 // Erases all elements that match predicate. It has O(size) complexity. 168 // 169 // flat_set<int> numbers; 170 // ... 171 // EraseIf(numbers, [](int number) { return number % 2 == 1; }); 172 173 // NOLINTNEXTLINE(misc-unused-using-decls) 174 using ::webrtc::flat_containers_internal::EraseIf; 175 176 } // namespace webrtc 177 178 #endif // RTC_BASE_CONTAINERS_FLAT_SET_H_ 179