X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=folly%2Fsorted_vector_types.h;h=41d26fc033dcb769fa2fabc954ec9bb2256a061d;hb=a130b23ab3fc1c0895c29f3d73597ea465f20bc3;hp=5d8d5344b5fa7caeedebca428d7c09ff72361975;hpb=3ffcb010fb7333a9ad6b233b47e1ecfdfb0fc2f0;p=folly.git

diff --git a/folly/sorted_vector_types.h b/folly/sorted_vector_types.h
index 5d8d5344..41d26fc0 100644
--- a/folly/sorted_vector_types.h
+++ b/folly/sorted_vector_types.h
@@ -122,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;
       }
     }
 
@@ -171,6 +169,15 @@ namespace detail {
     }
     if (middle != cont.begin() && cmp(*middle, *(middle - 1))) {
       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());
     }
   }
 }
@@ -253,6 +260,22 @@ 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_; }
 
@@ -490,6 +513,22 @@ 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_; }