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 PickConstReferenceTypeT =

[vmpstr, 2017/06/26 15:35:53]

nit: Maybe KeyTypeOrT? I'd still weakly prefer this to be either K or key_type
in the conditional and 

const typename KeyTypeOrT<K>::type& key_ref

in the calling code. It just makes the const and the & part be more local to the
caller. It's just a preference though, so feel free to keep it as is. If you do,
then I guess the name is OK :)

[dyaroshev, 2017/06/26 16:19:28]

Done.

+      typename std::conditional<IsTransparentCompare<key_compare>::value,
+                                const K&,
+                                const 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.

[vmpstr, 2017/06/26 15:35:53]

I'm not sure what this comment is referring to. This will only compile if K ->
key_type conversion is implicit?

Maybe just say "pick K if the comparator is transparent, and key_type
otherwise"?

[dyaroshev, 2017/06/26 16:19:28]

This is about using assignment over operator().

This way, 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;
```

If you instead use uniform initialisation, for example, it will compile and
crash.

+  PickConstReferenceTypeT<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 {
   KeyValueCompare key_value(impl_.get_key_comp());
-  return std::upper_bound(begin(), end(), key, key_value);
+
+  // Only compile when conversion is implicit.
+  PickConstReferenceTypeT<K> key_ref = key;
+  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_