Page MenuHomePhabricator

[ADT] Introduce lazy unique iterator
Needs ReviewPublic

Authored by lebedev.ri on Mar 26 2021, 2:23 PM.

Details

Summary

You sometimes want to only deal with unique values of an underlying range.
Manually maintaining a set of already-dealt-with elements is cumbersome.

This introduces a unique_iterator forward iterator,
which lazily(!) tracks the elements of the range that were pointed-at already,
and skips them afterwards.

I've added some basic tests and adjusted a few places to use it.

Diff Detail

Event Timeline

lebedev.ri created this revision.Mar 26 2021, 2:23 PM
lebedev.ri requested review of this revision.Mar 26 2021, 2:23 PM
grandinj added inline comments.
llvm/lib/Transforms/Utils/SimplifyCFG.cpp
310

using make_unique_range here, but did not remove the old "make unique logic" ?

lebedev.ri marked an inline comment as done.Mar 27 2021, 2:32 AM
lebedev.ri added inline comments.
llvm/lib/Transforms/Utils/SimplifyCFG.cpp
310

This is correct, we are dealing with two different ranges here,
and want to only deal with unique common successors.

Yeah, not entirely sure this abstraction carries its weight. (I was going to suggest the set could be moved from the iterator into a range object (rather than using iterator_range) but then copies of the iterator wouldn't be independent (only one of them would visit a given element and the other would skip it) & then that starts to make me worry about the abstraction in general - making the iterators a bit big/expensive to copy/etc)

Perhaps there are some more use cases you could highlight/migrate to demonstrate the value?

I probably wouldn't mind an algorithm-like function, rather than an iterator (not composable, but avoids some of the harder design issues) - llvm::for_each_unique_element(R, [](const T& t) { ... });