fix sorted_vector_{set,map} bulk_insert deduplication

Summary: this fixes the case where bulk inserting a range where the smallest element is equal to the largest element of the current set/map fails to deduplicate that element.

Reviewed By: mlogan, yfeldblum

Differential Revision: D5593284

fbshipit-source-id: 487500ee7a5e33f27c24321ad4a3c07a669fc26c

diff --git a/folly/sorted_vector_types.h b/folly/sorted_vector_types.h
index 7056ead2d2966c9d690ab90bf1f7c38cce83f83e..54f3cc26ab03b0eee54bbb583604b287d4576b9a 100644 (file)
--- a/folly/sorted_vector_types.h
+++ b/folly/sorted_vector_types.h
@@ -167,7 +167,7 @@ namespace detail {
     if (!std::is_sorted(middle, cont.end(), cmp)) {
       std::sort(middle, cont.end(), cmp);
     }
-    if (middle != cont.begin() && cmp(*middle, *(middle - 1))) {
+    if (middle != cont.begin() && !cmp(*(middle - 1), *middle)) {
       std::inplace_merge(cont.begin(), middle, cont.end(), cmp);
       cont.erase(
           std::unique(

diff --git a/folly/test/sorted_vector_test.cpp b/folly/test/sorted_vector_test.cpp
index 2afae8afdfee68d4fe848158bee10cbd7515ef0c..0dcd8d006644c94b9dd4420f8f47429fd21c5878 100644 (file)
--- a/folly/test/sorted_vector_test.cpp
+++ b/folly/test/sorted_vector_test.cpp
@@ -403,6 +403,23 @@ TEST(SortedVectorTypes, TestSetBulkInsertionSortMerge) {
       testing::ElementsAreArray({1, 2, 4, 5, 6, 7, 8, 10}));
 }
 
+TEST(SortedVectorTypes, TestSetBulkInsertionMiddleValuesEqualDuplication) {
+  auto s = makeVectorOfWrappers<CountCopyCtor, int>({4, 6, 8});
+
+  sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
+  check_invariant(vset);
+
+  s = makeVectorOfWrappers<CountCopyCtor, int>({8, 10, 12});
+
+  vset.insert(s.begin(), s.end());
+  check_invariant(vset);
+  EXPECT_EQ(vset.rbegin()->count_, 1);
+
+  EXPECT_THAT(
+      extractValues(vset),
+      testing::ElementsAreArray({4, 6, 8, 10, 12}));
+}
+
 TEST(SortedVectorTypes, TestSetBulkInsertionSortMergeDups) {
   auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});