From cc4eb4c8277e04ba1e2a3fac5db8655b4994e7f2 Mon Sep 17 00:00:00 2001
From: Marc Celani <marccelani@fb.com>
Date: Mon, 17 Mar 2014 09:17:50 -0700
Subject: [PATCH] sorted_vector_types have move inserts

Summary: sorted_vector_types were missing move inserts that come with std::map in c++11. This prevents me from using move iterators in folly::merge use case.

Test Plan: unit tests

Reviewed By: delong.j@fb.com

FB internal diff: D1223426
---
 folly/sorted_vector_types.h       | 34 +++++++++++++++++++++++--------
 folly/test/sorted_vector_test.cpp | 18 ++++++++++++++++
 2 files changed, 43 insertions(+), 9 deletions(-)

diff --git a/folly/sorted_vector_types.h b/folly/sorted_vector_types.h
index e8486055..86b57870 100644
--- a/folly/sorted_vector_types.h
+++ b/folly/sorted_vector_types.h
@@ -116,27 +116,27 @@ namespace detail {
   insert_with_hint(OurContainer& sorted,
                    Vector& cont,
                    typename OurContainer::iterator hint,
-                   typename OurContainer::value_type value,
+                   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(), value);
+        return cont.insert(cont.begin(), std::move(value));
       }
       if (cmp(*(hint - 1), value)) {
         hint = po.increase_capacity(cont, hint);
-        return cont.insert(hint, value);
+        return cont.insert(hint, std::move(value));
       }
-      return sorted.insert(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, value);
+        return cont.insert(it, std::move(value));
       }
     }
 
@@ -244,16 +244,24 @@ public:
   size_type capacity() const    { return m_.cont_.capacity(); }
 
   std::pair<iterator,bool> insert(const value_type& value) {
+    return insert(value_type(value));
+  }
+
+  std::pair<iterator,bool> insert(value_type&& value) {
     iterator it = lower_bound(value);
     if (it == end() || value_comp()(value, *it)) {
       it = get_growth_policy().increase_capacity(m_.cont_, it);
-      return std::make_pair(m_.cont_.insert(it, value), true);
+      return std::make_pair(m_.cont_.insert(it, std::move(value)), true);
     }
     return std::make_pair(it, false);
   }
 
   iterator insert(iterator hint, const value_type& value) {
-    return detail::insert_with_hint(*this, m_.cont_, hint, value,
+    return insert(hint, value_type(value));
+  }
+
+  iterator insert(iterator hint, value_type&& value) {
+    return detail::insert_with_hint(*this, m_.cont_, hint, std::move(value),
       get_growth_policy());
   }
 
@@ -479,16 +487,24 @@ public:
   size_type capacity() const    { return m_.cont_.capacity(); }
 
   std::pair<iterator,bool> insert(const value_type& value) {
+    return insert(value_type(value));
+  }
+
+  std::pair<iterator,bool> insert(value_type&& value) {
     iterator it = lower_bound(value.first);
     if (it == end() || value_comp()(value, *it)) {
       it = get_growth_policy().increase_capacity(m_.cont_, it);
-      return std::make_pair(m_.cont_.insert(it, value), true);
+      return std::make_pair(m_.cont_.insert(it, std::move(value)), true);
     }
     return std::make_pair(it, false);
   }
 
   iterator insert(iterator hint, const value_type& value) {
-    return detail::insert_with_hint(*this, m_.cont_, hint, value,
+    return insert(hint, value_type(value));
+  }
+
+  iterator insert(iterator hint, value_type&& value) {
+    return detail::insert_with_hint(*this, m_.cont_, hint, std::move(value),
       get_growth_policy());
   }
 
diff --git a/folly/test/sorted_vector_test.cpp b/folly/test/sorted_vector_test.cpp
index 80038a0a..2ea86d3e 100644
--- a/folly/test/sorted_vector_test.cpp
+++ b/folly/test/sorted_vector_test.cpp
@@ -301,3 +301,21 @@ TEST(SortedVectorTest, EmptyTest) {
   EXPECT_TRUE(emptyMap.lower_bound(10) == emptyMap.end());
   EXPECT_TRUE(emptyMap.find(10) == emptyMap.end());
 }
+
+TEST(SortedVectorTest, MoveTest) {
+  sorted_vector_set<std::unique_ptr<int>> s;
+  s.insert(std::unique_ptr<int>(new int(5)));
+  s.insert(s.end(), std::unique_ptr<int>(new int(10)));
+  EXPECT_EQ(s.size(), 2);
+
+  for (const auto& p : s) {
+    EXPECT_TRUE(*p == 5 || *p == 10);
+  }
+
+  sorted_vector_map<int, std::unique_ptr<int>> m;
+  m.insert(std::make_pair(5, std::unique_ptr<int>(new int(5))));
+  m.insert(m.end(), std::make_pair(10, std::unique_ptr<int>(new int(10))));
+
+  EXPECT_EQ(*m[5], 5);
+  EXPECT_EQ(*m[10], 10);
+}
-- 
2.34.1