OLD | NEW |
1 // Copyright 2017 The Chromium Authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #ifndef BASE_CONTAINERS_FLAT_SET_H_ | 5 #ifndef BASE_CONTAINERS_FLAT_SET_H_ |
6 #define BASE_CONTAINERS_FLAT_SET_H_ | 6 #define BASE_CONTAINERS_FLAT_SET_H_ |
7 | 7 |
8 #include <algorithm> | 8 #include "base/containers/flat_tree.h" |
9 #include <functional> | |
10 #include <utility> | |
11 #include <vector> | |
12 | 9 |
13 namespace base { | 10 namespace base { |
14 | 11 |
15 // Overview: | 12 // Overview: |
16 // This file implements flat_set container. It is an alternative to standard | 13 // This file implements flat_set container. It is an alternative to standard |
17 // sorted containers that stores it's elements in contiguous memory (current | 14 // sorted containers that stores it's elements in contiguous memory (current |
18 // version uses sorted std::vector). | 15 // version uses sorted std::vector). |
19 // Discussion that preceded introduction of this container can be found here: | 16 // Discussion that preceded introduction of this container can be found here: |
20 // https://groups.google.com/a/chromium.org/forum/#!searchin/chromium-dev/vector
$20based/chromium-dev/4uQMma9vj9w/HaQ-WvMOAwAJ | 17 // https://groups.google.com/a/chromium.org/forum/#!searchin/chromium-dev/vector
$20based/chromium-dev/4uQMma9vj9w/HaQ-WvMOAwAJ |
21 // | 18 // |
(...skipping 56 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
78 // but it seems to be a quadratic algorithm. For now we do not implement this | 75 // but it seems to be a quadratic algorithm. For now we do not implement this |
79 // method. | 76 // method. |
80 // TODO(dyaroshev): research an algorithm for range insertion crbug.com/682249. | 77 // TODO(dyaroshev): research an algorithm for range insertion crbug.com/682249. |
81 | 78 |
82 template <class Key, class Compare = std::less<Key>> | 79 template <class Key, class Compare = std::less<Key>> |
83 // Meets the requirements of Container, AssociativeContainer, | 80 // Meets the requirements of Container, AssociativeContainer, |
84 // ReversibleContainer. | 81 // ReversibleContainer. |
85 // Requires: Key is Movable, Compare is a StrictWeakOrdering on Key. | 82 // Requires: Key is Movable, Compare is a StrictWeakOrdering on Key. |
86 class flat_set { | 83 class flat_set { |
87 private: | 84 private: |
88 using underlying_type = std::vector<Key>; | 85 // In a set, the key is the same as the value. |
| 86 struct NullKeyExtractor { |
| 87 const Key& operator()(const Key& k) const { return k; } |
| 88 }; |
| 89 using tree = |
| 90 typename ::base::internal::flat_tree<Key, Key, NullKeyExtractor, Compare>; |
89 | 91 |
90 public: | 92 public: |
91 // -------------------------------------------------------------------------- | 93 // -------------------------------------------------------------------------- |
92 // Types. | 94 // Types. |
93 // | 95 // |
94 using key_type = Key; | 96 using key_type = typename tree::key_type; |
95 using key_compare = Compare; | 97 using key_compare = typename tree::key_compare; |
96 using value_type = Key; | 98 using value_type = typename tree::value_type; |
97 using value_compare = Compare; | 99 // Use the original Compare class rather than the one tree makes (which will |
| 100 // wrap the Compare class with a NoOp for a set. It's nicer for callers to |
| 101 // see the same type they passed in, and the wrapped class derives from |
| 102 // Compare so it can be converted. |
| 103 using value_compare = typename Compare; |
98 | 104 |
99 using pointer = typename underlying_type::pointer; | 105 using pointer = typename tree::pointer; |
100 using const_pointer = typename underlying_type::const_pointer; | 106 using const_pointer = typename tree::const_pointer; |
101 using reference = typename underlying_type::reference; | 107 using reference = typename tree::reference; |
102 using const_reference = typename underlying_type::const_reference; | 108 using const_reference = typename tree::const_reference; |
103 using size_type = typename underlying_type::size_type; | 109 using size_type = typename tree::size_type; |
104 using difference_type = typename underlying_type::difference_type; | 110 using difference_type = typename tree::difference_type; |
105 using iterator = typename underlying_type::iterator; | 111 using iterator = typename tree::iterator; |
106 using const_iterator = typename underlying_type::const_iterator; | 112 using const_iterator = typename tree::const_iterator; |
107 using reverse_iterator = typename underlying_type::reverse_iterator; | 113 using reverse_iterator = typename tree::reverse_iterator; |
108 using const_reverse_iterator = | 114 using const_reverse_iterator = typename tree::const_reverse_iterator; |
109 typename underlying_type::const_reverse_iterator; | |
110 | 115 |
111 // -------------------------------------------------------------------------- | 116 // -------------------------------------------------------------------------- |
112 // Lifetime. | 117 // Lifetime. |
113 // | 118 // |
114 // Constructors that take range guarantee O(N * log^2(N)) + O(N) complexity | 119 // Constructors that take range guarantee O(N * log^2(N)) + O(N) complexity |
115 // and take O(N * log(N)) + O(N) if extra memory is available (N is a range | 120 // and take O(N * log(N)) + O(N) if extra memory is available (N is a range |
116 // length). | 121 // length). |
117 // | 122 // |
118 // Assume that move constructors invalidate iterators and references. | 123 // Assume that move constructors invalidate iterators and references. |
119 | 124 |
(...skipping 139 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
259 // types, rather than using element-wise key_comp() as e.g. lower_bound() | 264 // types, rather than using element-wise key_comp() as e.g. lower_bound() |
260 // does. Implementation note: currently we use operator==() and operator<() on | 265 // does. Implementation note: currently we use operator==() and operator<() on |
261 // std::vector, because they have the same contract we need, so we use them | 266 // std::vector, because they have the same contract we need, so we use them |
262 // directly for brevity and in case it is more optimal than calling equal() | 267 // directly for brevity and in case it is more optimal than calling equal() |
263 // and lexicograhpical_compare(). If the underlying container type is changed, | 268 // and lexicograhpical_compare(). If the underlying container type is changed, |
264 // this code may need to be modified. | 269 // this code may need to be modified. |
265 | 270 |
266 void swap(flat_set& other); | 271 void swap(flat_set& other); |
267 | 272 |
268 friend bool operator==(const flat_set& lhs, const flat_set& rhs) { | 273 friend bool operator==(const flat_set& lhs, const flat_set& rhs) { |
269 return lhs.impl_.body_ == rhs.impl_.body_; | 274 return lhs.tree_ == rhs.tree_; |
270 } | 275 } |
271 | 276 |
272 friend bool operator!=(const flat_set& lhs, const flat_set& rhs) { | 277 friend bool operator!=(const flat_set& lhs, const flat_set& rhs) { |
273 return !(lhs == rhs); | 278 return !(lhs == rhs); |
274 } | 279 } |
275 | 280 |
276 friend bool operator<(const flat_set& lhs, const flat_set& rhs) { | 281 friend bool operator<(const flat_set& lhs, const flat_set& rhs) { |
277 return lhs.impl_.body_ < rhs.impl_.body_; | 282 return lhs.tree_ < rhs.tree_; |
278 } | 283 } |
279 | 284 |
280 friend bool operator>(const flat_set& lhs, const flat_set& rhs) { | 285 friend bool operator>(const flat_set& lhs, const flat_set& rhs) { |
281 return rhs < lhs; | 286 return rhs < lhs; |
282 } | 287 } |
283 | 288 |
284 friend bool operator>=(const flat_set& lhs, const flat_set& rhs) { | 289 friend bool operator>=(const flat_set& lhs, const flat_set& rhs) { |
285 return !(lhs < rhs); | 290 return !(lhs < rhs); |
286 } | 291 } |
287 | 292 |
288 friend bool operator<=(const flat_set& lhs, const flat_set& rhs) { | 293 friend bool operator<=(const flat_set& lhs, const flat_set& rhs) { |
289 return !(lhs > rhs); | 294 return !(lhs > rhs); |
290 } | 295 } |
291 | 296 |
292 friend void swap(flat_set& lhs, flat_set& rhs) { lhs.swap(rhs); } | 297 friend void swap(flat_set& lhs, flat_set& rhs) { lhs.swap(rhs); } |
293 | 298 |
294 private: | 299 private: |
295 const flat_set& as_const() { return *this; } | 300 tree tree_; |
296 | |
297 iterator const_cast_it(const_iterator c_it) { | |
298 auto distance = std::distance(cbegin(), c_it); | |
299 return std::next(begin(), distance); | |
300 } | |
301 | |
302 void sort_and_unique() { | |
303 // std::set sorts elements preserving stability because it doesn't have any | |
304 // performance wins in not doing that. We do, so we use an unstable sort. | |
305 std::sort(begin(), end(), value_comp()); | |
306 erase(std::unique(begin(), end(), | |
307 [this](const value_type& lhs, const value_type& rhs) { | |
308 // lhs is already <= rhs due to sort, therefore | |
309 // !(lhs < rhs) <=> lhs == rhs. | |
310 return !value_comp()(lhs, rhs); | |
311 }), | |
312 end()); | |
313 } | |
314 | |
315 // To support comparators that may not be possible to default-construct, we | |
316 // have to store an instance of Compare. Using this to store all internal | |
317 // state of flat_set and using private inheritance to store compare lets us | |
318 // take advantage of an empty base class optimization to avoid extra space in | |
319 // the common case when Compare has no state. | |
320 struct Impl : private Compare { | |
321 Impl() = default; | |
322 | |
323 template <class Cmp, class... Body> | |
324 explicit Impl(Cmp&& compare_arg, Body&&... underlying_type_args) | |
325 : Compare(std::forward<Cmp>(compare_arg)), | |
326 body_(std::forward<Body>(underlying_type_args)...) {} | |
327 | |
328 Compare compare() const { return *this; } | |
329 | |
330 underlying_type body_; | |
331 } impl_; | |
332 }; | 301 }; |
333 | 302 |
334 // ---------------------------------------------------------------------------- | 303 // ---------------------------------------------------------------------------- |
335 // Lifetime. | 304 // Lifetime. |
336 | 305 |
337 template <class Key, class Compare> | 306 template <class Key, class Compare> |
338 flat_set<Key, Compare>::flat_set() = default; | 307 flat_set<Key, Compare>::flat_set() = default; |
339 | 308 |
340 template <class Key, class Compare> | 309 template <class Key, class Compare> |
341 flat_set<Key, Compare>::flat_set(const Compare& comp) : impl_(comp) {} | 310 flat_set<Key, Compare>::flat_set(const Compare& comp) : tree_(comp) {} |
342 | 311 |
343 template <class Key, class Compare> | 312 template <class Key, class Compare> |
344 template <class InputIterator> | 313 template <class InputIterator> |
345 flat_set<Key, Compare>::flat_set(InputIterator first, | 314 flat_set<Key, Compare>::flat_set(InputIterator first, |
346 InputIterator last, | 315 InputIterator last, |
347 const Compare& comp) | 316 const Compare& comp) |
348 : impl_(comp, first, last) { | 317 : tree_(first, last, comp) {} |
349 sort_and_unique(); | |
350 } | |
351 | 318 |
352 template <class Key, class Compare> | 319 template <class Key, class Compare> |
353 flat_set<Key, Compare>::flat_set(const flat_set&) = default; | 320 flat_set<Key, Compare>::flat_set(const flat_set&) = default; |
354 | 321 |
355 template <class Key, class Compare> | 322 template <class Key, class Compare> |
356 flat_set<Key, Compare>::flat_set(flat_set&&) = default; | 323 flat_set<Key, Compare>::flat_set(flat_set&&) = default; |
357 | 324 |
358 template <class Key, class Compare> | 325 template <class Key, class Compare> |
359 flat_set<Key, Compare>::flat_set(std::initializer_list<value_type> ilist, | 326 flat_set<Key, Compare>::flat_set(std::initializer_list<value_type> ilist, |
360 const Compare& comp) | 327 const Compare& comp) |
361 : flat_set(std::begin(ilist), std::end(ilist), comp) {} | 328 : flat_set(std::begin(ilist), std::end(ilist), comp) {} |
362 | 329 |
363 template <class Key, class Compare> | 330 template <class Key, class Compare> |
364 flat_set<Key, Compare>::~flat_set() = default; | 331 flat_set<Key, Compare>::~flat_set() = default; |
365 | 332 |
366 // ---------------------------------------------------------------------------- | 333 // ---------------------------------------------------------------------------- |
367 // Assignments. | 334 // Assignments. |
368 | 335 |
369 template <class Key, class Compare> | 336 template <class Key, class Compare> |
370 auto flat_set<Key, Compare>::operator=(const flat_set&) -> flat_set& = default; | 337 auto flat_set<Key, Compare>::operator=(const flat_set&) -> flat_set& = default; |
371 | 338 |
372 template <class Key, class Compare> | 339 template <class Key, class Compare> |
373 auto flat_set<Key, Compare>::operator=(flat_set &&) -> flat_set& = default; | 340 auto flat_set<Key, Compare>::operator=(flat_set &&) -> flat_set& = default; |
374 | 341 |
375 template <class Key, class Compare> | 342 template <class Key, class Compare> |
376 auto flat_set<Key, Compare>::operator=(std::initializer_list<value_type> ilist) | 343 auto flat_set<Key, Compare>::operator=(std::initializer_list<value_type> ilist) |
377 -> flat_set& { | 344 -> flat_set& { |
378 impl_.body_ = ilist; | 345 tree_ = ilist; |
379 sort_and_unique(); | |
380 return *this; | 346 return *this; |
381 } | 347 } |
382 | 348 |
383 // ---------------------------------------------------------------------------- | 349 // ---------------------------------------------------------------------------- |
384 // Memory management. | 350 // Memory management. |
385 | 351 |
386 template <class Key, class Compare> | 352 template <class Key, class Compare> |
387 void flat_set<Key, Compare>::reserve(size_type new_capacity) { | 353 void flat_set<Key, Compare>::reserve(size_type new_capacity) { |
388 impl_.body_.reserve(new_capacity); | 354 tree_.reserve(new_capacity); |
389 } | 355 } |
390 | 356 |
391 template <class Key, class Compare> | 357 template <class Key, class Compare> |
392 auto flat_set<Key, Compare>::capacity() const -> size_type { | 358 auto flat_set<Key, Compare>::capacity() const -> size_type { |
393 return impl_.body_.capacity(); | 359 return tree_.capacity(); |
394 } | 360 } |
395 | 361 |
396 template <class Key, class Compare> | 362 template <class Key, class Compare> |
397 void flat_set<Key, Compare>::shrink_to_fit() { | 363 void flat_set<Key, Compare>::shrink_to_fit() { |
398 impl_.body_.shrink_to_fit(); | 364 tree_.shrink_to_fit(); |
399 } | 365 } |
400 | 366 |
401 // ---------------------------------------------------------------------------- | 367 // ---------------------------------------------------------------------------- |
402 // Size management. | 368 // Size management. |
403 | 369 |
404 template <class Key, class Compare> | 370 template <class Key, class Compare> |
405 void flat_set<Key, Compare>::clear() { | 371 void flat_set<Key, Compare>::clear() { |
406 impl_.body_.clear(); | 372 tree_.clear(); |
407 } | 373 } |
408 | 374 |
409 template <class Key, class Compare> | 375 template <class Key, class Compare> |
410 auto flat_set<Key, Compare>::size() const -> size_type { | 376 auto flat_set<Key, Compare>::size() const -> size_type { |
411 return impl_.body_.size(); | 377 return tree_.size(); |
412 } | 378 } |
413 | 379 |
414 template <class Key, class Compare> | 380 template <class Key, class Compare> |
415 auto flat_set<Key, Compare>::max_size() const -> size_type { | 381 auto flat_set<Key, Compare>::max_size() const -> size_type { |
416 return impl_.body_.max_size(); | 382 return tree_.max_size(); |
417 } | 383 } |
418 | 384 |
419 template <class Key, class Compare> | 385 template <class Key, class Compare> |
420 bool flat_set<Key, Compare>::empty() const { | 386 bool flat_set<Key, Compare>::empty() const { |
421 return impl_.body_.empty(); | 387 return tree_.empty(); |
422 } | 388 } |
423 | 389 |
424 // ---------------------------------------------------------------------------- | 390 // ---------------------------------------------------------------------------- |
425 // Iterators. | 391 // Iterators. |
426 | 392 |
427 template <class Key, class Compare> | 393 template <class Key, class Compare> |
428 auto flat_set<Key, Compare>::begin() -> iterator { | 394 auto flat_set<Key, Compare>::begin() -> iterator { |
429 return impl_.body_.begin(); | 395 return tree_.begin(); |
430 } | 396 } |
431 | 397 |
432 template <class Key, class Compare> | 398 template <class Key, class Compare> |
433 auto flat_set<Key, Compare>::begin() const -> const_iterator { | 399 auto flat_set<Key, Compare>::begin() const -> const_iterator { |
434 return impl_.body_.begin(); | 400 return tree_.begin(); |
435 } | 401 } |
436 | 402 |
437 template <class Key, class Compare> | 403 template <class Key, class Compare> |
438 auto flat_set<Key, Compare>::cbegin() const -> const_iterator { | 404 auto flat_set<Key, Compare>::cbegin() const -> const_iterator { |
439 return impl_.body_.cbegin(); | 405 return tree_.cbegin(); |
440 } | 406 } |
441 | 407 |
442 template <class Key, class Compare> | 408 template <class Key, class Compare> |
443 auto flat_set<Key, Compare>::end() -> iterator { | 409 auto flat_set<Key, Compare>::end() -> iterator { |
444 return impl_.body_.end(); | 410 return tree_.end(); |
445 } | 411 } |
446 | 412 |
447 template <class Key, class Compare> | 413 template <class Key, class Compare> |
448 auto flat_set<Key, Compare>::end() const -> const_iterator { | 414 auto flat_set<Key, Compare>::end() const -> const_iterator { |
449 return impl_.body_.end(); | 415 return tree_.end(); |
450 } | 416 } |
451 | 417 |
452 template <class Key, class Compare> | 418 template <class Key, class Compare> |
453 auto flat_set<Key, Compare>::cend() const -> const_iterator { | 419 auto flat_set<Key, Compare>::cend() const -> const_iterator { |
454 return impl_.body_.cend(); | 420 return tree_.cend(); |
455 } | 421 } |
456 | 422 |
457 template <class Key, class Compare> | 423 template <class Key, class Compare> |
458 auto flat_set<Key, Compare>::rbegin() -> reverse_iterator { | 424 auto flat_set<Key, Compare>::rbegin() -> reverse_iterator { |
459 return impl_.body_.rbegin(); | 425 return tree_.rbegin(); |
460 } | 426 } |
461 | 427 |
462 template <class Key, class Compare> | 428 template <class Key, class Compare> |
463 auto flat_set<Key, Compare>::rbegin() const -> const_reverse_iterator { | 429 auto flat_set<Key, Compare>::rbegin() const -> const_reverse_iterator { |
464 return impl_.body_.rbegin(); | 430 return tree_.rbegin(); |
465 } | 431 } |
466 | 432 |
467 template <class Key, class Compare> | 433 template <class Key, class Compare> |
468 auto flat_set<Key, Compare>::crbegin() const -> const_reverse_iterator { | 434 auto flat_set<Key, Compare>::crbegin() const -> const_reverse_iterator { |
469 return impl_.body_.crbegin(); | 435 return tree_.crbegin(); |
470 } | 436 } |
471 | 437 |
472 template <class Key, class Compare> | 438 template <class Key, class Compare> |
473 auto flat_set<Key, Compare>::rend() -> reverse_iterator { | 439 auto flat_set<Key, Compare>::rend() -> reverse_iterator { |
474 return impl_.body_.rend(); | 440 return tree_.rend(); |
475 } | 441 } |
476 | 442 |
477 template <class Key, class Compare> | 443 template <class Key, class Compare> |
478 auto flat_set<Key, Compare>::rend() const -> const_reverse_iterator { | 444 auto flat_set<Key, Compare>::rend() const -> const_reverse_iterator { |
479 return impl_.body_.rend(); | 445 return tree_.rend(); |
480 } | 446 } |
481 | 447 |
482 template <class Key, class Compare> | 448 template <class Key, class Compare> |
483 auto flat_set<Key, Compare>::crend() const -> const_reverse_iterator { | 449 auto flat_set<Key, Compare>::crend() const -> const_reverse_iterator { |
484 return impl_.body_.crend(); | 450 return tree_.crend(); |
485 } | 451 } |
486 | 452 |
487 // ---------------------------------------------------------------------------- | 453 // ---------------------------------------------------------------------------- |
488 // Insert operations. | 454 // Insert operations. |
489 // | 455 // |
490 // Currently we use position_hint the same way as eastl or boost: | 456 // 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 | 457 // https://github.com/electronicarts/EASTL/blob/master/include/EASTL/vector_set.
h#L493 |
492 // | 458 // |
493 // We duplicate code between copy and move version so that we can avoid | 459 // We duplicate code between copy and move version so that we can avoid |
494 // creating a temporary value. | 460 // creating a temporary value. |
495 | 461 |
496 template <class Key, class Compare> | 462 template <class Key, class Compare> |
497 auto flat_set<Key, Compare>::insert(const value_type& val) | 463 auto flat_set<Key, Compare>::insert(const value_type& val) |
498 -> std::pair<iterator, bool> { | 464 -> std::pair<iterator, bool> { |
499 auto position = lower_bound(val); | 465 return tree_.insert(val); |
500 | |
501 if (position == end() || value_comp()(val, *position)) | |
502 return {impl_.body_.insert(position, val), true}; | |
503 | |
504 return {position, false}; | |
505 } | 466 } |
506 | 467 |
507 template <class Key, class Compare> | 468 template <class Key, class Compare> |
508 auto flat_set<Key, Compare>::insert(value_type&& val) | 469 auto flat_set<Key, Compare>::insert(value_type&& val) |
509 -> std::pair<iterator, bool> { | 470 -> std::pair<iterator, bool> { |
510 auto position = lower_bound(val); | 471 return tree_.insert(std::move(val)); |
511 | |
512 if (position == end() || value_comp()(val, *position)) | |
513 return {impl_.body_.insert(position, std::move(val)), true}; | |
514 | |
515 return {position, false}; | |
516 } | 472 } |
517 | 473 |
518 template <class Key, class Compare> | 474 template <class Key, class Compare> |
519 auto flat_set<Key, Compare>::insert(const_iterator position_hint, | 475 auto flat_set<Key, Compare>::insert(const_iterator position_hint, |
520 const value_type& val) -> iterator { | 476 const value_type& val) -> iterator { |
521 if (position_hint == end() || value_comp()(val, *position_hint)) { | 477 return tree_.insert(position_hint, val); |
522 if (position_hint == begin() || value_comp()(*(position_hint - 1), val)) | |
523 // We have to cast away const because of crbug.com/677044. | |
524 return impl_.body_.insert(const_cast_it(position_hint), val); | |
525 } | |
526 return insert(val).first; | |
527 } | 478 } |
528 | 479 |
529 template <class Key, class Compare> | 480 template <class Key, class Compare> |
530 auto flat_set<Key, Compare>::insert(const_iterator position_hint, | 481 auto flat_set<Key, Compare>::insert(const_iterator position_hint, |
531 value_type&& val) -> iterator { | 482 value_type&& val) -> iterator { |
532 if (position_hint == end() || value_comp()(val, *position_hint)) { | 483 return tree_.insert(position_hint, std::move(val)); |
533 if (position_hint == begin() || value_comp()(*(position_hint - 1), val)) | |
534 // We have to cast away const because of crbug.com/677044. | |
535 return impl_.body_.insert(const_cast_it(position_hint), std::move(val)); | |
536 } | |
537 return insert(std::move(val)).first; | |
538 } | 484 } |
539 | 485 |
540 template <class Key, class Compare> | 486 template <class Key, class Compare> |
541 template <class... Args> | 487 template <class... Args> |
542 auto flat_set<Key, Compare>::emplace(Args&&... args) | 488 auto flat_set<Key, Compare>::emplace(Args&&... args) |
543 -> std::pair<iterator, bool> { | 489 -> std::pair<iterator, bool> { |
544 return insert(value_type(std::forward<Args>(args)...)); | 490 return tree_.emplace(std::forward<Args>(args)...); |
545 } | 491 } |
546 | 492 |
547 template <class Key, class Compare> | 493 template <class Key, class Compare> |
548 template <class... Args> | 494 template <class... Args> |
549 auto flat_set<Key, Compare>::emplace_hint(const_iterator position_hint, | 495 auto flat_set<Key, Compare>::emplace_hint(const_iterator position_hint, |
550 Args&&... args) -> iterator { | 496 Args&&... args) -> iterator { |
551 return insert(position_hint, value_type(std::forward<Args>(args)...)); | 497 return tree_.emplace_hint(position_hint, std::forward<Args>(args)...); |
552 } | 498 } |
553 | 499 |
554 // ---------------------------------------------------------------------------- | 500 // ---------------------------------------------------------------------------- |
555 // Erase operations. | 501 // Erase operations. |
556 | 502 |
557 template <class Key, class Compare> | 503 template <class Key, class Compare> |
558 auto flat_set<Key, Compare>::erase(const_iterator position) -> iterator { | 504 auto flat_set<Key, Compare>::erase(const_iterator position) -> iterator { |
559 // We have to cast away const because of crbug.com/677044. | 505 return tree_.erase(position); |
560 return impl_.body_.erase(const_cast_it(position)); | |
561 } | 506 } |
562 | 507 |
563 template <class Key, class Compare> | 508 template <class Key, class Compare> |
564 auto flat_set<Key, Compare>::erase(const key_type& val) -> size_type { | 509 auto flat_set<Key, Compare>::erase(const key_type& val) -> size_type { |
565 auto eq_range = equal_range(val); | 510 return tree_.erase(val); |
566 auto res = std::distance(eq_range.first, eq_range.second); | |
567 // We have to cast away const because of crbug.com/677044. | |
568 erase(const_cast_it(eq_range.first), const_cast_it(eq_range.second)); | |
569 return res; | |
570 } | 511 } |
571 | 512 |
572 template <class Key, class Compare> | 513 template <class Key, class Compare> |
573 auto flat_set<Key, Compare>::erase(const_iterator first, const_iterator last) | 514 auto flat_set<Key, Compare>::erase(const_iterator first, const_iterator last) |
574 -> iterator { | 515 -> iterator { |
575 // We have to cast away const because of crbug.com/677044. | 516 return tree_.erase(first, last); |
576 return impl_.body_.erase(const_cast_it(first), const_cast_it(last)); | |
577 } | 517 } |
578 | 518 |
579 // ---------------------------------------------------------------------------- | 519 // ---------------------------------------------------------------------------- |
580 // Comparators. | 520 // Comparators. |
581 | 521 |
582 template <class Key, class Compare> | 522 template <class Key, class Compare> |
583 auto flat_set<Key, Compare>::key_comp() const -> key_compare { | 523 auto flat_set<Key, Compare>::key_comp() const -> key_compare { |
584 return impl_.compare(); | 524 return tree_.key_comp(); |
585 } | 525 } |
586 | 526 |
587 template <class Key, class Compare> | 527 template <class Key, class Compare> |
588 auto flat_set<Key, Compare>::value_comp() const -> value_compare { | 528 auto flat_set<Key, Compare>::value_comp() const -> value_compare { |
589 return impl_.compare(); | 529 return tree_.value_comp(); |
590 } | 530 } |
591 | 531 |
592 // ---------------------------------------------------------------------------- | 532 // ---------------------------------------------------------------------------- |
593 // Search operations. | 533 // Search operations. |
594 | 534 |
595 template <class Key, class Compare> | 535 template <class Key, class Compare> |
596 auto flat_set<Key, Compare>::count(const key_type& key) const -> size_type { | 536 auto flat_set<Key, Compare>::count(const key_type& key) const -> size_type { |
597 auto eq_range = equal_range(key); | 537 return tree_.count(key); |
598 return std::distance(eq_range.first, eq_range.second); | |
599 } | 538 } |
600 | 539 |
601 template <class Key, class Compare> | 540 template <class Key, class Compare> |
602 auto flat_set<Key, Compare>::find(const key_type& key) -> iterator { | 541 auto flat_set<Key, Compare>::find(const key_type& key) -> iterator { |
603 return const_cast_it(as_const().find(key)); | 542 return tree_.find(key); |
604 } | 543 } |
605 | 544 |
606 template <class Key, class Compare> | 545 template <class Key, class Compare> |
607 auto flat_set<Key, Compare>::find(const key_type& key) const -> const_iterator { | 546 auto flat_set<Key, Compare>::find(const key_type& key) const -> const_iterator { |
608 auto eq_range = equal_range(key); | 547 return tree_.find(key); |
609 return (eq_range.first == eq_range.second) ? end() : eq_range.first; | |
610 } | 548 } |
611 | 549 |
612 template <class Key, class Compare> | 550 template <class Key, class Compare> |
613 auto flat_set<Key, Compare>::equal_range(const key_type& key) | 551 auto flat_set<Key, Compare>::equal_range(const key_type& key) |
614 -> std::pair<iterator, iterator> { | 552 -> std::pair<iterator, iterator> { |
615 auto res = as_const().equal_range(key); | 553 return tree_.equal_range(key); |
616 return {const_cast_it(res.first), const_cast_it(res.second)}; | |
617 } | 554 } |
618 | 555 |
619 template <class Key, class Compare> | 556 template <class Key, class Compare> |
620 auto flat_set<Key, Compare>::equal_range(const key_type& key) const | 557 auto flat_set<Key, Compare>::equal_range(const key_type& key) const |
621 -> std::pair<const_iterator, const_iterator> { | 558 -> std::pair<const_iterator, const_iterator> { |
622 auto lower = lower_bound(key); | 559 return tree_.equal_range(key); |
623 | |
624 if (lower == end() || key_comp()(key, *lower)) | |
625 return {lower, lower}; | |
626 | |
627 return {lower, std::next(lower)}; | |
628 } | 560 } |
629 | 561 |
630 template <class Key, class Compare> | 562 template <class Key, class Compare> |
631 auto flat_set<Key, Compare>::lower_bound(const key_type& key) -> iterator { | 563 auto flat_set<Key, Compare>::lower_bound(const key_type& key) -> iterator { |
632 return const_cast_it(as_const().lower_bound(key)); | 564 return tree_.lower_bound(key); |
633 } | 565 } |
634 | 566 |
635 template <class Key, class Compare> | 567 template <class Key, class Compare> |
636 auto flat_set<Key, Compare>::lower_bound(const key_type& key) const | 568 auto flat_set<Key, Compare>::lower_bound(const key_type& key) const |
637 -> const_iterator { | 569 -> const_iterator { |
638 return std::lower_bound(begin(), end(), key, key_comp()); | 570 return tree_.lower_bound(key); |
639 } | 571 } |
640 | 572 |
641 template <class Key, class Compare> | 573 template <class Key, class Compare> |
642 auto flat_set<Key, Compare>::upper_bound(const key_type& key) -> iterator { | 574 auto flat_set<Key, Compare>::upper_bound(const key_type& key) -> iterator { |
643 return const_cast_it(as_const().upper_bound(key)); | 575 return tree_.upper_bound(key); |
644 } | 576 } |
645 | 577 |
646 template <class Key, class Compare> | 578 template <class Key, class Compare> |
647 auto flat_set<Key, Compare>::upper_bound(const key_type& key) const | 579 auto flat_set<Key, Compare>::upper_bound(const key_type& key) const |
648 -> const_iterator { | 580 -> const_iterator { |
649 return std::upper_bound(begin(), end(), key, key_comp()); | 581 return tree_.upper_bound(key); |
650 } | 582 } |
651 | 583 |
652 // ---------------------------------------------------------------------------- | 584 // ---------------------------------------------------------------------------- |
653 // General operations. | 585 // General operations. |
654 | 586 |
655 template <class Key, class Compare> | 587 template <class Key, class Compare> |
656 void flat_set<Key, Compare>::swap(flat_set& other) { | 588 void flat_set<Key, Compare>::swap(flat_set& other) { |
657 std::swap(impl_, other.impl_); | 589 std::swap(tree_, other.tree_); |
658 } | 590 } |
659 | 591 |
660 } // namespace base | 592 } // namespace base |
661 | 593 |
662 #endif // BASE_CONTAINERS_FLAT_SET_H_ | 594 #endif // BASE_CONTAINERS_FLAT_SET_H_ |
OLD | NEW |