Improving flat containers interface.

base/containers/flat_tree.h

 // Copyright 2017 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #ifndef BASE_CONTAINERS_FLAT_TREE_H_
 #define BASE_CONTAINERS_FLAT_TREE_H_
 
 #include <algorithm>
 #include <iterator>
 #include <vector>
 
+#include "base/template_util.h"
+
 namespace base {
 
 enum FlatContainerDupes {
   KEEP_FIRST_OF_DUPES,
   KEEP_LAST_OF_DUPES,
 };
 
 namespace internal {
 
 // This is a convenience method returning true if Iterator is at least a
@@ skipping 26 matching lines @@
   for (Iterator next = std::next(first); next != last; ++next, ++first) {
     if (!compare(*first, *next))
       *replacable++ = std::move(*first);
   }
 
   // Last element should be copied unconditionally.
   *replacable++ = std::move(*first);
   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.
 //
 // The use of "value" in this is like std::map uses, meaning it's the thing
 // contained (in the case of map it's a <Kay, Mapped> pair). The Key is how
 // things are looked up. In the case of a set, Key == Value. In the case of
 // a map, the Key is a component of a Value.
 //
 // The helper class GetKeyFromValue provides the means to extract a key from a
 // value for comparison purposes. It should implement:
@@ skipping 159 matching lines @@
   // Erase operations.
   //
   // Assume that every operation invalidates iterators and references.
   //
   // erase(position), erase(first, last) can take O(size).
   // erase(key) may take O(size) + O(log(size)).
   //
   // 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.
 
   key_compare key_comp() const;
   value_compare value_comp() const;
 
   // --------------------------------------------------------------------------
   // Search operations.
   //
   // 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;
 
-  iterator find(const key_type& key);
-  const_iterator find(const key_type& key) const;
+  template <typename K>
+  iterator find(const K& key);
 
-  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>
+  const_iterator find(const K& key) const;
 
-  iterator lower_bound(const key_type& key);
-  const_iterator lower_bound(const key_type& key) const;
+  template <typename K>
+  std::pair<iterator, iterator> equal_range(const K& key);
 
-  iterator upper_bound(const key_type& key);
-  const_iterator upper_bound(const key_type& key) const;
+  template <typename K>
+  std::pair<const_iterator, const_iterator> equal_range(const K& key) const;
+
+  template <typename K>
+  iterator lower_bound(const K& key);
+
+  template <typename K>
+  const_iterator lower_bound(const K& key) const;
+
+  template <typename K>
+  iterator upper_bound(const K& key);
+
+  template <typename K>
+  const_iterator upper_bound(const K& key) const;
 
   // --------------------------------------------------------------------------
   // General operations.
   //
   // Assume that swap invalidates iterators and references.
   //
   // Implementation note: currently we use operator==() and operator<() on
   // std::vector, because they have the same contract we need, so we use them
   // directly for brevity and in case it is more optimal than calling equal()
   // and lexicograhpical_compare(). If the underlying container type is changed,
@@ skipping 34 matching lines @@
   iterator unsafe_emplace(const_iterator position, Args&&... args);
 
  private:
   // Helper class for e.g. lower_bound that can compare a value on the left
   // to a key on the right.
   struct KeyValueCompare {
     // The key comparison object must outlive this class.
     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_;
   };
 
   const flat_tree& as_const() { return *this; }
 
   iterator const_cast_it(const_iterator c_it) {
     auto distance = std::distance(cbegin(), c_it);
     return std::next(begin(), distance);
   }
 
@@ skipping 93 matching lines @@
     template <class Cmp, class... Body>
     explicit Impl(Cmp&& compare_arg, Body&&... underlying_type_args)
         : value_compare(std::forward<Cmp>(compare_arg)),
           body_(std::forward<Body>(underlying_type_args)...) {}
 
     const value_compare& get_value_comp() const { return *this; }
     const key_compare& get_key_comp() const { return *this; }
 
     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;
 };
 
 // ----------------------------------------------------------------------------
 // Lifetime.
 
 template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
 flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::flat_tree() = default;
 
 template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
 flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::flat_tree(
@@ skipping 311 matching lines @@
     const_iterator position_hint,
     Args&&... args) -> iterator {
   return insert(position_hint, value_type(std::forward<Args>(args)...));
 }
 
 // ----------------------------------------------------------------------------
 // Erase operations.
 
 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.
   erase(const_cast_it(eq_range.first), const_cast_it(eq_range.second));
   return res;
 }
 
 template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::erase(
     const_iterator first,
@@ skipping 14 matching lines @@
 template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::value_comp() const
     -> value_compare {
   return impl_.get_value_comp();
 }
 
 // ----------------------------------------------------------------------------
 // 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;
   if (lower == end() || impl_.get_key_comp()(key, extractor(*lower)))
     return {lower, lower};
 
   return {lower, std::next(lower)};
 }
 
 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 fails?

[dyaroshev, 2017/06/26 22:40:42]

If you type:
```
  base::flat_set<std::unique_ptr<int>, std::less<std::unique_ptr<int>>> test;
  test.lower_bound(&x);
```

You get a compilation error:
```
../../base/containers/flat_tree.h:916:24: error: reference to type 'const
KeyTypeOrK<int *>' (aka 'const std::__1::unique_ptr<int,
std::__1::default_delete<int> >') could not bind to an lvalue of type 'int
*const'
  const KeyTypeOrK<K>& key_ref = key;
```

[vmpstr, 2017/06/27 16:09:58]

We talked a bit about this. The error is somewhat hard to understand without
knowing the internals of how flat_tree is implemented. We came up with a couple
options to try to see if the error looks better. Do you mind doing one of these?
(or anything else you come up with that might be easier to understand from the
user's point of view)

1. Try to enable_if this function based on whether the comparator is transparent
and if it's not transparent, then only have a key_type& override. I think that
will probably give a better error, but more code to type.

2. Static assert that we can create this type. In this one, the phrasing of the
error is up to us, so maybe something like "Requested type cannot be bound to
the container's key_type".

+  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);
 }
 
 // ----------------------------------------------------------------------------
 // General operations.
 
 template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
 void flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::swap(
     flat_tree& other) {
   std::swap(impl_, other.impl_);
 }
@@ skipping 29 matching lines @@
 void EraseIf(base::internal::flat_tree<Key, Value, GetKeyFromValue, KeyCompare>&
                  container,
              Predicate pred) {
   container.erase(std::remove_if(container.begin(), container.end(), pred),
                   container.end());
 }
 
 }  // namespace base
 
 #endif  // BASE_CONTAINERS_FLAT_TREE_H_