From ae32b8a574e14ab8eb345504bdde3ad65ebfd0d5 Mon Sep 17 00:00:00 2001 From: Nick Jiang Date: Wed, 9 Aug 2017 15:23:24 -0700 Subject: [PATCH] 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 --- folly/sorted_vector_types.h | 2 +- folly/test/sorted_vector_test.cpp | 17 +++++++++++++++++ 2 files changed, 18 insertions(+), 1 deletion(-) diff --git a/folly/sorted_vector_types.h b/folly/sorted_vector_types.h index 7056ead2..54f3cc26 100644 --- 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 2afae8af..0dcd8d00 100644 --- 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({4, 6, 8}); + + sorted_vector_set vset(s.begin(), s.end()); + check_invariant(vset); + + s = makeVectorOfWrappers({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({6, 4, 8, 2}); -- 2.34.1