[SetVector] Add erase() method

[junbuml]

Summary

Add erase() which returns an iterator pointing to the next element after the
erased one. This makes it possible to erase selected elements while iterating
over the SetVector :

while (I != E)
  if (test(*I))
    I = SetVector.erase(I);
  else
    ++I;

[dblaikie]

Test coverage?

[MatzeB]

LGTM, but should have a test and should not be committed until you are ready to commit code that is using it.

include/llvm/ADT/SetVector.h

154

If the description fits into 1 line you can leave out the "\brief".

163–165

It's probably best not to check the return value of set_.erase(). llvm::DensetSet does indeed return a bool for erase(), however we can also use an std::set as a set and that does return an iterator and not a bool.

[junbuml]

Added a unittest and addressed Matthias' comments.

[junbuml]

If reviewers are still okay with the test I added, I will commit this change. Once this change is committed, I will land D17889 which this use this erase() method.

[dblaikie]

unittests/ADT/SetVectorTest.cpp

58

Might be easier to test with vectors of ints, ratehr than vectors of int*s? Then you can just use literal 0, 1, and 2 rather than the address of an array element, etc

[junbuml]

Addressed David's comment.

[dblaikie]

include/llvm/ADT/SetVector.h

159–165

This seems like it's doing extra work to find the element in the vector, given an iterator in the vector to begin with - right?

Should just be:

set_.erase(V);
return vector_.erase(I);

or am I missing something? (don't mind if you keep the assert(set_.count(V)))

unittests/ADT/SetVectorTest.cpp

20

I'd just make these two named functions into test functions - rather than having the test function call them.

Also, seems like these tests are testing a whole bunch of other stuff (which, granted, isn't tested elsewhere - since SetVector had no unit tests - but if it's going to be tested should probably be tested separately (& in a separate commit))

So I'd probably simplify these tests down quite a bit:

TEST(SetVector, EraseTest) {
  SetVector<int> S;
  S.insert(0);
  S.insert(1);
  S.insert(2);

  auto I = S.erase(std::next(S.begin()));

  // Test that the returned iterator is the expected one-after-erase
  // and the size/contents is the expected sequence {0, 2}
  EXPECT_EQ(std::next(S.begin()), I);
  EXPECT_EQ(2u, S.size());
  EXPECT_EQ(0, S.front());
  EXPECT_EQ(2, S.back());
}

& I wouldn't bother testing SmallSetVector - you only changed SetVector, there's no need to test every possible instantiation of it.

[junbuml]

Simplified the unittest as David commented. Please see my inline comment about using find().

include/llvm/ADT/SetVector.h

159–165

We cannot use the given iterator I directly because it's const_iterator which cannot be used in vector_.erase(). Please let me know if there is any better way to get a non const iterator which we can pass to vector_.erase().

[• dberlin]

And if you for some reason, can't do that (I'd like to understand why not):

iterator newIter (vector_.begin());
std::advance(newIter, std::distance<const_iterator>(newIter, I));

will work.
(and not require finding for random access containers)

[dblaikie]

include/llvm/ADT/SetVector.h

159–165

Ah, right - I've fixed SmallVector (in r264330) to match C++11's spec here, where the iterators to erase are const_iterators. That should help.

[junbuml]

Removed find() based on David's fix (r264330).

[dblaikie]

Looks good - please commit after removing the extra test & asserts.

include/llvm/ADT/SetVector.h

159–160

While I see these comparisons in SmallVector (which perhaps is where you got the idea) they're actually unspecified (see C++ standard 5.9 [expr.rel]/2) - if we used std::less they would be well defined, but I think we could just leave them out.

unittests/ADT/SetVectorTest.cpp

35–50

Remove this test - I don't think we gain enough benefit/improved coverage to keep it.

[junbuml]

Thanks David for the quick review. I will land it after fixing your comments.

[junbuml]

Looks like this broke the build:
http://lab.llvm.org:8011/builders/clang-s390x-linux/builds/2460

I will revert it.

[junbuml]

Reverted in r264420

[dblaikie]

Probably a buggy standard library implementation? Would be good to know
which version of libstdc++ is running there.

In any case, might have to process the iterator in some way to get the
non-const iterator to work aorund such a buggy implementation. (Danny
mentioned one possibility)

[junbuml]

/usr/include/c++/4.8/bits/vector.tcc:134:5: note: std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::erase(std::vector<_Tp, _Alloc>::iterator) [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::iterator = gnu_cxx::normal_iterator<int*, std::vector<int> >; typename std::_Vector_base<_Tp, _Alloc>::pointer = int*]

From the Buildbot log above c++4.8 seems to be used which do not have c++11's definition of vector.erase(). Let me get the a non-const iterator as Danny mentioned.

[• dberlin]

Does it have the range definition?
(and what is our minimum version required at this point?)

[junbuml]

To avoid the builedbot failure, pass non-const iterator to vector_.erase().

[junbuml]

Fixed David's comment.

[dblaikie]

Looks good - please commit

[junbuml]

Recommitted in r264450. Thank you so much for the review !

include/llvm/ADT/SetVector.h

if (set_.erase(X)) {
         std::find(vector_.begin(), vector_.end(), X);
       assert(I != vector_.end() && "Corrupted SetVector instances!");
       vector_.erase(I);
       return true;
     }
     return false;
   }
 
+  /// Erase a single element from the set vector.
+  /// \returns an iterator pointing to the next element that followed the
+  /// element erased. This is the end of the SetVector if the last element is
+  /// erased.
+  iterator erase(iterator I) {
+    const key_type &V = *I;
+    typename vector_type::iterator VI =
+        std::find(vector_.begin(), vector_.end(), V);
+    assert(VI != vector_.end() && "Iterator to erase is out of bounds.");
+    assert(set_.count(V) && "Corrupted SetVector instances!");
+    set_.erase(V);
+    return vector_.erase(VI);
+  }
+
   /// \brief Remove items from the set vector based on a predicate function.
   ///
   /// This is intended to be equivalent to the following code, if we could
   /// write it:
   ///
   /// \code
   ///   V.erase(std::remove_if(V.begin(), V.end(), P), V.end());
   /// \endcode

unittests/ADT/CMakeLists.txt

set(ADTSources
   PackedVectorTest.cpp
   PointerEmbeddedIntTest.cpp
   PointerIntPairTest.cpp
   PointerSumTypeTest.cpp
   PointerUnionTest.cpp
   PostOrderIteratorTest.cpp
   RangeAdapterTest.cpp
   SCCIteratorTest.cpp
+  SetVectorTest.cpp
   SmallPtrSetTest.cpp
   SmallStringTest.cpp
   SmallVectorTest.cpp
   SparseBitVectorTest.cpp
   SparseMultiSetTest.cpp
   SparseSetTest.cpp
   StringMapTest.cpp
   StringRefTest.cpp

unittests/ADT/SetVectorTest.cpp

+//===- llvm/unittest/ADT/SetVector.cpp ------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// SetVector unit tests.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/SetVector.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+void checkEraseAndIteratorsForSetVector(SetVector<int *> &S) {
+  int buf[3];
+  S.insert(&buf[0]);
+  S.insert(&buf[1]);
+  S.insert(&buf[2]);
+
+  auto B = S.begin();
+  auto M = std::next(B);
+
+  EXPECT_EQ(B, S.begin());
+  EXPECT_EQ(M, std::next(B));
+  EXPECT_TRUE(3 == S.size());
+  EXPECT_TRUE(*B == &buf[0]);
+  EXPECT_TRUE(*M == &buf[1]);
+
+  // Erase will return the iterator pointing to the next element after the
+  // erased one.
+  M = S.erase(M);
+  EXPECT_EQ(B, S.begin());
+  EXPECT_EQ(M, std::next(B));
+  EXPECT_TRUE(2 == S.size());
+  EXPECT_TRUE(*B == &buf[0]);
+  EXPECT_TRUE(*M == &buf[2]);
+
+  M = S.erase(M);
+  EXPECT_EQ(B, S.begin());
+  EXPECT_EQ(M, std::next(B));
+  EXPECT_TRUE(1 == S.size());
+  EXPECT_EQ(M, S.end());
+  EXPECT_TRUE(*B == &buf[0]);
+
+  M = S.erase(B);
+  EXPECT_EQ(S.begin(), S.end());
+  EXPECT_EQ(M, S.end());
+  EXPECT_TRUE(0 == S.size());
+}
+
+void checkEraseAndIteratorsForSmallSetVector(SmallSetVector<int *, 2> &S) {
+  int buf[3];
+  S.insert(&buf[0]);
+  S.insert(&buf[1]);
+  S.insert(&buf[2]);
+
+  auto B = S.begin();
+  auto M = std::next(B);
+
+  EXPECT_EQ(B, S.begin());
+  EXPECT_EQ(M, std::next(B));
+  EXPECT_TRUE(3 == S.size());
+  EXPECT_TRUE(*B == &buf[0]);
+  EXPECT_TRUE(*M == &buf[1]);
+
+  // Erase will return the iterator pointing to the next element after the
+  // erased one.
+  M = S.erase(M);
+  EXPECT_EQ(B, S.begin());
+  EXPECT_EQ(M, std::next(B));
+  EXPECT_TRUE(2 == S.size());
+  EXPECT_TRUE(*B == &buf[0]);
+  EXPECT_TRUE(*M == &buf[2]);
+
+  M = S.erase(M);
+  EXPECT_EQ(B, S.begin());
+  EXPECT_EQ(M, std::next(B));
+  EXPECT_TRUE(1 == S.size());
+  EXPECT_EQ(M, S.end());
+  EXPECT_TRUE(*B == &buf[0]);
+
+  M = S.erase(B);
+  EXPECT_EQ(S.begin(), S.end());
+  EXPECT_EQ(M, S.end());
+  EXPECT_TRUE(0 == S.size());
+}
+
+TEST(SetVector, EraseTest) {
+  // Test for SetVector.
+  SetVector<int *> B;
+  checkEraseAndIteratorsForSetVector(B);
+
+  // Test for SmallSetVector.
+  SmallSetVector<int *, 2> A;
+  checkEraseAndIteratorsForSmallSetVector(A);
+}