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 <iterator> |
10 #include <vector> | 10 #include <vector> |
11 | 11 |
12 #include "base/type_traits.h" | |
13 | |
12 namespace base { | 14 namespace base { |
13 | 15 |
14 enum FlatContainerDupes { | 16 enum FlatContainerDupes { |
15 KEEP_FIRST_OF_DUPES, | 17 KEEP_FIRST_OF_DUPES, |
16 KEEP_LAST_OF_DUPES, | 18 KEEP_LAST_OF_DUPES, |
17 }; | 19 }; |
18 | 20 |
19 namespace internal { | 21 namespace internal { |
20 | 22 |
21 // This is a convenience method returning true if Iterator is at least a | 23 // This is a convenience method returning true if Iterator is at least a |
(...skipping 26 matching lines...) Expand all Loading... | |
48 for (Iterator next = std::next(first); next != last; ++next, ++first) { | 50 for (Iterator next = std::next(first); next != last; ++next, ++first) { |
49 if (!compare(*first, *next)) | 51 if (!compare(*first, *next)) |
50 *replacable++ = std::move(*first); | 52 *replacable++ = std::move(*first); |
51 } | 53 } |
52 | 54 |
53 // Last element should be copied unconditionally. | 55 // Last element should be copied unconditionally. |
54 *replacable++ = std::move(*first); | 56 *replacable++ = std::move(*first); |
55 return replacable; | 57 return replacable; |
56 } | 58 } |
57 | 59 |
60 // Concepts ------------------------------------------------------------------- | |
61 | |
62 template <typename Y> | |
63 using HasIsTransparentMember = typename Y::is_transparent; | |
64 | |
65 template <typename T> | |
66 constexpr bool TransparentCompare() { | |
67 return is_detected_c<HasIsTransparentMember, T>(); | |
68 } | |
69 | |
70 // Implementation ------------------------------------------------------------- | |
71 | |
58 // Implementation of a sorted vector for backing flat_set and flat_map. Do not | 72 // Implementation of a sorted vector for backing flat_set and flat_map. Do not |
59 // use directly. | 73 // use directly. |
60 // | 74 // |
61 // The use of "value" in this is like std::map uses, meaning it's the thing | 75 // The use of "value" in this is like std::map uses, meaning it's the thing |
62 // contained (in the case of map it's a <Kay, Mapped> pair). The Key is how | 76 // contained (in the case of map it's a <Kay, Mapped> pair). The Key is how |
63 // things are looked up. In the case of a set, Key == Value. In the case of | 77 // things are looked up. In the case of a set, Key == Value. In the case of |
64 // a map, the Key is a component of a Value. | 78 // a map, the Key is a component of a Value. |
65 // | 79 // |
66 // The helper class GetKeyFromValue provides the means to extract a key from a | 80 // The helper class GetKeyFromValue provides the means to extract a key from a |
67 // value for comparison purposes. It should implement: | 81 // value for comparison purposes. It should implement: |
(...skipping 159 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
227 // Erase operations. | 241 // Erase operations. |
228 // | 242 // |
229 // Assume that every operation invalidates iterators and references. | 243 // Assume that every operation invalidates iterators and references. |
230 // | 244 // |
231 // erase(position), erase(first, last) can take O(size). | 245 // erase(position), erase(first, last) can take O(size). |
232 // erase(key) may take O(size) + O(log(size)). | 246 // erase(key) may take O(size) + O(log(size)). |
233 // | 247 // |
234 // Prefer base::EraseIf() or some other variation on erase(remove(), end()) | 248 // Prefer base::EraseIf() or some other variation on erase(remove(), end()) |
235 // idiom when deleting multiple non-consecutive elements. | 249 // idiom when deleting multiple non-consecutive elements. |
236 | 250 |
251 iterator erase(iterator position); | |
237 iterator erase(const_iterator position); | 252 iterator erase(const_iterator position); |
238 iterator erase(const_iterator first, const_iterator last); | 253 iterator erase(const_iterator first, const_iterator last); |
239 size_type erase(const key_type& key); | 254 template <typename K> |
255 size_type erase(const K& key); | |
240 | 256 |
241 // -------------------------------------------------------------------------- | 257 // -------------------------------------------------------------------------- |
242 // Comparators. | 258 // Comparators. |
243 | 259 |
244 key_compare key_comp() const; | 260 key_compare key_comp() const; |
245 value_compare value_comp() const; | 261 value_compare value_comp() const; |
246 | 262 |
247 // -------------------------------------------------------------------------- | 263 // -------------------------------------------------------------------------- |
248 // Search operations. | 264 // Search operations. |
249 // | 265 // |
250 // Search operations have O(log(size)) complexity. | 266 // Search operations have O(log(size)) complexity. |
251 | 267 |
252 size_type count(const key_type& key) const; | 268 template <typename K> |
269 size_type count(const K& key) const; | |
253 | 270 |
254 iterator find(const key_type& key); | 271 template <typename K> |
255 const_iterator find(const key_type& key) const; | 272 iterator find(const K& key); |
256 | 273 |
257 std::pair<iterator, iterator> equal_range(const key_type& ket); | 274 template <typename K> |
258 std::pair<const_iterator, const_iterator> equal_range( | 275 const_iterator find(const K& key) const; |
259 const key_type& key) const; | |
260 | 276 |
261 iterator lower_bound(const key_type& key); | 277 template <typename K> |
262 const_iterator lower_bound(const key_type& key) const; | 278 std::pair<iterator, iterator> equal_range(const K& key); |
263 | 279 |
264 iterator upper_bound(const key_type& key); | 280 template <typename K> |
265 const_iterator upper_bound(const key_type& key) const; | 281 std::pair<const_iterator, const_iterator> equal_range(const K& key) const; |
282 | |
283 template <typename K> | |
284 iterator lower_bound(const K& key); | |
285 | |
286 template <typename K> | |
287 const_iterator lower_bound(const K& key) const; | |
288 | |
289 template <typename K> | |
290 iterator upper_bound(const K& key); | |
291 | |
292 template <typename K> | |
293 const_iterator upper_bound(const K& key) const; | |
266 | 294 |
267 // -------------------------------------------------------------------------- | 295 // -------------------------------------------------------------------------- |
268 // General operations. | 296 // General operations. |
269 // | 297 // |
270 // Assume that swap invalidates iterators and references. | 298 // Assume that swap invalidates iterators and references. |
271 // | 299 // |
272 // Implementation note: currently we use operator==() and operator<() on | 300 // Implementation note: currently we use operator==() and operator<() on |
273 // std::vector, because they have the same contract we need, so we use them | 301 // std::vector, because they have the same contract we need, so we use them |
274 // directly for brevity and in case it is more optimal than calling equal() | 302 // directly for brevity and in case it is more optimal than calling equal() |
275 // and lexicograhpical_compare(). If the underlying container type is changed, | 303 // and lexicograhpical_compare(). If the underlying container type is changed, |
(...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
310 iterator unsafe_emplace(const_iterator position, Args&&... args); | 338 iterator unsafe_emplace(const_iterator position, Args&&... args); |
311 | 339 |
312 private: | 340 private: |
313 // Helper class for e.g. lower_bound that can compare a value on the left | 341 // Helper class for e.g. lower_bound that can compare a value on the left |
314 // to a key on the right. | 342 // to a key on the right. |
315 struct KeyValueCompare { | 343 struct KeyValueCompare { |
316 // The key comparison object must outlive this class. | 344 // The key comparison object must outlive this class. |
317 explicit KeyValueCompare(const key_compare& key_comp) | 345 explicit KeyValueCompare(const key_compare& key_comp) |
318 : key_comp_(key_comp) {} | 346 : key_comp_(key_comp) {} |
319 | 347 |
320 bool operator()(const value_type& left, const key_type& right) const { | 348 template <typename T, typename U> |
321 GetKeyFromValue extractor; | 349 bool operator()(const T& lhs, const U& rhs) const { |
322 return key_comp_(extractor(left), right); | 350 return key_comp_(extract_if_value_type(lhs), extract_if_value_type(rhs)); |
323 } | 351 } |
324 | 352 |
325 private: | 353 private: |
354 const key_type& extract_if_value_type(const value_type& v) const { | |
355 GetKeyFromValue extractor; | |
356 return extractor(v); | |
357 } | |
358 | |
359 template <typename K> | |
360 const K& extract_if_value_type(const K& k) const { | |
361 return k; | |
362 } | |
363 | |
326 const key_compare& key_comp_; | 364 const key_compare& key_comp_; |
327 }; | 365 }; |
328 | 366 |
329 const flat_tree& as_const() { return *this; } | 367 const flat_tree& as_const() { return *this; } |
330 | 368 |
331 iterator const_cast_it(const_iterator c_it) { | 369 iterator const_cast_it(const_iterator c_it) { |
332 auto distance = std::distance(cbegin(), c_it); | 370 auto distance = std::distance(cbegin(), c_it); |
333 return std::next(begin(), distance); | 371 return std::next(begin(), distance); |
334 } | 372 } |
335 | 373 |
(...skipping 424 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
760 const_iterator position_hint, | 798 const_iterator position_hint, |
761 Args&&... args) -> iterator { | 799 Args&&... args) -> iterator { |
762 return insert(position_hint, value_type(std::forward<Args>(args)...)); | 800 return insert(position_hint, value_type(std::forward<Args>(args)...)); |
763 } | 801 } |
764 | 802 |
765 // ---------------------------------------------------------------------------- | 803 // ---------------------------------------------------------------------------- |
766 // Erase operations. | 804 // Erase operations. |
767 | 805 |
768 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | 806 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
769 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::erase( | 807 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::erase( |
808 iterator position) -> iterator { | |
809 return impl_.body_.erase(position); | |
810 } | |
811 | |
812 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | |
813 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::erase( | |
770 const_iterator position) -> iterator { | 814 const_iterator position) -> iterator { |
771 // We have to cast away const because of crbug.com/677044. | 815 // We have to cast away const because of crbug.com/677044. |
772 return impl_.body_.erase(const_cast_it(position)); | 816 return erase(const_cast_it(position)); |
773 } | 817 } |
774 | 818 |
775 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | 819 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
776 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::erase( | 820 template <typename K> |
777 const key_type& val) -> size_type { | 821 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::erase(const K& val) |
822 -> size_type { | |
778 auto eq_range = equal_range(val); | 823 auto eq_range = equal_range(val); |
779 auto res = std::distance(eq_range.first, eq_range.second); | 824 auto res = std::distance(eq_range.first, eq_range.second); |
780 // We have to cast away const because of crbug.com/677044. | 825 // We have to cast away const because of crbug.com/677044. |
781 erase(const_cast_it(eq_range.first), const_cast_it(eq_range.second)); | 826 erase(const_cast_it(eq_range.first), const_cast_it(eq_range.second)); |
782 return res; | 827 return res; |
783 } | 828 } |
784 | 829 |
785 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | 830 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
786 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::erase( | 831 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::erase( |
787 const_iterator first, | 832 const_iterator first, |
(...skipping 14 matching lines...) Expand all Loading... | |
802 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | 847 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
803 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::value_comp() const | 848 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::value_comp() const |
804 -> value_compare { | 849 -> value_compare { |
805 return impl_.get_value_comp(); | 850 return impl_.get_value_comp(); |
806 } | 851 } |
807 | 852 |
808 // ---------------------------------------------------------------------------- | 853 // ---------------------------------------------------------------------------- |
809 // Search operations. | 854 // Search operations. |
810 | 855 |
811 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | 856 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
857 template <typename K> | |
812 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::count( | 858 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::count( |
813 const key_type& key) const -> size_type { | 859 const K& key) const -> size_type { |
814 auto eq_range = equal_range(key); | 860 auto eq_range = equal_range(key); |
815 return std::distance(eq_range.first, eq_range.second); | 861 return std::distance(eq_range.first, eq_range.second); |
816 } | 862 } |
817 | 863 |
818 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | 864 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
819 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::find( | 865 template <typename K> |
820 const key_type& key) -> iterator { | 866 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::find(const K& key) |
867 -> iterator { | |
821 return const_cast_it(as_const().find(key)); | 868 return const_cast_it(as_const().find(key)); |
822 } | 869 } |
823 | 870 |
824 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | 871 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
872 template <typename K> | |
825 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::find( | 873 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::find( |
826 const key_type& key) const -> const_iterator { | 874 const K& key) const -> const_iterator { |
827 auto eq_range = equal_range(key); | 875 auto eq_range = equal_range(key); |
828 return (eq_range.first == eq_range.second) ? end() : eq_range.first; | 876 return (eq_range.first == eq_range.second) ? end() : eq_range.first; |
829 } | 877 } |
830 | 878 |
831 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | 879 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
880 template <typename K> | |
832 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::equal_range( | 881 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::equal_range( |
833 const key_type& key) -> std::pair<iterator, iterator> { | 882 const K& key) -> std::pair<iterator, iterator> { |
834 auto res = as_const().equal_range(key); | 883 auto res = as_const().equal_range(key); |
835 return {const_cast_it(res.first), const_cast_it(res.second)}; | 884 return {const_cast_it(res.first), const_cast_it(res.second)}; |
836 } | 885 } |
837 | 886 |
838 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | 887 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
888 template <typename K> | |
839 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::equal_range( | 889 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::equal_range( |
840 const key_type& key) const -> std::pair<const_iterator, const_iterator> { | 890 const K& key) const -> std::pair<const_iterator, const_iterator> { |
841 auto lower = lower_bound(key); | 891 auto lower = lower_bound(key); |
842 | 892 |
843 GetKeyFromValue extractor; | 893 GetKeyFromValue extractor; |
844 if (lower == end() || impl_.get_key_comp()(key, extractor(*lower))) | 894 if (lower == end() || impl_.get_key_comp()(key, extractor(*lower))) |
845 return {lower, lower}; | 895 return {lower, lower}; |
846 | 896 |
847 return {lower, std::next(lower)}; | 897 return {lower, std::next(lower)}; |
848 } | 898 } |
849 | 899 |
850 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | 900 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
901 template <typename K> | |
851 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::lower_bound( | 902 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::lower_bound( |
852 const key_type& key) -> iterator { | 903 const K& key) -> iterator { |
853 return const_cast_it(as_const().lower_bound(key)); | 904 return const_cast_it(as_const().lower_bound(key)); |
854 } | 905 } |
855 | 906 |
856 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | 907 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
908 template <typename K> | |
857 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::lower_bound( | 909 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::lower_bound( |
858 const key_type& key) const -> const_iterator { | 910 const K& key) const -> const_iterator { |
911 // if the compare is not transparent -> construct key_type once. | |
brettw
2017/06/20 18:13:35
Comment nits: capital "I" (same below)
| |
912 condtional_t<TransparentCompare<key_compare>(), const K&, const key_type&> | |
913 key_ref = key; // Only compile when conversion is implicit. | |
914 | |
859 KeyValueCompare key_value(impl_.get_key_comp()); | 915 KeyValueCompare key_value(impl_.get_key_comp()); |
860 return std::lower_bound(begin(), end(), key, key_value); | 916 return std::lower_bound(begin(), end(), key_ref, key_value); |
861 } | 917 } |
862 | 918 |
863 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | 919 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
920 template <typename K> | |
864 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::upper_bound( | 921 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::upper_bound( |
865 const key_type& key) -> iterator { | 922 const K& key) -> iterator { |
866 return const_cast_it(as_const().upper_bound(key)); | 923 return const_cast_it(as_const().upper_bound(key)); |
867 } | 924 } |
868 | 925 |
869 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | 926 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
927 template <typename K> | |
870 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::upper_bound( | 928 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::upper_bound( |
871 const key_type& key) const -> const_iterator { | 929 const K& key) const -> const_iterator { |
872 KeyValueCompare key_value(impl_.get_key_comp()); | 930 KeyValueCompare key_value(impl_.get_key_comp()); |
873 return std::upper_bound(begin(), end(), key, key_value); | 931 |
932 // if the compare is not transparent -> construct key_type once. | |
933 condtional_t<TransparentCompare<key_compare>(), const K&, const key_type&> | |
934 key_ref = key; // Only compile when conversion is implicit. | |
935 return std::upper_bound(begin(), end(), key_ref, key_value); | |
874 } | 936 } |
875 | 937 |
876 // ---------------------------------------------------------------------------- | 938 // ---------------------------------------------------------------------------- |
877 // General operations. | 939 // General operations. |
878 | 940 |
879 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | 941 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
880 void flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::swap( | 942 void flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::swap( |
881 flat_tree& other) { | 943 flat_tree& other) { |
882 std::swap(impl_, other.impl_); | 944 std::swap(impl_, other.impl_); |
883 } | 945 } |
(...skipping 29 matching lines...) Expand all Loading... | |
913 void EraseIf(base::internal::flat_tree<Key, Value, GetKeyFromValue, KeyCompare>& | 975 void EraseIf(base::internal::flat_tree<Key, Value, GetKeyFromValue, KeyCompare>& |
914 container, | 976 container, |
915 Predicate pred) { | 977 Predicate pred) { |
916 container.erase(std::remove_if(container.begin(), container.end(), pred), | 978 container.erase(std::remove_if(container.begin(), container.end(), pred), |
917 container.end()); | 979 container.end()); |
918 } | 980 } |
919 | 981 |
920 } // namespace base | 982 } // namespace base |
921 | 983 |
922 #endif // BASE_CONTAINERS_FLAT_TREE_H_ | 984 #endif // BASE_CONTAINERS_FLAT_TREE_H_ |
OLD | NEW |