Difficulty designing a map with custom structs.

[Steve Edwards]

Hi,

With much help from this forum I've been using stl containers, but
always with other common - or stl - types as members. I've now run in to
a problem while trying to use some of my own structures:

enum MySym{symA, symB, symC, symD ... etc.}

typedef struct{
MySym s1, s2, s3;
}SymTriple;


I have a large (10k) collection of SymTriples, and many of them are
equal (i.e. have same values for s1, s2, s3).
What I'd like to do is have a smaller collection without duplicates, and
a count of how many times a particular one occurs.

Maybe...

typedef struct{
SymTriple st;
long numEntries;
}SymTripleCount;

I've tried various permutations of maps/multimaps, by using the
SymTriple as a key and keeping count of when that key already exists.
The problem is I always get this error:
error: no match for 'operator<' in '__x < __y'


I'm guessing this means that the stl container can not compare or sort
my structs?

Is there any way to store my structs in an stl container, with no
duplicates, but with a count the number of occurences of each matching
pattern?

Thanks

Steve

( I could do this in regular C by looping through every 10k structs and
then testing against every (0 - x,000) unique structs I've already
collected, but this is impossibly slow.)

 

[Heinz Ozwirk]

Hi,

With much help from this forum I've been using stl containers, but
always with other common - or stl - types as members. I've now run in to
a problem while trying to use some of my own structures:

enum MySym{symA, symB, symC, symD ... etc.}

typedef struct{
MySym s1, s2, s3;
}SymTriple;


I have a large (10k) collection of SymTriples, and many of them are
equal (i.e. have same values for s1, s2, s3).
What I'd like to do is have a smaller collection without duplicates, and
a count of how many times a particular one occurs.

Maybe...

typedef struct{
SymTriple st;
long numEntries;
}SymTripleCount;

I've tried various permutations of maps/multimaps, by using the
SymTriple as a key and keeping count of when that key already exists.
The problem is I always get this error:
error: no match for 'operator<' in '__x < __y'

The compiler cannot guess when one of your user defined objects is less than another. You have to help and define one. The easiest way to do so is implementing it like

bool operator<(SymTripleCount const& lhs, SymTripleCount const& rhs)
{
return lhs.s1 < rhs.s1
|| lhs.s1 == rhs.s1 && lhs.s2 < rhs.s2
|| lhs.s1 == rhs.s1 && lhs.s2 == rhs.s2 && lhs.s3 < rhs.s3;
}

But I would prefer using std::map<SymTriple, int> instead of std::set<SymTripleCount>. Using a set, you cannot modify the count later, but using a map, you can. Of cause, with a map you have to define operator< for SymTriple, not for SymTripleCount, but that shouldn't be too hard.

HTH
Heinz
}

 

[Steve Edwards]

The compiler cannot guess when one of your user defined objects is less than
another. You have to help and define one. The easiest way to do so is
implementing it like

bool operator<(SymTripleCount const& lhs, SymTripleCount const& rhs)
{
return lhs.s1 < rhs.s1
|| lhs.s1 == rhs.s1 && lhs.s2 < rhs.s2
|| lhs.s1 == rhs.s1 && lhs.s2 == rhs.s2 && lhs.s3 < rhs.s3;
}

But I would prefer using std::map<SymTriple, int> instead of
std::set<SymTripleCount>. Using a set, you cannot modify the count later, but
using a map, you can. Of cause, with a map you have to define operator< for
SymTriple, not for SymTripleCount, but that shouldn't be too hard.

HTH
Heinz
}

Thanks, Heinz, I can see how that works now. But how does the compiler
know to use my new operator< ? How is the association made?

Steve

 

[Heinz Ozwirk]

Thanks, Heinz, I can see how that works now. But how does the compiler
know to use my new operator< ? How is the association made?

The compiler has to use some operator<. That's how std::set and std::map have been implemented. It has to use one, so it takes the one that matches its needs best. Without your own definition of operator<, there was no suitable one at all (otherwise the compiler hadn't complained). So yours will be the only one it can use. Read about function overloading in a book of your choice or google for it.

HTH
Heinz

 

[Marcus Kwok]

But I would prefer using std::map<SymTriple, int> instead of std::set<SymTripleCount>. Using a set, you cannot modify the count later, but using a map, you can. Of cause, with a map you have to define operator< for SymTriple, not for SymTripleCount, but that shouldn't be too hard.

I would suggest using a std::multiset<SymTriple>, and you can use the
count() member function to keep track of the duplicates. You still need
to define operator< for your SymTriples though.

 

[Jerry Coffin]

[ ... ]

Thanks, Heinz, I can see how that works now. But how does the compiler
know to use my new operator< ? How is the association made?

The container uses whatever comparison function has been
specified for it. If you don't specify something else, it
uses std::less<T>. std::less<T> looks something like
this:

template <class T>
bool less(T const &a, T const &b) {
return a < b;
}

IOW, it just ends up attempting to use the '<' operator
to compare the objects. If you're storing built-in types
for which '<' is pre-defined, it uses the built-in
version. If you're storing some user-defined type, you
have to define the operator yourself. The alternative is
to specify a functor (or function) of your own it should
use to do the comparison. This tend to be most useful
when you have a type that you want to look at in
different orders (e.g. ordering people alphabetically by
last name or by height, depending...)