Delete element using iterator, without knowing vector

Question

I have a situation. I have used a templated function for one of my task. To this function, I pass iterator by reference. Now, I have to delete few elements from a vector. How do I do this using only iterators? Pl find the respective code:

template <class BidirectionalIterator, class Iterator> bool

SomeFunc( BidirectionalIterator& first, BidirectionalIterator& last, Iterator anotherVecBegin )
{
    while((first+1) != last)
    {
        if(some_condition)
            // delete (first); HOW?
        else if(some_other_condition)
            // delete (first + 1); HOW?
    }

    // add something to another vector using anotherVecBegin

    return true;
}

There are many already asked questions, but they all have a vector in context. so myVec.erase(*first) is easy..

I am also aware that its not a very good way that I pass iterator by reference. But I am following simple rules: use references when something is expected to be changed or to avoid heavy copy. My scenario is fitting first condition.

So How do I delete?

score 6 · Accepted Answer · answered Jan 11 '16 at 09:43

6

You cannot modify a container if all you have are iterators for the container elements. The whole point of iterators is separating the concept of a container from the concept of range of elements, so that algorithms can be expressed universally in terms of the latter without caring about the former. That's also why we have a remove algorithm that permutes a range and returns an iterator that's suitable for erasing elements from a container, but the erasing needs to be done by someone who knows the container.

answered Jan 11 '16 at 09:43

Kerrek SB

464,522
92
875
1,084

2

See [`std::erase(std::remove_if())` idiom](http://en.cppreference.com/w/cpp/algorithm/remove) – YSC Jan 11 '16 at 09:46
1

@YSC I don't think there's an `std::erase`. The point is you need an `std::vector` instance to call `std::vector::erase` on. – juanchopanza Jan 11 '16 at 09:51
@juanchopanza Not here is not. I can't edit though. Monday morning typo. – YSC Jan 11 '16 at 09:59
@YSC: You can hit delete and then post a new comment. – Kerrek SB Jan 11 '16 at 10:32
"You cannot modify a container if all you have are iterators"—I don't think that's accurate. For instance, when you use `std::iter_swap`, as sorting algorithms do, you in fact **modify** the container, i.e., it's contents. Otherwise, I agree with respect to erasing an element. – Daniel Langr Jan 11 '16 at 10:42
Maybe, better formulation would be something as that you cannot modify the structure of a container. – Daniel Langr Jan 11 '16 at 10:48
@DanielLangr: What you mean is "modifying the values of the container elements". I'd like to think of that as distinct from modifying the container. The former never invalidates iterators or references. – Kerrek SB Jan 11 '16 at 11:20

score 2 · Answer 2 · answered Jan 11 '16 at 09:42

2

You can't. Deleting an element from a container will invalidate all iterators, so you will have to update first and last after each deletion.

answered Jan 11 '16 at 09:42

Šimon Tóth

35,456
20
106
151

_"Deleting an element from a container will invalidate all iterators"_ - This is incorrect. Different containers has different iterator invalidation rules for erasure. See for instance http://stackoverflow.com/a/6442829/6345 – Johann Gerell Jan 11 '16 at 13:13

score 2 · Answer 3 · answered Jan 11 '16 at 09:46

Standard library: You must get the reference to the container, or defer the deletion to a place where you have it. There is no way around it. The container is needed to add or remove elements and there is no way to find the container from iterator.

Additionally, don't forget, that erasing from a vector invalidates all iterators to that vector.
Other libraries: Boost.Intrusive has some containers that allow you to do anything with just a pointer to the object (which doubles as iterator), but they are linked lists, which are generally less efficient than vectors for most purposes.

Delete element using iterator, without knowing vector

3 Answers3