[ADT] Allow SmallPtrSet to be used with a std::insert_iterator

[aaron.ballman]

Summary

Currently, the SmallPtrSet type allows inserting elements but it does not support inserting elements with a positional hint. The lack of this signature means that you cannot use SmallPtrSet with std::insert_iterator or std::inserter(), which makes some code constructs more awkward. For example, it would be nice to be able to write:

llvm::copy_if(Buffer, std::inserter(SomeSmallPtrSet, SomeSmallPtrSet.begin()), [](...) { return whatever(); });

The positional hint is unused by SmallPtrSet and the call is equivalent to calling insert() without a hint.

[dblaikie]

llvm/unittests/ADT/SmallPtrSetTest.cpp

407

I'd probably/prefer to make a direct call to the API, rather than testing it through a bunch of other container machinery. More isolated testing, clearer failures (not layers of template goo inside the standard library), etc.

(& my minor preference is towards using member begin/end unless the fully generic ADL call is needed (in which case you need llvm::adl_* functions or the raw using+unqualified call))

[aaron.ballman]

Updating based on review feedback.

llvm/unittests/ADT/SmallPtrSetTest.cpp

407

Does the new test look better to you?

[dblaikie]

llvm/unittests/ADT/SmallPtrSetTest.cpp

407

Sure thing!

[aaron.ballman]

Thanks for the review! I've commit in ec04e2850adc044d84c840d7c48ebe3291ec47f7

llvm/include/llvm/ADT/SmallPtrSet.h

public:
   /// Ptr. The bool component of the returned pair is true if and only if the
   /// insertion takes place, and the iterator component of the pair points to
   /// the element equal to Ptr.
   std::pair<iterator, bool> insert(PtrType Ptr) {
     auto p = insert_imp(PtrTraits::getAsVoidPointer(Ptr));
     return std::make_pair(makeIterator(p.first), p.second);
   }
 
+  /// Insert the given pointer with an iterator hint that is ignored. This is
+  /// identical to calling insert(Ptr), but allows SmallPtrSet to be used by
+  /// std::insert_iterator and std::inserter().
+  iterator insert(iterator, PtrType Ptr) {
+    return insert(Ptr).first;
+  }
+
   /// erase - If the set contains the specified pointer, remove it and return
   /// true, otherwise return false.
   bool erase(PtrType Ptr) {
     return erase_imp(PtrTraits::getAsVoidPointer(Ptr));
   }
   /// count - Return 1 if the specified pointer is in the set, 0 otherwise.
   size_type count(ConstPtrType Ptr) const {
     return find_imp(ConstPtrTraits::getAsVoidPointer(Ptr)) != EndPointer();

llvm/unittests/ADT/SmallPtrSetTest.cpp

 //===- llvm/unittest/ADT/SmallPtrSetTest.cpp ------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // SmallPtrSet unit tests.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/PointerIntPair.h"
 #include "llvm/Support/PointerLikeTypeTraits.h"
 #include "gtest/gtest.h"
+#include <algorithm>
+#include <iterator>
 
 using namespace llvm;
 
 TEST(SmallPtrSetTest, Assignment) {
   int buf[8];
   for (int i = 0; i < 8; ++i)
     buf[i] = 0;
 
TEST(SmallPtrSetTest, Contains) {
   EXPECT_FALSE(Set.contains(&buf[1]));
 
   Set.insert(&buf[1]);
   Set.insert(&buf[2]);
   EXPECT_TRUE(Set.contains(&buf[0]));
   EXPECT_TRUE(Set.contains(&buf[1]));
   EXPECT_TRUE(Set.contains(&buf[2]));
 }
+
+TEST(SmallPtrSetTest, InsertIterator) {
+  SmallPtrSet<int *, 5> Set;
+  int Vals[5] = {11, 22, 33, 44, 55};
+  int *Buf[5] = {&Vals[0], &Vals[1], &Vals[2], &Vals[3], &Vals[4]};
+
+  // Ensure that we can use SmallPtrSet with std::inserter().
+  std::copy(std::begin(Buf), std::end(Buf), std::inserter(Set, Set.begin()));
+
+  // Ensure that all of the values were copied into the set.
+  for (const auto *Ptr : Buf)
+    EXPECT_TRUE(Set.contains(Ptr));
+}