2

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?

Mahmoud Al-Qudsi
  • 28,357
  • 12
  • 85
  • 125
  • 3
    Not the answer to the question you're asking but a problem for you anyway: `§25.1[algorithms.general]/8` -- *"... The function object pred shall not apply any non-constant function through the dereferenced iterator."* – Benjamin Lindley Jul 20 '12 at 03:31
  • 1
    Note that `remove(_if)` does *not* kill the elements, it only moves elements from the end to their place. You have to `erase` them afterwards with the erase-remove idiom: `cont.erase(std::remove_if(...), cont.end());`, that's how it works. And if you really need your predicate to modify the ref counter, you're doing something terribly wrong and are not adhering to the [RAII principle](http://stackoverflow.com/q/161177/500104). – Xeo Jul 20 '12 at 03:39
  • @Xeo Yeah. Dealing with some weird restrictions in someone's code, basically all I have is the predicate which is supplied to the library as a callback. Benjamin's answer makes me second-guess this approach. – Mahmoud Al-Qudsi Jul 20 '12 at 03:42
  • Just saw this again due to a notification and I don’t think the limitation on non-constant functions is an issue. Eg decrementing a ref count is absolutely a “constant” complexity and even calling free/delete might be, depending on the implementation. I must say, that is a weird constraint to specify though. There usually aren’t complexity constraints for user code. – Mahmoud Al-Qudsi Jan 08 '22 at 20:21

1 Answers1

3

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.

David Rodríguez - dribeas
  • 204,818
  • 23
  • 294
  • 489
chris
  • 60,560
  • 13
  • 143
  • 205
  • Nice catch. I didn't think of it that way - I guess the only way an iterator could be passed in twice while still conforming to the standard is if another iterator was skipped in exchange ;-) – Mahmoud Al-Qudsi Jul 20 '12 at 03:47
  • @MahmoudAl-Qudsi, Yeah, I was thinking about that, too, but it's really just putting two and two together what with it conforming to this, as well as the guaranteed behaviour of the function itself. – chris Jul 20 '12 at 03:49
  • Since `O(kn)` is also equal to `O(n)` this doesn't unambiguously answer the question. – c z Nov 23 '20 at 10:03
  • @c z: But the spec isn’t using big-O notation and it says the complexity is “exactly” the distance. O(n) would translate to “linearly proportionate to the distance” and would be very incorrect to read as “exactly the distance” so I think even if it isn’t altogether unambiguous it’s not as ambiguous as you are suggesting it might be. – Mahmoud Al-Qudsi Jan 08 '22 at 20:17