This is an archive of the discontinued LLVM Phabricator instance.

[SetVector] Add erase() method
ClosedPublic

Authored by junbuml on Mar 18 2016, 2:14 PM.

Details

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;

Diff Detail

Event Timeline

junbuml updated this revision to Diff 51068.Mar 18 2016, 2:14 PM
junbuml retitled this revision from to [SetVector] Add erase() method.
junbuml updated this object.
junbuml added reviewers: MatzeB, qcolombet, mcrosier.
junbuml added a subscriber: llvm-commits.

Test coverage?

MatzeB accepted this revision.Mar 18 2016, 2:24 PM
MatzeB edited edge metadata.

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.

This revision is now accepted and ready to land.Mar 18 2016, 2:24 PM
junbuml updated this revision to Diff 51470.Mar 23 2016, 2:02 PM
junbuml edited edge metadata.

Added a unittest and addressed Matthias' comments.

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 added inline comments.Mar 24 2016, 10:28 AM
unittests/ADT/SetVectorTest.cpp
58 ↗(On Diff #51470)

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 updated this revision to Diff 51570.Mar 24 2016, 10:46 AM
junbuml marked an inline comment as done.

Addressed David's comment.

dblaikie added inline comments.Mar 24 2016, 11:05 AM
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
19 ↗(On Diff #51570)

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 updated this revision to Diff 51578.Mar 24 2016, 11:54 AM

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().

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 added inline comments.Mar 24 2016, 1:41 PM
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 updated this revision to Diff 51634.Mar 25 2016, 7:21 AM

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

dblaikie accepted this revision.Mar 25 2016, 8:33 AM
dblaikie added a reviewer: 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
34–49 ↗(On Diff #51634)

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

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

This revision was automatically updated to reflect the committed changes.

Reverted in r264420

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)

/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.

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

junbuml updated this revision to Diff 51666.Mar 25 2016, 11:42 AM
junbuml edited edge metadata.
junbuml removed rL LLVM as the repository for this revision.

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

junbuml updated this revision to Diff 51670.Mar 25 2016, 12:21 PM

Fixed David's comment.

Looks good - please commit

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