change all objects that contain a certain value

[Stauricus]

hello everybody
in the following code, i want to change all elements of "a" that contains any element from "i" to 0.

#include <vector>
#include <algorithm>

class A{
    public:
    int n;
    A(int integer){
        n = integer;
    }
};

int main(){
    std::vector<int> i = {2, 4};
    std::vector<A> a = {1, 2, 3, 2, 4, 2, 5};

    //
    return 0;
}

what i mean is, a[1], a[3], a[4], and a[5] to have their "n" changed to 0.

i did some google search, and found that i should use std::find_if. but i'm unable to make it work. i tried following this explanation: https://stackoverflow.com/questions/15517991/search-a-vector-of-objects-by-object-attribute
but i'm stuck on how to put all together.


thanks in advance :)

[gunnerfunner]

# include <iostream>
# include <vector>
# include <algorithm>


class A{
    public:
    int n;
    A(int integer) : n(integer){}
};

int main(){

    std::vector<int> i = {2, 4};
    std::vector<A> a = {1, 2, 3, 2, 4, 2, 5};
    for (auto & elem : a)
    {
        if(std::find(i.cbegin(), i.cend(), elem.n) != i.end()) elem.n = 0;
    }
    for (const auto& elem : a)
    {
        std::cout << elem.n << " ";
    }
}

[JLBorges]

> i did some google search, and found that i should use std::find_if. but i'm unable to make it work

Since the vector of integers is sorted (if it is not sorted, sort it first), use std::binary_search
http://en.cppreference.com/w/cpp/algorithm/binary_search
(Lot more efficient if the vector contains some non-trivial number of integers)

#include <iostream>
#include <vector>
#include <algorithm>

struct A {

    int n;
    A( int integer ) : n(integer){}
};

int main() {

    std::vector<int> i = {2, 4};
    // std::sort( i.begin(), i.end() ) ; // if i was not already sorted

    std::vector<A> a = {1, 2, 3, 2, 4, 2, 5};
    for ( const A& v : a ) std::cout << v.n << ' ' ;
    std::cout << '\n' ;

    for( A& v : a ) if( std::binary_search( i.begin(), i.end(), v.n ) ) v.n = 0 ;

    for ( const A& v : a ) std::cout << v.n << ' ' ;
    std::cout << '\n' ;
}

http://coliru.stacked-crooked.com/a/be43bc071c1a69ce

[Stauricus]

great! and what if i want to delete the elem, instead of changing it to 0? this line didn't work
if(std::find(i.cbegin(), i.cend(), elem.n) != i.end()) elem.erase();

it's kinda obvious, since elem is an instance of the class, and not the vector itself. i don't know how to access the vector to delete elem.

[JLBorges]

#include <iostream>
#include <vector>
#include <algorithm>

struct A {

    int n;
    A( int integer ) : n(integer){}
};

int main() {

    std::vector<int> i = {2, 4};
    // std::sort( i.begin(), i.end() ) ; // if i was not already sorted

    std::vector<A> a = {1, 2, 3, 2, 4, 2, 5};
    for ( const A& v : a ) std::cout << v.n << ' ' ;
    std::cout << '\n' ;

    // erase-remove idiom: https://en.wikipedia.org/wiki/Erase-remove_idiom
    const auto found_it_in_i = [&i] ( const A& a ) { return std::binary_search( i.begin(), i.end(), a.n ) ; };
    a.erase( std::remove_if( a.begin(), a.end(), found_it_in_i ), a.end() ) ;

    for ( const A& v : a ) std::cout << v.n << ' ' ;
    std::cout << '\n' ;
}

http://coliru.stacked-crooked.com/a/fe79adbdebb4405f

[gunnerfunner]

# include <iostream>
# include <vector>
# include <algorithm>


class A{
    public:
    int n;
    A(int integer) : n(integer){}
};

int main(){

    std::vector<int> i = {2, 4};
    std::vector<A> a = {1, 2, 3, 2, 4, 2, 5};
    a.erase(std::remove_if(a.begin(), a.end(), [&i](A& a)
                {return std::find(i.cbegin(), i.cend(), a.n) != i.cend();}), a.end());
    for (const auto& elem : a)
    {
        std::cout << elem.n << " ";
    }
}

[Stauricus]

thanks, to both of you :)
i'll try to spot the differences between these codes you two provided.

[JLBorges]

Here is a third version:

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>

struct A {

    int n;
    A( int integer ) : n(integer){}
};

int main() {

    const std::vector<int> i = { 4, 2 }; // need not be sorted

    std::vector<A> a = {1, 2, 3, 2, 4, 2, 5};
    for ( const A& v : a ) std::cout << v.n << ' ' ;
    std::cout << '\n' ;

    // erase-remove idiom: https://en.wikipedia.org/wiki/Erase-remove_idiom
    const std::unordered_set<int> ivals { i.begin(), i.end() } ; // create a hash table
    const auto found_it_in_ivals = [&ivals] ( const A& a ) { return ivals.find(a.n) != ivals.end() ; };
    a.erase( std::remove_if( a.begin(), a.end(), found_it_in_ivals ), a.end() ) ;

    for ( const A& v : a ) std::cout << v.n << ' ' ;
    std::cout << '\n' ;
}

http://coliru.stacked-crooked.com/a/a561fd3bfcc4dce4

Complexity with N being the size of vector a and M being the size of vector i

std::find: O(N*M) time, O(1) space
sort i and then std::binary_search: O( (N+M) * logM ) time, O(1) space
std::unordered_set: O(N+M) time, O(M) space