[C++] Array indexen sorteren

[Twilight Burn]

Ik ben bezig met een C++ applicatie, en ik heb twee arrays, zeg array A[100] en B[100]. Array A bevat de hoogtes van cellen, en array B bevat initieel indexen van A (dus B[x] == x), met uitzondering van een paar die niet meegenomen moeten worden, hiervoor geld B[y] = -1.

Nu wil ik B oplopend sorteren, aan de hand van de hoogte van A. Ik kan A zelf niet sorteren, omdat ik later ook nog naar de buren van cellen in A moet kijken.

Dit doe ik nu op de volgende manier:

C++:

sort(B, B + 100, heightSort);

inline bool heightSort(int index1, int index2) {
    if (index1 == -1) return false;
    if (index2 == -1) return true;
    return A[index1] < A[index2];
}

Dit werkt goed, mits ik A globaal definieer (althans, in dezelfde scope als de functie heightSort, en de functie die de sort() aanroept) - dit is alleen niet wat ik wil, ik wil namelijk verschillende array's "A" kunnen gebruiken. Hoe kan ik dus A als parameter meegeven aan de sort functie?

[Shadowman]

Denk niet dat het zo gaat werken aangezien je geen index meekrijgt, maar de inhoud.

Je kunt zo proberen om het toch voor elkaar te krijgen:

C++:

struct heightSort {
        int *a;
        inline bool operator()(int index1, int index2) {
                if (index1 == -1) return false;
                if (index2 == -1) return true;
                return a[index1] < a[index2];
        }
} heightSort;

met aanroep:

C++:

heightSort.a = A;
sort(B, B+100, heightSort);

edit:
@QuaQu: De naamgeving van de parameters is (semantisch gezien) onjuist, je krijgt bij de heightSort-functie twee elementen uit de array mee, niet de indexen van die twee elementen (zoals de naamgeving suggereert).

[ Voor 18% gewijzigd door Shadowman op 11-06-2007 17:16 ]

[QuaQu]

Misschien moet je eens kijken naar arrays en pointers, dat staat in elke fatsoenlijke C-tutorial wel genoemd voor les nr. 10. Je moet denk ik de indexen van de arrays en de pointers van de arrays meegeven, dan kan je daar verder elke willekeurige sorteeractie voor lke index en array-combinatie.
Even wat handige zoektermen door GooGle halen en je bent er! Zolas bijvoorbeeld "c arrays pointers tutorial"

C:

sort(B, B + 100, heightSort);

C:

inline bool heightSort(int index1, int index2)

Hoe zit dit? heightSort krijgt helemaal geen parameters mee....
Laat maar, dat kan in princiepe verder prima. Je gebruikt met "B, B+100" de pointers al verder goed icm arrays, waarom dat niet gewoon verder uitbreiden naar de functie heightSort?
Edit:

C:

 if (index1 == -1) return false; 

een index van -1? Dat lijkt me nogal onwaarschijnlijk en ook niet echt best qua geheugenmanagement als dit voor kan komen!
Je bedoelt neem ik aan

C:

if(array[index] == -1) return false;

[ Voor 23% gewijzigd door QuaQu op 11-06-2007 17:06 ]

[Twilight Burn]

De heigtsort functie krijgt inderdaad de twee waarden uit de B array mee. Deze waarden worden gebruikt als indexen in de A array. Ik had ook pointers naar elementen in de A array kunnen gebruiken, maar dat lost het probleem niet op.

Array A bevat (een deel van) een terrein (elk element in het array bevat de hoogte van een cel van het terrein)

In het algoritme moet ik alle cellen in het terrein (behalve die op de rand) van laag naar hoog afwerken. Op het moment dat ik een cel verwerk, moet ik ook naar de buren van die cel kijken, ik kan daarom array A dus niet sorteren.
Vandaar dat ik dus een array B gebruik, die de indexen (pointers) naar elementen in A bevat. De elementen die op de rand liggen mogen niet meegenomen worden, dus die zet ik op "-1" in array B.

De code zoals ik die gegeven heb is de huidige code die ik gebruik, en die werkt dus gewoon! De enige aanpassing die ik zoek, is dat ik array A variabel kan maken, zodat ik meer dan een deel van het terrein tegelijkertijd kan verwerken.

[.oisyn]

QuaQu schreef op maandag 11 juni 2007 @ 16:55:
[hele post over C]

Newsflash: C is geen C++

Twilight Burn schreef op maandag 11 juni 2007 @ 18:04:
De code zoals ik die gegeven heb is de huidige code die ik gebruik, en die werkt dus gewoon! De enige aanpassing die ik zoek, is dat ik array A variabel kan maken, zodat ik meer dan een deel van het terrein tegelijkertijd kan verwerken.

Wat werkt er niet aan de oplossing van Shadowman?

[ Voor 56% gewijzigd door .oisyn op 11-06-2007 18:09 ]

[Twilight Burn]

.oisyn schreef op maandag 11 juni 2007 @ 18:07:

[...]

Wat werkt er niet aan de oplossing van Shadowman?

Ik wil de code parallel gaan uitvoeren, de oplossing van Shadowman laat men nog maar array A tegelijk sorteren.

[.oisyn]

En verder snap je C++ gewoon niet? Want het lijkt me nou niet zo heel erg moeilijk om het om te zetten naar iets dat wél parallel werkt (wat hij doet met die globale variabele is sowieso erg vies, dan kun je net zo goed je A array globaal maken en de functie gebruiken die je nu al hebt)

C++:

struct HeightSort
{
    int * array;
    HeightSort(int * a) : array(a) { }
    bool operator()(int index1, int index2) { /* whatever */ }
}

void foo()
{
    std::sort(B, B+100, HeightSort(A));
}

[ Voor 10% gewijzigd door .oisyn op 11-06-2007 18:34 ]

[Twilight Burn]

Dat lijkt inderdaad wel te werken. C++ is idd niet een taal waar ik erg thuis in ben.