using set::find() when it contains a struct or class 
Author Message
 using set::find() when it contains a struct or class

Hey all-

I have a set that holds instances of type Fun, which is a struct:
struct Fun
{
   int x;
   double d;
   std::string str;

Quote:
};

std::set<Fun> FunSet;

The problem I'm having is that I want to find an element in this set.
I would like to be able to do:

Fun f;
f.x = 23;
f.d = 421.533;
str = "test";

std::set<Fun>::iterator it
if ( it = FunSet.find(f) != FunSet.end() )
{
    // found the struct in the set

Quote:
}

else
{
    // didn't find the struct in the set

Quote:
}

Except that when I do this, it is always found, regardless of whether
the
struct with those values is there or not. I tried using the
algorithms, but because they're linear, and we're talking a *lot* of
elements, it's way too slow to be useful.

Any ideas on how to make this work?

Thanks



Tue, 28 Dec 2004 03:49:39 GMT  
 using set::find() when it contains a struct or class

Quote:
> I have a set that holds instances of type Fun, which is a struct:
> struct Fun
> {
>    int x;
>    double d;
>    std::string str;
> };

> std::set<Fun> FunSet;

> The problem I'm having is that I want to find an element in this set.
> I would like to be able to do:

> Fun f;
> f.x = 23;
> f.d = 421.533;
> str = "test";

> std::set<Fun>::iterator it
> if ( it = FunSet.find(f) != FunSet.end() )
> {
>     // found the struct in the set
> }
> else
> {
>     // didn't find the struct in the set
> }

> Except that when I do this, it is always found, regardless of whether
> the
> struct with those values is there or not. I tried using the
> algorithms, but because they're linear, and we're talking a *lot* of
> elements, it's way too slow to be useful.

> Any ideas on how to make this work?

How do you define operator<(const Fun&, const Fun&)? If it's not
a strict weak ordering, don't expect sensible behavior from the set.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com



Tue, 28 Dec 2004 04:23:57 GMT  
 using set::find() when it contains a struct or class
I forgot to include that function, but it went along the lines of:

bool operator < (const Fun& fun )
{
    return x < fun.x && d < fun.d && str < fun.str;

Quote:
}

the issue I'm sure I'm raising is the string. Any suggestions on improving
this?

Quote:


> > I have a set that holds instances of type Fun, which is a struct:
> > struct Fun
> > {
> >    int x;
> >    double d;
> >    std::string str;
> > };

> > std::set<Fun> FunSet;

> > The problem I'm having is that I want to find an element in this set.
> > I would like to be able to do:

> > Fun f;
> > f.x = 23;
> > f.d = 421.533;
> > str = "test";

> > std::set<Fun>::iterator it
> > if ( it = FunSet.find(f) != FunSet.end() )
> > {
> >     // found the struct in the set
> > }
> > else
> > {
> >     // didn't find the struct in the set
> > }

> > Except that when I do this, it is always found, regardless of whether
> > the
> > struct with those values is there or not. I tried using the
> > algorithms, but because they're linear, and we're talking a *lot* of
> > elements, it's way too slow to be useful.

> > Any ideas on how to make this work?

> How do you define operator<(const Fun&, const Fun&)? If it's not
> a strict weak ordering, don't expect sensible behavior from the set.

> P.J. Plauger
> Dinkumware, Ltd.
> http://www.dinkumware.com



Tue, 28 Dec 2004 10:36:04 GMT  
 using set::find() when it contains a struct or class

Quote:
> I forgot to include that function, but it went along the lines of:

> bool operator < (const Fun& fun )
> {
>     return x < fun.x && d < fun.d && str < fun.str;
> }

That's not a good choice for less than; whenever (!(a < b) && !(b < a)), a
is considered equivalent to b, which means searching for a will return b.
Your less than creates a lot of equivalencies that you probably don't want.
For example, if

a = (10, 0.0, "foo")
b = (0, 10.0, "foo")

then according to your less than, a is not less than b and b is not less
than  a, therefore they are equivalent.

You probably want a lexicographical style less than; try this one:

bool operator < (const Fun& fun )
{
  if (x < fun.x) return true;
  if (fun.x < x) return false;
  if (d < fun.d) return true;
  if (fun.d < d) return false;
  return str < fun.str;

Quote:
}

Of course, there are many variations of this...

Ken



Tue, 28 Dec 2004 11:41:23 GMT  
 using set::find() when it contains a struct or class

Quote:
> I forgot to include that function, but it went along the lines of:

> bool operator < (const Fun& fun )
> {
>     return x < fun.x && d < fun.d && str < fun.str;
> }

That is not strict weak ordering so your set is broken.

If in your struct

struct Fun
{
   int x;
   double d;
   std::string str;

Quote:
};

x is primary, d is secondary and str is tertiary (meaning the sets orders on
x, if x is equal then d and d is equal then str) then

bool operator < (const Fun& fun )
{
    if (x < fun.x)
        return true;
    else if (x > fun.x)
        return false;
    else if (d < fun.d)
        return true;
    else if (d > fun.d)
        return false;
    else
        return (str < fun.str);

Quote:
}

follows strict weak ordering.

Quote:
>> Any suggestions on improving this?

That depends on what you want "less than" to means for this struct. If I had

struct OneOfTheStatesInUSA
{
    long         population;
    double     gdp;
    double     area;
    string       name;

Quote:
};

and I had a set of them, what would "less than" mean?

I could have 4 sets, ordered by  the least populous of the states to the
most populous, the poorest to the richest, the smallest in terms of size to
the largest, and finally the states in alphabetical order. In each case
"less than" means something different.

Nobody can "improve" on what you have until you say "less than" means for
your struct. And your "less than" has to behave the same way as a "less
than" does for integers which means that if you know that two arbitrary
elements x, y of your struct are not equal  then if

(x < y) is true

then

(y < x)

must return false for arbitrary x, y

Stephen Howe



Wed, 29 Dec 2004 04:28:32 GMT  
 
 [ 5 post ] 

 Relevant Pages 

1. performance issue in using set::find and set::insert with comparision function specified

2. Malloc & structs contain struct*

3. Initialisation of structs containing arrays of structs...?

4. native dll calling with structs containing arrays of nested structs

5. Using reflection to set the value of an inline ValueType struct

6. call from nested class method nonstatic of the class containing

7. Class containing list of classes objects

8. Class from a string that contains the name of the class

9. Problems using class as a member variable in a C struct

10. Structs -vs- Classes & using Arrays[]

11. array that contains structs

12. Struct containing pointer to function

 

 
Powered by phpBB® Forum Software