11

I've just written the following code, and was very surprised it doesn't compile:

std::deque<int> container;
// filling the container...
for (auto it = container.rbegin(); it != container.rend(); ++it)
    if (*it == 5)
    {
        container.erase(it);
        break;
    }

As you can see, I want to delete the last element matching a certain criteria, if any.

The error is

no matching function for call to std::deque::erase(std::reverse_iterator...

At first I didn't believe it was caused by the reverse iterator, but that is indeed the case since replacing rbegin/rend with begin/end solves it.

So, 2 questions:

  1. Why isn't this supported? Is it merely one of those little things the C++ committee forgot to include in the standard, or is there a justification for this overload missing?
  2. What is the most elegant way to do what I want? Am I stuck with iterating by index?
Violet Giraffe
  • 32,368
  • 48
  • 194
  • 335
  • 4
    I think your answer is here: http://stackoverflow.com/questions/1830158/how-to-call-erase-with-a-reverse-iterator –  Jan 25 '16 at 15:33
  • Are `m_container` and `container`, the same? – zdf Jan 25 '16 at 15:39
  • @ZDF: yeah, of course. Fixed. – Violet Giraffe Jan 25 '16 at 15:43
  • @MartinBroadhurst: googling upon your suggestion I've found this article which provides some insight, but it still doesn't explain why `reverse_iterator::base` points to where it does :( : http://www.drdobbs.com/cpp/three-guidelines-for-effective-iterator/184401406?pgno=3 – Violet Giraffe Jan 25 '16 at 15:44
  • @Violet Giraffe You could use `iterator( rev_it.base() )` as SergeyA suggested already. If you plan to use it in a `for`, like in your example, it might not work since the erase will invalidate all iterators. – zdf Jan 25 '16 at 16:11
  • In the name of all that is holy, please use [`std::remove_if`](http://en.cppreference.com/w/cpp/algorithm/remove). For such menial tasks, loops and `break`s should be a relic of the past. – screwnut Jan 25 '16 at 16:31
  • @screwnut `remove_if` removes elements by shifting (the actual number of elements will remain the same). I guess the actual code should be something like: `erase( remove_if(...`. – zdf Jan 25 '16 at 17:02
  • 1
    @Violet - The *reason* is that `rend()` cannot return an iterator one-before-begin, as there isn't anything like that. So it instead holds `begin()` and adjusts all its accesses by 1 to compensate. – Bo Persson Jan 25 '16 at 17:19
  • @screwnut: but that's the thing - I cannot! Please read the question carefully. I do always use `remove_if` wherever possible; I've even made a wrapper to make use of erase-remove simpler. – Violet Giraffe Jan 25 '16 at 17:29
  • @ZDF: yep, it's called the "erase-remove idiom`. – Violet Giraffe Jan 25 '16 at 17:31
  • 1
    @VioletGiraffe You're right, I'm an idiot. Still, in the spirit of using `` as much as possible, I'll suggest using `erase` with the result of `find_if(container.rbegin()...` (even if it doesn't reduce the number of lines). – screwnut Jan 25 '16 at 22:07
  • @screwnut The for loop is perfectly clear and readable to everybody. Don't use "fancy new things" just for the sake of it. – Asteroids With Wings Dec 07 '20 at 15:31
  • @AsteroidsWithWings Are you arguing that the words "find" and "erase" confuse you? – screwnut Dec 07 '20 at 15:36
  • 1
    @screwnut No, I'm arguing that you're insisting the OP switch from clear, easy-to-understand code to something more arcane for absolutely no good reason. Your first suggestion was even a pessimisation. What's the point? _"in the spirit of using as much as possible"_ Cargo cult programming = bad. – Asteroids With Wings Dec 07 '20 at 17:16
  • @AsteroidsWithWings I'm arguing that using English words to describe your intent in a program is mountains better that keywords like `for` and `if`. Also, thank you for your input and let's put this to rest, please. – screwnut Dec 09 '20 at 11:13

2 Answers2

1

I figure that the quantity of additional overloads that would need to be added throughout the standard library make this an unseemly task, when there is no "need" for it.

Sure, the "most elegant" workaround is hardly expressive:

container.erase((it+1).base());

…but there is one, and reverse iterators are likely not used often enough to warrant all the extra noise that would be caused by having overloads everywhere that do nothing but wrap the above line of code.

If you find yourself using it a lot, you can wrap the more general solution yourself:

template <typename ReverseIterator>
auto AsForwardIterator(ReverseIterator rit)
{
    std::advance(rit, 1);
    return rit.base();
}

Then it's just:

container.erase(AsForwardIterator(it));

And, quite frankly, the simplicity of this seems worth not having all those overloads in every container.

Asteroids With Wings
  • 17,071
  • 2
  • 21
  • 35
0

I can't answer on 'why' question, but to answer the 'how' - you should call base() on your iterator. It's going to return a proper forward iterator.

While doing so, keep in mind relationship between reverse and forward iterators. it might be confusing at first, but actually quite simple. If you have a std::vector containing of following items: 

1, 2, 3, 4, 5

And you have a reverse_iterator rit, which upon dereferencing gives you 3, then *(rit.base) will be equal to 4. To see why, just remember that in normal iterators begin() is dereferencable, but end() is not. In reverse iterators, the property has to be the same - rbegin() has to be dereferencible, but rend() should not - i.e., should point beyond the beginning of the container.

Since by definition, rend.base() is the same as begin() (because rend can be constructed as reverse_iterator(begin()), the only way all of the above can hold, is if rend.base() will return a next right element to the one beyond the beginning - begin(). It is easy to see that the same symmetry holds for rend().

SergeyA
  • 61,605
  • 5
  • 78
  • 137
  • Downvoted the answer because you can't simply pass `reverse_iterator::base()` to the `erase` method. – Violet Giraffe Jan 25 '16 at 17:32
  • @VioletGiraffe, why? – SergeyA Jan 25 '16 at 17:33
  • Because it would erase the wrong element! The iterator must be adjusted by 1 first. – Violet Giraffe Jan 25 '16 at 17:34
  • @VioletGiraffe, define *wrong*. It would delete the element your reverse iterator is currently pointing to. – SergeyA Jan 25 '16 at 17:34
  • No, see the suggested answer. – Violet Giraffe Jan 25 '16 at 17:35
  • @VioletGiraffe, yeah, you need to advance it, which is clear, since rbegin is not dereferenceable, but begin is. I didn't give you the code, just a technique. Nevertheless, your are the owner of your downvotes and you can use them as you want. ) – SergeyA Jan 25 '16 at 17:45
  • SO answers are public artifacts that will be seen by hundreds, or even thousands, people in the future. And most of these people wil copy-paste the answer and then be confused as to why it's not working. And no, it is not clear to me that the iterator must be advanced. In fact, it is so opaque that I will use an index-based loop instead, just to keep the code readable. – Violet Giraffe Jan 25 '16 at 17:51
  • @VioletGiraffe, point taken. I tried enhancing the answer with some explanations. It is actually very easy with reverse iterators, there is no arcane magic to them. – SergeyA Jan 25 '16 at 18:11
  • This answer doesn't actually show the solution, nor does it address the main part of the question. – Asteroids With Wings Dec 07 '20 at 15:25