X-Git-Url: http://plrg.eecs.uci.edu/git/?p=folly.git;a=blobdiff_plain;f=folly%2Fsorted_vector_types.h;h=432b9411094a58dec138ea3ea132bd952a2229c0;hp=18540185a064ea5c19513bde5c9f26c986eddb89;hb=eb7bc45f22e034751a76bf02445c669471e60780;hpb=048c596476a712233b4e63e276b4fc41a85bf04f

diff --git a/folly/sorted_vector_types.h b/folly/sorted_vector_types.h
index 18540185..432b9411 100644
--- a/folly/sorted_vector_types.h
+++ b/folly/sorted_vector_types.h
@@ -1,5 +1,5 @@
 /*
- * Copyright 2016 Facebook, Inc.
+ * Copyright 2017 Facebook, Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -34,7 +34,7 @@
  * example growth policy that grows one element at a time:
  *
  *    struct OneAtATimePolicy {
- *      template<class Container>
+ *      template <class Container>
  *      void increase_capacity(Container& c) {
  *        if (c.size() == c.capacity()) {
  *          c.reserve(c.size() + 1);
@@ -69,82 +69,131 @@
 
 #include <boost/operators.hpp>
 
+#include <folly/Traits.h>
+#include <folly/portability/BitsFunctexcept.h>
+
 namespace folly {
 
 //////////////////////////////////////////////////////////////////////
 
 namespace detail {
 
-  // This wrapper goes around a GrowthPolicy and provides iterator
-  // preservation semantics, but only if the growth policy is not the
-  // default (i.e. nothing).
-  template<class Policy>
-  struct growth_policy_wrapper : private Policy {
-    template<class Container, class Iterator>
-    Iterator increase_capacity(Container& c, Iterator desired_insertion)
-    {
-      typedef typename Container::difference_type diff_t;
-      diff_t d = desired_insertion - c.begin();
-      Policy::increase_capacity(c);
-      return c.begin() + d;
-    }
-  };
-  template<>
-  struct growth_policy_wrapper<void> {
-    template<class Container, class Iterator>
-    Iterator increase_capacity(Container&, Iterator it) {
-      return it;
-    }
-  };
+template <typename, typename Compare, typename Key, typename T>
+struct sorted_vector_enable_if_is_transparent {};
 
-  /*
-   * This helper returns the distance between two iterators if it is
-   * possible to figure it out without messing up the range
-   * (i.e. unless they are InputIterators).  Otherwise this returns
-   * -1.
-   */
-  template<class Iterator>
-  int distance_if_multipass(Iterator first, Iterator last) {
-    typedef typename std::iterator_traits<Iterator>::iterator_category categ;
-    if (std::is_same<categ,std::input_iterator_tag>::value)
-      return -1;
-    return std::distance(first, last);
-  }
-
-  template<class OurContainer, class Vector, class GrowthPolicy>
-  typename OurContainer::iterator
-  insert_with_hint(OurContainer& sorted,
-                   Vector& cont,
-                   typename OurContainer::iterator hint,
-                   typename OurContainer::value_type&& value,
-                   GrowthPolicy& po)
-  {
-    const typename OurContainer::value_compare& cmp(sorted.value_comp());
-    if (hint == cont.end() || cmp(value, *hint)) {
-      if (hint == cont.begin()) {
-        po.increase_capacity(cont, cont.begin());
-        return cont.insert(cont.begin(), std::move(value));
-      }
-      if (cmp(*(hint - 1), value)) {
-        hint = po.increase_capacity(cont, hint);
-        return cont.insert(hint, std::move(value));
-      }
+template <typename Compare, typename Key, typename T>
+struct sorted_vector_enable_if_is_transparent<
+    void_t<typename Compare::is_transparent>,
+    Compare,
+    Key,
+    T> {
+  using type = T;
+};
+
+// This wrapper goes around a GrowthPolicy and provides iterator
+// preservation semantics, but only if the growth policy is not the
+// default (i.e. nothing).
+template <class Policy>
+struct growth_policy_wrapper : private Policy {
+  template <class Container, class Iterator>
+  Iterator increase_capacity(Container& c, Iterator desired_insertion) {
+    typedef typename Container::difference_type diff_t;
+    diff_t d = desired_insertion - c.begin();
+    Policy::increase_capacity(c);
+    return c.begin() + d;
+  }
+};
+template <>
+struct growth_policy_wrapper<void> {
+  template <class Container, class Iterator>
+  Iterator increase_capacity(Container&, Iterator it) {
+    return it;
+  }
+};
+
+/*
+ * This helper returns the distance between two iterators if it is
+ * possible to figure it out without messing up the range
+ * (i.e. unless they are InputIterators).  Otherwise this returns
+ * -1.
+ */
+template <class Iterator>
+int distance_if_multipass(Iterator first, Iterator last) {
+  typedef typename std::iterator_traits<Iterator>::iterator_category categ;
+  if (std::is_same<categ, std::input_iterator_tag>::value) {
+    return -1;
+  }
+  return std::distance(first, last);
+}
+
+template <class OurContainer, class Vector, class GrowthPolicy>
+typename OurContainer::iterator insert_with_hint(
+    OurContainer& sorted,
+    Vector& cont,
+    typename OurContainer::iterator hint,
+    typename OurContainer::value_type&& value,
+    GrowthPolicy& po) {
+  const typename OurContainer::value_compare& cmp(sorted.value_comp());
+  if (hint == cont.end() || cmp(value, *hint)) {
+    if (hint == cont.begin() || cmp(*(hint - 1), value)) {
+      hint = po.increase_capacity(cont, hint);
+      return cont.insert(hint, std::move(value));
+    } else {
       return sorted.insert(std::move(value)).first;
     }
+  }
 
-    if (cmp(*hint, value)) {
-      if (hint + 1 == cont.end() || cmp(value, *(hint + 1))) {
-        typename OurContainer::iterator it =
-          po.increase_capacity(cont, hint + 1);
-        return cont.insert(it, std::move(value));
-      }
+  if (cmp(*hint, value)) {
+    if (hint + 1 == cont.end() || cmp(value, *(hint + 1))) {
+      hint = po.increase_capacity(cont, hint + 1);
+      return cont.insert(hint, std::move(value));
+    } else {
+      return sorted.insert(std::move(value)).first;
     }
-
-    // Value and *hint did not compare, so they are equal keys.
-    return hint;
   }
 
+  // Value and *hint did not compare, so they are equal keys.
+  return hint;
+}
+
+template <class OurContainer, class Vector, class InputIterator>
+void bulk_insert(
+    OurContainer& sorted,
+    Vector& cont,
+    InputIterator first,
+    InputIterator last) {
+  // prevent deref of middle where middle == cont.end()
+  if (first == last) {
+    return;
+  }
+
+  auto const& cmp(sorted.value_comp());
+
+  int const d = distance_if_multipass(first, last);
+  if (d != -1) {
+    cont.reserve(cont.size() + d);
+  }
+  auto const prev_size = cont.size();
+
+  std::copy(first, last, std::back_inserter(cont));
+  auto const middle = cont.begin() + prev_size;
+  if (!std::is_sorted(middle, cont.end(), cmp)) {
+    std::sort(middle, cont.end(), cmp);
+  }
+  if (middle != cont.begin() && !cmp(*(middle - 1), *middle)) {
+    std::inplace_merge(cont.begin(), middle, cont.end(), cmp);
+    cont.erase(
+        std::unique(
+            cont.begin(),
+            cont.end(),
+            [&](typename OurContainer::value_type const& a,
+                typename OurContainer::value_type const& b) {
+              return !cmp(a, b) && !cmp(b, a);
+            }),
+        cont.end());
+  }
 }
+} // namespace detail
 
 //////////////////////////////////////////////////////////////////////
 
@@ -162,47 +211,50 @@ namespace detail {
  * @author Akhil Wable    <akhil@fb.com>
  * @author Jordan DeLong  <delong.j@fb.com>
  */
-template<class T,
-         class Compare      = std::less<T>,
-         class Allocator    = std::allocator<T>,
-         class GrowthPolicy = void>
+template <
+    class T,
+    class Compare = std::less<T>,
+    class Allocator = std::allocator<T>,
+    class GrowthPolicy = void,
+    class Container = std::vector<T, Allocator>>
 class sorted_vector_set
-  : boost::totally_ordered1<
-      sorted_vector_set<T,Compare,Allocator,GrowthPolicy>
-    , detail::growth_policy_wrapper<GrowthPolicy> >
-{
-  typedef std::vector<T,Allocator> ContainerT;
-
+    : boost::totally_ordered1<
+          sorted_vector_set<T, Compare, Allocator, GrowthPolicy>,
+          detail::growth_policy_wrapper<GrowthPolicy>> {
   detail::growth_policy_wrapper<GrowthPolicy>&
   get_growth_policy() { return *this; }
 
-public:
+  template <typename K, typename V, typename C = Compare>
+  using if_is_transparent =
+      _t<detail::sorted_vector_enable_if_is_transparent<void, C, K, V>>;
+
+ public:
   typedef T       value_type;
   typedef T       key_type;
   typedef Compare key_compare;
   typedef Compare value_compare;
 
-  typedef typename ContainerT::pointer                pointer;
-  typedef typename ContainerT::reference              reference;
-  typedef typename ContainerT::const_reference        const_reference;
+  typedef typename Container::pointer pointer;
+  typedef typename Container::reference reference;
+  typedef typename Container::const_reference const_reference;
   /*
    * XXX: Our normal iterator ought to also be a constant iterator
    * (cf. Defect Report 103 for std::set), but this is a bit more of a
    * pain.
    */
-  typedef typename ContainerT::iterator               iterator;
-  typedef typename ContainerT::const_iterator         const_iterator;
-  typedef typename ContainerT::difference_type        difference_type;
-  typedef typename ContainerT::size_type              size_type;
-  typedef typename ContainerT::reverse_iterator       reverse_iterator;
-  typedef typename ContainerT::const_reverse_iterator const_reverse_iterator;
+  typedef typename Container::iterator iterator;
+  typedef typename Container::const_iterator const_iterator;
+  typedef typename Container::difference_type difference_type;
+  typedef typename Container::size_type size_type;
+  typedef typename Container::reverse_iterator reverse_iterator;
+  typedef typename Container::const_reverse_iterator const_reverse_iterator;
 
   explicit sorted_vector_set(const Compare& comp = Compare(),
                              const Allocator& alloc = Allocator())
     : m_(comp, alloc)
   {}
 
-  template<class InputIterator>
+  template <class InputIterator>
   explicit sorted_vector_set(
       InputIterator first,
       InputIterator last,
@@ -215,7 +267,7 @@ public:
     insert(first, last);
   }
 
-  explicit sorted_vector_set(
+  /* implicit */ sorted_vector_set(
       std::initializer_list<value_type> list,
       const Compare& comp = Compare(),
       const Allocator& alloc = Allocator())
@@ -224,12 +276,30 @@ public:
     insert(list.begin(), list.end());
   }
 
+  // Construct a sorted_vector_set by stealing the storage of a prefilled
+  // container. The container need not be sorted already. This supports
+  // bulk construction of sorted_vector_set with zero allocations, not counting
+  // those performed by the caller. (The iterator range constructor performs at
+  // least one allocation).
+  //
+  // Note that `sorted_vector_set(const Container& container)` is not provided,
+  // since the purpose of this constructor is to avoid an unnecessary copy.
+  explicit sorted_vector_set(
+      Container&& container,
+      const Compare& comp = Compare())
+      : m_(comp, container.get_allocator()) {
+    std::sort(container.begin(), container.end(), value_comp());
+    m_.cont_.swap(container);
+  }
+
   key_compare key_comp() const { return m_; }
   value_compare value_comp() const { return m_; }
 
   iterator begin()                      { return m_.cont_.begin();  }
   iterator end()                        { return m_.cont_.end();    }
+  const_iterator cbegin() const         { return m_.cont_.cbegin(); }
   const_iterator begin() const          { return m_.cont_.begin();  }
+  const_iterator cend() const           { return m_.cont_.cend();   }
   const_iterator end() const            { return m_.cont_.end();    }
   reverse_iterator rbegin()             { return m_.cont_.rbegin(); }
   reverse_iterator rend()               { return m_.cont_.rend();   }
@@ -266,19 +336,13 @@ public:
       get_growth_policy());
   }
 
-  template<class InputIterator>
+  template <class InputIterator>
   void insert(InputIterator first, InputIterator last) {
-    int d = detail::distance_if_multipass(first, last);
-    if (d != -1) {
-      m_.cont_.reserve(m_.cont_.size() + d);
-    }
-    for (; first != last; ++first) {
-      insert(end(), *first);
-    }
+    detail::bulk_insert(*this, m_.cont_, first, last);
   }
 
   size_type erase(const key_type& key) {
-    iterator it = lower_bound(key);
+    iterator it = find(key);
     if (it == end()) {
       return 0;
     }
@@ -295,23 +359,32 @@ public:
   }
 
   iterator find(const key_type& key) {
-    iterator it = lower_bound(key);
-    if (it == end() || !key_comp()(key, *it))
-      return it;
-    return end();
+    return find(*this, key);
   }
 
   const_iterator find(const key_type& key) const {
-    const_iterator it = lower_bound(key);
-    if (it == end() || !key_comp()(key, *it))
-      return it;
-    return end();
+    return find(*this, key);
+  }
+
+  template <typename K>
+  if_is_transparent<K, iterator> find(const K& key) {
+    return find(*this, key);
+  }
+
+  template <typename K>
+  if_is_transparent<K, const_iterator> find(const K& key) const {
+    return find(*this, key);
   }
 
   size_type count(const key_type& key) const {
     return find(key) == end() ? 0 : 1;
   }
 
+  template <typename K>
+  if_is_transparent<K, size_type> count(const K& key) const {
+    return find(key) == end() ? 0 : 1;
+  }
+
   iterator lower_bound(const key_type& key) {
     return std::lower_bound(begin(), end(), key, key_comp());
   }
@@ -320,6 +393,16 @@ public:
     return std::lower_bound(begin(), end(), key, key_comp());
   }
 
+  template <typename K>
+  if_is_transparent<K, iterator> lower_bound(const K& key) {
+    return std::lower_bound(begin(), end(), key, key_comp());
+  }
+
+  template <typename K>
+  if_is_transparent<K, const_iterator> lower_bound(const K& key) const {
+    return std::lower_bound(begin(), end(), key, key_comp());
+  }
+
   iterator upper_bound(const key_type& key) {
     return std::upper_bound(begin(), end(), key, key_comp());
   }
@@ -328,12 +411,34 @@ public:
     return std::upper_bound(begin(), end(), key, key_comp());
   }
 
-  std::pair<iterator,iterator> equal_range(const key_type& key) {
+  template <typename K>
+  if_is_transparent<K, iterator> upper_bound(const K& key) {
+    return std::upper_bound(begin(), end(), key, key_comp());
+  }
+
+  template <typename K>
+  if_is_transparent<K, const_iterator> upper_bound(const K& key) const {
+    return std::upper_bound(begin(), end(), key, key_comp());
+  }
+
+  std::pair<iterator, iterator> equal_range(const key_type& key) {
+    return std::equal_range(begin(), end(), key, key_comp());
+  }
+
+  std::pair<const_iterator, const_iterator> equal_range(
+      const key_type& key) const {
     return std::equal_range(begin(), end(), key, key_comp());
   }
 
-  std::pair<const_iterator,const_iterator>
-  equal_range(const key_type& key) const {
+  template <typename K>
+  if_is_transparent<K, std::pair<iterator, iterator>> equal_range(
+      const K& key) {
+    return std::equal_range(begin(), end(), key, key_comp());
+  }
+
+  template <typename K>
+  if_is_transparent<K, std::pair<const_iterator, const_iterator>> equal_range(
+      const K& key) const {
     return std::equal_range(begin(), end(), key, key_comp());
   }
 
@@ -354,7 +459,7 @@ public:
     return m_.cont_ < other.m_.cont_;
   }
 
-private:
+ private:
   /*
    * This structure derives from the comparison object in order to
    * make use of the empty base class optimization if our comparison
@@ -371,12 +476,26 @@ private:
       : Compare(c)
       , cont_(alloc)
     {}
-    ContainerT cont_;
+    Container cont_;
   } m_;
+
+  template <typename Self>
+  using self_iterator_t = _t<
+      std::conditional<std::is_const<Self>::value, const_iterator, iterator>>;
+
+  template <typename Self, typename K>
+  static self_iterator_t<Self> find(Self& self, K const& key) {
+    auto end = self.end();
+    auto it = self.lower_bound(key);
+    if (it == end || !self.key_comp()(key, *it)) {
+      return it;
+    }
+    return end;
+  }
 };
 
 // Swap function that can be found using ADL.
-template<class T, class C, class A, class G>
+template <class T, class C, class A, class G>
 inline void swap(sorted_vector_set<T,C,A,G>& a,
                  sorted_vector_set<T,C,A,G>& b) {
   return a.swap(b);
@@ -399,22 +518,25 @@ inline void swap(sorted_vector_set<T,C,A,G>& a,
  * @author Akhil Wable    <akhil@fb.com>
  * @author Jordan DeLong  <delong.j@fb.com>
  */
-template<class Key,
-         class Value,
-         class Compare        = std::less<Key>,
-         class Allocator      = std::allocator<std::pair<Key,Value> >,
-         class GrowthPolicy   = void>
+template <
+    class Key,
+    class Value,
+    class Compare = std::less<Key>,
+    class Allocator = std::allocator<std::pair<Key, Value>>,
+    class GrowthPolicy = void,
+    class Container = std::vector<std::pair<Key, Value>, Allocator>>
 class sorted_vector_map
-  : boost::totally_ordered1<
-      sorted_vector_map<Key,Value,Compare,Allocator,GrowthPolicy>
-    , detail::growth_policy_wrapper<GrowthPolicy> >
-{
-  typedef std::vector<std::pair<Key,Value>,Allocator> ContainerT;
-
+    : boost::totally_ordered1<
+          sorted_vector_map<Key, Value, Compare, Allocator, GrowthPolicy>,
+          detail::growth_policy_wrapper<GrowthPolicy>> {
   detail::growth_policy_wrapper<GrowthPolicy>&
   get_growth_policy() { return *this; }
 
-public:
+  template <typename K, typename V, typename C = Compare>
+  using if_is_transparent =
+      _t<detail::sorted_vector_enable_if_is_transparent<void, C, K, V>>;
+
+ public:
   typedef Key                                       key_type;
   typedef Value                                     mapped_type;
   typedef std::pair<key_type,mapped_type>           value_type;
@@ -425,27 +547,27 @@ public:
       return Compare::operator()(a.first, b.first);
     }
 
-  protected:
+   protected:
     friend class sorted_vector_map;
     explicit value_compare(const Compare& c) : Compare(c) {}
   };
 
-  typedef typename ContainerT::pointer                pointer;
-  typedef typename ContainerT::reference              reference;
-  typedef typename ContainerT::const_reference        const_reference;
-  typedef typename ContainerT::iterator               iterator;
-  typedef typename ContainerT::const_iterator         const_iterator;
-  typedef typename ContainerT::difference_type        difference_type;
-  typedef typename ContainerT::size_type              size_type;
-  typedef typename ContainerT::reverse_iterator       reverse_iterator;
-  typedef typename ContainerT::const_reverse_iterator const_reverse_iterator;
+  typedef typename Container::pointer pointer;
+  typedef typename Container::reference reference;
+  typedef typename Container::const_reference const_reference;
+  typedef typename Container::iterator iterator;
+  typedef typename Container::const_iterator const_iterator;
+  typedef typename Container::difference_type difference_type;
+  typedef typename Container::size_type size_type;
+  typedef typename Container::reverse_iterator reverse_iterator;
+  typedef typename Container::const_reverse_iterator const_reverse_iterator;
 
   explicit sorted_vector_map(const Compare& comp = Compare(),
                              const Allocator& alloc = Allocator())
     : m_(value_compare(comp), alloc)
   {}
 
-  template<class InputIterator>
+  template <class InputIterator>
   explicit sorted_vector_map(
       InputIterator first,
       InputIterator last,
@@ -465,12 +587,30 @@ public:
     insert(list.begin(), list.end());
   }
 
+  // Construct a sorted_vector_map by stealing the storage of a prefilled
+  // container. The container need not be sorted already. This supports
+  // bulk construction of sorted_vector_map with zero allocations, not counting
+  // those performed by the caller. (The iterator range constructor performs at
+  // least one allocation).
+  //
+  // Note that `sorted_vector_map(const Container& container)` is not provided,
+  // since the purpose of this constructor is to avoid an unnecessary copy.
+  explicit sorted_vector_map(
+      Container&& container,
+      const Compare& comp = Compare())
+      : m_(value_compare(comp), container.get_allocator()) {
+    std::sort(container.begin(), container.end(), value_comp());
+    m_.cont_.swap(container);
+  }
+
   key_compare key_comp() const { return m_; }
   value_compare value_comp() const { return m_; }
 
   iterator begin()                      { return m_.cont_.begin();  }
   iterator end()                        { return m_.cont_.end();    }
+  const_iterator cbegin() const         { return m_.cont_.cbegin(); }
   const_iterator begin() const          { return m_.cont_.begin();  }
+  const_iterator cend() const           { return m_.cont_.cend();   }
   const_iterator end() const            { return m_.cont_.end();    }
   reverse_iterator rbegin()             { return m_.cont_.rbegin(); }
   reverse_iterator rend()               { return m_.cont_.rend();   }
@@ -507,15 +647,9 @@ public:
       get_growth_policy());
   }
 
-  template<class InputIterator>
+  template <class InputIterator>
   void insert(InputIterator first, InputIterator last) {
-    int d = detail::distance_if_multipass(first, last);
-    if (d != -1) {
-      m_.cont_.reserve(m_.cont_.size() + d);
-    }
-    for (; first != last; ++first) {
-      insert(end(), *first);
-    }
+    detail::bulk_insert(*this, m_.cont_, first, last);
   }
 
   size_type erase(const key_type& key) {
@@ -536,17 +670,21 @@ public:
   }
 
   iterator find(const key_type& key) {
-    iterator it = lower_bound(key);
-    if (it == end() || !key_comp()(key, it->first))
-      return it;
-    return end();
+    return find(*this, key);
   }
 
   const_iterator find(const key_type& key) const {
-    const_iterator it = lower_bound(key);
-    if (it == end() || !key_comp()(key, it->first))
-      return it;
-    return end();
+    return find(*this, key);
+  }
+
+  template <typename K>
+  if_is_transparent<K, iterator> find(const K& key) {
+    return find(*this, key);
+  }
+
+  template <typename K>
+  if_is_transparent<K, const_iterator> find(const K& key) const {
+    return find(*this, key);
   }
 
   mapped_type& at(const key_type& key) {
@@ -554,7 +692,7 @@ public:
     if (it != end()) {
       return it->second;
     }
-    throw std::out_of_range("sorted_vector_map::at");
+    std::__throw_out_of_range("sorted_vector_map::at");
   }
 
   const mapped_type& at(const key_type& key) const {
@@ -562,61 +700,73 @@ public:
     if (it != end()) {
       return it->second;
     }
-    throw std::out_of_range("sorted_vector_map::at");
+    std::__throw_out_of_range("sorted_vector_map::at");
   }
 
   size_type count(const key_type& key) const {
     return find(key) == end() ? 0 : 1;
   }
 
+  template <typename K>
+  if_is_transparent<K, size_type> count(const K& key) const {
+    return find(key) == end() ? 0 : 1;
+  }
+
   iterator lower_bound(const key_type& key) {
-    auto c = key_comp();
-    auto f = [&](const value_type& a, const key_type& b) {
-      return c(a.first, b);
-    };
-    return std::lower_bound(begin(), end(), key, f);
+    return lower_bound(*this, key);
   }
 
   const_iterator lower_bound(const key_type& key) const {
-    auto c = key_comp();
-    auto f = [&](const value_type& a, const key_type& b) {
-      return c(a.first, b);
-    };
-    return std::lower_bound(begin(), end(), key, f);
+    return lower_bound(*this, key);
+  }
+
+  template <typename K>
+  if_is_transparent<K, iterator> lower_bound(const K& key) {
+    return lower_bound(*this, key);
+  }
+
+  template <typename K>
+  if_is_transparent<K, const_iterator> lower_bound(const K& key) const {
+    return lower_bound(*this, key);
   }
 
   iterator upper_bound(const key_type& key) {
-    auto c = key_comp();
-    auto f = [&](const key_type& a, const value_type& b) {
-      return c(a, b.first);
-    };
-    return std::upper_bound(begin(), end(), key, f);
+    return upper_bound(*this, key);
   }
 
   const_iterator upper_bound(const key_type& key) const {
-    auto c = key_comp();
-    auto f = [&](const key_type& a, const value_type& b) {
-      return c(a, b.first);
-    };
-    return std::upper_bound(begin(), end(), key, f);
+    return upper_bound(*this, key);
   }
 
-  std::pair<iterator,iterator> equal_range(const key_type& key) {
-    // Note: std::equal_range can't be passed a functor that takes
-    // argument types different from the iterator value_type, so we
-    // have to do this.
-    iterator low = lower_bound(key);
-    auto c = key_comp();
-    auto f = [&](const key_type& a, const value_type& b) {
-      return c(a, b.first);
-    };
-    iterator high = std::upper_bound(low, end(), key, f);
-    return std::make_pair(low, high);
+  template <typename K>
+  if_is_transparent<K, iterator> upper_bound(const K& key) {
+    return upper_bound(*this, key);
+  }
+
+  template <typename K>
+  if_is_transparent<K, const_iterator> upper_bound(const K& key) const {
+    return upper_bound(*this, key);
+  }
+
+  std::pair<iterator, iterator> equal_range(const key_type& key) {
+    return equal_range(*this, key);
+  }
+
+  std::pair<const_iterator, const_iterator> equal_range(
+      const key_type& key) const {
+    return equal_range(*this, key);
+  }
+
+  template <typename K>
+  if_is_transparent<K, std::pair<iterator, iterator>> equal_range(
+      const K& key) {
+    return equal_range(*this, key);
   }
 
-  std::pair<const_iterator,const_iterator>
-  equal_range(const key_type& key) const {
-    return const_cast<sorted_vector_map*>(this)->equal_range(key);
+  template <typename K>
+  if_is_transparent<K, std::pair<const_iterator, const_iterator>> equal_range(
+      const K& key) const {
+    return equal_range(*this, key);
   }
 
   // Nothrow as long as swap() on the Compare type is nothrow.
@@ -644,7 +794,7 @@ public:
     return m_.cont_ < other.m_.cont_;
   }
 
-private:
+ private:
   // This is to get the empty base optimization; see the comment in
   // sorted_vector_set.
   struct EBO : value_compare {
@@ -652,12 +802,52 @@ private:
       : value_compare(c)
       , cont_(alloc)
     {}
-    ContainerT cont_;
+    Container cont_;
   } m_;
+
+  template <typename Self>
+  using self_iterator_t = _t<
+      std::conditional<std::is_const<Self>::value, const_iterator, iterator>>;
+
+  template <typename Self, typename K>
+  static self_iterator_t<Self> find(Self& self, K const& key) {
+    auto end = self.end();
+    auto it = self.lower_bound(key);
+    if (it == end || !self.key_comp()(key, it->first)) {
+      return it;
+    }
+    return end;
+  }
+
+  template <typename Self, typename K>
+  static self_iterator_t<Self> lower_bound(Self& self, K const& key) {
+    auto f = [c = self.key_comp()](value_type const& a, K const& b) {
+      return c(a.first, b);
+    };
+    return std::lower_bound(self.begin(), self.end(), key, f);
+  }
+
+  template <typename Self, typename K>
+  static self_iterator_t<Self> upper_bound(Self& self, K const& key) {
+    auto f = [c = self.key_comp()](K const& a, value_type const& b) {
+      return c(a, b.first);
+    };
+    return std::upper_bound(self.begin(), self.end(), key, f);
+  }
+
+  template <typename Self, typename K>
+  static std::pair<self_iterator_t<Self>, self_iterator_t<Self>> equal_range(
+      Self& self,
+      K const& key) {
+    // Note: std::equal_range can't be passed a functor that takes
+    // argument types different from the iterator value_type, so we
+    // have to do this.
+    return {lower_bound(self, key), upper_bound(self, key)};
+  }
 };
 
 // Swap function that can be found using ADL.
-template<class K, class V, class C, class A, class G>
+template <class K, class V, class C, class A, class G>
 inline void swap(sorted_vector_map<K,V,C,A,G>& a,
                  sorted_vector_map<K,V,C,A,G>& b) {
   return a.swap(b);
@@ -665,4 +855,4 @@ inline void swap(sorted_vector_map<K,V,C,A,G>& a,
 
 //////////////////////////////////////////////////////////////////////
 
-}
+} // namespace folly