SERVER-38668 Use ordered_unique_range_t when creating flat_set from sorted vector to get fast path in boost.

3 files changed, 25 insertions, 2 deletions

diff --git a/src/mongo/bson/bson_comparator_interface_base.h b/src/mongo/bson/bson_comparator_interface_base.h
index 74a30aeb05b..494e4498b11 100644
--- a/src/mongo/bson/bson_comparator_interface_base.h
+++ b/src/mongo/bson/bson_comparator_interface_base.h
@@ -253,6 +253,13 @@ protected:
         return FlatSet(elements.begin(), elements.end(), LessThan(this));
     }
 
+    template <typename InputIterator>
+    FlatSet makeFlatSetFromSortedUnique(InputIterator begin, InputIterator end) const {
+        dassert(std::is_sorted(begin, end, LessThan(this)));
+        dassert(std::adjacent_find(begin, end, EqualTo(this)) == end);
+        return FlatSet(boost::container::ordered_unique_range_t(), begin, end, LessThan(this));
+    }
+
     UnorderedSet makeUnorderedSet(std::initializer_list<T> init = {}) const {
         return UnorderedSet(init, 0, Hasher(this), EqualTo(this));
     }
diff --git a/src/mongo/bson/bsonelement_comparator_interface.h b/src/mongo/bson/bsonelement_comparator_interface.h
index 4e6ef65faaf..2a94ee7afe5 100644
--- a/src/mongo/bson/bsonelement_comparator_interface.h
+++ b/src/mongo/bson/bsonelement_comparator_interface.h
@@ -74,6 +74,16 @@ public:
     }
 
     /**
+     * Constructs a BSONEltFlatSet whose equivalence classes are given by this comparator. This
+     * comparator must outlive the returned set.
+     * The elements in the input range must be sorted and unique.
+     */
+    template <typename InputIterator>
+    FlatSet makeBSONEltFlatSetFromSortedUniqueRange(InputIterator begin, InputIterator end) const {
+        return makeFlatSetFromSortedUnique(begin, end);
+    }
+
+    /**
      * Constructs a BSONEltUnorderedSet whose equivalence classes are given by this
      * comparator. This comparator must outlive the returned set.
      */
diff --git a/src/mongo/db/matcher/expression_leaf.cpp b/src/mongo/db/matcher/expression_leaf.cpp
index 42c61fbea05..ad4c90e7d22 100644
--- a/src/mongo/db/matcher/expression_leaf.cpp
+++ b/src/mongo/db/matcher/expression_leaf.cpp
@@ -509,7 +509,10 @@ void InMatchExpression::_doSetCollator(const CollatorInterface* collator) {
     }
 
     // We need to re-compute '_equalitySet', since our set comparator has changed.
-    _equalitySet = _eltCmp.makeBSONEltFlatSet(_originalEqualityVector);
+    _equalitySet = _eltCmp.makeBSONEltFlatSetFromSortedUniqueRange(
+        _originalEqualityVector.begin(),
+        std::unique(
+            _originalEqualityVector.begin(), _originalEqualityVector.end(), _eltCmp.makeEqualTo()));
 }
 
 Status InMatchExpression::setEqualities(std::vector<BSONElement> equalities) {
@@ -538,7 +541,10 @@ Status InMatchExpression::setEqualities(std::vector<BSONElement> equalities) {
             _originalEqualityVector.begin(), _originalEqualityVector.end(), _eltCmp.makeLessThan());
     }
 
-    _equalitySet = _eltCmp.makeBSONEltFlatSet(_originalEqualityVector);
+    _equalitySet = _eltCmp.makeBSONEltFlatSetFromSortedUniqueRange(
+        _originalEqualityVector.begin(),
+        std::unique(
+            _originalEqualityVector.begin(), _originalEqualityVector.end(), _eltCmp.makeEqualTo()));
 
     return Status::OK();
 }