Szakkörök‎ > ‎Algoritmus szakkör‎ > ‎2011-2012‎ > ‎

11. óra

2011.12.05.

A mai szakkörön egy a témánkhoz lazán kötődő feladatot kell önállóan megoldani.

Feladat


Megjegyzés: rendezés C++ könyvtári függvénnyel

A megoldás kódolásakor egy érdekes hibajelenséggel találkoztunk, amelynek megfejtése Fehér Gábor segítségével sikerült. Az alábbiakban röviden ismertetjük a problémát.

A jelenség

C++ programozók örömmel használnak standard könyvtárakban található eljárásokat, mert így például nem kell saját rendezést írniuk. tekintsük például a következő kódrészletet:

#include <algorithm>
using namespace std;

bool compare(int a, int b) {
    if( a>b )
        return false;
    else
        return true;
}

int main() {
     int a[50];  // Automatikus inicializálás csupa 0-ra
     sort(a, a+50, compare);
     return 1;
}


Ez a program a fordító beállításaitól és az operációs rendszertől függően elszáll, vagy furcsa viselkedést produkál. Az első lépés a megfejtés felé annak tudatosítása, hogy a compare csak kétféle logikai értéket tud visszaadni, pedig két elem összehasonlításának három kimenete lehet. a < b, a = b, a > b.

Mi történik egyenlőség esetén?

Függvényünk igaz értékkel tér vissza, ha két egyenlő elemet kell összehasonlítania. A C++ referenciába mélyedve rábukkanhatunk arra a bekezdésre, amiből kiderül, hogy ez baj, egyenlőség esetén hamisat kell visszaadni:

"Comparison function object that, taking two values of the same type than those contained in the range, returns true if the first argument goes before the second argument in the specific strict weak ordering it defines, and false otherwise."

Tehát a compare helyesen így néz ki (értelemszerűen a konkrét típus összehasonlítása bonyolultabb):

bool compare(int a, int b) {
    return (a<b);
}

De miért szállt el a program a rossz összehasonlítással?

A C++ belső ügyeinek ismerete nélkül csak találgatni tudunk.

Egy ajánlott diagnosztikai eszköz memóriakezelési hibák felderítéséhez