Re: erase vector v2 elements from v1
"James Juno" <juno@noplace.fake> wrote in message
news:GbadnTVsYtsMZf3UnZ2dnUVZ_uudnZ2d@scnresearch.com...
Hi folks,
Rudimentary container question. I have something like
std::vector<int> v1;
std::vector<int> v2;
For analysis purposes we will call the number of elements in v1 "N", and the
number of elements in V2 "M". Right now, besided the correcctness issues,
you have an O(N*M) algorithm.
I want to remove all elements in v2 from v1. Right now I'm using this
horrible non-STL loop:
for ( size_t i = 0; i < v1.size(); ++i )
for ( size_t j = 0; j < v2.size(); ++j )
{
if ( v1[i] == v2[j] )
{
v1.erase( v1.begin() + i );
break;
}
}
Yuck. There has got to be a cleaner, more STL-like way of doing this.
That is not very efficent in the first place. O(N*M).
If it is not a problem, the simplest solution is to sort them both, and use
the std::set_difference algorithm.
std::sort(v1.begin(),v1.end());
std::sort(v2.begin(),v2.end());
v1.erase(
std::set_difference(
v1.begin(),
v1.end(),
v2.begin(),
v2.end(),
v1.begin()),
v1.end());
This is O(N*lg(N)+M*lg(M));
---------------------------
In the case that it is important not to sort v1, we have a slightly more
verbose alternative.
Our first step should be to sort v2, if that would not be a problem.
std::sort(v2.begin(),v2.end());
Otherwise if possible, we should create a copy and sort it.
std::vector<int> v3(v2);
std::sort(v3.begin(),v3.end());
Either way that is O(M*lg(M)).
Now we can loop through v1 to find the elements we wish to remove, searching
for them in v2 as needed. The search would be O(lg(M)), and the loop O(N),
so this step is O(N*lg(M))
v1.erase(
std::remove_if(
v1.begin(),
v1.end(),
func
),
v1.end()
);
Overall we have a O(N*lg(M)+M*lg(M)) algorithm, but we need to determine
what to use for func.
With TR1, we can do this inline:
v1.erase(
std::remove_if(
v1.begin(),
v1.end(),
std::tr1::bind(
std::binary_search<std::vector<int>::iterator,int>,
v2.begin(),
v2.end(),
_1)),
v1.end()
);
Otherwise (without TR1), you would want to add a helper template:
template<typename Sequence>
struct seq_binary_search_type{
seq_binary_search_type(Sequence seq): sq(seq) {};
bool operator()(Sequence::value_type val)
{
return std::binary_search(sq.begin(),sq.end(),val);
}
private:
Sequence& sq;
};
//Helper function:
template<typename Sequence>
seq_binary_search_type<Sequence> seq_binary_search(Sequence sq)
{ return seq_binary_search_type<Sequence>(sq);}
and with that available you would use:
v1.erase(
std::remove_if(
v1.begin(),
v1.end(),
seq_binary_search(v2)
),
v1.end()
);