STL Sort Comparison Functions

[amadhusudan]

Recently something funny happened in a program that I was writing.

I have a structure which I am pushing back in a vector. This structure contains other structures. Let me show the basic detail

Structure1 consists of some floats and some classes (all well written with constructors etc). No pointer variables.
Structure1
{
float,
float,
<Simple String Structure>
<Simple String Structure>
<Simple String Structure>
}

Structure2 contains structure1 and some other basic and well written structures
Structure2
{
Structure1
float
<Others>
}

Structure3 contains structure2 and one more structure which contains basic ints.
Structure3
{
Structure2
<Others>
}

My vector pushes back structure3 types
vector<structure3> myvector.

The code is pretty simple. I populate the structure with a number of elements of type structure3. And at some point I sort them. I have written the comparison function.
The comparison function uses the float value in structure2 and if they are equal falls back to a float value in structure1. The code is something like this

bool compare(structure3& one, structure3& two)
{
if(one.structure2.float != two.structure2.float)
{
return one.structure2.float < two.structure2.float
}

return one.structure2.structure1.float-two.structure2.structure1.float;
}

The program runs multiple times (in a single session) with different inputs as part of a regression. For a particular input the sorting fails as it tries to access some illegal memory. It fails when trying to copy structure1's string element type. The memory passed to it is illegal. I checked the memory location and the memory which precedes the vectors first element is being used.

After some time I realized that the line of contention in the comparison code is where I am returning a float value (instead of a boolean). If I change this to a boolean (using < operator) the crash stops.

Here is why I am in a conundrum.
1. If I isolate the input that caused the crash and run it individually, the program does not crash
2. Multiple inputs of same value cause the program to crash after n iterations
3. If I return an integer (converting floats to ints. I assumed that float was incorrectly being converted to a bool), The program still crashes.
4. The program works if and only if I return the valid boolean (using < )

Any ideas why the float or int might be causing problems. I fear that returning the correct boolean value has only suppressed the larger issue for the moment.

Regards
MAdhusudan

[MiiNiPaa]

How do you sort your vector?

Note that comparsion function should have some standatd behavior: http://en.cppreference.com/w/cpp/concept/LessThanComparable

Let say we have following struct:

struct c
{
    int x;
}

bool operator<(c& left, c& right)
{
    return left.x - right.x; 
}

Our operator< will calculate difference between members and convert it to bool. Standard states, tat everything aside 0 is true. So if int members in two structs are different, this function will always equals to true!
Let imagine we have following code:

void bubble_sort(c in[], int size)
{
    bool do_next_iteration= false;
    do {
        do_next_iteration = false;
        for(int i = 1; i < size; ++i) {
            if(in[i] < in[i-1]) {
                std::swap(in[i], in[i-1])
                do_next_iteration = true;
            }
        }
    }while(do_next_iteration);
}

The following:

            if(in[i] < in[i-1]) {
                std::swap(in[i], in[i-1])

Will be executed on each iteration for any pair of differet values, because we have both a < b and b < a at once! And so it will be an infinite loop.

[JLBorges]

bool compare(structure3& one, structure3& two)
{
    if(one.structure2.Float != two.structure2.Float)
    {
        return one.structure2.Float < two.structure2.Float
    }

     return one.structure2.structure1.Float-two.structure2.structure1.Float;
}

This predicate for std::sort is fundamentally flawed; it does not induce a strict weak ordering.
http://www.sgi.com/tech/stl/StrictWeakOrdering.html

In addition, you may want to read up on 'comparing floating point numbers'.

EDIT: The first point is essentially a restatement of MiiNiPaa's post (which I hadn't seen at the time).

[amadhusudan]

I use std::sort and I do not have an overloaded "<" operator. I use the comparison function.

I call it as

std::sort(vector.begin(), vector.end(), ComparisonFunc)

My problem is not with the semantics or the fact that it does not sort. I am trying to analyze why my program crashes. It performs the sort correctly for 3 tries with the same input and crashed during the 4th. The program flow is same and the values in the vector are identical each time.

If I return a float or an int it crashes.

[MiiNiPaa]

1) Your current fuction (as you post it) can cause infinite loop and (depending on imolementation) stack overflow in sort() function if floats in structure2 are equal (which they probably only will when you define them as compile-time constants — read about dloat comparsion to know why).
2) If any of inclused other data types which you didn't show are not TriviallyCopyable, then you can run into shallow copy problems.

[JLBorges]

> I am trying to analyze why my program crashes.
> It performs the sort correctly for 3 tries with the same input and crashed during the 4th. ...

There is nothing to analyse. Your program crashes because it is not a correct program. There are no guarantees as to what would happen if the requirements as specified in the standard are violated.