How can I define the operator< for a struct?

Question

I have the srtucts:

struct Arco {

    int i, j;
    Arco () {};
    Arco (const Arco& obj): i(obj.i), j(obj.j) {};
    Arco(int _i, int _j) : i(_i), j(_j) {}    

};

struct ARCO_TEMPO {
    Arco a;
    int slotTimeU; 
    int slotTimeV; 
    ARCO_TEMPO () {};
    ARCO_TEMPO (const ARCO_TEMPO& obj): a(obj.a), slotTimeU(obj.slotTimeU), slotTimeV(obj.slotTimeV) {};
    ARCO_TEMPO (Arco _a, int _slotTimeU, int _slotTimeV) : a(_a), slotTimeU(_slotTimeU), slotTimeV(_slotTimeV) {}    

};

struct CICLO {
    set<ARCO_TEMPO> arco_tempo_order;
    set<int> arco_tempo_Aux;
    int aircraftType; 
    float COST;
    float reducedCost;
    float duracao;
    int numAircrafts;
    vector<bool> VisitedNodes; 
    vector<vector<bool>> VisitedVertices;
};

I need to define the operator< to the struct CICLO. As I want to order the CICLOs by their COSTs, I start the comparison by their COSTs. Next, I verify if the CICLOs are operated by the same aircraft, and then if they have the same amount of ARCOs_TEMPO. If it is the case, I need to verify if these ARCOs_TEMPO are the same. Using these ideas, I wrote the code below: (I wrote same couts to try to analyze where is the problem)

bool operator<(const CICLO& obj1, const CICLO& obj2) {

    cout << "obj1  = { aircraft type: "<< obj1.aircraftType << " " ;
    set<ARCO_TEMPO>::iterator itobj1;
    for (itobj1 = obj1.arco_tempo_order.begin();  itobj1 != obj1.arco_tempo_order.end(); itobj1++) {
        cout << "(" << itobj1->a.i+1 << "," << itobj1->a.j+1 << ")-("<<itobj1->slotTimeU<<", "<<itobj1->slotTimeV << "); ";
    }
    printf (" COST: %.0f }\n", obj1.COST);

    cout << "obj2  = { aircraft type: "<< obj2.aircraftType << " " ;
    set<ARCO_TEMPO>::iterator itobj2;
    for (itobj2 = obj2.arco_tempo_order.begin();  itobj2 != obj2.arco_tempo_order.end(); itobj2++) {
        cout << "(" << itobj2->a.i+1 << "," << itobj2->a.j+1 << ")-("<<itobj2->slotTimeU<<", "<<itobj2->slotTimeV << "); ";
    }
    printf (" COST: %.0f }\n", obj2.COST);

    if (obj1.COST < obj2.COST - 1) {
        cout << "1\n";
        return true;
    }
    else {
        if ( (abs(obj1.COST - obj2.COST) < 1) && obj1.aircraftType < obj2.aircraftType) {
            cout << "2\n";
            return true;
        }
        else {
            if (obj1.aircraftType == obj2.aircraftType && (abs(obj1.COST - obj2.COST) < 1) && obj1.arco_tempo_order.size() < obj2.arco_tempo_order.size()) {
                cout << "3\n";
                return true;
            }
            else {
                if (obj1.aircraftType == obj2.aircraftType && (abs(obj1.COST - obj2.COST) < 1) && obj1.arco_tempo_order.size() == obj2.arco_tempo_order.size()) {
                    bool igual = true;
                    set<ARCO_TEMPO>::iterator itobj1;
                    set<ARCO_TEMPO>::iterator itobj2;
                    for (itobj1 = obj1.arco_tempo_order.begin(), itobj2 = obj2.arco_tempo_order.begin();  itobj1 != obj1.arco_tempo_order.end(); itobj1++,itobj2++) {
                        if (igual && *itobj1 < *itobj2) {
                            cout << "4\n";
                            return true;
                        } 
                        else {
                            if (itobj1->a.i == itobj2->a.i && itobj1->a.j == itobj2->a.j && itobj1->slotTimeU == itobj2->slotTimeU && itobj1->slotTimeV == itobj2->slotTimeV) {
                                igual = true;
                            }
                            else {
                                cout << "5\n";
                                return false;
                            }
                        }
                    }
                    cout << "6\n";
                    return false;
                }
                else{ 
                    cout << "7\n"; 
                    return false;
                }
            }
        }
    }
}

However, different cycles are being considered as equals. I have a set of CICLOs:

set<CICLO>ConjCiclos;

I insert some inicial CICLOS in ConjCiclos, having ConjCiclos =

CICLO[1] = { aircraft type: 2; arco_tempo_order: (4,5)-(1, 2); (5,4)-(2, 3); (4,4)-(3, 4); (4,4)-(4, 5); (4,4)-(5, 6); (4,4)-(6, 7); (4,4)-(7, 1);  COST: 25000096 }
CICLO[2] = { aircraft type: 2; arco_tempo_order:  (1,5)-(1, 2); (5,1)-(2, 3); (1,1)-(3, 4); (1,1)-(4, 5); (1,1)-(5, 6); (1,1)-(6, 7); (1,1)-(7, 1);  COST: 25000142 }
CICLO[3] = { aircraft type: 2; arco_tempo_order:  (2,5)-(1, 2); (5,2)-(2, 3); (2,2)-(3, 4); (2,2)-(4, 5); (2,2)-(5, 6); (2,2)-(6, 7); (2,2)-(7, 1);  COST: 25000164 }
CICLO[4] = { aircraft type: 2; arco_tempo_order:  (1,2)-(1, 2); (2,1)-(2, 3); (1,1)-(3, 4); (1,1)-(4, 5); (1,1)-(5, 6); (1,1)-(6, 7); (1,1)-(7, 1);  COST: 25000220 }
CICLO[5] = { aircraft type: 2; arco_tempo_order:  (1,4)-(1, 2); (4,1)-(2, 3); (1,1)-(3, 4); (1,1)-(4, 5); (1,1)-(5, 6); (1,1)-(6, 7); (1,1)-(7, 1);  COST: 25000228 }
CICLO[6] = { aircraft type: 2; arco_tempo_order:  (2,4)-(1, 2); (4,2)-(2, 3); (2,2)-(3, 4); (2,2)-(4, 5); (2,2)-(5, 6); (2,2)-(6, 7); (2,2)-(7, 1);  COST: 25000232 }
CICLO[7] = { aircraft type: 2; arco_tempo_order:  (3,5)-(1, 2); (5,3)-(2, 3); (3,3)-(3, 4); (3,3)-(4, 5); (3,3)-(5, 6); (3,3)-(6, 7); (3,3)-(7, 1);  COST: 25000284 }
CICLO[8] = { aircraft type: 2; arco_tempo_order:  (3,4)-(1, 2); (4,3)-(2, 3); (3,3)-(3, 4); (3,3)-(4, 5); (3,3)-(5, 6); (3,3)-(6, 7); (3,3)-(7, 1);  COST: 25000326 }
CICLO[9] = { aircraft type: 2; arco_tempo_order:  (1,3)-(1, 2); (3,1)-(2, 3); (1,1)-(3, 4); (1,1)-(4, 5); (1,1)-(5, 6); (1,1)-(6, 7); (1,1)-(7, 1);  COST: 25000360 }

I try to add a different cycle to ConjCiclos:

CICLO[10] = { aircraft type: 2; arco_tempo_order:  (2,3)-(1, 2); (3,2)-(2, 3); (2,2)-(3, 4); (2,2)-(4, 5); (2,2)-(5, 6); (2,2)-(6, 7); (2,2)-(7, 1);  COST: 25000140 }

As we can see, CICLO[10] is a new CICLO to ConjCiclos, but it detects CICLO[10] as a redundant CICLO.

Debugging the code, I verify that it makes the comparasion of CICLO[10] as:

obj1  = { aircraft type: 2 (1,4)-(1, 2); (4,1)-(2, 3); (1,1)-(3, 4); (1,1)-(4, 5); (1,1)-(5, 6); (1,1)-(6, 7); (1,1)-(7, 1);  COST: 25000228 }
obj2  = { aircraft type: 2 (2,3)-(1, 2); (3,2)-(2, 3); (2,2)-(3, 4); (2,2)-(4, 5); (2,2)-(5, 6); (2,2)-(6, 7); (2,2)-(7, 1);  COST: 25000140 }
7
obj1  = { aircraft type: 2 (2,5)-(1, 2); (5,2)-(2, 3); (2,2)-(3, 4); (2,2)-(4, 5); (2,2)-(5, 6); (2,2)-(6, 7); (2,2)-(7, 1);  COST: 25000164 }
obj2  = { aircraft type: 2 (2,3)-(1, 2); (3,2)-(2, 3); (2,2)-(3, 4); (2,2)-(4, 5); (2,2)-(5, 6); (2,2)-(6, 7); (2,2)-(7, 1);  COST: 25000140 }
7
obj1  = { aircraft type: 2 (1,5)-(1, 2); (5,1)-(2, 3); (1,1)-(3, 4); (1,1)-(4, 5); (1,1)-(5, 6); (1,1)-(6, 7); (1,1)-(7, 1);  COST: 25000142 }
obj2  = { aircraft type: 2 (2,3)-(1, 2); (3,2)-(2, 3); (2,2)-(3, 4); (2,2)-(4, 5); (2,2)-(5, 6); (2,2)-(6, 7); (2,2)-(7, 1);  COST: 25000140 }
7
obj1  = { aircraft type: 2 (4,5)-(1, 2); (5,4)-(2, 3); (4,4)-(3, 4); (4,4)-(4, 5); (4,4)-(5, 6); (4,4)-(6, 7); (4,4)-(7, 1);  COST: 25000096 }
obj2  = { aircraft type: 2 (2,3)-(1, 2); (3,2)-(2, 3); (2,2)-(3, 4); (2,2)-(4, 5); (2,2)-(5, 6); (2,2)-(6, 7); (2,2)-(7, 1);  COST: 25000140 }
1
obj1  = { aircraft type: 2 (2,3)-(1, 2); (3,2)-(2, 3); (2,2)-(3, 4); (2,2)-(4, 5); (2,2)-(5, 6); (2,2)-(6, 7); (2,2)-(7, 1);  COST: 25000140 }
obj2  = { aircraft type: 2 (1,5)-(1, 2); (5,1)-(2, 3); (1,1)-(3, 4); (1,1)-(4, 5); (1,1)-(5, 6); (1,1)-(6, 7); (1,1)-(7, 1);  COST: 25000142 }
7

If I try to replace the operator< function to the one below:

bool operator<(const CICLO& lhs, const CICLO& rhs) { return std::tie(lhs.COST, lhs.aircraftType, lhs.arco_tempo_order) < std::tie(rhs.COST, rhs.aircraftType, rhs.arco_tempo_order); }

the same CICLO is added a lot of time.

I have for example both of CICLOs below added:

CICLO[11499] = { aircraft type: 2 (3,2)-(3, 4); (2,1)-(4, 5); (1,5)-(5, 1); (5,5)-(1, 2); (5,5)-(2, 3); (5,5)-(3, 4); (5,3)-(4, 5); (3,3)-(5, 1); (3,3)-(1, 2); (3,3)-(2, 3);  COST: 46000392.0000000000 }
CICLOIT[11500] = { aircraft type: 2 (3,2)-(3, 4); (2,1)-(4, 5); (1,5)-(5, 1); (5,5)-(1, 2); (5,5)-(2, 3); (5,5)-(3, 4); (5,5)-(4, 5); (5,3)-(5, 1); (3,3)-(1, 2); (3,3)-(2, 3);  COST: 46000392.0000000000 }

Does anyone know why it is happening?

Welcome to Stack Overflow. Can you give us an example of two CICLOs, what the operator ought to return, and what it actually does return? — Beta, Apr 09 '18 at 20:32
Simply use something like: `bool operator<(const CICLO& lhs, const CICLO& rhs) { return std::tie(lhs.COST, lhs.aircraftType, lhs.arco_tempo_order) < std::tie(rhs.COST, rhs.aircraftType, rhs.arco_tempo_order); }` — Jarod42, Apr 09 '18 at 20:35
Even if COST, aircraftType and arco_tempo_order.size() are the same, I need to vrify each ARCO_TEMPO within arco_tempo_order to conclude if the two CICLOs are or not the same. So, I don't think I can use only what you said, @Jarod42! — rbl, Apr 09 '18 at 20:39
When I try to replace my operator< for yours, the same CICLO is generated a lot of times. I think that as COST is a float variable, and I am working with big and small values to calculate COST, I need to add some small value in the original COST. I think that it is considering equal CICLOS as different ones because of a little difference in COST values. I tried to add 1 in rhs.COST, but then a error message appears. — rbl, Apr 09 '18 at 21:08

Martin York · Answer 1 · 2018-04-09T20:50:06.287

1

The operator < has to have a "Strict Weak Ordering" for it to work correctly with the STL.

This statement:

if (obj1.COST < obj2.COST - 1) {
    return true;
}

Makes the condition untrue.

obj1.COST = 9;
obj2.COST = 10;

obj1 < obj2      false
obj2 < obj1      false

This implies the two objects are equal (all other things being the same).

Lets extend this to three objects.

obj1.COST = 9;
obj2.COST = 10;
obj3.COST = 11;

obj1 < obj2      false
obj2 < obj1      false
// So obj1 == obj2


obj2 < obj3      false
obj3 < obj2      false
// So obj2 == obj3

// This we should be able to assume:
obj1 == obj3
// Otherwise strict weak ordering is not working.


obj1 < obj3      true
obj3 < obj1      false
// So they are not equal.
// Something is very wrong and thus your set is not going to work.

Checkout this answer for https://stackoverflow.com/a/37269108/14065 for an easy way to implement the solution.

edited Apr 09 '18 at 20:50

answered Apr 09 '18 at 20:38

Martin York

257,169
86
333
562

The thing is that I am delaing with big values of COST. Then, I won't have CICLOS with cost difference of one unit. I tried to replace my operator< for the one that @Jarod42! suggested, but in thta case, the same CICLO is added a lot of time. – rbl Apr 09 '18 at 21:15
@LuizaReal Basically you need to define the less than in a way that is consistent. Your method is not consistent. You need to think of another way of doing this (subtracting 1 from the rhs is not going to work). Comparing floating point values is always going to be tricky (try and avoid that (i.e. cast to integer). – Martin York Apr 09 '18 at 23:45
Thank you, @MartinYork! I replace float by double and that worked. – rbl Apr 11 '18 at 14:48

How can I define the operator< for a struct?

1 Answers1