Index: base/containers/flat_tree.h |
diff --git a/base/containers/flat_tree.h b/base/containers/flat_tree.h |
index afbbf95c4fdda48db3065cb86c202c9ef169e1f6..4b638aaae97fd0442e1bdcfe5eaa949e2d86689b 100644 |
--- a/base/containers/flat_tree.h |
+++ b/base/containers/flat_tree.h |
@@ -9,6 +9,8 @@ |
#include <iterator> |
#include <vector> |
+#include "base/template_util.h" |
+ |
namespace base { |
enum FlatContainerDupes { |
@@ -55,6 +57,15 @@ Iterator LastUnique(Iterator first, Iterator last, BinaryPredicate compare) { |
return replacable; |
} |
+// Uses SFINAE to detect whether type has is_transparent member. |
+template <typename T, typename = void> |
+struct IsTransparentCompare : std::false_type {}; |
+template <typename T> |
+struct IsTransparentCompare<T, void_t<typename T::is_transparent>> |
+ : std::true_type {}; |
+ |
+// Implementation ------------------------------------------------------------- |
+ |
// Implementation of a sorted vector for backing flat_set and flat_map. Do not |
// use directly. |
// |
@@ -234,9 +245,11 @@ class flat_tree { |
// Prefer base::EraseIf() or some other variation on erase(remove(), end()) |
// idiom when deleting multiple non-consecutive elements. |
+ iterator erase(iterator position); |
iterator erase(const_iterator position); |
iterator erase(const_iterator first, const_iterator last); |
- size_type erase(const key_type& key); |
+ template <typename K> |
+ size_type erase(const K& key); |
// -------------------------------------------------------------------------- |
// Comparators. |
@@ -249,20 +262,32 @@ class flat_tree { |
// |
// Search operations have O(log(size)) complexity. |
- size_type count(const key_type& key) const; |
+ template <typename K> |
+ size_type count(const K& key) const; |
+ |
+ template <typename K> |
+ iterator find(const K& key); |
+ |
+ template <typename K> |
+ const_iterator find(const K& key) const; |
+ |
+ template <typename K> |
+ std::pair<iterator, iterator> equal_range(const K& key); |
- iterator find(const key_type& key); |
- const_iterator find(const key_type& key) const; |
+ template <typename K> |
+ std::pair<const_iterator, const_iterator> equal_range(const K& key) const; |
- std::pair<iterator, iterator> equal_range(const key_type& ket); |
- std::pair<const_iterator, const_iterator> equal_range( |
- const key_type& key) const; |
+ template <typename K> |
+ iterator lower_bound(const K& key); |
- iterator lower_bound(const key_type& key); |
- const_iterator lower_bound(const key_type& key) const; |
+ template <typename K> |
+ const_iterator lower_bound(const K& key) const; |
- iterator upper_bound(const key_type& key); |
- const_iterator upper_bound(const key_type& key) const; |
+ template <typename K> |
+ iterator upper_bound(const K& key); |
+ |
+ template <typename K> |
+ const_iterator upper_bound(const K& key) const; |
// -------------------------------------------------------------------------- |
// General operations. |
@@ -317,12 +342,22 @@ class flat_tree { |
explicit KeyValueCompare(const key_compare& key_comp) |
: key_comp_(key_comp) {} |
- bool operator()(const value_type& left, const key_type& right) const { |
- GetKeyFromValue extractor; |
- return key_comp_(extractor(left), right); |
+ template <typename T, typename U> |
+ bool operator()(const T& lhs, const U& rhs) const { |
+ return key_comp_(extract_if_value_type(lhs), extract_if_value_type(rhs)); |
} |
private: |
+ const key_type& extract_if_value_type(const value_type& v) const { |
+ GetKeyFromValue extractor; |
+ return extractor(v); |
+ } |
+ |
+ template <typename K> |
+ const K& extract_if_value_type(const K& k) const { |
+ return k; |
+ } |
+ |
const key_compare& key_comp_; |
}; |
@@ -436,6 +471,11 @@ class flat_tree { |
underlying_type body_; |
} impl_; |
+ |
+ // If the compare is not transparent we want to construct key_type once. |
+ template <typename K> |
+ using KeyTypeOrK = typename std:: |
+ conditional<IsTransparentCompare<key_compare>::value, K, key_type>::type; |
}; |
// ---------------------------------------------------------------------------- |
@@ -767,14 +807,21 @@ auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::emplace_hint( |
template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::erase( |
+ iterator position) -> iterator { |
+ return impl_.body_.erase(position); |
+} |
+ |
+template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
+auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::erase( |
const_iterator position) -> iterator { |
// We have to cast away const because of crbug.com/677044. |
- return impl_.body_.erase(const_cast_it(position)); |
+ return erase(const_cast_it(position)); |
} |
template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
-auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::erase( |
- const key_type& val) -> size_type { |
+template <typename K> |
+auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::erase(const K& val) |
+ -> size_type { |
auto eq_range = equal_range(val); |
auto res = std::distance(eq_range.first, eq_range.second); |
// We have to cast away const because of crbug.com/677044. |
@@ -809,35 +856,40 @@ auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::value_comp() const |
// Search operations. |
template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
+template <typename K> |
auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::count( |
- const key_type& key) const -> size_type { |
+ const K& key) const -> size_type { |
auto eq_range = equal_range(key); |
return std::distance(eq_range.first, eq_range.second); |
} |
template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
-auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::find( |
- const key_type& key) -> iterator { |
+template <typename K> |
+auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::find(const K& key) |
+ -> iterator { |
return const_cast_it(as_const().find(key)); |
} |
template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
+template <typename K> |
auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::find( |
- const key_type& key) const -> const_iterator { |
+ const K& key) const -> const_iterator { |
auto eq_range = equal_range(key); |
return (eq_range.first == eq_range.second) ? end() : eq_range.first; |
} |
template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
+template <typename K> |
auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::equal_range( |
- const key_type& key) -> std::pair<iterator, iterator> { |
+ const K& key) -> std::pair<iterator, iterator> { |
auto res = as_const().equal_range(key); |
return {const_cast_it(res.first), const_cast_it(res.second)}; |
} |
template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
+template <typename K> |
auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::equal_range( |
- const key_type& key) const -> std::pair<const_iterator, const_iterator> { |
+ const K& key) const -> std::pair<const_iterator, const_iterator> { |
auto lower = lower_bound(key); |
GetKeyFromValue extractor; |
@@ -848,29 +900,39 @@ auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::equal_range( |
} |
template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
+template <typename K> |
auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::lower_bound( |
- const key_type& key) -> iterator { |
+ const K& key) -> iterator { |
return const_cast_it(as_const().lower_bound(key)); |
} |
template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
+template <typename K> |
auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::lower_bound( |
- const key_type& key) const -> const_iterator { |
+ const K& key) const -> const_iterator { |
+ // Only compile when conversion is implicit. |
danakj
2017/06/26 19:33:12
What does the compiler error look like when this f
dyaroshev
2017/06/26 22:40:42
If you type:
```
base::flat_set<std::unique_ptr<
vmpstr
2017/06/27 16:09:58
We talked a bit about this. The error is somewhat
|
+ const KeyTypeOrK<K>& key_ref = key; |
+ |
KeyValueCompare key_value(impl_.get_key_comp()); |
- return std::lower_bound(begin(), end(), key, key_value); |
+ return std::lower_bound(begin(), end(), key_ref, key_value); |
} |
template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
+template <typename K> |
auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::upper_bound( |
- const key_type& key) -> iterator { |
+ const K& key) -> iterator { |
return const_cast_it(as_const().upper_bound(key)); |
} |
template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
+template <typename K> |
auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::upper_bound( |
- const key_type& key) const -> const_iterator { |
+ const K& key) const -> const_iterator { |
+ // Only compile when conversion is implicit. |
+ const KeyTypeOrK<K>& key_ref = key; |
+ |
KeyValueCompare key_value(impl_.get_key_comp()); |
- return std::upper_bound(begin(), end(), key, key_value); |
+ return std::upper_bound(begin(), end(), key_ref, key_value); |
} |
// ---------------------------------------------------------------------------- |