237

I am trying to do something like this:

for ( std::list< Cursor::Enum >::reverse_iterator i = m_CursorStack.rbegin(); i != m_CursorStack.rend(); ++i )
{
    if ( *i == pCursor )
    {
        m_CursorStack.erase( i );
        break;
    }
}

However erase takes an iterator and not a reverse iterator. is there a way to convert a reverse iterator to a regular iterator or another way to remove this element from the list?

0xC0DEFACE
  • 8,825
  • 7
  • 34
  • 35
  • 19
    As an aside, when writing loops like these, don't repeatedly compute the end iterator as you do here with `i != m_CursorStack.rend()`. Instead, write `i = m_CursorStack.rbegin(), end = m_CursorStack.rend(); i != end;`. That is, initialize an iterator you can keep around for repeated comparison -- assuming that the end position won't be changing as a side effect of your loop body. – seh Dec 02 '09 at 03:10
  • It seems to me that the obvious question here would be why you're doing this at all. What do you gain from traversing the list in reverse? What do you gain by writing this code yourself instead of using `std::remove`? – Jerry Coffin Dec 02 '09 at 03:32
  • And is an iterator on a std::list still valid to increment after the element to which it refers has been erased? – Steve Jessop Dec 02 '09 at 03:45
  • 4
    I only want to remove 1 element, thus the 'break;', using 'remove' would get rid of any that match taking longer and not doing what i want. The element I want to remove in this particular case will nearly always be the end of the list or very close to it, so iterating in reverse is also quicker and better suited to the problem. – 0xC0DEFACE Dec 02 '09 at 03:51
  • @Steve - It doesn't get incremented cause when its erased it breaks out of the loop – 0xC0DEFACE Dec 02 '09 at 03:53
  • @0xC0DEFACE: sorry, I didn't read carefully enough, and didn't notice the break. In this case, I'd still use something like: `list.erase(--std::find(list.rbegin(), list.rend(), pCursor).base());` – Jerry Coffin Dec 02 '09 at 04:33
  • @Jerry - Nice suggestion, I might change it to that! – 0xC0DEFACE Dec 02 '09 at 05:16
  • Sorry, yes, I made the same mistake as Jerry. Not paying attention. – Steve Jessop Dec 02 '09 at 14:37
  • 4
    https://stackoverflow.com/a/2160581/12386 This says the designers specifically don't define the implementation because you as the user aren't supposed to know or care, yet @seh above expects us to magically just know that rend() is calculated and expensive. – stu Mar 14 '18 at 19:19
  • @JerryCoffin, from the spec for std::vector::erase(): "Invalidates iterators and references at or after the point of the erase, including the end() iterator." So if you want to zap several things in a vector you can iterate from the end to the beginning, zapping along the way and you don't have to worry about your iterator becoming invalid. – Eric M Sep 16 '21 at 08:03

14 Answers14

229

After some more research and testing I found the solution. Apparently according to the standard [24.4.1/1] the relationship between i.base() and i is:

&*(reverse_iterator(i)) == &*(i - 1)

(from a Dr. Dobbs article):

So you need to apply an offset when getting the base(). Therefore the solution is:

m_CursorStack.erase( --(i.base()) );

EDIT

Updated for C++11, two additional solutions:

  • reverse_iterator i is unchanged:

      m_CursorStack.erase( std::next(i).base() );

  • reverse_iterator i is advanced:

      std::advance(i, 1);
  m_CursorStack.erase( i.base() );

I find these much clearer than my previous solution. Use whichever you require.

Olivia Stork
  • 4,660
  • 5
  • 27
  • 40
0xC0DEFACE
  • 8,825
  • 7
  • 34
  • 35
  • Thanks for pointing out that erase(i.base()) is wrong -- I have some code that does that and works, and now I don't know why! :( – Dan Dec 02 '09 at 04:31
  • 28
    You should take note of a bit more of the article you cited - to be portable the expression should be `m_CursorStack.erase( (++i).base())` (man, doing this stuff with reverse iterators makes my head hurt...). It should also be noted that the DDJ article is incorporated into Meyer's "Effective STL" book. – Michael Burr Dec 02 '09 at 06:25
  • 9
    I find that diagram more confusing than helpful. Since rbegin, ri and rend are all *actually* pointing at the element to the right of what they are drawn to be pointing at. The diagram shows what element you would access if you `*` them, but we're talking about what element you'd be pointing at if you `base` them, which is one element to the right. I'm not such a fan of the `--(i.base())` or `(++i).base()` solutions since they mutate the iterator. I prefer `(i+1).base()` which works as well. – mgiuca Jun 16 '12 at 11:20
  • 7
    Reverse iterators are liars.. when deferenced, a reverse iterator returns the element _before it_. [See here](http://stackoverflow.com/a/14760316/111307) – bobobobo Feb 07 '13 at 20:51
  • @MichaelBurr But ++i would change i, right? Also am I correct to say that once we erase using a reverse iterator's base, that reverse iterator is also invalidated? So basically I can't reuse `i` say in a loop to delete elements in a container. If all this is true, reverse iterator seems pretty useless.... – Rich Mar 13 '14 at 06:48
  • @0xC0DEFACE You meant `std::advance(i,1)` I guess. – adl Jul 08 '15 at 10:59
  • In the VS 2013 STL implementation the second param defaults to 1, the same as std::next. I didn't realise that was non-standard. – 0xC0DEFACE Jul 10 '15 at 06:31
  • What if you aren't erasing a list, but rather from a `std::deque`, where erasing in the middle invalidates all iterators (except the one returned from the `.erase` call)? – Yakk - Adam Nevraumont Jul 15 '15 at 17:56
  • 5
    Just to be absolutely clear, this technique still cannot be used in a normal for loop (where the iterator is incremented in the normal manner). See http://stackoverflow.com/questions/37005449/how-to-call-erase-with-a-reverse-iterator-using-a-for-loop – logidelic May 03 '16 at 18:02
  • 1
    m_CursorStack.erase( (++i).base()) seems like it would be a problem if ++i got you to past the last element. can you call erase on end()? – stu Mar 14 '18 at 19:21
  • How do you assign the result of erase() back to your iterator (if you wanted to continue iterating over the container after the deletion)? – user997112 Aug 13 '18 at 14:51
  • Should we advance `i` or not? – Dominic Feb 15 '22 at 14:25
24

Funny that there is no correct solution on this page yet. So, the following is the correct one:

In case of the forward iterator the solution is straight forward:

std::list< int >::iterator i = myList.begin();
while ( i != myList.end() ) {
  if ( *i == to_delete ) {
    i = myList.erase( i );
  } else {
    ++i;
  } 
}

In case of reverse iterator you need to do the same:

std::list< int >::reverse_iterator i = myList.rbegin();
while ( i != myList.rend() ) {
  if ( *i == to_delete ) {
    i = decltype(i)(myList.erase( std::next(i).base() ));
  } else {
    ++i;
  } 
}

Notes:

  • You can construct a reverse_iterator from an iterator
  • You can use the return value of std::list::erase
Patrick Parker
  • 4,863
  • 4
  • 19
  • 51
Gaetano Mendola
  • 1,344
  • 3
  • 12
  • 27
  • 4
    This code works, but please explain why next is used and how is it safe to cast a forward iterator to a reverse iterator without the world collapsing – Lefteris E Mar 23 '20 at 12:13
  • 2
    @LefterisE That's not a cast. It creates a new reverse iterator out of an interator. This is normal constructor of the reverse iterator. – Šimon Tóth Jun 16 '20 at 22:41
  • Outside of "the most vexing parse" examples, this might be the best example I've run into where using brace initialisation would make the code much more clear to readers. – Chuu May 12 '22 at 16:44
17

Please note that m_CursorStack.erase( (++i).base()) may be a problem if used in a for loop (see original question) because it changes the value of i. Correct expression is m_CursorStack.erase((i+1).base())

Andrey
  • 171
  • 1
  • 2
  • 4
    You'd need to create a copy of the iterator and do `iterator j = i ; ++j`, because `i+1` doesn't work on an iterator, but that's the right idea – bobobobo Feb 07 '13 at 21:12
  • 4
    @bobobobo, you can use `m_CursorStack.erase(boost::next(i).base())` with Boost. or in C++11 `m_CursorStack.erase(std::next(i).base())` – alfC Jun 10 '14 at 08:59
13

... or another way to remove this element from the list?

This requires the -std=c++11 flag (for auto):

auto it=vt.end();
while (it>vt.begin())
{
    it--;
    if (*it == pCursor) //{ delete *it;
        it = vt.erase(it); //}
}
slashmais
  • 7,069
  • 9
  • 54
  • 80
4

While using the reverse_iterator's base() method and decrementing the result works here, it's worth noting that reverse_iterators are not given the same status as regular iterators. In general, you should prefer regular iterators to reverse_iterators (as well as to const_iterators and const_reverse_iterators), for precisely reasons like this. See Doctor Dobbs' Journal for an in-depth discussion of why.

Adam Rosenfield
  • 390,455
  • 97
  • 512
  • 589
3

And here is the piece of code to convert the result of erase back to a reverse iterator in order to erase an element in a container while iterating in the reverse. A bit strange, but it works even when erasing the first or last element:

std::set<int> set{1,2,3,4,5};

for (auto itr = set.rbegin(); itr != set.rend(); )
{    
    if (*itr == 3)
    {
        auto it = set.erase(--itr.base());
        itr = std::reverse_iterator(it);            
    }
    else
        ++itr;
}
etham
  • 3,158
  • 2
  • 16
  • 13
3
typedef std::map<size_t, some_class*> TMap;
TMap Map;
.......

for( TMap::const_reverse_iterator It = Map.rbegin(), end = Map.rend(); It != end; It++ )
{
    TMap::const_iterator Obsolete = It.base();   // conversion into const_iterator
    It++;
    Map.erase( Obsolete );
    It--;
}
Nismo
  • 31
  • 1
2

If you don't need to erase everything as you go along, then to solve the problem, you can use the erase-remove idiom:

m_CursorStack.erase(std::remove(m_CursorStack.begin(), m_CursorStack.end(), pCursor), m_CursorStack.end());

std::remove swaps all the items in the container that match pCursor to the end, and returns an iterator to the first match item. Then, the erase using a range will erase from the first match, and go to the end. The order of the non-matching elements is preserved.

This might work out faster for you if you're using a std::vector, where erasing in the middle of the contents can involve a lot of copying or moving.

Or course, the answers above explaining the use of reverse_iterator::base() are interesting and worth knowing, to solve the exact problem stated, I'd argue that std::remove is a better fit.

gavinbeatty
  • 319
  • 2
  • 10
1

Just wanted to clarify something: In some of the above comments and answers the portable version for erase is mentioned as (++i).base(). However unless I am missing something the correct statement is (++ri).base(), meaning you 'increment' the reverse_iterator (not the iterator).

I ran into a need to do something similar yesterday and this post was helpful. Thanks everyone.

user1493570
  • 127
  • 1
  • 10
0

To complement other's answers and because I stumbled upon this question whilst searching about std::string without much success, here goes a response with the usage of std::string, std::string::erase and std::reverse_iterator

My problem was erasing the an image filename from a complete filename string. It was originally solved with std::string::find_last_of, yet I research an alternative way with std::reverse_iterator.

std::string haystack("\\\\UNC\\complete\\file\\path.exe");
auto&& it = std::find_if( std::rbegin(haystack), std::rend(haystack), []( char ch){ return ch == '\\'; } );
auto&& it2 = std::string::iterator( std::begin( haystack ) + std::distance(it, std::rend(haystack)) );
haystack.erase(it2, std::end(haystack));
std::cout << haystack;  ////// prints: '\\UNC\complete\file\'

This uses algorithm, iterator and string headers.

fmmarques
  • 301
  • 3
  • 3
0

reverse iterator is quite hard to use. So just used general iterator. 'r' It start from last element. When find something to erase. erase it and return next iterator. eg when delete 3rd element it will pointing current 4th element. and new 3rd. So it should be decreased 1 to move left

void remchar(string& s,char c)
{      
    auto r = s.end() - 1;
    while (r >= s.begin() && *r == c)
    {
        r = s.erase(r);
        r -= 1;
    }
}
Mark Yang
  • 226
  • 3
  • 16
0

This idiom of trying to erase the back of the map is common in limit order book management in the financial industry.

Top of book ask orders are lowest ask price, and naturally sort to the beginning of the map.

Top of book bid orders are highest bid price, and naturally sort to the end of the map.

I'm somewhat hesitant to use the funky std::next(i).base().

Instead, if the map is commonly used with reverse iterators, change the comparison operator to gt instead. Large values will sort to the beginning of the map, and normal iterators can then be used -- eliminating the need for the reverse iterator adjustment on erase.

Raymond Burkholder
  • 494
  • 4
  • 12
-1

If m_CursorStack is a vector, you can erase by taking index:

m_CursorStack.erase(m_CursorStack.begin() + m_CursorStack.size() + int(m_CursorStack.rbegin() - i) - 1);
Kitiara
  • 343
  • 6
  • 21
-1

The reason that m_map.erase((++r_iter).base() doesn't work in a loop is that erase() would invalidate the ++r_iter!! We just need to use the return value from the erase().

Kai Xiong
  • 1