Comparing an element with a set
Sean Dalton
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[i] != remove[k])
{
cout<<oldlist[k]<<endl;
}
}
Obviously this is not working because I need to compare all elements
from REMOVE *at once* with oldlist[i]. 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[i] != 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
Daniel T.
> 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.
Use set_difference from the standard header, algorithm.
<http://www.sgi.com/tech/stl/set_difference.html>
James Kanze
> On Jul 5, 4:43 pm, Sean Dalton <sean.dalton...@yahoo.ca> wrote:
> > 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[i] != 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.
--
James Kanze (GABI Software) email:james...@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34