X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=folly%2Fsorted_vector_types.h;h=54f3cc26ab03b0eee54bbb583604b287d4576b9a;hb=a95a6976020356513a4c0dc8a3c8557c0b2b4496;hp=df826299bf77929f4c28031a83d5cf0c879ba578;hpb=6215a88d9b95143e9067b8068ee3d335873633f1;p=folly.git

diff --git a/folly/sorted_vector_types.h b/folly/sorted_vector_types.h
index df826299..54f3cc26 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);
@@ -62,11 +62,13 @@
 #include <algorithm>
 #include <initializer_list>
 #include <iterator>
+#include <stdexcept>
+#include <type_traits>
 #include <utility>
 #include <vector>
+
 #include <boost/operators.hpp>
-#include <boost/bind.hpp>
-#include <boost/type_traits/is_same.hpp>
+#include <folly/portability/BitsFunctexcept.h>
 
 namespace folly {
 
@@ -77,9 +79,9 @@ 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>
+  template <class Policy>
   struct growth_policy_wrapper : private Policy {
-    template<class Container, class Iterator>
+    template <class Container, class Iterator>
     Iterator increase_capacity(Container& c, Iterator desired_insertion)
     {
       typedef typename Container::difference_type diff_t;
@@ -88,9 +90,9 @@ namespace detail {
       return c.begin() + d;
     }
   };
-  template<>
+  template <>
   struct growth_policy_wrapper<void> {
-    template<class Container, class Iterator>
+    template <class Container, class Iterator>
     Iterator increase_capacity(Container&, Iterator it) {
       return it;
     }
@@ -102,15 +104,15 @@ namespace detail {
    * (i.e. unless they are InputIterators).  Otherwise this returns
    * -1.
    */
-  template<class Iterator>
+  template <class Iterator>
   int distance_if_multipass(Iterator first, Iterator last) {
     typedef typename std::iterator_traits<Iterator>::iterator_category categ;
-    if (boost::is_same<categ,std::input_iterator_tag>::value)
+    if (std::is_same<categ,std::input_iterator_tag>::value)
       return -1;
     return std::distance(first, last);
   }
 
-  template<class OurContainer, class Vector, class GrowthPolicy>
+  template <class OurContainer, class Vector, class GrowthPolicy>
   typename OurContainer::iterator
   insert_with_hint(OurContainer& sorted,
                    Vector& cont,
@@ -120,22 +122,20 @@ namespace detail {
   {
     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)) {
+      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;
       }
-      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));
+        hint = po.increase_capacity(cont, hint + 1);
+        return cont.insert(hint, std::move(value));
+      } else {
+        return sorted.insert(std::move(value)).first;
       }
     }
 
@@ -143,6 +143,43 @@ namespace detail {
     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());
+    }
+  }
 }
 
 //////////////////////////////////////////////////////////////////////
@@ -161,10 +198,11 @@ 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 sorted_vector_set
   : boost::totally_ordered1<
       sorted_vector_set<T,Compare,Allocator,GrowthPolicy>
@@ -175,7 +213,7 @@ class sorted_vector_set
   detail::growth_policy_wrapper<GrowthPolicy>&
   get_growth_policy() { return *this; }
 
-public:
+ public:
   typedef T       value_type;
   typedef T       key_type;
   typedef Compare key_compare;
@@ -201,7 +239,7 @@ public:
     : m_(comp, alloc)
   {}
 
-  template<class InputIterator>
+  template <class InputIterator>
   explicit sorted_vector_set(
       InputIterator first,
       InputIterator last,
@@ -214,7 +252,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())
@@ -223,12 +261,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 ContainerT& container)` is not provided,
+  // since the purpose of this constructor is to avoid an unnecessary copy.
+  explicit sorted_vector_set(
+      ContainerT&& 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();   }
@@ -265,19 +321,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;
     }
@@ -353,7 +403,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
@@ -375,7 +425,7 @@ private:
 };
 
 // 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);
@@ -398,11 +448,12 @@ 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 sorted_vector_map
   : boost::totally_ordered1<
       sorted_vector_map<Key,Value,Compare,Allocator,GrowthPolicy>
@@ -413,21 +464,18 @@ class sorted_vector_map
   detail::growth_policy_wrapper<GrowthPolicy>&
   get_growth_policy() { return *this; }
 
-public:
+ public:
   typedef Key                                       key_type;
   typedef Value                                     mapped_type;
   typedef std::pair<key_type,mapped_type>           value_type;
   typedef Compare                                   key_compare;
 
-  struct value_compare
-    : std::binary_function<value_type,value_type,bool>
-    , private Compare
-  {
+  struct value_compare : private Compare {
     bool operator()(const value_type& a, const value_type& b) const {
       return Compare::operator()(a.first, b.first);
     }
 
-  protected:
+   protected:
     friend class sorted_vector_map;
     explicit value_compare(const Compare& c) : Compare(c) {}
   };
@@ -447,7 +495,7 @@ public:
     : m_(value_compare(comp), alloc)
   {}
 
-  template<class InputIterator>
+  template <class InputIterator>
   explicit sorted_vector_map(
       InputIterator first,
       InputIterator last,
@@ -467,12 +515,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 ContainerT& container)` is not provided,
+  // since the purpose of this constructor is to avoid an unnecessary copy.
+  explicit sorted_vector_map(
+      ContainerT&& 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();   }
@@ -509,15 +575,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) {
@@ -556,7 +616,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 {
@@ -564,7 +624,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");
   }
 
   size_type count(const key_type& key) const {
@@ -646,7 +706,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 {
@@ -659,7 +719,7 @@ private:
 };
 
 // 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);