Comparing an element with a set

[Sean Dalton]

Hello,

I have a two sets OLDLIST and REMOVE.

I would like to remove every element in OLDLIST if it is also occuring
in REMOVE
and store the remaining elements from OLDLIST into NEWLIST.

So far, I have read in both lists but I'm struggling comparing the
elements
- I have something like

double oldlist[oldsize];
double remove[remsize];

for(i = 0; i < oldsize; i++)
{

for(k = 0; k < remsize; k ++)

if(oldlist != remove[k])
{
cout<<oldlist[k]<<endl;

}

}

Obviously this is not working because I need to compare all elements
from REMOVE *at once* with oldlist. So how do I compare all
elements
at once?

Many thanks,
Sean

 

[Ivan Novick]

Hello,

I have a two sets OLDLIST and REMOVE.

I would like to remove every element in OLDLIST if it is also occuring
in REMOVE
and store the remaining elements from OLDLIST into NEWLIST.

So far, I have read in both lists but I'm struggling comparing the
elements
- I have something like

double oldlist[oldsize];
double remove[remsize];

for(i = 0; i < oldsize; i++)
{

for(k = 0; k < remsize; k ++)

if(oldlist != remove[k])
{
cout<<oldlist[k]<<endl;

}

}

Are you sure you want to use arrays to store your data? This would be
a n-squared algorithm. Better would be to store the remove set into a
hash_map or some other container which can do a constant time lookup
to see if you need to remove the data.

Ivan Novick
http://www.mycppquiz.com

 

[James Kanze]

I have a two sets OLDLIST and REMOVE.
I would like to remove every element in OLDLIST if it is
also occuring in REMOVE and store the remaining elements
from OLDLIST into NEWLIST.
So far, I have read in both lists but I'm struggling
comparing the elements
- I have something like
double oldlist[oldsize];
double remove[remsize];
for(i = 0; i < oldsize; i++)
{
for(k = 0; k < remsize; k ++)
if(oldlist != remove[k])
{
cout<<oldlist[k]<<endl;
}
}

Are you sure you want to use arrays to store your data?

Since the sizes are changing, he obviously needs std::vector,
and not C style arrays.

This would be a n-squared algorithm.

Not if the vectors are sorted first. If both vectors are
sorted, it's O(n) and if only only the remove list is sorted,
it's O(n ln m) (where n is the number of elements in the old
vector, and m the number of elements in the remove list).

Better would be to store the remove set into a hash_map or
some other container which can do a constant time lookup to
see if you need to remove the data.

If you can find a good hash function for double, let us know.