c++algorithmgcciteratorclang

Equivalence of two algorithms using backwards and forwards iterators


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


Solution

  • 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!