CODEWITHSUNDEEP
c++stliteratorreverse-iterator
Pete Baughman
Pete Baughman

Reputation: 3034

Reversing an on-demand iterator

I have an iterator DataIterator that produces values on-demand, so the dereference operator returns a Data, and not a Data&. I thought it was an OK thing to do, until I tried to reverse the data DataIterator by wrapping it in a reverse_iterator.

DataCollection collection

std::reverse_iterator<DataIterator> rBegin(iter) //iter is a DataIterator that's part-way through the collection
std::reverse_iterator<DataIterator> rEnd(collection.cbegin());

auto Found = std::find_if(
    rBegin, 
    rEnd,
    [](const Data& candidate){
        return candidate.Value() == 0x00;
});

When I run the above code, it never finds a Data object whose value is equal to 0, even though I know one exists. When I stick a breakpoint inside the predicate, I see weird values that I would never expect to see like 0xCCCC - probably uninitialized memory. What happens is that the reverse_iterator's dereference operator looks like this (from xutility - Visual Studio 2010)

Data& operator*() const
{   // return designated value
    DataIterator _Tmp = current;
    return (*--_Tmp); //Here's the problem - the * operator on DataIterator returns a value instead of a reference
}

The last line is where the problem is - a temporary Data gets created and reference to that data gets returned. The reference is invalid immediately.

If I change my predicate in std::find_if to take (Data candidate) instead of (const Data& candidate) then the predicate works - but I'm pretty sure I'm just getting lucky with undefined behavior there. The reference is invalid, but I'm making a copy of the data before the memory gets clobbered.

What can I do?

  1. Fix my DataIterator so that operator* returns a Data& instead of a Data? I don't really see how this is possible. The whole point of my DataIterator returning a Data instead of a Data& is because I don't have room to hold the entire uncompressed data set in memory, so I create the items that you want to look at on demand. Maybe I could hold onto the 'current' data value - but then that reference is going to become invalid the moment you increment or decrement the DataIterator. Edit one of the answers suggests a shared_ptr
  2. Write a specialization of the reverse_iterator and make its dereference operator return a value instead of a reference? This seems like a frustrating amount of work, but understandable since it's my DataIterator that's not playing nice here - not the rest of the STL.
  3. Along the same lines, maybe make a find_if that goes in reverse - probably less work than specializing reverse_iterator.
  4. Something else I haven't thought of

Is there something I can do to DataIterator that will prevent someone else from blowing half a day figuring out what's wrong when they try the same thing 6 months from now?

Upvotes: 5

Views: 200

Answers (3)

Pete Baughman
Pete Baughman

Reputation: 3034

I ended up going with Casey's suggestion in the comments. He didn't post it as an answer that I can accept, so I'll write it up myself.

I made a specialization of the reverse_iterator for DataIterator that returns a value instead of a reference. This involved copy/pasting the implementation from xutility, specifying one of the template arguments to be a DataIterator, and changing

reference operator*() const

to

value operator*() const

Upvotes: 0

Ben Voigt
Ben Voigt

Reputation: 283893

It's because the reverse_iterator interface was designed before the existence of decltype. Today, that would be written as

auto operator*() const -> decltype(*current)
{   // return designated value
    DataIterator _Tmp = current;
    return (*--_Tmp);
}

and in C++14, even the trailing return type won't be needed, since it can be inferred.

decltype(auto) operator*() const
{   // return designated value
    DataIterator _Tmp = current;
    return (*--_Tmp);
}

Upvotes: 1

woolstar
woolstar

Reputation: 5083

Not that I'm a great fan of the idea, but if you heap allocated a Data object and then returned a ref to a shared_ptr to it, that would allow the outside world to hold onto it longer if needed, and for you to "forget" about it when you step forward.

On the other hand, implementing your own native reverse_iterator might be a bigger win. That's what I did for my own linked list since I didn't use a sentinel object like gcc does and couldn't use std::reverse_iterator. It really wasn't that difficult.

Upvotes: 1

Related Questions