OLD | NEW |
---|---|
(Empty) | |
1 // Copyright 2017 The Chromium Authors. All rights reserved. | |
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_MAP_H_ | |
6 #define BASE_CONTAINERS_FLAT_MAP_H_ | |
7 | |
8 #include <utility> | |
9 | |
10 #include "base/containers/flat_tree.h" | |
11 | |
12 namespace base { | |
13 | |
14 // Overview: | |
15 // This file implements flat_map container. It is an alternative to standard | |
16 // sorted containers that stores it's elements in contiguous memory (current | |
dyaroshev
2017/02/24 22:55:48
Nit:
Is plural intentional?
brettw
2017/02/27 19:20:15
Done.
| |
17 // version uses sorted std::vector). | |
18 // | |
19 // Motivation: | |
20 // Contiguous memory is very beneficial to iteration and copy speed at the cost | |
21 // of worse algorithmic complexity of insertion/erasure operations. They can | |
22 // be very fast for set operations and for small number of elements. | |
23 // | |
dyaroshev
2017/02/24 22:55:48
Maybe we want to mention stbility here explicitly,
brettw
2017/02/27 19:20:15
I mentioned this in the constructor comment (I thi
dyaroshev
2017/02/27 22:23:37
Assigment too.
Well, I think it's an important usa
| |
24 // Usage guidance: | |
25 // Prefer base::flat_map for: | |
26 // * Very small maps, something that is an easy fit for cache. Consider | |
27 // "very small" to be under a 100 32bit integers. | |
28 // * Maps that are built once (using flat_map::flat_map(first, last)). Consider | |
29 // collecting all data in a vector<pair> and then building flat_map out of | |
30 // it. TODO(dyaroshev): improve the interface to better support this | |
31 // pattern (crbug.com/682254). | |
32 // * Copying and iterating. | |
33 // * Set operations (union/intersect etc). | |
34 // | |
35 // Additional commentary is in flat_set.h. | |
36 template <class Key, class Mapped, class Compare = std::less<Key>> | |
37 // Meets the requirements of Container, AssociativeContainer, | |
38 // ReversibleContainer. | |
39 // Requires: Key is Movable, Compare is a StrictWeakOrdering on Key. | |
40 class flat_map { | |
41 private: | |
42 struct PairFirstExtractor { | |
43 const Key& operator()(const std::pair<Key, Mapped>& p) const { | |
44 return p.first; | |
45 } | |
46 }; | |
47 using tree = typename ::base::internal:: | |
48 flat_tree<Key, std::pair<Key, Mapped>, PairFirstExtractor, Compare>; | |
49 | |
50 public: | |
51 // -------------------------------------------------------------------------- | |
52 // Types. | |
53 // | |
54 using key_type = typename tree::key_type; | |
55 using key_compare = typename tree::key_compare; | |
56 using value_type = typename tree::value_type; | |
57 using value_compare = typename tree::value_compare; | |
58 using mapped_type = Mapped; | |
59 | |
60 using pointer = typename tree::pointer; | |
61 using const_pointer = typename tree::const_pointer; | |
62 using reference = typename tree::reference; | |
63 using const_reference = typename tree::const_reference; | |
64 using size_type = typename tree::size_type; | |
65 using difference_type = typename tree::difference_type; | |
66 using iterator = typename tree::iterator; | |
67 using const_iterator = typename tree::const_iterator; | |
68 using reverse_iterator = typename tree::reverse_iterator; | |
69 using const_reverse_iterator = typename tree::const_reverse_iterator; | |
70 | |
71 // -------------------------------------------------------------------------- | |
72 // Lifetime. | |
73 // | |
74 // Constructors that take range guarantee O(N * log^2(N)) + O(N) complexity | |
75 // and take O(N * log(N)) + O(N) if extra memory is available (N is a range | |
76 // length). | |
dyaroshev
2017/02/24 22:55:48
Unfortunatly, this comment has to be updated to ju
brettw
2017/02/27 19:20:15
Done, I updated the comment.
| |
77 // | |
78 // Assume that move constructors invalidate iterators and references. | |
79 | |
80 flat_map(); | |
81 explicit flat_map(const Compare& comp); | |
82 | |
83 template <class InputIterator> | |
84 flat_map(InputIterator first, | |
85 InputIterator last, | |
86 const Compare& comp = Compare()); | |
87 | |
88 flat_map(const flat_map&); | |
89 flat_map(flat_map&&); | |
90 | |
91 flat_map(std::initializer_list<value_type> ilist, | |
92 const Compare& comp = Compare()); | |
93 | |
94 ~flat_map(); | |
95 | |
96 // -------------------------------------------------------------------------- | |
97 // Assignments. | |
98 // | |
99 // Assume that move assignment invalidates iterators and references. | |
100 | |
101 flat_map& operator=(const flat_map&); | |
102 flat_map& operator=(flat_map&&); | |
103 flat_map& operator=(std::initializer_list<value_type> ilist); | |
104 | |
105 // -------------------------------------------------------------------------- | |
106 // Memory management. | |
107 // | |
108 // Beware that shrink_to_fit() simply forwards the request to the | |
109 // underlying_type and its implementation is free to optimize otherwise and | |
110 // leave capacity() to be greater that its size. | |
111 // | |
112 // reserve() and shrink_to_fit() invalidate iterators and references. | |
113 | |
114 void reserve(size_type new_capacity); | |
115 size_type capacity() const; | |
116 void shrink_to_fit(); | |
117 | |
118 // -------------------------------------------------------------------------- | |
119 // Size management. | |
120 // | |
121 // clear() leaves the capacity() of the flat_map unchanged. | |
122 | |
123 void clear(); | |
124 | |
125 size_type size() const; | |
126 size_type max_size() const; | |
127 bool empty() const; | |
128 | |
129 // -------------------------------------------------------------------------- | |
130 // Iterators. | |
131 | |
132 iterator begin(); | |
133 const_iterator begin() const; | |
134 const_iterator cbegin() const; | |
135 | |
136 iterator end(); | |
137 const_iterator end() const; | |
138 const_iterator cend() const; | |
139 | |
140 reverse_iterator rbegin(); | |
141 const_reverse_iterator rbegin() const; | |
142 const_reverse_iterator crbegin() const; | |
143 | |
144 reverse_iterator rend(); | |
145 const_reverse_iterator rend() const; | |
146 const_reverse_iterator crend() const; | |
147 | |
148 // -------------------------------------------------------------------------- | |
149 // Insert operations. | |
150 // | |
151 // Assume that every operation invalidates iterators and references. | |
152 // Insertion of one element can take O(size). See the Notes section in the | |
153 // class comments on why we do not currently implement range insertion. | |
154 // Capacity of flat_map grows in an implementation-defined manner. | |
155 // | |
156 // NOTE: Prefer to build a new flat_map from a std::vector<pair> (or similar) | |
157 // instead of calling insert() repeatedly. | |
158 | |
159 mapped_type& operator[](const key_type& key); | |
160 mapped_type& operator[](key_type&& key); | |
dyaroshev
2017/02/24 22:55:48
Wouldn't at be useful as well? We can do CHECK in
brettw
2017/02/27 19:20:15
Done.
| |
161 | |
162 std::pair<iterator, bool> insert(const value_type& val); | |
163 std::pair<iterator, bool> insert(value_type&& val); | |
164 | |
165 iterator insert(const_iterator position_hint, const value_type& x); | |
166 iterator insert(const_iterator position_hint, value_type&& x); | |
167 | |
168 template <class... Args> | |
169 std::pair<iterator, bool> emplace(Args&&... args); | |
170 | |
171 template <class... Args> | |
172 iterator emplace_hint(const_iterator position_hint, Args&&... args); | |
173 | |
174 // -------------------------------------------------------------------------- | |
175 // Erase operations. | |
176 // | |
177 // Assume that every operation invalidates iterators and references. | |
178 // | |
179 // erase(position), erase(first, last) can take O(size). | |
180 // erase(key) may take O(size) + O(log(size)). | |
181 // | |
182 // Prefer the erase(std::remove(), end()) idiom for deleting multiple | |
183 // elements. | |
184 | |
185 iterator erase(const_iterator position); | |
186 iterator erase(const_iterator first, const_iterator last); | |
187 size_type erase(const key_type& key); | |
188 | |
189 // -------------------------------------------------------------------------- | |
190 // Comparators. | |
191 | |
192 key_compare key_comp() const; | |
193 value_compare value_comp() const; | |
194 | |
195 // -------------------------------------------------------------------------- | |
196 // Search operations. | |
197 // | |
198 // Search operations have O(log(size)) complexity. | |
199 | |
200 size_type count(const key_type& key) const; | |
201 | |
202 iterator find(const key_type& key); | |
203 const_iterator find(const key_type& key) const; | |
204 | |
205 std::pair<iterator, iterator> equal_range(const key_type& ket); | |
206 std::pair<const_iterator, const_iterator> equal_range( | |
207 const key_type& key) const; | |
208 | |
209 iterator lower_bound(const key_type& key); | |
210 const_iterator lower_bound(const key_type& key) const; | |
211 | |
212 iterator upper_bound(const key_type& key); | |
213 const_iterator upper_bound(const key_type& key) const; | |
214 | |
215 // -------------------------------------------------------------------------- | |
216 // General operations. | |
217 // | |
218 // Assume that swap invalidates iterators and references. | |
219 // | |
220 // As with std::set, equality and ordering operations for the whole flat_map | |
221 // are equivalent to using equal() and lexicographical_compare() on the key | |
222 // types, rather than using element-wise key_comp() as e.g. lower_bound() | |
223 // does. Implementation note: currently we use operator==() and operator<() on | |
dyaroshev
2017/02/24 22:55:48
This code won't change - you use opertors on the t
brettw
2017/02/27 19:20:15
Yeah, I just removed this part of the comment.
| |
224 // std::vector, because they have the same contract we need, so we use them | |
225 // directly for brevity and in case it is more optimal than calling equal() | |
226 // and lexicograhpical_compare(). If the underlying container type is changed, | |
227 // this code may need to be modified. | |
228 | |
229 void swap(flat_map& other); | |
230 | |
231 friend bool operator==(const flat_map& lhs, const flat_map& rhs) { | |
232 return lhs.tree_ == rhs.tree_; | |
233 } | |
234 | |
235 friend bool operator!=(const flat_map& lhs, const flat_map& rhs) { | |
236 return !(lhs == rhs); | |
237 } | |
238 | |
239 friend bool operator<(const flat_map& lhs, const flat_map& rhs) { | |
240 return lhs.tree_ < rhs.tree_; | |
241 } | |
242 | |
243 friend bool operator>(const flat_map& lhs, const flat_map& rhs) { | |
244 return rhs < lhs; | |
245 } | |
246 | |
247 friend bool operator>=(const flat_map& lhs, const flat_map& rhs) { | |
248 return !(lhs < rhs); | |
249 } | |
250 | |
251 friend bool operator<=(const flat_map& lhs, const flat_map& rhs) { | |
252 return !(lhs > rhs); | |
253 } | |
254 | |
255 friend void swap(flat_map& lhs, flat_map& rhs) { lhs.swap(rhs); } | |
256 | |
257 private: | |
258 tree tree_; | |
259 }; | |
260 | |
261 // ---------------------------------------------------------------------------- | |
262 // Lifetime. | |
263 | |
264 template <class Key, class Mapped, class Compare> | |
265 flat_map<Key, Mapped, Compare>::flat_map() = default; | |
266 | |
267 template <class Key, class Mapped, class Compare> | |
268 flat_map<Key, Mapped, Compare>::flat_map(const Compare& comp) : tree_(comp) {} | |
269 | |
270 template <class Key, class Mapped, class Compare> | |
271 template <class InputIterator> | |
272 flat_map<Key, Mapped, Compare>::flat_map(InputIterator first, | |
273 InputIterator last, | |
274 const Compare& comp) | |
275 : tree_(first, last, comp) {} | |
276 | |
277 template <class Key, class Mapped, class Compare> | |
278 flat_map<Key, Mapped, Compare>::flat_map(const flat_map&) = default; | |
279 | |
280 template <class Key, class Mapped, class Compare> | |
281 flat_map<Key, Mapped, Compare>::flat_map(flat_map&&) = default; | |
282 | |
283 template <class Key, class Mapped, class Compare> | |
284 flat_map<Key, Mapped, Compare>::flat_map( | |
285 std::initializer_list<value_type> ilist, | |
286 const Compare& comp) | |
287 : flat_map(std::begin(ilist), std::end(ilist), comp) {} | |
288 | |
289 template <class Key, class Mapped, class Compare> | |
290 flat_map<Key, Mapped, Compare>::~flat_map() = default; | |
291 | |
292 // ---------------------------------------------------------------------------- | |
293 // Assignments. | |
294 | |
295 template <class Key, class Mapped, class Compare> | |
296 auto flat_map<Key, Mapped, Compare>::operator=(const flat_map&) | |
297 -> flat_map& = default; | |
298 | |
299 template <class Key, class Mapped, class Compare> | |
300 auto flat_map<Key, Mapped, Compare>::operator=(flat_map &&) | |
301 -> flat_map& = default; | |
302 | |
303 template <class Key, class Mapped, class Compare> | |
304 auto flat_map<Key, Mapped, Compare>::operator=( | |
305 std::initializer_list<value_type> ilist) -> flat_map& { | |
306 tree_ = ilist; | |
307 return *this; | |
308 } | |
309 | |
310 // ---------------------------------------------------------------------------- | |
311 // Memory management. | |
312 | |
313 template <class Key, class Mapped, class Compare> | |
314 void flat_map<Key, Mapped, Compare>::reserve(size_type new_capacity) { | |
315 tree_.reserve(new_capacity); | |
316 } | |
317 | |
318 template <class Key, class Mapped, class Compare> | |
319 auto flat_map<Key, Mapped, Compare>::capacity() const -> size_type { | |
320 return tree_.capacity(); | |
321 } | |
322 | |
323 template <class Key, class Mapped, class Compare> | |
324 void flat_map<Key, Mapped, Compare>::shrink_to_fit() { | |
325 tree_.shrink_to_fit(); | |
326 } | |
327 | |
328 // ---------------------------------------------------------------------------- | |
329 // Size management. | |
330 | |
331 template <class Key, class Mapped, class Compare> | |
332 void flat_map<Key, Mapped, Compare>::clear() { | |
333 tree_.clear(); | |
334 } | |
335 | |
336 template <class Key, class Mapped, class Compare> | |
337 auto flat_map<Key, Mapped, Compare>::size() const -> size_type { | |
338 return tree_.size(); | |
339 } | |
340 | |
341 template <class Key, class Mapped, class Compare> | |
342 auto flat_map<Key, Mapped, Compare>::max_size() const -> size_type { | |
343 return tree_.max_size(); | |
344 } | |
345 | |
346 template <class Key, class Mapped, class Compare> | |
347 bool flat_map<Key, Mapped, Compare>::empty() const { | |
348 return tree_.empty(); | |
349 } | |
350 | |
351 // ---------------------------------------------------------------------------- | |
352 // Iterators. | |
353 | |
354 template <class Key, class Mapped, class Compare> | |
355 auto flat_map<Key, Mapped, Compare>::begin() -> iterator { | |
356 return tree_.begin(); | |
357 } | |
358 | |
359 template <class Key, class Mapped, class Compare> | |
360 auto flat_map<Key, Mapped, Compare>::begin() const -> const_iterator { | |
361 return tree_.begin(); | |
362 } | |
363 | |
364 template <class Key, class Mapped, class Compare> | |
365 auto flat_map<Key, Mapped, Compare>::cbegin() const -> const_iterator { | |
366 return tree_.cbegin(); | |
367 } | |
368 | |
369 template <class Key, class Mapped, class Compare> | |
370 auto flat_map<Key, Mapped, Compare>::end() -> iterator { | |
371 return tree_.end(); | |
372 } | |
373 | |
374 template <class Key, class Mapped, class Compare> | |
375 auto flat_map<Key, Mapped, Compare>::end() const -> const_iterator { | |
376 return tree_.end(); | |
377 } | |
378 | |
379 template <class Key, class Mapped, class Compare> | |
380 auto flat_map<Key, Mapped, Compare>::cend() const -> const_iterator { | |
381 return tree_.cend(); | |
382 } | |
383 | |
384 template <class Key, class Mapped, class Compare> | |
385 auto flat_map<Key, Mapped, Compare>::rbegin() -> reverse_iterator { | |
386 return tree_.rbegin(); | |
387 } | |
388 | |
389 template <class Key, class Mapped, class Compare> | |
390 auto flat_map<Key, Mapped, Compare>::rbegin() const -> const_reverse_iterator { | |
391 return tree_.rbegin(); | |
392 } | |
393 | |
394 template <class Key, class Mapped, class Compare> | |
395 auto flat_map<Key, Mapped, Compare>::crbegin() const -> const_reverse_iterator { | |
396 return tree_.crbegin(); | |
397 } | |
398 | |
399 template <class Key, class Mapped, class Compare> | |
400 auto flat_map<Key, Mapped, Compare>::rend() -> reverse_iterator { | |
401 return tree_.rend(); | |
402 } | |
403 | |
404 template <class Key, class Mapped, class Compare> | |
405 auto flat_map<Key, Mapped, Compare>::rend() const -> const_reverse_iterator { | |
406 return tree_.rend(); | |
407 } | |
408 | |
409 template <class Key, class Mapped, class Compare> | |
410 auto flat_map<Key, Mapped, Compare>::crend() const -> const_reverse_iterator { | |
411 return tree_.crend(); | |
412 } | |
413 | |
414 // ---------------------------------------------------------------------------- | |
415 // Insert operations. | |
416 // | |
417 // Currently we use position_hint the same way as eastl or boost: | |
418 // https://github.com/electronicarts/EASTL/blob/master/include/EASTL/vector_set. h#L493 | |
419 // | |
420 // We duplicate code between copy and move version so that we can avoid | |
421 // creating a temporary value. | |
dyaroshev
2017/02/24 22:55:48
This commemt refers to implementation, so it shoul
brettw
2017/02/27 19:20:15
Done.
| |
422 | |
423 template <class Key, class Mapped, class Compare> | |
424 auto flat_map<Key, Mapped, Compare>::operator[](const key_type& key) | |
425 -> mapped_type& { | |
426 iterator found = lower_bound(key); | |
427 if (found == end() || key_comp()(key, found->first)) | |
428 found = insert(found, value_type(key, Mapped())); | |
429 return found->second; | |
430 } | |
431 | |
432 template <class Key, class Mapped, class Compare> | |
433 auto flat_map<Key, Mapped, Compare>::operator[](key_type&& key) | |
434 -> mapped_type& { | |
435 const Key& key_ref = key; | |
436 iterator found = lower_bound(key_ref); | |
437 if (found == end() || key_comp()(key, found->first)) | |
438 found = insert(found, value_type(std::move(key), Mapped())); | |
439 return found->second; | |
440 } | |
441 | |
442 template <class Key, class Mapped, class Compare> | |
443 auto flat_map<Key, Mapped, Compare>::insert(const value_type& val) | |
444 -> std::pair<iterator, bool> { | |
445 return tree_.insert(val); | |
446 } | |
447 | |
448 template <class Key, class Mapped, class Compare> | |
449 auto flat_map<Key, Mapped, Compare>::insert(value_type&& val) | |
450 -> std::pair<iterator, bool> { | |
451 return tree_.insert(std::move(val)); | |
452 } | |
453 | |
454 template <class Key, class Mapped, class Compare> | |
455 auto flat_map<Key, Mapped, Compare>::insert(const_iterator position_hint, | |
456 const value_type& val) -> iterator { | |
457 return tree_.insert(position_hint, val); | |
458 } | |
459 | |
460 template <class Key, class Mapped, class Compare> | |
461 auto flat_map<Key, Mapped, Compare>::insert(const_iterator position_hint, | |
462 value_type&& val) -> iterator { | |
463 return tree_.insert(position_hint, std::move(val)); | |
464 } | |
465 | |
466 template <class Key, class Mapped, class Compare> | |
467 template <class... Args> | |
468 auto flat_map<Key, Mapped, Compare>::emplace(Args&&... args) | |
469 -> std::pair<iterator, bool> { | |
470 return tree_.emplace(std::forward<Args>(args)...); | |
471 } | |
472 | |
473 template <class Key, class Mapped, class Compare> | |
474 template <class... Args> | |
475 auto flat_map<Key, Mapped, Compare>::emplace_hint(const_iterator position_hint, | |
476 Args&&... args) -> iterator { | |
477 return tree_.emplace_hint(position_hint, std::forward<Args>(args)...); | |
478 } | |
479 | |
480 // ---------------------------------------------------------------------------- | |
481 // Erase operations. | |
482 | |
483 template <class Key, class Mapped, class Compare> | |
484 auto flat_map<Key, Mapped, Compare>::erase(const_iterator position) | |
485 -> iterator { | |
486 return tree_.erase(position); | |
487 } | |
488 | |
489 template <class Key, class Mapped, class Compare> | |
490 auto flat_map<Key, Mapped, Compare>::erase(const key_type& val) -> size_type { | |
491 return tree_.erase(val); | |
492 } | |
493 | |
494 template <class Key, class Mapped, class Compare> | |
495 auto flat_map<Key, Mapped, Compare>::erase(const_iterator first, | |
496 const_iterator last) -> iterator { | |
497 return tree_.erase(first, last); | |
498 } | |
499 | |
500 // ---------------------------------------------------------------------------- | |
501 // Comparators. | |
502 | |
503 template <class Key, class Mapped, class Compare> | |
504 auto flat_map<Key, Mapped, Compare>::key_comp() const -> key_compare { | |
505 return tree_.key_comp(); | |
506 } | |
507 | |
508 template <class Key, class Mapped, class Compare> | |
509 auto flat_map<Key, Mapped, Compare>::value_comp() const -> value_compare { | |
510 return tree_.value_comp(); | |
511 } | |
512 | |
513 // ---------------------------------------------------------------------------- | |
514 // Search operations. | |
515 | |
516 template <class Key, class Mapped, class Compare> | |
517 auto flat_map<Key, Mapped, Compare>::count(const key_type& key) const | |
518 -> size_type { | |
519 return tree_.count(key); | |
520 } | |
521 | |
522 template <class Key, class Mapped, class Compare> | |
523 auto flat_map<Key, Mapped, Compare>::find(const key_type& key) -> iterator { | |
524 return tree_.find(key); | |
525 } | |
526 | |
527 template <class Key, class Mapped, class Compare> | |
528 auto flat_map<Key, Mapped, Compare>::find(const key_type& key) const | |
529 -> const_iterator { | |
530 return tree_.find(key); | |
531 } | |
532 | |
533 template <class Key, class Mapped, class Compare> | |
534 auto flat_map<Key, Mapped, Compare>::equal_range(const key_type& key) | |
535 -> std::pair<iterator, iterator> { | |
536 return tree_.equal_range(key); | |
537 } | |
538 | |
539 template <class Key, class Mapped, class Compare> | |
540 auto flat_map<Key, Mapped, Compare>::equal_range(const key_type& key) const | |
541 -> std::pair<const_iterator, const_iterator> { | |
542 return tree_.equal_range(key); | |
543 } | |
544 | |
545 template <class Key, class Mapped, class Compare> | |
546 auto flat_map<Key, Mapped, Compare>::lower_bound(const key_type& key) | |
547 -> iterator { | |
548 return tree_.lower_bound(key); | |
549 } | |
550 | |
551 template <class Key, class Mapped, class Compare> | |
552 auto flat_map<Key, Mapped, Compare>::lower_bound(const key_type& key) const | |
553 -> const_iterator { | |
554 return tree_.lower_bound(key); | |
555 } | |
556 | |
557 template <class Key, class Mapped, class Compare> | |
558 auto flat_map<Key, Mapped, Compare>::upper_bound(const key_type& key) | |
559 -> iterator { | |
560 return tree_.upper_bound(key); | |
561 } | |
562 | |
563 template <class Key, class Mapped, class Compare> | |
564 auto flat_map<Key, Mapped, Compare>::upper_bound(const key_type& key) const | |
565 -> const_iterator { | |
566 return tree_.upper_bound(key); | |
567 } | |
568 | |
569 // ---------------------------------------------------------------------------- | |
570 // General operations. | |
571 | |
572 template <class Key, class Mapped, class Compare> | |
573 void flat_map<Key, Mapped, Compare>::swap(flat_map& other) { | |
574 std::swap(tree_, other.tree_); | |
575 } | |
576 | |
577 } // namespace base | |
578 | |
579 #endif // BASE_CONTAINERS_FLAT_MAP_H_ | |
OLD | NEW |