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?

Kerrek SB · Accepted Answer · 2016-01-11 09:43:32Z

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, 2016 at 9:43

Kerrek SB

481k96 gold badges904 silver badges1.1k bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

YSC Over a year ago

See std::erase(std::remove_if()) idiom

juanchopanza Over a year ago

@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.

YSC Over a year ago

@juanchopanza Not here is not. I can't edit though. Monday morning typo.

Kerrek SB Over a year ago

@YSC: You can hit delete and then post a new comment.

Daniel Langr Over a year ago

"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.

|

Šimon Tóth · Accepted Answer · 2016-01-11 09:42:14Z

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, 2016 at 9:42

Šimon Tóth

36.7k21 gold badges116 silver badges154 bronze badges

1 Comment

Johann Gerell Over a year ago

"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 stackoverflow.com/a/6442829/6345

Jan Hudec · Accepted Answer · 2016-01-11 09:46:19Z

2

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.

answered Jan 11, 2016 at 9:46

Jan Hudec

76.8k13 gold badges138 silver badges190 bronze badges

Collectives™ on Stack Overflow

Delete element using iterator, without knowing vector

3 Answers 3

7 Comments

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

7 Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related