Given
struct pt{int x,y;};
auto cmpSet = [](pt a, pt b) { return a.x<b.x;};
std::set<pt, decltype(cmpSet)> s(cmpSet);
Are
if(upper==s.begin()) continue;
auto it= std::prev(upper);
while(it!=s.end() && (*it).y<=p.y){
auto prv = it == s.begin() ? s.end() : std::prev(it);
s.erase(it);
it=prv;
}
And
if(upper==s.begin()) continue;
auto it = std::make_reverse_iterator(upper);
while (it != s.rend() && (*it).y <= p.y) {
auto victim = std::prev(it.base());
it = std::next(it);
s.erase(victim);
}
Necessarily equivalent? I have reasons to believe they either aren't. My reason is that when i submit these two codes: Forwards vs Backwards to an algorithm judge, Forwards gets accepted and Backwards gets a Runtime Error.
Context: It should report which 3d points out of a set of n unique points don't have other 3d points such that there is no other point that has greater X, greater Y, and lesser Z in time O(n)=nlogn. It does this by ordering in Z direction and keeping a minstack-like structure with a std::set
that represents the current frontier in the XY plane.
I don't have access to the dataset or a debug stacktrace, and the judge is OmegaUp but the contest was private and has passed(Coder Bloom May 31st programming contest).
No they aren't equivalent.
it
uses it.base()
as a backing forward iterator, which points to the next going forwardly element in the set. Yes, *it
is not equal to *it.base()
.
Here's the catch: when erasing the victim
, it
gets invalidated!
So the following code
if(upper==s.begin()) continue;
auto it= std::prev(upper);
while(it!=s.end() && (*it).y<=p.y){
auto prv = it == s.begin() ? s.end() : std::prev(it);
s.erase(it);
it=prv;
}
Would actually be equivalent to:
//checking if(upper==s.begin()) is redundant
auto it = std::make_reverse_iterator(upper);
while (it != s.rend() && (*it).y <= p.y) s.erase(*it);
//or equivalently but faster: s.erase(std::prev(it.base()));
Funnily enough, since it
is a backwards iterator, deleting *it
doesn't invalidate it
, but makes it point to the next (going in reverse) element!