Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to efficiently delete elements from a vector given an another vector

What is the best way to delete elements from a vector given an another vector?

I have come up with the following code:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void remove_elements(vector<int>& vDestination, const vector<int>& vSource) 
{
    if(!vDestination.empty() && !vSource.empty())
    {
        for(auto i: vSource) {
            vDestination.erase(std::remove(vDestination.begin(), vDestination.end(), i), vDestination.end());
        }
    }
}

int main() 
{
    vector<int> v1={1,2,3};
    vector<int> v2={4,5,6};
    vector<int> v3={1,2,3,4,5,6,7,8,9};
    remove_elements(v3,v1);
    remove_elements(v3,v2);
    for(auto i:v3)
        cout << i << endl;
    return 0;
}

Here the output will be:

7
8
9
like image 434
user3898160 Avatar asked Aug 25 '16 07:08

user3898160


People also ask

How do you delete a vector from another vector?

All the elements of the vector are removed using clear() function. erase() function, on the other hand, is used to remove specific elements from the container or a range of elements from the container, thus reducing its size by the number of elements removed.

How do you delete multiple vector elements?

If you need to remove multiple elements from the vector, the std::remove will copy each, not removed element only once to its final location, while the vector::erase approach would move all of the elements from the position to the end multiple times. For Example, Consider removing all elements < 5 in following vector.

How do you remove a specific vector from an element?

The erase() function can remove an element from the beginning, within, or end of the vector. In order to remove all the elements from the vector, using erase(), the erase() function has to be repeated the number of times there are elements, beginning from the first element.

How do you delete a vector from a 2D vector?

Removing elements from 2D vectors in C++ Similar to the 'insert()' function, it requires a positional argument as an iterator. To remove all the vectors from the 2-D vector, 'clear()' function can be used.


1 Answers

My version is the following, I only apply erase after all elements from the vector vSource have been moved to the end by std::remove and keep track of the pointer to the end of the vector vDestination to not iterate over it for nothing.

void remove_elements(vector<int>& vDestination, const vector<int>& vSource) 
{
    auto last = std::end(vDestination);
    std::for_each(std::begin(vSource), std::end(vSource), [&](const int & val) {
        last = std::remove(std::begin(vDestination), last, val);
    });
    vDestination.erase(last, std::end(vDestination));
}

See on coliru : http://coliru.stacked-crooked.com/a/6e86893babb6759c


Update

Here is a template version, so you don't care about the container type :

template <class ContainerA, class ContainerB>
void remove_elements(ContainerA & vDestination, const ContainerB & vSource) 
{
    auto last = std::end(vDestination);
    std::for_each(std::begin(vSource), std::end(vSource), [&](typename ContainerB::const_reference val) {
        last = std::remove(std::begin(vDestination), last, val);
    });
    vDestination.erase(last, std::end(vDestination));
}

Note

This version works for vectors without any constraints, if your vectors are sorted you can take some shortcuts and avoid iterating over and over the vector to delete each element.

like image 164
dkg Avatar answered Nov 03 '22 10:11

dkg