[ADT] Make SmallSet::insert(const T &) return const_iterator

[piggynl]

Summary

This patch makes SmallSet::insert(const T &) return std::pair<const_iterator, bool> instead of std::pair<NoneType, bool>. This will exactly match std::set's behavior and make deduplicating items with SmallSet easier.

[piggynl]

Update comments.

[dblaikie]

Sounds OK, with a minor improvement using structured bindings.

llvm/include/llvm/ADT/SmallSet.h

180–182

Could use a structure binding here?

186

Not sure the iterators need to be renamed - they're in distinct scopes and it'd probably be OK for them both to be named I despite them having different types.

[lattner]

nice, thank you for improving this!

[piggynl]

Revise according to @dblaikie's comments.

llvm/include/llvm/ADT/SmallSet.h

 class SmallSet {
   /// Use a SmallVector to hold the elements here (even though it will never
   /// reach its 'large' stage) to avoid calling the default ctors of elements
   /// we will never use.
   SmallVector<T, N> Vector;
   std::set<T, C> Set;
 
   using VIterator = typename SmallVector<T, N>::const_iterator;
+  using SIterator = typename std::set<T, C>::const_iterator;
   using mutable_iterator = typename SmallVector<T, N>::iterator;
 
   // In small mode SmallPtrSet uses linear search for the elements, so it is
   // not a good idea to choose this value too high. You may consider using a
   // DenseSet<> instead if you expect many elements in the set.
   static_assert(N <= 32, "N should be small");
 
 public:
if (isSmall()) {
       // Since the collection is small, just do a linear search.
       return vfind(V) == Vector.end() ? 0 : 1;
     } else {
       return Set.count(V);
     }
   }
 
   /// insert - Insert an element into the set if it isn't already there.
-  /// Returns true if the element is inserted (it was not in the set before).
-  /// The first value of the returned pair is unused and provided for
-  /// partial compatibility with the standard library self-associative container
-  /// concept.
-  // FIXME: Add iterators that abstract over the small and large form, and then
-  // return those here.
-  std::pair<NoneType, bool> insert(const T &V) {
-    if (!isSmall())
-      return std::make_pair(None, Set.insert(V).second);
+  /// Returns a pair. The first value of it is an iterator to the inserted
+  /// element or the existing element in the set. The second value is true
+  /// if the element is inserted (it was not in the set before).
+  std::pair<const_iterator, bool> insert(const T &V) {
+    if (!isSmall()) {
+      auto [I, Inserted] = Set.insert(V);
+      return std::make_pair(const_iterator(I), Inserted);
+    }
 
     VIterator I = vfind(V);
     if (I != Vector.end())    // Don't reinsert if it already exists.
-      return std::make_pair(None, false);
+      return std::make_pair(const_iterator(I), false);
     if (Vector.size() < N) {
       Vector.push_back(V);
-      return std::make_pair(None, true);
+      return std::make_pair(const_iterator(std::prev(Vector.end())), true);
     }
 
     // Otherwise, grow from vector to set.
     while (!Vector.empty()) {
       Set.insert(Vector.back());
       Vector.pop_back();
     }
-    Set.insert(V);
-    return std::make_pair(None, true);
+    return std::make_pair(const_iterator(Set.insert(V).first), true);
   }
 
   template <typename IterT>
   void insert(IterT I, IterT E) {
     for (; I != E; ++I)
       insert(*I);
   }
 

llvm/unittests/ADT/SmallSetTest.cpp

 #include <string>
 
 using namespace llvm;
 
 TEST(SmallSetTest, Insert) {
 
   SmallSet<int, 4> s1;
 
-  for (int i = 0; i < 4; i++)
-    s1.insert(i);
+  for (int i = 0; i < 4; i++) {
+    auto InsertResult = s1.insert(i);
+    EXPECT_EQ(*InsertResult.first, i);
+    EXPECT_EQ(InsertResult.second, true);
+  }
 
-  for (int i = 0; i < 4; i++)
-    s1.insert(i);
+  for (int i = 0; i < 4; i++) {
+    auto InsertResult = s1.insert(i);
+    EXPECT_EQ(*InsertResult.first, i);
+    EXPECT_EQ(InsertResult.second, false);
+  }
 
   EXPECT_EQ(4u, s1.size());
 
   for (int i = 0; i < 4; i++)
     EXPECT_EQ(1u, s1.count(i));
 
   EXPECT_EQ(0u, s1.count(4));
 }
 
 TEST(SmallSetTest, Grow) {
   SmallSet<int, 4> s1;
 
-  for (int i = 0; i < 8; i++)
-    s1.insert(i);
+  for (int i = 0; i < 8; i++) {
+    auto InsertResult = s1.insert(i);
+    EXPECT_EQ(*InsertResult.first, i);
+    EXPECT_EQ(InsertResult.second, true);
+  }
+
+  for (int i = 0; i < 8; i++) {
+    auto InsertResult = s1.insert(i);
+    EXPECT_EQ(*InsertResult.first, i);
+    EXPECT_EQ(InsertResult.second, false);
+  }
 
   EXPECT_EQ(8u, s1.size());
 
   for (int i = 0; i < 8; i++)
     EXPECT_EQ(1u, s1.count(i));
 
   EXPECT_EQ(0u, s1.count(8));
 }