From 3900132e235520bee366c554279af09ca4208667 Mon Sep 17 00:00:00 2001
From: Mark Logan <mlogan@fb.com>
Date: Thu, 23 Feb 2017 12:21:31 -0800
Subject: [PATCH] Remove duplicates during bulk insertion.

Summary:
antonl noticed that bulk_insert doesn't remove duplicates.
We now run a std::unique() pass after merging.

Reviewed By: yfeldblum

Differential Revision: D4595304

fbshipit-source-id: 538364150aeea64b95488da158c09e07a6597e7c
---
 folly/sorted_vector_types.h       |  8 ++++++++
 folly/test/sorted_vector_test.cpp | 34 +++++++++++++++++++++++++++++++
 2 files changed, 42 insertions(+)

diff --git a/folly/sorted_vector_types.h b/folly/sorted_vector_types.h
index 255b4518..f70f7979 100644
--- a/folly/sorted_vector_types.h
+++ b/folly/sorted_vector_types.h
@@ -171,6 +171,14 @@ namespace detail {
     }
     if (middle != cont.begin() && cmp(*middle, *(middle - 1))) {
       std::inplace_merge(cont.begin(), middle, cont.end(), cmp);
+      auto last = 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.erase(last, cont.end());
     }
   }
 }
diff --git a/folly/test/sorted_vector_test.cpp b/folly/test/sorted_vector_test.cpp
index 4805be24..9207fa03 100644
--- a/folly/test/sorted_vector_test.cpp
+++ b/folly/test/sorted_vector_test.cpp
@@ -388,6 +388,40 @@ TEST(SortedVectorTypes, TestSetBulkInsertionSortMerge) {
       testing::ElementsAreArray({1, 2, 4, 5, 6, 7, 8, 10}));
 }
 
+TEST(SortedVectorTypes, TestSetBulkInsertionSortMergeDups) {
+  auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
+
+  sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
+  check_invariant(vset);
+
+  // Add an unsorted range that will have to be merged in.
+  s = makeVectorOfWrappers<CountCopyCtor, int>({10, 6, 5, 2});
+
+  vset.insert(s.begin(), s.end());
+  check_invariant(vset);
+  EXPECT_EQ(vset.rbegin()->count_, 1);
+  EXPECT_THAT(
+      extractValues(vset), testing::ElementsAreArray({2, 4, 5, 6, 8, 10}));
+}
+
+TEST(SortedVectorTypes, TestSetInsertionDupsOneByOne) {
+  auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
+
+  sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
+  check_invariant(vset);
+
+  // Add an unsorted range that will have to be merged in.
+  s = makeVectorOfWrappers<CountCopyCtor, int>({10, 6, 5, 2});
+
+  for (const auto& elem : s) {
+    vset.insert(elem);
+  }
+  check_invariant(vset);
+  EXPECT_EQ(vset.rbegin()->count_, 3);
+  EXPECT_THAT(
+      extractValues(vset), testing::ElementsAreArray({2, 4, 5, 6, 8, 10}));
+}
+
 TEST(SortedVectorTypes, TestSetBulkInsertionSortNoMerge) {
   auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
 
-- 
2.34.1