how can I delete every second element from std::list in cpp?

Question

I'm trying to delete every second element from std::list but I'm getting segment error (core dump) when I run erase().

#include <bits/stdc++.h>

using namespace std;

int main()
{
    list <int> num_list;
    list <int> :: iterator it;
    num_list.push_back(1);
    num_list.push_back(2);
    num_list.push_back(3);
    num_list.push_back(4);
    num_list.push_back(5);
    cout << num_list.size() << endl;
    it = num_list.begin();
    advance(it, 1);
    for(it; it != num_list.end(); advance(it, 2)) {
        num_list.erase(it);
    }
    for(it = num_list.begin(); it != num_list.end(); ++it) {
        cout << *it << " ";
    } 
    cout << endl;
    return 0;
}

@Rup "_What's `advance`_?" [std::advance](https://en.cppreference.com/w/cpp/iterator/advance). — Algirdas Preidžius, Nov 13 '18 at 16:32
Your `advance(it, 2)` call will run past the end of the list if it has an even number of elements. Your erase call also invalidates `it`, so advancing it afterwards is undefined behaviour. — Peter Ruderman, Nov 13 '18 at 16:36
Unrelated: `#include ` should not be used ([Why](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h)). `using namespace std;` should be avoided ([Why](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice)). Together they amplify some of the other's worst effects and can result in some very odd errors. — user4581301, Nov 13 '18 at 16:37
@Rup " it = num_list.erase(it) " do the job. but the for loop doesn't stop because it goes back to 1, how can i make it stop ?? — Shaman Sharif Asif, Nov 13 '18 at 16:40
@PeterRuderman: That looks like an answer - please post it as such. Comments are to help improve the question. — MSalters, Nov 13 '18 at 16:45
@MSalters, I think this question should be closed. The OP's problems relate to fundamental misunderstandings of basic C++. The question has nothing to do with how to delete every second element from a list (which the OP has already figured out). — Peter Ruderman, Nov 13 '18 at 16:47
Why should this be closed? Deleting alternating elements is a non-trivial task (due to iterator invalidation). Somewhat surprisingly, it does not appear to be asked before. The code (now fixed) is pretty minimal and causes the error claimed, while the intent is also clear. — MSalters, Nov 13 '18 at 16:51
Because the question should really be something along the lines of "how do I erase from a list while traversing it?" (along with a minimal example) — Peter Ruderman, Nov 13 '18 at 16:54
@PeterRuderman: usually you'd do that with `std::remove_if`. That won't work here, though. So another reason why this isn't such a bad question. — MSalters, Nov 13 '18 at 16:57

Peter · Accepted Answer · 2018-11-13T16:59:05.127

Start from the second item: next(num_list.begin(), 1). The erase method returns an iterator to the next item of the removed item. So you can use just ++ operator to step 2.

int main()
{
    list<int> num_list;
    num_list.push_back(1);
    num_list.push_back(2);
    num_list.push_back(3);
    num_list.push_back(4);
    num_list.push_back(5);
    cout << num_list.size() << endl;

    for (auto it = next(num_list.begin(), 1); it != num_list.end();) {
        it = num_list.erase(it);
        if (it != num_list.end())
            ++it;
    }
    for (auto it = num_list.begin(); it != num_list.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
    return 0;
}

Fureeish · Answer 2 · 2018-11-13T17:34:54.443

For a good explanation on why your approach does not work, see Stepan Lechner's answer.

A completely different approach using std::remove_if and lambda expressions:

int main() {
    std::list<int> ints{1, 2, 3, 4, 5};

    auto position = std::remove_if(ints.begin(), ints.end(),
            [counter = 0](const auto x) mutable {
        return ++counter % 2 == 0;
    });

    ints.erase(position, ints.end());

    for(const auto x : ints) {
        std::cout << x << ' ';
    }
}

std::remove_if, paired with erase methods calls, is the algorithm for removing particular elements from a range. Here, it gets a little tricky - we want to remove every second element, so we need a predicate, which will return true only for the even positions in the list. We achieve it using a member counter initialized with lambda init capture.

EDIT: As correctly stated by MSalters in the comments, using std::list::remove_if is a superior solution to erase-remove idiom from <algorithm>. It takes advantage of internal std::list implementation, plus it's simply less awkward to type:

// *ints* being the list itself
ints.remove_if([counter = 0](const auto x) mutable {
    return ++counter % 2 == 0;
});

as opposed to the original:

auto position = std::remove_if(ints.begin(), ints.end(),
        [counter = 0](const auto x) mutable {
    return ++counter % 2 == 0;
});

ints.erase(position, ints.end());

There's a `std::list::remove_if` which does not require the `.erase`. — MSalters, Nov 13 '18 at 17:17
@MSalters that is indeed the superior solution. I have added that to my answer — Fureeish, Nov 13 '18 at 17:24

score 4 · Answer 3 · answered Nov 13 '18 at 16:49

Erasing an element of a list invalidates the respective iterator, such that it must not be used for dereferencing or advancing any more. Iterators pointing to other elements than the erased one, however, are not affected.

So you just need to remember an iterator position to be deleted and advance the original iterator before erasing the "toDelete"-position:

int main()
{
    list <int> num_list;
    num_list.push_back(1);
    num_list.push_back(2);
    num_list.push_back(3);
    num_list.push_back(4);
    num_list.push_back(5);

    size_t size = num_list.size();
    cout << size << endl;

    list <int> :: iterator it = num_list.begin();
    while(size--) {
        auto toDelete = it;
        it++;

        if (size%2==1)
            num_list.erase(toDelete);
    }

    for(it = num_list.begin(); it != num_list.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
    return 0;
}

A bit overkill to keep two state variables (`size` and `it`) but it works. — MSalters, Nov 13 '18 at 16:55

how can I delete every second element from std::list in cpp?

3 Answers3