Removing an object from vector while iterating through it

Question

I'm new to C++ so I'm having trouble figuring out how to best remove an object from a vector while still iterating through it.

Basically, I need to iterate through two vectors. For every item, if the ID's match, I can remove them.

//For every person, check to see if the available bags match:
        for(std::vector<Person>::iterator pit = waitingPeopleVector.begin(); pit != waitingPeopleVector.end(); ++pit) {
            for(std::vector<Bag>::iterator bit = waitingBagsVector.begin(); bit != waitingBagsVector.end(); ++bit) {
                int pId = pit->getId();
                int bId = bit->getId();
                if(pId == bId){
                    //a match occurs, remove the bag and person
                }
            }
        }

Working with iterators is a bit confusing, I know I can use the .erase() function on my vectors, but I can't really pass pit or bit. Any help appreciated. Thanks

`vector` might not be the best container for this, because removing elements from a vector is expensive and a bit awkward. — melpomene, Jun 10 '16 at 00:46
Related: http://stackoverflow.com/questions/6096279/keeping-a-valid-vectoriterator-after-erase — πάντα ῥεῖ, Jun 10 '16 at 00:48
Another issue is that your approach is `O(n*n)` complexity. 100 peope, 100 bags, that loop goes for 10,000 iterations. Is it possible to sort the two vectors on id first? — PaulMcKenzie, Jun 10 '16 at 00:51
What do you mean, you can't pass `pit` or `bit`? Why can't you? And have you tried the simpler exercise of deleting elements from *one* container? — Beta, Jun 10 '16 at 01:09
Off topic: This doesn't help much in terms of speed, but `std::find` should make your job a bit easier. You can also hoist `int pId = pit->getId();` up one loop. — user4581301, Jun 10 '16 at 01:13

Mendes · Answer 1 · 2016-06-10T11:41:32.477

From the standard:

The iterator returned from a.erase(q) points to the element immediately following q prior to the element being erased. If no such element exists, a.end() is returned.

I would use it in something like using the erase method:

std::vector<Person>::iterator pit = waitingPeopleVector.begin();
std::vector<Bag>::iterator bit = waitingBagsVector.begin();

while (pit != waitingPeopleVector.end())
{
    bool didit;

    while (bit != waitingBagsVector.end())
    {
        didit = false;
        if (pit->getId() == bit->getId() && !didit)
        {
            bit = waitingBagsVector.erase(bit);
            pit = waitingPeopleVector.erase(pit);
            didit = true;
        }
        else
        {
            ++bit;
        }
    }

    if (didit)
        continue;
    else
        ++pit;
}

Maybe break out of the inner loop if you get a match. Otherwise you're doing redundant checks against the iterator that is returned from `waitingPeopleVector.erase(pit)`. Also note your typo, waiting**Bags**Vector.erase(pit) should be waiting**People**Vector.erase(pit) — Benjamin Lindley, Jun 10 '16 at 01:39

score 0 · Answer 2 · answered Jun 10 '16 at 01:18

0

Using the erase-remove idiom will achieve this objective, the below offers an (untested) way using lambdas and <algorithm> functions to remove elements from wPL which have the same ID as wBL. It shouldn't be too much effort to extend this to both lists. Note, we have used std::list instead of std::vector for faster removal.

std::list<Person> wPL;
std::list<Bag> wBL;
//...
wPL.erase(std::remove_if(wPL.begin(), wPL.end(),
    [&wBL](auto x) { return std::find_if(wBL.begin(), wBL.end(), [](auto y) 
        { return x.getId() == y.getId();); }), wPL.end() };

answered Jun 10 '16 at 01:18

sjrowlinson

3,297
1
18
35

I doubt removal would be faster for `std::list` than `std::vector` in the general case. But you can be certain that it's not going to be faster if you use `std::remove_if`, since it still has to shift values around. That's why there's `std::list::remove_if`, which works on nodes. – Benjamin Lindley Jun 10 '16 at 01:24
@BenjaminLindley You're quite right, I guess 2:20am isn't the time to being answering questions - I'll edit tomorrow. – sjrowlinson Jun 10 '16 at 01:27
this only removes from `wPL` not `wBL` – Steve Lorimer Jun 10 '16 at 01:42

Removing an object from vector while iterating through it

2 Answers2