Can I use std::vector.size() to control a loop that's removing elements?

Question

I have a big headache in a object detector I'm working on.
I have already created this thread about other part that could be the problem: Heap Corruption trying to add elements to existing std::vector

But, now, I'm thinking maybe the way I remove elements from a vector might be my problem. So, simple question, can i do something like this...

for (int i=0; i < vector.size(); i++){
    if(iNeedToRemoveThisElement){
        std::swap(vector[i],vector.back());
        vector.pop_back();
        i--;
    }

?

[`std::remove()`](http://en.cppreference.com/w/cpp/io/c/remove) should actually help to heal your _headaches_. — πάντα ῥεῖ, Mar 15 '15 at 22:32
Yes you can, the loop condition been called in every iteration of the loop. But there are more efficient ways to do so. you can use `erase` to delete item from anywhere in the vector. — SHR, Mar 15 '15 at 22:34
@πάνταῥεῖ [This other `std::remove()`](http://en.cppreference.com/w/cpp/algorithm/remove) might also help ;) — Emil Laine, Mar 15 '15 at 22:54

celtschk · Accepted Answer · 2015-03-15T23:35:04.897

1

Your loop is OK (assuming iNeedToRemoveThisElement does not do anything bad, of course). The loop condition is executed every time, so you always compare with the current vector.size() reflecting the latest updates.

Also, a careful examination of the loop also reveals that you don't fall into the other potential pitfall of the comparison: If i is negative, the comparison would give false because vector.size() is unsigned. However it turns out that at the time of comparison, i is never negative.

There is one caveat where I'm not completely sure: If i refers to the last element, you swap that element with itself; I'm not sure whether that is defined behaviour (with the C++98/C++03 copy imlementation, there's of course no problem, but I'm not sure whether the C++11 move implementation also supports it). So it might be needed to special-case this. Update: As dyp explains in the comments, self-swap is allowed, so there's no need to special-case for it.

In any case, you should look up the algorithms std::remove and std::remove_if from the C++ standard library. They allow you to get rid of the loop completely, and if you can use C++11's lambda functions, it's also simpler than the loop.

edited Mar 15 '15 at 23:35

answered Mar 15 '15 at 23:11

celtschk

19,311
3
39
64

The C++11 default move implementation of `swap` also uses a temporary, hence, self move-assignment does not occur. IIRC, self-swapping must be safe for various algorithms (see, e.g. [a comment by Howard Hinnant on that topic](http://stackoverflow.com/questions/13127455/what-does-the-standard-library-guarantee-about-self-move-assignment#comment17853023_13127916)). – dyp Mar 15 '15 at 23:28
@dyp: Thank you for that information. I actually suspected that it is required to work, but I couldn't find that information. I'll update my answer accordingly. – celtschk Mar 15 '15 at 23:32
As far as I know, this is yet another instance of "it's required to work because it's not allowed to fail". I couldn't find it in the Standard either, with a quick search. – dyp Mar 15 '15 at 23:53
@dyp actually the current standard says it's allowed to fail, see 17.6.4.9 [res.on.arguments]/1 (1.3) ... but that needs to be fixed (and I keep promising to write a paper about it). – Jonathan Wakely Mar 16 '15 at 00:28
@JonathanWakely Sorry, I can't see in C++14 IS what you're talking about. I can see something about rvalue references, but how's that relevant for `swap`? – dyp Mar 16 '15 at 00:31
@dyp because the generic `swap` is defined in terms of move-assigning rvalues. See http://stackoverflow.com/q/13129031/981959 and my answer there. – Jonathan Wakely Mar 16 '15 at 00:40
@JonathanWakely Ah silly me, I forgot about the first move assignment in my mental model. I wonder though if one can deduce the implementation from the requirements ("Exchanges values" in the generic version) In theory, two local variables could also be used as far as I can see, which would prevent self-move-assignment. – dyp Mar 16 '15 at 01:02
@dyp, yes, I suppose two tmp variables could be used, but noone does it that way, and users would complain about the extra move :) The standard should just be fixed instead. – Jonathan Wakely Mar 16 '15 at 01:20

Can I use std::vector.size() to control a loop that's removing elements?

1 Answers1