CODEWITHSUNDEEP
c++
0xC0DEFACE
0xC0DEFACE

Reputation: 9211

How to call erase with a reverse iterator

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?

Upvotes: 250

Views: 103753

Answers (14)

slashmais
slashmais

Reputation: 7155

... 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())
while (it!=vt.begin())
{
    it--;
    if (*it == pCursor) //{ delete *it;
        it = vt.erase(it); //}
}

Upvotes: 13

Raymond Burkholder
Raymond Burkholder

Reputation: 504

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.

Upvotes: 0

0xC0DEFACE
0xC0DEFACE

Reputation: 9211

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.

Upvotes: 242

Kai Xiong
Kai Xiong

Reputation: 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().

Upvotes: -1

Gaetano Mendola
Gaetano Mendola

Reputation: 1394

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

Upvotes: 26

Kitiara
Kitiara

Reputation: 498

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

Upvotes: -1

Mark Yang
Mark Yang

Reputation: 344

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;
    }
}

Upvotes: 0

fmmarques
fmmarques

Reputation: 301

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.

Upvotes: 0

etham
etham

Reputation: 3525

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;
}

Upvotes: 4

user1493570
user1493570

Reputation: 127

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.

Upvotes: 1

Nismo
Nismo

Reputation: 31

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--;
}

Upvotes: 3

gavinbeatty
gavinbeatty

Reputation: 319

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.

Upvotes: 2

Andrey
Andrey

Reputation: 171

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

Upvotes: 17

Adam Rosenfield
Adam Rosenfield

Reputation: 400204

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.

Upvotes: 4

Related Questions