C++ Set Iterators not reaching end of Set

Question

I recently decided to attempt a C++ solution to a recently ended topcoder.com competition, as a way to learn the language (being new to C++). However, I became stumped when iteration through a std::set object did not successfully reach all elements in the set (set.count > # elements traversed). I've searched in vain for others who have experienced this here at StackExchange and elsewhere.

The Specifics

I have posted the code to pastebin: http://pastebin.com/U7xQzDQg .

What I am attempting to do is a naive clustering algorithm. I'm sure there are better ways to achieve what I want to do; but this does not interest me at this stage (as my focus is on learning the language and its idiosyncrasies). I represent squares in a Cartesian grid by a Position object, with properties "x" and "y". Using an iterative method, I scan the whole grid looking for objects of the same colour, grouping them into Cluster objects. When the algorithm is complete, there will be a set of Clusters, each of which includes a set of Position objects that are spaced by no more than a set distance. At some point during the algorithm, it is necessary to merge clusters that are close to one another; which is where I start to have problems.

If you compile and run the code posted on pastebin, you will see messages like the following:

TO MERGE:
Cluster of size 1: [1,1], 
Cluster of size 2: [0,1], [0,2], 
MERGED: 0x7fffb5e9b970Cluster of size 3: [0,1], [1,1], 

What should be shown in the last line, if my code was working correctly, is:

MERGED: <Memory Address of Cluster>Cluster of size 3: [0,1], [1,1], [0,2],

These lines are generated whenever a merge is attempted (see line 54); with the string representation of the Cluster objects generated by an operator casting method (see line 97) using standard set iteration.

What is clear is that though the set claims to have the right number of elements, iterating through the set does not reach all of them. I thought it might be a problem with objects passing out of scope, and being destructed; but this does not appear to be the case, as std::set objects copy elements before inserting them into the data structure (and tests with a destructor on the Position elements suggested otherwise).

I'm really at a loss, and don't want to hack around it... because I think there is something significant that I am missing here. Can anyone help me?

Best, Matthew

Answer 1

Your program exhibits undefined behaviour because your operator< does not induce a strict weak ordering for your Position objects.

bool operator< (Position other) const {
    return other.x - x + 100*(other.y - y);
}

You can use the following instead:

bool operator< (Position other) const {
    if (y < other.y) return true;
    if (y > other.y) return false;
    return x < other.x;
}

Answer 2

This

return output.c_str();

Is undefined behavior because your output string goes out of scope and the underlying character array is deleted when the function returns.

Your operator const char* () const function should probably be a

friend std::ostream& operator<<(std::ostream&, Cluster const&)

function that writes directly to std::cout.

Remember to free anything you have calloced too, or better still don't allocate stuff on the heap at all if you can avoid it.