Is remove_if predicate guaranteed to be called only once per iterator?

Question

I've been reading the latest C++ spec, and I'm unable to figure out whether or not remove_if can be called multiple times for the same element. In particular, I'm looking at std::remove_if being called on deque iterators. So far as I can figure, there's no reason for it to be called multiple times if all it does is simply start from the first param and iterate along till the second.

The code I'm working on uses manual reference counting and, as such, in case the remove_if predicate will return true, it'll decrement and delete the underlying object reference. The obvious catch being that this will only work if the remove_if predicate is only called once for each element, otherwise subsequent calls will be accessing a deleted object. Something tells me this isn't guaranteed to be OK and there will come a point where the same element will be passed to the remove_if predicate twice for a single remove_if call.

If you had some kind of crazy datastructure that implemented iterators and say, randomly selected an entry for each iterator increment until it (randomly) came upon the end iterator, I could see how this would fail. But for straight-forward, standardized structures like deque, vector, and list, can a single element be passed multiple times to the predicate?

Answer 1

According to a draft of the standard §23.3.4.6/14:

Complexity: Exactly distance(begin(), end()) applications 
of the corresponding predicate.

Forgive me if the reference is a little off; it's actually a first for me officially quoting it. I hope it's the information you're looking for.