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 // No duplicate elements found. |
| 27 if (replacable == last) |
25 return last; | 28 return last; |
26 | 29 |
27 Iterator dest = first; | 30 first = std::next(replacable); |
28 Iterator cur = first; | 31 |
29 Iterator prev = cur; | 32 // Last element is a duplicate but all others are unique. |
30 while (++cur != last) { | 33 if (first == last) |
31 if (!compare(*prev, *cur)) { | 34 return replacable; |
32 // Non-identical one. | 35 |
33 if (dest != prev) | 36 // This loop is based on std::adjacent_find but std::adjacent_find doesn't |
34 *dest = std::move(*prev); | 37 // quite cut it. |
35 ++dest; | 38 for (Iterator next = std::next(first); next != last; ++next, ++first) { |
36 } | 39 if (!compare(*first, *next)) |
37 prev = cur; | 40 *replacable++ = std::move(*first); |
38 } | 41 } |
39 | 42 |
40 if (dest != prev) | 43 // Last element should be copied unconditionally. |
41 *dest = std::move(*prev); | 44 *replacable++ = std::move(*first); |
42 return ++dest; | 45 return replacable; |
43 } | 46 } |
44 | 47 |
45 // Implementation of a sorted vector for backing flat_set and flat_map. Do not | 48 // Implementation of a sorted vector for backing flat_set and flat_map. Do not |
46 // use directly. | 49 // use directly. |
47 // | 50 // |
48 // The use of "value" in this is like std::map uses, meaning it's the thing | 51 // 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 | 52 // 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 | 53 // 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. | 54 // a map, the Key is a component of a Value. |
52 // | 55 // |
(...skipping 712 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
765 void EraseIf(base::internal::flat_tree<Key, Value, GetKeyFromValue, KeyCompare>& | 768 void EraseIf(base::internal::flat_tree<Key, Value, GetKeyFromValue, KeyCompare>& |
766 container, | 769 container, |
767 Predicate pred) { | 770 Predicate pred) { |
768 container.erase(std::remove_if(container.begin(), container.end(), pred), | 771 container.erase(std::remove_if(container.begin(), container.end(), pred), |
769 container.end()); | 772 container.end()); |
770 } | 773 } |
771 | 774 |
772 } // namespace base | 775 } // namespace base |
773 | 776 |
774 #endif // BASE_CONTAINERS_FLAT_TREE_H_ | 777 #endif // BASE_CONTAINERS_FLAT_TREE_H_ |
OLD | NEW |