duplicated member in template Set?

[yixiuge]

Associative containter-Set is new to me and was used in my program, and I found there ARE duplicated members in the Set. I suspected this could be related to the way the call-back function is defined. The element type for Set is a struct pointT(with x and y as members). Can any expert here kindly reivew a snippet of the code and give some advice?

Thanks so much!


#include <iostream>
#include "random.h"
#include "set.h"

struct pointT {
int row;
int col;
};

void testSet();

int main ()
{
testSet();
return 0;
}


int CmpByRowCol(pointT a, pointT b)
{
if (a.col== b.col && a.row ==b.row) return 0;
else if (a.col<b.col || a.row<b.row) return -1;
else return 1;
}

void printSet(Set<pointT> &set)
{
cout<<"print set with size of "<<set.size()<<endl;
Set<pointT>::Iterator itr = set.iterator();
while(itr.hasNext())
{ pointT temp = itr.next();
cout<<temp.col<<","<<temp.row<<endl;
}
}

void testSet()
{
Set<pointT> set(CmpByRowCol);
Randomize();
pointT testPT;
while(true)
{
testPT.col = RandomInteger(1,2);
testPT.row = RandomInteger(1,3);
set.add(testPT);
if (set.size()==6) break;
}
printSet(set);
}

[jsmith]

This code does not use std::set; it uses its own implementation.

You need to look at the set implementation to see whether or not it allows duplicates
and then at the code that inserts elements into the set.

[yixiuge]

Hey, Thanks for your reply.
I am using a university package, which uses std::set under the hood. I just verified using simple element type(integer), and set does not allow duplicated members. :-(

[jsmith]

Then it would seem there is a bug in the package. set does not allow duplicates. Note that you can define your own comparator function for set to do anything you want.

[Hammurabi]

This is not a strict ordering (I think):

    else if (a.col<b.col || a.row<b.row) return -1;

Try this:

int CmpByRowCol(pointT a, pointT b)
{
    if (a.col== b.col && a.row ==b.row) return 0;
    else if (a.col<b.col || (a.col==b.col && a.row<b.row)) return -1;
    else return 1;
}

[yixiuge]

Hi, Hammurabi,

This really solved the problem! Thanks a lot.
While I still do not quite understand why this change can totally change the behavior of set, could you shed some light on this?
I was thinking internally the member duplication is only flagged on when a.col== b.col && a.row ==b.row. Why the second branch(else if) would matter?

Thanks again

[Hammurabi]

Before it can be compared for equality using your first case, the element must be found, which involves the second case. If the ordering is not strict, it may not find an existing element after others have been added.

[yixiuge]

Thanks for the insights. :-)

[yixiuge]

One more question about this special set.
The callback function is specified when I declare this set as following

Set<pointT> set(CmpByRowCol);

I want to declare a nested datatype which is queue of this kind of set, and did the following:

Queue<Set<pointT> > queueOfSet(CmpByRowCol);

Somehow the compiler complained and errored a message. Could you advise on the correct syntax for the declaration of this nested datatype ?

Thanks so much!

[Hammurabi]

No sets are created when you create the queue, so you don't need any initialization of the sets at that point. Instead, initialize the sets when you create them before you push them onto the queue. So just do this:

Queue<Set<pointT> > q;

Then use it like this:

Set<pointT> s(CmpByRowCol);
// Insert some stuff into s, then:
q.push( s );

Of course, you may wish to push pointers onto the queue instead of (copies of) the sets.

[yixiuge]

Hmm, I tried this approach, however it has the same complain that the set in the queue does not have an appropriate comparison callback function when I enqueued the set.

Thanks for the help!