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 <vector> | 9 #include <vector> |
10 | 10 |
11 namespace base { | 11 namespace base { |
12 | 12 |
13 enum FlatContainerDupes { | 13 enum FlatContainerDupes { |
14 KEEP_FIRST_OF_DUPES, | 14 KEEP_FIRST_OF_DUPES, |
15 KEEP_LAST_OF_DUPES, | 15 KEEP_LAST_OF_DUPES, |
16 }; | 16 }; |
17 | 17 |
18 namespace internal { | 18 namespace internal { |
19 | 19 |
20 // This algorithm is like unique() from the standard library except it | 20 // This algorithm is like unique() from the standard library except it |
21 // selects only the last of consecutive values instead of the first. | 21 // selects only the last of consecutive values instead of the first. |
22 template <class Iterator, class BinaryPredicate> | 22 template <class Iterator, class BinaryPredicate> |
23 Iterator LastUnique(Iterator first, Iterator last, BinaryPredicate compare) { | 23 Iterator LastUnique(Iterator first, Iterator last, BinaryPredicate compare) { |
24 if (first == last) | 24 Iterator replacable = std::adjacent_find(first, last, compare); |
25 | |
26 if (replacable == last) | |
25 return last; | 27 return last; |
brettw
2017/04/26 21:48:51
Can you append to this line "No duplicate elements
| |
26 | 28 |
27 Iterator dest = first; | 29 first = std::next(replacable); |
28 Iterator cur = first; | |
29 Iterator prev = cur; | |
30 while (++cur != last) { | |
31 if (!compare(*prev, *cur)) { | |
32 // Non-identical one. | |
33 if (dest != prev) | |
34 *dest = std::move(*prev); | |
35 ++dest; | |
36 } | |
37 prev = cur; | |
38 } | |
39 | 30 |
40 if (dest != prev) | 31 if (first == last) |
41 *dest = std::move(*prev); | 32 return replacable; |
42 return ++dest; | 33 |
34 // adjacent_find will force us to use BidirectionalIterator. | |
brettw
2017/04/26 21:48:51
This comment is confusing by itself here. I think
dyaroshev
2017/04/27 19:11:46
I've done smth. Looks better?
| |
35 // to get the previous element. | |
36 for (Iterator next = std::next(first); next != last; ++next, ++first) | |
brettw
2017/04/26 21:48:51
This should have {} by our style guide (# lines is
dyaroshev
2017/04/27 19:11:46
Done.
| |
37 if (!compare(*first, *next)) | |
38 *replacable++ = std::move(*first); | |
39 | |
40 // last element should be copied unconditionally. | |
brettw
2017/04/26 21:48:51
Minor nit: capital letter @ beginning.
dyaroshev
2017/04/27 19:11:46
Done.
| |
41 *replacable++ = std::move(*first); | |
42 return replacable; | |
43 } | 43 } |
44 | 44 |
45 // Implementation of a sorted vector for backing flat_set and flat_map. Do not | 45 // Implementation of a sorted vector for backing flat_set and flat_map. Do not |
46 // use directly. | 46 // use directly. |
47 // | 47 // |
48 // The use of "value" in this is like std::map uses, meaning it's the thing | 48 // The use of "value" in this is like std::map uses, meaning it's the thing |
49 // contained (in the case of map it's a <Kay, Mapped> pair). The Key is how | 49 // contained (in the case of map it's a <Kay, Mapped> pair). The Key is how |
50 // things are looked up. In the case of a set, Key == Value. In the case of | 50 // things are looked up. In the case of a set, Key == Value. In the case of |
51 // a map, the Key is a component of a Value. | 51 // a map, the Key is a component of a Value. |
52 // | 52 // |
(...skipping 712 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
765 void EraseIf(base::internal::flat_tree<Key, Value, GetKeyFromValue, KeyCompare>& | 765 void EraseIf(base::internal::flat_tree<Key, Value, GetKeyFromValue, KeyCompare>& |
766 container, | 766 container, |
767 Predicate pred) { | 767 Predicate pred) { |
768 container.erase(std::remove_if(container.begin(), container.end(), pred), | 768 container.erase(std::remove_if(container.begin(), container.end(), pred), |
769 container.end()); | 769 container.end()); |
770 } | 770 } |
771 | 771 |
772 } // namespace base | 772 } // namespace base |
773 | 773 |
774 #endif // BASE_CONTAINERS_FLAT_TREE_H_ | 774 #endif // BASE_CONTAINERS_FLAT_TREE_H_ |
OLD | NEW |