[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

186–188

Could use a structure binding here?

189–191

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:
size_type count(const T &V) const {
     }
   }
 
   /// 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);
+  std::pair<const_iterator, bool> insert(const T &V) {
+    if (!isSmall()) {
+      SIterator SIt;
+      bool Inserted;
+      std::tie(SIt, Inserted) = Set.insert(V);
+      return std::make_pair(const_iterator(SIt), Inserted);
+    }
 
-    VIterator I = vfind(V);
-    if (I != Vector.end())    // Don't reinsert if it already exists.
-      return std::make_pair(None, false);
+    VIterator VIt = vfind(V);
+    if (VIt != Vector.end()) // Don't reinsert if it already exists.
+      return std::make_pair(const_iterator(VIt), 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));
 }