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_MAP_H_
14 #define RTC_BASE_CONTAINERS_FLAT_MAP_H_
15
16 #include <functional>
17 #include <tuple>
18 #include <utility>
19 #include <vector>
20
21 #include "rtc_base/checks.h"
22 #include "rtc_base/containers/flat_tree.h" // IWYU pragma: export
23
24 namespace webrtc {
25
26 namespace flat_containers_internal {
27
28 // An implementation of the flat_tree GetKeyFromValue template parameter that
29 // extracts the key as the first element of a pair.
30 struct GetFirst {
31 template <class Key, class Mapped>
operatorGetFirst32 constexpr const Key& operator()(const std::pair<Key, Mapped>& p) const {
33 return p.first;
34 }
35 };
36
37 } // namespace flat_containers_internal
38
39 // flat_map is a container with a std::map-like interface that stores its
40 // contents in a sorted container, by default a vector.
41 //
42 // Its implementation mostly tracks the corresponding standardization proposal
43 // https://wg21.link/P0429, except that the storage of keys and values is not
44 // split.
45 //
46 // PROS
47 //
48 // - Good memory locality.
49 // - Low overhead, especially for smaller maps.
50 // - Performance is good for more workloads than you might expect (see
51 // //base/containers/README.md in Chromium repository)
52 // - Supports C++14 map interface.
53 //
54 // CONS
55 //
56 // - Inserts and removals are O(n).
57 //
58 // IMPORTANT NOTES
59 //
60 // - Iterators are invalidated across mutations. This means that the following
61 // line of code has undefined behavior since adding a new element could
62 // resize the container, invalidating all iterators:
63 // container["new element"] = it.second;
64 // - If possible, construct a flat_map in one operation by inserting into
65 // a container and moving that container into the flat_map constructor.
66 //
67 // QUICK REFERENCE
68 //
69 // Most of the core functionality is inherited from flat_tree. Please see
70 // flat_tree.h for more details for most of these functions. As a quick
71 // reference, the functions available are:
72 //
73 // Constructors (inputs need not be sorted):
74 // flat_map(const flat_map&);
75 // flat_map(flat_map&&);
76 // flat_map(InputIterator first, InputIterator last,
77 // const Compare& compare = Compare());
78 // flat_map(const container_type& items,
79 // const Compare& compare = Compare());
80 // flat_map(container_type&& items,
81 // const Compare& compare = Compare()); // Re-use storage.
82 // flat_map(std::initializer_list<value_type> ilist,
83 // const Compare& comp = Compare());
84 //
85 // Constructors (inputs need to be sorted):
86 // flat_map(sorted_unique_t,
87 // InputIterator first, InputIterator last,
88 // const Compare& compare = Compare());
89 // flat_map(sorted_unique_t,
90 // const container_type& items,
91 // const Compare& compare = Compare());
92 // flat_map(sorted_unique_t,
93 // container_type&& items,
94 // const Compare& compare = Compare()); // Re-use storage.
95 // flat_map(sorted_unique_t,
96 // std::initializer_list<value_type> ilist,
97 // const Compare& comp = Compare());
98 //
99 // Assignment functions:
100 // flat_map& operator=(const flat_map&);
101 // flat_map& operator=(flat_map&&);
102 // flat_map& operator=(initializer_list<value_type>);
103 //
104 // Memory management functions:
105 // void reserve(size_t);
106 // size_t capacity() const;
107 // void shrink_to_fit();
108 //
109 // Size management functions:
110 // void clear();
111 // size_t size() const;
112 // size_t max_size() const;
113 // bool empty() const;
114 //
115 // Iterator functions:
116 // iterator begin();
117 // const_iterator begin() const;
118 // const_iterator cbegin() const;
119 // iterator end();
120 // const_iterator end() const;
121 // const_iterator cend() const;
122 // reverse_iterator rbegin();
123 // const reverse_iterator rbegin() const;
124 // const_reverse_iterator crbegin() const;
125 // reverse_iterator rend();
126 // const_reverse_iterator rend() const;
127 // const_reverse_iterator crend() const;
128 //
129 // Insert and accessor functions:
130 // mapped_type& operator[](const key_type&);
131 // mapped_type& operator[](key_type&&);
132 // mapped_type& at(const K&);
133 // const mapped_type& at(const K&) const;
134 // pair<iterator, bool> insert(const value_type&);
135 // pair<iterator, bool> insert(value_type&&);
136 // iterator insert(const_iterator hint, const value_type&);
137 // iterator insert(const_iterator hint, value_type&&);
138 // void insert(InputIterator first, InputIterator last);
139 // pair<iterator, bool> insert_or_assign(K&&, M&&);
140 // iterator insert_or_assign(const_iterator hint, K&&, M&&);
141 // pair<iterator, bool> emplace(Args&&...);
142 // iterator emplace_hint(const_iterator, Args&&...);
143 // pair<iterator, bool> try_emplace(K&&, Args&&...);
144 // iterator try_emplace(const_iterator hint, K&&, Args&&...);
145
146 // Underlying type functions:
147 // container_type extract() &&;
148 // void replace(container_type&&);
149 //
150 // Erase functions:
151 // iterator erase(iterator);
152 // iterator erase(const_iterator);
153 // iterator erase(const_iterator first, const_iterator& last);
154 // template <class K> size_t erase(const K& key);
155 //
156 // Comparators (see std::map documentation).
157 // key_compare key_comp() const;
158 // value_compare value_comp() const;
159 //
160 // Search functions:
161 // template <typename K> size_t count(const K&) const;
162 // template <typename K> iterator find(const K&);
163 // template <typename K> const_iterator find(const K&) const;
164 // template <typename K> bool contains(const K&) const;
165 // template <typename K> pair<iterator, iterator> equal_range(const K&);
166 // template <typename K> iterator lower_bound(const K&);
167 // template <typename K> const_iterator lower_bound(const K&) const;
168 // template <typename K> iterator upper_bound(const K&);
169 // template <typename K> const_iterator upper_bound(const K&) const;
170 //
171 // General functions:
172 // void swap(flat_map&);
173 //
174 // Non-member operators:
175 // bool operator==(const flat_map&, const flat_map);
176 // bool operator!=(const flat_map&, const flat_map);
177 // bool operator<(const flat_map&, const flat_map);
178 // bool operator>(const flat_map&, const flat_map);
179 // bool operator>=(const flat_map&, const flat_map);
180 // bool operator<=(const flat_map&, const flat_map);
181 //
182 template <class Key,
183 class Mapped,
184 class Compare = std::less<>,
185 class Container = std::vector<std::pair<Key, Mapped>>>
186 class flat_map : public ::webrtc::flat_containers_internal::flat_tree<
187 Key,
188 flat_containers_internal::GetFirst,
189 Compare,
190 Container> {
191 private:
192 using tree = typename ::webrtc::flat_containers_internal::
193 flat_tree<Key, flat_containers_internal::GetFirst, Compare, Container>;
194
195 public:
196 using key_type = typename tree::key_type;
197 using mapped_type = Mapped;
198 using value_type = typename tree::value_type;
199 using reference = typename Container::reference;
200 using const_reference = typename Container::const_reference;
201 using size_type = typename Container::size_type;
202 using difference_type = typename Container::difference_type;
203 using iterator = typename tree::iterator;
204 using const_iterator = typename tree::const_iterator;
205 using reverse_iterator = typename tree::reverse_iterator;
206 using const_reverse_iterator = typename tree::const_reverse_iterator;
207 using container_type = typename tree::container_type;
208
209 // --------------------------------------------------------------------------
210 // Lifetime and assignments.
211 //
212 // Note: we explicitly bring operator= in because otherwise
213 // flat_map<...> x;
214 // x = {...};
215 // Would first create a flat_map and then move assign it. This most likely
216 // would be optimized away but still affects our debug builds.
217
218 using tree::tree;
219 using tree::operator=;
220
221 // Out-of-bound calls to at() will CHECK.
222 template <class K>
223 mapped_type& at(const K& key);
224 template <class K>
225 const mapped_type& at(const K& key) const;
226
227 // --------------------------------------------------------------------------
228 // Map-specific insert operations.
229 //
230 // Normal insert() functions are inherited from flat_tree.
231 //
232 // Assume that every operation invalidates iterators and references.
233 // Insertion of one element can take O(size).
234
235 mapped_type& operator[](const key_type& key);
236 mapped_type& operator[](key_type&& key);
237
238 template <class K, class M>
239 std::pair<iterator, bool> insert_or_assign(K&& key, M&& obj);
240 template <class K, class M>
241 iterator insert_or_assign(const_iterator hint, K&& key, M&& obj);
242
243 template <class K, class... Args>
244 std::enable_if_t<std::is_constructible<key_type, K&&>::value,
245 std::pair<iterator, bool>>
246 try_emplace(K&& key, Args&&... args);
247
248 template <class K, class... Args>
249 std::enable_if_t<std::is_constructible<key_type, K&&>::value, iterator>
250 try_emplace(const_iterator hint, K&& key, Args&&... args);
251
252 // --------------------------------------------------------------------------
253 // General operations.
254 //
255 // Assume that swap invalidates iterators and references.
256
257 void swap(flat_map& other) noexcept;
258
swap(flat_map & lhs,flat_map & rhs)259 friend void swap(flat_map& lhs, flat_map& rhs) noexcept { lhs.swap(rhs); }
260 };
261
262 // ----------------------------------------------------------------------------
263 // Lookups.
264
265 template <class Key, class Mapped, class Compare, class Container>
266 template <class K>
267 auto flat_map<Key, Mapped, Compare, Container>::at(const K& key)
268 -> mapped_type& {
269 iterator found = tree::find(key);
270 RTC_CHECK(found != tree::end());
271 return found->second;
272 }
273
274 template <class Key, class Mapped, class Compare, class Container>
275 template <class K>
276 auto flat_map<Key, Mapped, Compare, Container>::at(const K& key) const
277 -> const mapped_type& {
278 const_iterator found = tree::find(key);
279 RTC_CHECK(found != tree::cend());
280 return found->second;
281 }
282
283 // ----------------------------------------------------------------------------
284 // Insert operations.
285
286 template <class Key, class Mapped, class Compare, class Container>
287 auto flat_map<Key, Mapped, Compare, Container>::operator[](const key_type& key)
288 -> mapped_type& {
289 iterator found = tree::lower_bound(key);
290 if (found == tree::end() || tree::key_comp()(key, found->first))
291 found = tree::unsafe_emplace(found, key, mapped_type());
292 return found->second;
293 }
294
295 template <class Key, class Mapped, class Compare, class Container>
296 auto flat_map<Key, Mapped, Compare, Container>::operator[](key_type&& key)
297 -> mapped_type& {
298 iterator found = tree::lower_bound(key);
299 if (found == tree::end() || tree::key_comp()(key, found->first))
300 found = tree::unsafe_emplace(found, std::move(key), mapped_type());
301 return found->second;
302 }
303
304 template <class Key, class Mapped, class Compare, class Container>
305 template <class K, class M>
306 auto flat_map<Key, Mapped, Compare, Container>::insert_or_assign(K&& key,
307 M&& obj)
308 -> std::pair<iterator, bool> {
309 auto result =
310 tree::emplace_key_args(key, std::forward<K>(key), std::forward<M>(obj));
311 if (!result.second)
312 result.first->second = std::forward<M>(obj);
313 return result;
314 }
315
316 template <class Key, class Mapped, class Compare, class Container>
317 template <class K, class M>
318 auto flat_map<Key, Mapped, Compare, Container>::insert_or_assign(
319 const_iterator hint,
320 K&& key,
321 M&& obj) -> iterator {
322 auto result = tree::emplace_hint_key_args(hint, key, std::forward<K>(key),
323 std::forward<M>(obj));
324 if (!result.second)
325 result.first->second = std::forward<M>(obj);
326 return result.first;
327 }
328
329 template <class Key, class Mapped, class Compare, class Container>
330 template <class K, class... Args>
331 auto flat_map<Key, Mapped, Compare, Container>::try_emplace(K&& key,
332 Args&&... args)
333 -> std::enable_if_t<std::is_constructible<key_type, K&&>::value,
334 std::pair<iterator, bool>> {
335 return tree::emplace_key_args(
336 key, std::piecewise_construct,
337 std::forward_as_tuple(std::forward<K>(key)),
338 std::forward_as_tuple(std::forward<Args>(args)...));
339 }
340
341 template <class Key, class Mapped, class Compare, class Container>
342 template <class K, class... Args>
343 auto flat_map<Key, Mapped, Compare, Container>::try_emplace(const_iterator hint,
344 K&& key,
345 Args&&... args)
346 -> std::enable_if_t<std::is_constructible<key_type, K&&>::value, iterator> {
347 return tree::emplace_hint_key_args(
348 hint, key, std::piecewise_construct,
349 std::forward_as_tuple(std::forward<K>(key)),
350 std::forward_as_tuple(std::forward<Args>(args)...))
351 .first;
352 }
353
354 // ----------------------------------------------------------------------------
355 // General operations.
356
357 template <class Key, class Mapped, class Compare, class Container>
swap(flat_map & other)358 void flat_map<Key, Mapped, Compare, Container>::swap(flat_map& other) noexcept {
359 tree::swap(other);
360 }
361
362 // Erases all elements that match predicate. It has O(size) complexity.
363 //
364 // flat_map<int, Timestamp> last_times;
365 // ...
366 // EraseIf(last_times,
367 // [&](const auto& element) { return now - element.second > kLimit; });
368
369 // NOLINTNEXTLINE(misc-unused-using-decls)
370 using ::webrtc::flat_containers_internal::EraseIf;
371
372 } // namespace webrtc
373
374 #endif // RTC_BASE_CONTAINERS_FLAT_MAP_H_
375