Jump to content
  • Advertisement
Sign in to follow this  
Mantear

C++ std containers, reverse iterators, and erase()

This topic is 2951 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have a std::deque<> which contains elements that have a timestamp on them. Periodically, the deque must be purged of elements that are too old. There is an exception where, if a component of the element is pending on a result, the element is not purged/removed even if has timed out. So I need to perform a search on the deque looking at two properties of the elements to determine if the element needs to be removed.

The elements in the deque are inserted in order of timestamps, so it can be assumed that the element at the front of the deque is the oldest and the element at the back of the deque is the newest. This should let me search from the front of the deque to the back, allowing me to break out of searching as soon as I find the first element that has not timed out. My inital thought was to do the following:
// Not checked to see if this compiles, but it should describe my problem.
std::deque<Element*>reverse_iterator riter;
for (riter = elementQueue.rbegin();
riter != elementQueue.rend();
)
{
if ((*riter)->TimedOut(currentTime))
{
if (!(*riter)->WaitingForResult())
{
delete *riter;
riter = elementQueue.erase((++riter).base()); // <--- ERROR
}
else
{
++riter;
}
}
else
{
// Element has not timed out, can stop searching.
break;
}
}

The line marked as 'ERROR' would erase the correct element from the deque, but ::erase() returns an iterator, not a reverse_iterator. So how should I go about performing this process? It should be noted that, for performance reasons, I do not want to search the entire deque and want to use the fact that I can stop searching once I find the first non-timed out element.

Share this post


Link to post
Share on other sites
Advertisement
You can't call erase with a reverse_iterator. Simple as that.
I don't know what the specific reason for this is but I'm sure someone else can enlighten us.

Maybe you should consider using a different container if performance is important when removing items.

Share this post


Link to post
Share on other sites
Quote:
Original post by Scarabus2
You can't call erase with a reverse_iterator. Simple as that.
I don't know what the specific reason for this is but I'm sure someone else can enlighten us.

Maybe you should consider using a different container if performance is important when removing items.


The actual erase() itself works just fine. 'elementQueue.erase((++riter).base());' is completely valid and does what I want. However, ::erase() returns an iterator and not a reverse_iterator, so 'riter = elementQueue.erase((++riter).base());' is what fails.

99% of the time, items are pushed on and off the ends of the queues. The current section of code isn't the only place where these queues are touched, so changing the underlying container for this particular situation isn't really a good option.

Share this post


Link to post
Share on other sites
Sadly, there are no clean ways to reverse an iterator (aside from using random access iterator arithmetic to construct the reverse iterator from rbegin() again).

On the other hand, I would probably re-engineer the algorithm into two different steps:

- Whenever you need to remove elements, run through them, determine if they have to be removed, delete them and set them to NULL.

- Whenever there's a possibility that elements have been removed, use std::remove_if and erase to eliminate all NULL element.

This has the benefit of being conceptually easier on the brain, since you don't have to care about removing elements while iterating.

Share this post


Link to post
Share on other sites
You might just want to use an index-based approach to the iteration and not deal with reverse iterators at all, since as you've seen yourself they're sometimes not as easy to work with as forward iterators. However with indexes your code ends up being a bit cleaner:

for(int i = (int)elementQueue.size() - 1; i >= 0; --i)
{
if (elementQueue->TimedOut(currentTime))
{
if (!elementQueue->WaitingForResult())
{
delete elementQueue;
elementQueue.erase(elementQueue.begin() + i);
}
}
else
{
break;
}
}




You can get rid of the signed integer cast if you're willing to add some additional logic to prevent the underflow case, but the erase is going to remain a little ugly :/ Handling the erase is a second pass is also an option.

Share this post


Link to post
Share on other sites
Find the range of elements from which we can remove stuff, and then remove stuff from that range. Use standard library algorithms.


struct NotTimedOut {
Time t;
bool operator()(Element* const& e) { return !e->TimedOut(t); }
NotTimedOut(const Time& t): t(t) {}
};

struct WaitingForResult {
bool operator()(Element* const& e) { return e->WaitingForResult(); }
};

typedef std::deque<Element*> reverse_iterator iterator;
iterator begin = elementQueue.rbegin(), end = elementQueue.rend();
iterator first_new = std::find(begin, end, NotTimedOut(currentTime));
elementQueue.erase(std::remove_if(begin, first_new, WaitingForResult()), first_new);


Share this post


Link to post
Share on other sites
Quote:

You can get rid of the signed integer cast if you're willing to add some additional logic to prevent the underflow case, but the erase is going to remain a little ugly :/


If people weren't that resistent to


for(size_t i = elementQueue.size(); i --> 0; )


I think that could become an idiom for reverse iterating.

Honestly.

:)


Share this post


Link to post
Share on other sites
Quote:
Original post by SiCrane
That won't compile. std::deque<>::erase() doesn't accept reverse_iterators.


:(

Fine. We can solve the problem just as easily with forwards iteration. This only costs us performance when the timed-out elements are statistically likely to be a small fraction of the total.


struct TimedOut {
Time t;
bool operator()(Element* const& e) { return e->TimedOut(t); }
TimedOut(const Time& t): t(t) {}
};

typedef std::deque<Element*> iterator iterator;
iterator begin = elementQueue.begin(), end = elementQueue.end();
iterator first_old = std::find(begin, end, TimedOut(currentTime));
elementQueue.erase(std::remove_if(first_old, end, WaitingForResult()), end);


Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!