9

I've been up and down stackoverflow and even the very, very nice Dr. Dobbs article but I can't find a definitive answer to the question.

A section of the answer to the question What are the shortcomings of std::reverse_iterator? says that it might not be possible at all.


std::list::reverse_iterator it = list.rbegin();

while(  it != list.rend() )
{
   int value=*it;
   if( some_cond_met_on(value) )
   {     
        ++it;
        list.erase( it.base() );
   }
   else
   {
     ++it;
   }
}

PS: I do know there are other alternatives, such as erase_if(), but I'm looking for an answer to this specific question.

Community
  • 1
  • 1
Migs
  • 825
  • 1
  • 9
  • 16

2 Answers2

16

It should just be

std::list<int>::reverse_iterator it = list.rbegin();

while(  it != list.rend() )
{
   int value=*it;
   if( some_cond_met_on(value) )
   {     
        ++it;
        it= reverse_iterator(list.erase(it.base()); // change to this!
   }
   else
   {
     ++it;
   }
}
MSN
  • 53,214
  • 7
  • 75
  • 105
  • I'll give it a try. How did you figure this one out? (Just asking to learn how to learn) – Migs Dec 23 '11 at 23:19
  • @Migs, the invariant of reverse iterators is: `&*(reverse_iterator(i))==&*(i - 1)`. Map backwards from that (or just think about deleting `rbegin()`) and you get to the code in the answer. – MSN Dec 23 '11 at 23:22
  • Thanks @MSN. It worked perfectly. I read that invariant in Dobbs' article, but I guess I just can't grasp the implications of it. I'll keep staring until something (hopefully) happens. – Migs Dec 23 '11 at 23:25
  • @Migs, I had to think about it too. But if you think about deleting `rbegin() + 1` in `[0, 1, 2, 3, 4]`, the result of deleting the correct forward iterator (via `.erase()`)is exactly where you want the reverse iterator to be built on top of. – MSN Dec 23 '11 at 23:27
  • @MichaelBurr, I was showing what to add to his snippet, but I'll edit it to make it more obvious. – MSN Dec 24 '11 at 04:59
  • 1
    That code doesn't compile in Visual Studio. Don't you mean `it = std::list::reverse_iterator(list.erase(it.base()));`. Also a question, isn't it better in a static cast like `static_cast::reverse_iterator>(list.erase(it.base()));`. Thanks – loop Mar 10 '14 at 03:06
0

Most erase() implementations I have seen return the next iterator in the sequence for exactly this kind of situation, eg:

std::list<int>::reverse_iterator it = list.rbegin();
while( it != list.rend() )
{
    int value = *it;
    if( some_cond_met_on(value) )
    {
        it = list.erase( it );
    }
    else
    {
        ++it;
    }
}
Remy Lebeau
  • 555,201
  • 31
  • 458
  • 770
  • This is correct. However, erase is a member of the structure, not the iterator. As such, whether you are using an iterator or reverse_iterator, erase() still accepts and returns an iterator. There is no r_erase(), which accepts and returns a reverse_iterator. – Dewi Morgan Jan 30 '15 at 04:03