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