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
– melpomene, Commented Jun 10, 2016 at 0:46
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
– PaulMcKenzie, Commented Jun 10, 2016 at 0: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
– Beta, Commented Jun 10, 2016 at 1: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
– user4581301, Commented Jun 10, 2016 at 1:13

Mendes · Accepted Answer · 2016-06-10 11:41:32Z

1

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;
}

edited Jun 10, 2016 at 11:41

answered Jun 10, 2016 at 1:20

Mendes

18.7k40 gold badges167 silver badges284 bronze badges

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

1 Comment

Benjamin Lindley Over a year ago

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, waitingBagsVector.erase(pit) should be waitingPeopleVector.erase(pit)

sjrowlinson · Accepted Answer · 2016-06-10 01:18:59Z

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, 2016 at 1:18

sjrowlinson

3,3651 gold badge22 silver badges37 bronze badges

3 Comments

Benjamin Lindley Over a year ago

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.

sjrowlinson Over a year ago

@BenjaminLindley You're quite right, I guess 2:20am isn't the time to being answering questions - I'll edit tomorrow.

Steve Lorimer Over a year ago

this only removes from wPL not wBL

Collectives™ on Stack Overflow

Removing an object from vector while iterating through it

2 Answers 2

1 Comment

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related