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_TREE_H_ | |
6 #define BASE_CONTAINERS_FLAT_TREE_H_ | |
7 | |
8 #include <algorithm> | |
9 #include <vector> | |
10 | |
11 namespace base { | |
12 namespace internal { | |
13 | |
14 // Implementation of a sorted vector for backing flat_set and flat_map. Do not | |
15 // use directly. | |
16 // | |
17 // The use of "value" in this is like std::map uses, meaning it's the thing | |
18 // contained (in the case of map it's a <Kay, Mapped> pair). The Key is how | |
19 // things are looked up. In the case of a set, Key == Value. In the case of | |
20 // a map, the Key is a component of a Value. | |
21 // | |
22 // The helper class GetKeyFromValue provides the means to extract a key from a | |
23 // value for comparison purposes. It should implement: | |
24 // const Key& operator()(const Value&). | |
25 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
26 class flat_tree { | |
27 public: | |
28 private: | |
29 using underlying_type = std::vector<Value>; | |
30 | |
31 public: | |
32 // -------------------------------------------------------------------------- | |
33 // Types. | |
34 // | |
35 using key_type = Key; | |
36 using key_compare = KeyCompare; | |
37 using value_type = Value; | |
38 | |
39 // Wraps the templated key comparison to compare values. | |
40 class value_compare : public key_compare { | |
41 public: | |
42 value_compare() = default; | |
43 | |
44 template <class Cmp> | |
45 explicit value_compare(Cmp&& compare_arg) | |
46 : KeyCompare(std::forward<Cmp>(compare_arg)) {} | |
47 | |
48 bool operator()(const Value& left, const Value& right) const { | |
49 GetKeyFromValue extractor; | |
50 return key_compare::operator()(extractor(left), extractor(right)); | |
51 } | |
52 }; | |
53 | |
54 using pointer = typename underlying_type::pointer; | |
55 using const_pointer = typename underlying_type::const_pointer; | |
56 using reference = typename underlying_type::reference; | |
57 using const_reference = typename underlying_type::const_reference; | |
58 using size_type = typename underlying_type::size_type; | |
59 using difference_type = typename underlying_type::difference_type; | |
60 using iterator = typename underlying_type::iterator; | |
61 using const_iterator = typename underlying_type::const_iterator; | |
62 using reverse_iterator = typename underlying_type::reverse_iterator; | |
63 using const_reverse_iterator = | |
64 typename underlying_type::const_reverse_iterator; | |
65 | |
66 // -------------------------------------------------------------------------- | |
67 // Lifetime. | |
68 // | |
69 // Constructors that take range guarantee O(N * log^2(N)) + O(N) complexity | |
70 // and take O(N * log(N)) + O(N) if extra memory is available (N is a range | |
71 // length). | |
72 // | |
73 // Assume that move constructors invalidate iterators and references. | |
74 | |
75 flat_tree(); | |
76 explicit flat_tree(const key_compare& comp); | |
77 | |
78 // Not stable in the presence of duplicates in the initializer list. | |
79 template <class InputIterator> | |
80 flat_tree(InputIterator first, | |
81 InputIterator last, | |
82 const key_compare& comp = key_compare()); | |
83 | |
84 flat_tree(const flat_tree&); | |
85 flat_tree(flat_tree&&); | |
86 | |
87 // Not stable in the presence of duplicates in the initializer list. | |
88 flat_tree(std::initializer_list<value_type> ilist, | |
89 const key_compare& comp = key_compare()); | |
90 | |
91 ~flat_tree(); | |
92 | |
93 // -------------------------------------------------------------------------- | |
94 // Assignments. | |
95 // | |
96 // Assume that move assignment invalidates iterators and references. | |
97 | |
98 flat_tree& operator=(const flat_tree&); | |
99 flat_tree& operator=(flat_tree&&); | |
100 // Not stable in the presence of duplicates in the initializer list. | |
101 flat_tree& operator=(std::initializer_list<value_type> ilist); | |
102 | |
103 // -------------------------------------------------------------------------- | |
104 // Memory management. | |
105 // | |
106 // Beware that shrink_to_fit() simply forwards the request to the | |
107 // underlying_type and its implementation is free to optimize otherwise and | |
108 // leave capacity() to be greater that its size. | |
109 // | |
110 // reserve() and shrink_to_fit() invalidate iterators and references. | |
111 | |
112 void reserve(size_type new_capacity); | |
113 size_type capacity() const; | |
114 void shrink_to_fit(); | |
115 | |
116 // -------------------------------------------------------------------------- | |
117 // Size management. | |
118 // | |
119 // clear() leaves the capacity() of the flat_tree unchanged. | |
120 | |
121 void clear(); | |
122 | |
123 size_type size() const; | |
124 size_type max_size() const; | |
125 bool empty() const; | |
126 | |
127 // -------------------------------------------------------------------------- | |
128 // Iterators. | |
129 | |
130 iterator begin(); | |
131 const_iterator begin() const; | |
132 const_iterator cbegin() const; | |
133 | |
134 iterator end(); | |
135 const_iterator end() const; | |
136 const_iterator cend() const; | |
137 | |
138 reverse_iterator rbegin(); | |
139 const_reverse_iterator rbegin() const; | |
140 const_reverse_iterator crbegin() const; | |
141 | |
142 reverse_iterator rend(); | |
143 const_reverse_iterator rend() const; | |
144 const_reverse_iterator crend() const; | |
145 | |
146 // -------------------------------------------------------------------------- | |
147 // Insert operations. | |
148 // | |
149 // Assume that every operation invalidates iterators and references. | |
150 // Insertion of one element can take O(size). See the Notes section in the | |
151 // class comments on why we do not currently implement range insertion. | |
152 // Capacity of flat_tree grows in an implementation-defined manner. | |
153 // | |
154 // NOTE: Prefer to build a new flat_tree from a std::vector (or similar) | |
155 // instead of calling insert() repeatedly. | |
156 | |
157 std::pair<iterator, bool> insert(const value_type& val); | |
158 std::pair<iterator, bool> insert(value_type&& val); | |
159 | |
160 iterator insert(const_iterator position_hint, const value_type& x); | |
161 iterator insert(const_iterator position_hint, value_type&& x); | |
162 | |
163 template <class... Args> | |
164 std::pair<iterator, bool> emplace(Args&&... args); | |
165 | |
166 template <class... Args> | |
167 iterator emplace_hint(const_iterator position_hint, Args&&... args); | |
168 | |
169 // -------------------------------------------------------------------------- | |
170 // Erase operations. | |
171 // | |
172 // Assume that every operation invalidates iterators and references. | |
173 // | |
174 // erase(position), erase(first, last) can take O(size). | |
175 // erase(key) may take O(size) + O(log(size)). | |
176 // | |
177 // Prefer the erase(std::remove(), end()) idiom for deleting multiple | |
178 // elements. | |
179 | |
180 iterator erase(const_iterator position); | |
181 iterator erase(const_iterator first, const_iterator last); | |
182 size_type erase(const key_type& key); | |
183 | |
184 // -------------------------------------------------------------------------- | |
185 // Comparators. | |
186 | |
187 key_compare key_comp() const; | |
188 value_compare value_comp() const; | |
189 | |
190 // -------------------------------------------------------------------------- | |
191 // Search operations. | |
192 // | |
193 // Search operations have O(log(size)) complexity. | |
194 | |
195 size_type count(const key_type& key) const; | |
196 | |
197 iterator find(const key_type& key); | |
198 const_iterator find(const key_type& key) const; | |
199 | |
200 std::pair<iterator, iterator> equal_range(const key_type& ket); | |
201 std::pair<const_iterator, const_iterator> equal_range( | |
202 const key_type& key) const; | |
203 | |
204 iterator lower_bound(const key_type& key); | |
205 const_iterator lower_bound(const key_type& key) const; | |
206 | |
207 iterator upper_bound(const key_type& key); | |
208 const_iterator upper_bound(const key_type& key) const; | |
209 | |
210 // -------------------------------------------------------------------------- | |
211 // General operations. | |
212 // | |
213 // Assume that swap invalidates iterators and references. | |
214 // | |
215 // Implementation note: currently we use operator==() and operator<() on | |
216 // std::vector, because they have the same contract we need, so we use them | |
217 // directly for brevity and in case it is more optimal than calling equal() | |
218 // and lexicograhpical_compare(). If the underlying container type is changed, | |
219 // this code may need to be modified. | |
220 | |
221 void swap(flat_tree& other); | |
222 | |
223 friend bool operator==(const flat_tree& lhs, const flat_tree& rhs) { | |
224 return lhs.impl_.body_ == rhs.impl_.body_; | |
225 } | |
226 | |
227 friend bool operator!=(const flat_tree& lhs, const flat_tree& rhs) { | |
228 return !(lhs == rhs); | |
229 } | |
230 | |
231 friend bool operator<(const flat_tree& lhs, const flat_tree& rhs) { | |
232 return lhs.impl_.body_ < rhs.impl_.body_; | |
233 } | |
234 | |
235 friend bool operator>(const flat_tree& lhs, const flat_tree& rhs) { | |
236 return rhs < lhs; | |
237 } | |
238 | |
239 friend bool operator>=(const flat_tree& lhs, const flat_tree& rhs) { | |
240 return !(lhs < rhs); | |
241 } | |
242 | |
243 friend bool operator<=(const flat_tree& lhs, const flat_tree& rhs) { | |
244 return !(lhs > rhs); | |
245 } | |
246 | |
247 friend void swap(flat_tree& lhs, flat_tree& rhs) { lhs.swap(rhs); } | |
248 | |
249 protected: | |
250 // Inserts a new item into the tree that is known not to be in it. This | |
251 // is for implementing map [] and at(). | |
252 iterator unsafe_insert_new_at(const_iterator position, const value_type& val); | |
253 iterator unsafe_insert_new_at(const_iterator position, value_type&& val); | |
dyaroshev
2017/02/28 18:40:53
Nit: this could be one unsafe_emplace.
dyaroshev
2017/03/06 17:41:55
I still think this is a good idea.
| |
254 | |
255 private: | |
256 // Helper class for e.g. lower_bound that can compare a value on the left | |
257 // to a key on the right. | |
258 struct KeyValueCompare { | |
259 // The key comparison object must outlive this class. | |
260 explicit KeyValueCompare(const key_compare& key_comp) | |
261 : key_comp_(key_comp) {} | |
262 | |
263 bool operator()(const value_type& left, const key_type& right) const { | |
264 GetKeyFromValue extractor; | |
265 return key_comp_(extractor(left), right); | |
266 } | |
267 | |
268 private: | |
269 const key_compare& key_comp_; | |
270 }; | |
271 | |
272 const flat_tree& as_const() { return *this; } | |
273 | |
274 iterator const_cast_it(const_iterator c_it) { | |
275 auto distance = std::distance(cbegin(), c_it); | |
276 return std::next(begin(), distance); | |
277 } | |
278 | |
279 void sort_and_unique() { | |
280 // std::set sorts elements preserving stability because it doesn't have any | |
281 // performance wins in not doing that. We do, so we use an unstable sort. | |
282 std::sort(begin(), end(), impl_.get_value_comp()); | |
283 erase(std::unique(begin(), end(), | |
284 [this](const value_type& lhs, const value_type& rhs) { | |
285 // lhs is already <= rhs due to sort, therefore | |
286 // !(lhs < rhs) <=> lhs == rhs. | |
287 return !impl_.get_value_comp()(lhs, rhs); | |
288 }), | |
289 end()); | |
290 } | |
291 | |
292 // To support comparators that may not be possible to default-construct, we | |
293 // have to store an instance of Compare. Using this to store all internal | |
294 // state of flat_tree and using private inheritance to store compare lets us | |
295 // take advantage of an empty base class optimization to avoid extra space in | |
296 // the common case when Compare has no state. | |
297 struct Impl : private value_compare { | |
298 Impl() = default; | |
299 | |
300 template <class Cmp, class... Body> | |
301 explicit Impl(Cmp&& compare_arg, Body&&... underlying_type_args) | |
302 : value_compare(std::forward<Cmp>(compare_arg)), | |
303 body_(std::forward<Body>(underlying_type_args)...) {} | |
304 | |
305 const value_compare& get_value_comp() const { return *this; } | |
306 const key_compare& get_key_comp() const { return *this; } | |
307 | |
308 underlying_type body_; | |
309 } impl_; | |
310 }; | |
311 | |
312 // ---------------------------------------------------------------------------- | |
313 // Lifetime. | |
314 | |
315 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
316 flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::flat_tree() = default; | |
317 | |
318 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
319 flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::flat_tree( | |
320 const KeyCompare& comp) | |
321 : impl_(comp) {} | |
322 | |
323 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
324 template <class InputIterator> | |
325 flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::flat_tree( | |
326 InputIterator first, | |
327 InputIterator last, | |
328 const KeyCompare& comp) | |
329 : impl_(comp, first, last) { | |
330 sort_and_unique(); | |
331 } | |
332 | |
333 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
334 flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::flat_tree( | |
335 const flat_tree&) = default; | |
336 | |
337 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
338 flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::flat_tree(flat_tree&&) = | |
339 default; | |
340 | |
341 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
342 flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::flat_tree( | |
343 std::initializer_list<value_type> ilist, | |
344 const KeyCompare& comp) | |
345 : flat_tree(std::begin(ilist), std::end(ilist), comp) {} | |
346 | |
347 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
348 flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::~flat_tree() = default; | |
349 | |
350 // ---------------------------------------------------------------------------- | |
351 // Assignments. | |
352 | |
353 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
354 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::operator=( | |
355 const flat_tree&) -> flat_tree& = default; | |
356 | |
357 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
358 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::operator=(flat_tree &&) | |
359 -> flat_tree& = default; | |
360 | |
361 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
362 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::operator=( | |
363 std::initializer_list<value_type> ilist) -> flat_tree& { | |
364 impl_.body_ = ilist; | |
365 sort_and_unique(); | |
366 return *this; | |
367 } | |
368 | |
369 // ---------------------------------------------------------------------------- | |
370 // Memory management. | |
371 | |
372 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
373 void flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::reserve( | |
374 size_type new_capacity) { | |
375 impl_.body_.reserve(new_capacity); | |
376 } | |
377 | |
378 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
379 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::capacity() const | |
380 -> size_type { | |
381 return impl_.body_.capacity(); | |
382 } | |
383 | |
384 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
385 void flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::shrink_to_fit() { | |
386 impl_.body_.shrink_to_fit(); | |
387 } | |
388 | |
389 // ---------------------------------------------------------------------------- | |
390 // Size management. | |
391 | |
392 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
393 void flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::clear() { | |
394 impl_.body_.clear(); | |
395 } | |
396 | |
397 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
398 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::size() const | |
399 -> size_type { | |
400 return impl_.body_.size(); | |
401 } | |
402 | |
403 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
404 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::max_size() const | |
405 -> size_type { | |
406 return impl_.body_.max_size(); | |
407 } | |
408 | |
409 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
410 bool flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::empty() const { | |
411 return impl_.body_.empty(); | |
412 } | |
413 | |
414 // ---------------------------------------------------------------------------- | |
415 // Iterators. | |
416 | |
417 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
418 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::begin() -> iterator { | |
419 return impl_.body_.begin(); | |
420 } | |
421 | |
422 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
423 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::begin() const | |
424 -> const_iterator { | |
425 return impl_.body_.begin(); | |
426 } | |
427 | |
428 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
429 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::cbegin() const | |
430 -> const_iterator { | |
431 return impl_.body_.cbegin(); | |
432 } | |
433 | |
434 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
435 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::end() -> iterator { | |
436 return impl_.body_.end(); | |
437 } | |
438 | |
439 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
440 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::end() const | |
441 -> const_iterator { | |
442 return impl_.body_.end(); | |
443 } | |
444 | |
445 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
446 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::cend() const | |
447 -> const_iterator { | |
448 return impl_.body_.cend(); | |
449 } | |
450 | |
451 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
452 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::rbegin() | |
453 -> reverse_iterator { | |
454 return impl_.body_.rbegin(); | |
455 } | |
456 | |
457 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
458 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::rbegin() const | |
459 -> const_reverse_iterator { | |
460 return impl_.body_.rbegin(); | |
461 } | |
462 | |
463 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
464 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::crbegin() const | |
465 -> const_reverse_iterator { | |
466 return impl_.body_.crbegin(); | |
467 } | |
468 | |
469 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
470 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::rend() | |
471 -> reverse_iterator { | |
472 return impl_.body_.rend(); | |
473 } | |
474 | |
475 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
476 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::rend() const | |
477 -> const_reverse_iterator { | |
478 return impl_.body_.rend(); | |
479 } | |
480 | |
481 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
482 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::crend() const | |
483 -> const_reverse_iterator { | |
484 return impl_.body_.crend(); | |
485 } | |
486 | |
487 // ---------------------------------------------------------------------------- | |
488 // Insert operations. | |
489 // | |
490 // Currently we use position_hint the same way as eastl or boost: | |
491 // https://github.com/electronicarts/EASTL/blob/master/include/EASTL/vector_set. h#L493 | |
492 // | |
493 // We duplicate code between copy and move version so that we can avoid | |
494 // creating a temporary value. | |
495 | |
496 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
497 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::insert( | |
498 const value_type& val) -> std::pair<iterator, bool> { | |
499 auto position = lower_bound(val); | |
500 | |
501 if (position == end() || impl_.get_value_comp()(val, *position)) | |
502 return {impl_.body_.insert(position, val), true}; | |
503 | |
504 return {position, false}; | |
505 } | |
506 | |
507 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
508 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::insert( | |
509 value_type&& val) -> std::pair<iterator, bool> { | |
510 GetKeyFromValue extractor; | |
511 auto position = lower_bound(extractor(val)); | |
512 | |
513 if (position == end() || impl_.get_value_comp()(val, *position)) | |
514 return {impl_.body_.insert(position, std::move(val)), true}; | |
515 | |
516 return {position, false}; | |
517 } | |
518 | |
519 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
520 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::insert( | |
521 const_iterator position_hint, | |
522 const value_type& val) -> iterator { | |
523 if (position_hint == end() || impl_.get_value_comp()(val, *position_hint)) { | |
524 if (position_hint == begin() || | |
525 impl_.get_value_comp()(*(position_hint - 1), val)) | |
526 // We have to cast away const because of crbug.com/677044. | |
527 return impl_.body_.insert(const_cast_it(position_hint), val); | |
528 } | |
529 return insert(val).first; | |
530 } | |
531 | |
532 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
533 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::insert( | |
534 const_iterator position_hint, | |
535 value_type&& val) -> iterator { | |
536 if (position_hint == end() || impl_.get_value_comp()(val, *position_hint)) { | |
537 if (position_hint == begin() || | |
538 impl_.get_value_comp()(*(position_hint - 1), val)) | |
539 // We have to cast away const because of crbug.com/677044. | |
540 return impl_.body_.insert(const_cast_it(position_hint), std::move(val)); | |
541 } | |
542 return insert(std::move(val)).first; | |
543 } | |
544 | |
545 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
546 template <class... Args> | |
547 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::emplace(Args&&... args) | |
548 -> std::pair<iterator, bool> { | |
549 return insert(value_type(std::forward<Args>(args)...)); | |
550 } | |
551 | |
552 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
553 template <class... Args> | |
554 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::emplace_hint( | |
555 const_iterator position_hint, | |
556 Args&&... args) -> iterator { | |
557 return insert(position_hint, value_type(std::forward<Args>(args)...)); | |
558 } | |
559 | |
560 // ---------------------------------------------------------------------------- | |
561 // Erase operations. | |
562 | |
563 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
564 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::erase( | |
565 const_iterator position) -> iterator { | |
566 // We have to cast away const because of crbug.com/677044. | |
567 return impl_.body_.erase(const_cast_it(position)); | |
568 } | |
569 | |
570 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
571 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::erase( | |
572 const key_type& val) -> size_type { | |
573 auto eq_range = equal_range(val); | |
574 auto res = std::distance(eq_range.first, eq_range.second); | |
575 // We have to cast away const because of crbug.com/677044. | |
576 erase(const_cast_it(eq_range.first), const_cast_it(eq_range.second)); | |
577 return res; | |
578 } | |
579 | |
580 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
581 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::erase( | |
582 const_iterator first, | |
583 const_iterator last) -> iterator { | |
584 // We have to cast away const because of crbug.com/677044. | |
585 return impl_.body_.erase(const_cast_it(first), const_cast_it(last)); | |
586 } | |
587 | |
588 // ---------------------------------------------------------------------------- | |
589 // Comparators. | |
590 | |
591 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
592 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::key_comp() const | |
593 -> key_compare { | |
594 return impl_.get_key_comp(); | |
595 } | |
596 | |
597 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
598 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::value_comp() const | |
599 -> value_compare { | |
600 return impl_.get_value_comp(); | |
601 } | |
602 | |
603 // ---------------------------------------------------------------------------- | |
604 // Search operations. | |
605 | |
606 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
607 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::count( | |
608 const key_type& key) const -> size_type { | |
609 auto eq_range = equal_range(key); | |
610 return std::distance(eq_range.first, eq_range.second); | |
611 } | |
612 | |
613 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
614 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::find( | |
615 const key_type& key) -> iterator { | |
616 return const_cast_it(as_const().find(key)); | |
617 } | |
618 | |
619 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
620 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::find( | |
621 const key_type& key) const -> const_iterator { | |
622 auto eq_range = equal_range(key); | |
623 return (eq_range.first == eq_range.second) ? end() : eq_range.first; | |
624 } | |
625 | |
626 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
627 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::equal_range( | |
628 const key_type& key) -> std::pair<iterator, iterator> { | |
629 auto res = as_const().equal_range(key); | |
630 return {const_cast_it(res.first), const_cast_it(res.second)}; | |
631 } | |
632 | |
633 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
634 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::equal_range( | |
635 const key_type& key) const -> std::pair<const_iterator, const_iterator> { | |
636 auto lower = lower_bound(key); | |
637 | |
638 GetKeyFromValue extractor; | |
639 if (lower == end() || impl_.get_key_comp()(key, extractor(*lower))) | |
640 return {lower, lower}; | |
641 | |
642 return {lower, std::next(lower)}; | |
643 } | |
644 | |
645 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
646 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::lower_bound( | |
647 const key_type& key) -> iterator { | |
648 return const_cast_it(as_const().lower_bound(key)); | |
649 } | |
650 | |
651 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
652 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::lower_bound( | |
653 const key_type& key) const -> const_iterator { | |
654 KeyValueCompare key_value(impl_.get_key_comp()); | |
655 return std::lower_bound(begin(), end(), key, key_value); | |
656 } | |
657 | |
658 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
659 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::upper_bound( | |
660 const key_type& key) -> iterator { | |
661 return const_cast_it(as_const().upper_bound(key)); | |
662 } | |
663 | |
664 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
665 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::upper_bound( | |
666 const key_type& key) const -> const_iterator { | |
667 KeyValueCompare key_value(impl_.get_key_comp()); | |
668 return std::upper_bound(begin(), end(), key, key_value); | |
669 } | |
670 | |
671 // ---------------------------------------------------------------------------- | |
672 // General operations. | |
673 | |
674 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
675 void flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::swap( | |
676 flat_tree& other) { | |
677 std::swap(impl_, other.impl_); | |
678 } | |
679 | |
680 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
681 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::unsafe_insert_new_at( | |
682 const_iterator position, | |
683 const value_type& val) -> iterator { | |
684 return impl_.body_.insert(const_cast_it(position), val); | |
685 } | |
686 | |
687 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
688 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::unsafe_insert_new_at( | |
689 const_iterator position, | |
690 value_type&& val) -> iterator { | |
691 // We have to cast away const because of crbug.com/677044. | |
692 return impl_.body_.insert(const_cast_it(position), std::move(val)); | |
693 } | |
694 | |
695 // For containers like sets, the key is the same as the value. This implements | |
696 // the GetKeyFromValue template parameter to flat_tree for this case. | |
697 template <class Key> | |
698 struct GetKeyFromValueIdentity { | |
699 const Key& operator()(const Key& k) const { return k; } | |
700 }; | |
701 | |
702 } // namespace internal | |
703 } // namespace base | |
704 | |
705 #endif // BASE_CONTAINERS_FLAT_TREE_H_ | |
OLD | NEW |