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/type_traits.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;
 }
 
+// Concepts -------------------------------------------------------------------
+
+template <typename Y>
+using HasIsTransparentMember = typename Y::is_transparent;
+
+template <typename T>
+constexpr bool TransparentCompare() {
+  return is_detected_c<HasIsTransparentMember, T>();
+}
+
+// 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);

[jdoerrie, 2017/06/20 23:51:09]

Just out of curiosity: Why don't we simply inline extractor here and in other
places? Wouldn't `return GetKeyFromValue()(v);` also work?

[dyaroshev, 2017/06/22 10:41:43]

Sure. I just kept it as is.

+    }
+
+    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 424 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 {
+  // If the compare is not transparent -> construct key_type once.
+  conditional_t<TransparentCompare<key_compare>(), const K&, const key_type&>
+      key_ref = key;  // Only compile when conversion is implicit.
+
   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);

[jdoerrie, 2017/06/20 23:51:09]

key_value could also be inlined, correct? `KeyValueCompare(key_comp())` should
be the same.

[dyaroshev, 2017/06/22 10:41:43]

Yep, but previously it wasn't so I didn't touch it.

 }
 
 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);
+
+  // If the compare is not transparent -> construct key_type once.
+  conditional_t<TransparentCompare<key_compare>(), const K&, const key_type&>
+      key_ref = key;  // Only compile when conversion is implicit.
+  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_