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_TREE_H_ | 5 #ifndef BASE_CONTAINERS_FLAT_TREE_H_ |
6 #define BASE_CONTAINERS_FLAT_TREE_H_ | 6 #define BASE_CONTAINERS_FLAT_TREE_H_ |
7 | 7 |
8 #include <algorithm> | 8 #include <algorithm> |
9 #include <iterator> | |
9 #include <vector> | 10 #include <vector> |
10 | 11 |
11 namespace base { | 12 namespace base { |
12 | 13 |
13 enum FlatContainerDupes { | 14 enum FlatContainerDupes { |
14 KEEP_FIRST_OF_DUPES, | 15 KEEP_FIRST_OF_DUPES, |
15 KEEP_LAST_OF_DUPES, | 16 KEEP_LAST_OF_DUPES, |
16 }; | 17 }; |
17 | 18 |
18 namespace internal { | 19 namespace internal { |
(...skipping 161 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
180 const_reverse_iterator crbegin() const; | 181 const_reverse_iterator crbegin() const; |
181 | 182 |
182 reverse_iterator rend(); | 183 reverse_iterator rend(); |
183 const_reverse_iterator rend() const; | 184 const_reverse_iterator rend() const; |
184 const_reverse_iterator crend() const; | 185 const_reverse_iterator crend() const; |
185 | 186 |
186 // -------------------------------------------------------------------------- | 187 // -------------------------------------------------------------------------- |
187 // Insert operations. | 188 // Insert operations. |
188 // | 189 // |
189 // Assume that every operation invalidates iterators and references. | 190 // Assume that every operation invalidates iterators and references. |
190 // Insertion of one element can take O(size). See the Notes section in the | 191 // Insertion of one element can take O(size). Capacity of flat_tree grows in |
191 // class comments on why we do not currently implement range insertion. | 192 // an implementation-defined manner. |
192 // Capacity of flat_tree grows in an implementation-defined manner. | |
193 // | 193 // |
194 // NOTE: Prefer to build a new flat_tree from a std::vector (or similar) | 194 // NOTE: Prefer to build a new flat_tree from a std::vector (or similar) |
195 // instead of calling insert() repeatedly. | 195 // instead of calling insert() repeatedly. |
196 | 196 |
197 std::pair<iterator, bool> insert(const value_type& val); | 197 std::pair<iterator, bool> insert(const value_type& val); |
198 std::pair<iterator, bool> insert(value_type&& val); | 198 std::pair<iterator, bool> insert(value_type&& val); |
199 | 199 |
200 iterator insert(const_iterator position_hint, const value_type& x); | 200 iterator insert(const_iterator position_hint, const value_type& x); |
201 iterator insert(const_iterator position_hint, value_type&& x); | 201 iterator insert(const_iterator position_hint, value_type&& x); |
202 | 202 |
203 template <class InputIterator> | |
204 void insert(InputIterator first, InputIterator last); | |
205 | |
203 template <class... Args> | 206 template <class... Args> |
204 std::pair<iterator, bool> emplace(Args&&... args); | 207 std::pair<iterator, bool> emplace(Args&&... args); |
205 | 208 |
206 template <class... Args> | 209 template <class... Args> |
207 iterator emplace_hint(const_iterator position_hint, Args&&... args); | 210 iterator emplace_hint(const_iterator position_hint, Args&&... args); |
208 | 211 |
209 // -------------------------------------------------------------------------- | 212 // -------------------------------------------------------------------------- |
210 // Erase operations. | 213 // Erase operations. |
211 // | 214 // |
212 // Assume that every operation invalidates iterators and references. | 215 // Assume that every operation invalidates iterators and references. |
(...skipping 383 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
596 if (position_hint == end() || impl_.get_value_comp()(val, *position_hint)) { | 599 if (position_hint == end() || impl_.get_value_comp()(val, *position_hint)) { |
597 if (position_hint == begin() || | 600 if (position_hint == begin() || |
598 impl_.get_value_comp()(*(position_hint - 1), val)) | 601 impl_.get_value_comp()(*(position_hint - 1), val)) |
599 // We have to cast away const because of crbug.com/677044. | 602 // We have to cast away const because of crbug.com/677044. |
600 return impl_.body_.insert(const_cast_it(position_hint), std::move(val)); | 603 return impl_.body_.insert(const_cast_it(position_hint), std::move(val)); |
601 } | 604 } |
602 return insert(std::move(val)).first; | 605 return insert(std::move(val)).first; |
603 } | 606 } |
604 | 607 |
605 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | 608 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
609 template <class InputIterator> | |
610 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::insert( | |
611 InputIterator first, | |
612 InputIterator last) -> void { | |
613 // Only add elements that are not already present. | |
614 size_type prev_size = size(); | |
615 std::copy_if(first, last, std::back_inserter(impl_.body_), | |
616 [this, prev_size](const value_type& val) { | |
617 return !std::binary_search( | |
618 begin(), std::next(begin(), prev_size), val, value_comp()); | |
619 }); | |
dyaroshev
2017/05/09 01:38:49
You are doing binary search for the first non-uniq
dyaroshev
2017/05/09 11:31:42
I thought about it a bit - you would have to find
jdoerrie
2017/05/09 17:03:30
Yeah, I gave this some though as well. Given that
dyaroshev
2017/05/09 21:37:19
I think, that this binary search might be why you
jdoerrie
2017/05/10 15:39:18
Done.
| |
620 | |
621 // The new elements might be unordered and contain duplicates, so post-process | |
622 // the just inserted elements. | |
623 iterator middle = std::next(begin(), prev_size); | |
624 std::stable_sort(middle, end(), value_comp()); | |
625 erase(std::unique(middle, end(), | |
626 [this](const value_type& lhs, const value_type& rhs) { | |
627 // lhs is already <= rhs due to sort, therefore | |
628 // !(lhs < rhs) <=> lhs == rhs. | |
629 return !value_comp()(lhs, rhs); | |
630 }), | |
631 end()); | |
dyaroshev
2017/05/09 01:38:49
Just add begin/end to sort_and_unque method?
jdoerrie
2017/05/09 17:03:30
Done.
| |
632 | |
633 // Merge the old and new elements if necessary, do a binary search for the | |
634 // first inversion. | |
635 if (middle != begin() && middle != end() && | |
636 !value_comp()(*std::prev(middle), *middle)) { | |
637 std::inplace_merge(std::lower_bound(begin(), middle, *middle, value_comp()), | |
dyaroshev
2017/05/09 01:52:50
!value_comp()(*std::prev(middle), *middle)) <==> l
jdoerrie
2017/05/09 17:03:30
That is true, however an advantage with the curren
dyaroshev
2017/05/09 21:37:19
Is it your binary search or is it the one in inpla
jdoerrie
2017/05/10 15:39:18
Yeah, this was my binary search. I think (buffered
| |
638 middle, end(), value_comp()); | |
639 } | |
640 } | |
641 | |
642 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
606 template <class... Args> | 643 template <class... Args> |
607 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::emplace(Args&&... args) | 644 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::emplace(Args&&... args) |
608 -> std::pair<iterator, bool> { | 645 -> std::pair<iterator, bool> { |
609 return insert(value_type(std::forward<Args>(args)...)); | 646 return insert(value_type(std::forward<Args>(args)...)); |
610 } | 647 } |
611 | 648 |
612 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | 649 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
613 template <class... Args> | 650 template <class... Args> |
614 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::emplace_hint( | 651 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::emplace_hint( |
615 const_iterator position_hint, | 652 const_iterator position_hint, |
(...skipping 152 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
768 void EraseIf(base::internal::flat_tree<Key, Value, GetKeyFromValue, KeyCompare>& | 805 void EraseIf(base::internal::flat_tree<Key, Value, GetKeyFromValue, KeyCompare>& |
769 container, | 806 container, |
770 Predicate pred) { | 807 Predicate pred) { |
771 container.erase(std::remove_if(container.begin(), container.end(), pred), | 808 container.erase(std::remove_if(container.begin(), container.end(), pred), |
772 container.end()); | 809 container.end()); |
773 } | 810 } |
774 | 811 |
775 } // namespace base | 812 } // namespace base |
776 | 813 |
777 #endif // BASE_CONTAINERS_FLAT_TREE_H_ | 814 #endif // BASE_CONTAINERS_FLAT_TREE_H_ |
OLD | NEW |