Efficiently remove last element from std::list

Question

This seems like a simple problem, and it is certainly doable, but I'd like to do it efficiently.

The Objective:
Remove the last element from a std::list if it meets a condition.

The Problem:
My compiler (MSVC++ 10) is unhappy about casting a reverse iterator to a const iterator for a method call to std::list.erase(). The message is:

error C2664: 'std::_List_iterator<_Mylist>
 std::list<_Ty>::erase(std::_List_const_iterator<_Mylist>)' : cannot
 convert parameter 1 from 'std::reverse_iterator<_RanIt>' to
 'std::_List_const_iterator<_Mylist>'

The Code I Tried:

std::list<mytype> mylist;

// lots of code omitted for clarity
bool ends_badly = true;

while(ends_badly && mylist.size() > 0)
{
    auto pos = mylist.crbegin(); // Last element in the list
    if ((*pos)->Type() == unwanted)
    {
        mylist.erase(pos); // Here is where the compiler complains
    }
    else
    {
        ends_badly = false;
    }
}

I can get around this by using forward iterators and looping through the list to the end, but that's so cumbersome. The compiler is OK with a forward iterator in this context, and I tried casting a the reverse iterator to a const iterator but the compiler didn't like that either.

Erasing a list element from a bidirectional list using a reverse iterator seems like a reasonable thing. Is there something obvious I'm missing here?

You can call `base()` on a reverse iterator, but you need to take care of the correct offsetting yourself. — Kerrek SB, Apr 22 '16 at 22:11
@KerrekSB Can you elaborate? I'm not sufficiently knowledgeable about iterators to know how to use your suggestion. — vacuumhead, Apr 22 '16 at 22:13
I might be missing a subtext here, [but why not `pop_back`?](http://en.cppreference.com/w/cpp/container/list/pop_back) — user4581301, Apr 22 '16 at 22:18
in addition to what @user4581301 says, you can use `remove_if` with the `back` iterator. — Brad Allred, Apr 22 '16 at 22:34
also why would you use a const iterator if you actually need to modify the list? — Brad Allred, Apr 22 '16 at 22:38
FWIW, "ForwardIterator" has a meaning, and it isn't "iterator that isn't a reverse iterator" — Ben Voigt, Apr 22 '16 at 22:45
@BradAllred By the time I posted the question, I used `crbegin()` because I was just trying to get past what appeared to be a casting problem. I had already tried `rbegin()`. I'm just learning to use `std::list` and hadn't been aware of the much simpler solution of just using the `back()` method. I'm updating some Windows code that had originally used `CObList` and made the mistake of trying to do it line by line instead of logical blocks at a time. — vacuumhead, Apr 24 '16 at 17:23

Edgar Rokjān · Accepted Answer · 2016-04-22T22:26:37.563

8

I suppose that you can simplify your code snippet doing it the next way:

while (!mylist.empty() && mylist.back()->Type() == unwanted) {
    mylist.pop_back();
}

edited Apr 22 '16 at 22:26

answered Apr 22 '16 at 22:18

Edgar Rokjān

17,245
4
40
67

2

`mylist.back()->Type() == unwanted` is even simpler. – SirGuy Apr 22 '16 at 22:25

score 3 · Answer 2 · edited May 23 '17 at 12:06

3

To fix the specific error in your code Can I convert a reverse iterator to a forward iterator?

mylist.erase((pos+1).base());

Using std::reverse_iterator::base

The base iterator refers to the element that is next (from the std::reverse_iterator::iterator_type perspective) to the element the reverse_iterator is currently pointing to.

Anyway, pop_back is the best choice in your case.

edited May 23 '17 at 12:06

Community

1
1

answered Apr 22 '16 at 22:37

gdlmx

6,479
1
21
39

Efficiently remove last element from std::list

2 Answers2