Vector manipulieren

Hi,
ich möchte gerne Vector "labelsInRegions" dahingehend manipulieren, dass ich die darin enthaltenen Vektoren zusammenführen und andere wiederum löschen möchte. Das mit dem Löschen klappt gut, nur das Zusammenführen nicht.
Im Code werden labelSetA und labelSetB zusammengeführt, die wiederum in labelsInRegions enthalten sind. Iteriere ich durch labelSetA, dann sehe ich, dass die Vereinigung geklappt hat. Iteriere ich durch labelsInRegions, also der Obermenge, dann sehe ich, dass das fehlgeschlagen hat.
Ich vermute, dass mir die Funktion getLabelSet() eine Kopie eines Iterators gibt, der woanders hinzeigt. Dass der Iterator eine Kopie ist, ist klar, aber ich dachte, er zeigt innerhalb labelsInRegions.

Weiß jemand weiter?

static vector< vector<unsigned char> > resolveLabelCollisions(vector<pair<unsigned char, unsigned char> >& collisions, const unsigned char amountLabels, const unsigned char labelBegin)
{
    vector< vector<unsigned char> > labelsInRegions;

    // Create a partitioning of the labels as a vector of sets, one set for each label
    for (int label = labelBegin; label < amountLabels; label++) {
        vector<unsigned char> labelSet;
        labelSet.push_back(label);

        labelsInRegions.push_back(labelSet);
    }

    vector< pair<unsigned char, unsigned char> >::iterator itCollisions;

    for (itCollisions = collisions.begin(); itCollisions != collisions.end(); itCollisions++) {
        pair<unsigned char, unsigned char> collision = *itCollisions;

        // Get the label set that contains A
        vector<unsigned char> labelSetA = *getLabelSet(labelsInRegions.begin(), labelsInRegions.end(), collision.first);

        // Get the label set that contains B
        vector< vector<unsigned char> >::iterator itLabelSetB = getLabelSet(labelsInRegions.begin(), labelsInRegions.end(), collision.second);
        vector<unsigned char> labelSetB = *itLabelSetB;

        // Union of labelSetA and labelSetB.
        labelSetA.insert(labelSetA.end(), labelSetB.begin(), labelSetB.end());

        // Notiz: Union von labelSetA hat zwar funktioniert, hat aber keine Auswirkungen auf labelsInRegions.

        // Delete labelSetB
        labelsInRegions.erase(itLabelSetB);
    }

    return labelsInRegions;
}

static vector< vector<unsigned char> >::iterator getLabelSet(vector< vector<unsigned char> >::iterator begin, vector< vector<unsigned char> >::iterator end, unsigned char labelToBeSearched)
{
    vector< vector<unsigned char> >::iterator itRegions;

    for (itRegions = begin; itRegions != end; itRegions++) {    
        vector<unsigned char> labels = *itRegions;
        vector<unsigned char>::iterator itLabels;

        for (itLabels = labels.begin(); itLabels != labels.end(); itLabels++) {
            unsigned char label = *itLabels;

            if (label == labelToBeSearched) {
                return itRegions;
            }
        }
    }

    char errorMsg[90];
    sprintf(errorMsg, "mxSequentialLabeling.cpp: label %u not found in function getLabelSet()", labelToBeSearched);
    mexErrMsgTxt(errorMsg);
}

Danke, im Voraus.

Gruß,
IBV

SeppJ

IBV schrieb:

Iteriere ich durch labelsInRegions, also der Obermenge, dann sehe ich, dass das fehlgeschlagen hat.

Du hast ja auch nur deine beiden lokalen Kopien zusammengeführt, die du in Zeilen 19 und 22 erstellt hast. Dir ist schon klar, dass dort keine Iteratoren mehr sind, da du den zurück gegebenen Iterator dereferenzierst?

Allgemein: Dein Code sieht umständlich aus. Da werden haufenweise versteckte Kopien von teuer zu kopierenden Objekten erstellt, bald darauf wieder verworfen und insgesamt passiert aber nicht viel. Genau das, was C-Programmierer denken, was der große Nachteil an C++ wäre. Und meistens falsch liegen, aber hier nicht.

Was soll der Code denn insgesamt machen? Das kann man sicherlich auch wesentlich einfacher (und lesbarer!) erreichen. Sind eventuell auch die Datenstrukturen ungeeignet? An einigen Stelle in deinem Code schreit es für mich geradezu nach einem set/multiset. Und mittels des bewährten Duos aus Templates und Iteratoren könnte man alles viel schöner schreiben, ohne die vieln verschachtelten vector<vector<typ>>.

"amount" heißt übrigens so viel wie "Menge" oder "Größe", nicht "Anzahl". Du suchst "number of".

Hi SeppJ,

also erst mal:

http://www.angelfoodcomic.com/wp-content/uploads/I-have-no-idea-what-I-am-doing.jpg

C++ hatte ich nie gelernt nur Java und C.

Ich versuche das hier umzusetzen:

http://books.google.de/books?id=3u5hboQaJAYC&pg=PA202&lpg=PA200&dq=Die+sequentielle+Regionenmarkierung+ist+eine+klassische,+nicht+rekursive&source=bl&ots=4BExWq6RpB&sig=h3VAnOz8RdEqb2C3AopmeIR_L7Y&hl=de&sa=X&ei=oORzU_rEE-ab1AWY_YCIAQ&ved=0CDUQ6AEwAA#v=onepage&q=Die sequentielle Regionenmarkierung ist eine klassische%2C nicht rekursive&f=false

Verstehe ich richtig, dass bei Zeile 20 und 22 der komplette Vektor mit allen seinen Elementen kopiert wird?!

Gruß,
IBV

SeppJ

IBV schrieb:

Ich versuche das hier umzusetzen:

http://books.google.de/books?id=3u5hboQaJAYC&pg=PA202&lpg=PA200&dq=Die+sequentielle+Regionenmarkierung+ist+eine+klassische,+nicht+rekursive&source=bl&ots=4BExWq6RpB&sig=h3VAnOz8RdEqb2C3AopmeIR_L7Y&hl=de&sa=X&ei=oORzU_rEE-ab1AWY_YCIAQ&ved=0CDUQ6AEwAA#v=onepage&q=Die sequentielle Regionenmarkierung ist eine klassische%2C nicht rekursive&f=false

Die Benutzen den Ausdruck "set" dort nicht ohne Grund. Zwar ist ein Set im Sinne einer mathematischen Menge gemeint, aber eine gute Umsetzung eines Sets in C++ ist eben nicht der vector, sondern das set (oder einer seiner Verwandten, wie multiset, unordered_set & Co.)

Verstehe ich richtig, dass bei Zeile 20 und 22 der komplette Vektor mit allen seinen Elementen kopiert wird?!

Ja. In C++ sind Variablen keine Verweise auf Objekte wie in Java. Das ist ein ganz wichtiger Unterschied und mit einer der Gründe, warum C++-Code oft so viel schneller ist als Java. Leider erreicht man aber den gegenteiligen Effekt, wenn man dies nicht weiß und erzeugt dann ungewollt viele, langsame Kopieraktionen. Ganz zu schweigen natürlich davon, dass das Programm nicht richtig funktioniert. :p

SeppJ schrieb:

Verstehe ich richtig, dass bei Zeile 20 und 22 der komplette Vektor mit allen seinen Elementen kopiert wird?!

Ja. In C++ sind Variablen keine Verweise auf Objekte wie in Java. Das ist ein ganz wichtiger Unterschied und mit einer der Gründe, warum C++-Code oft so viel schneller ist als Java.

Ich komme aber nicht umhin die Iteratoren zu dereferenzieren. Irgendwie muss ich ja auf die Vektoren zugreifen die ich vereinigen und löschen will.
Wie wäre die korrekte Umsetzung?

Gruß,
IBV

Ich habe das Problem dahingehend gelöst, dass getLabelSet() nun den Index des gesuchten Labels zurückgibt. Außerdem muss ich überprüfen, ob Set A und B unterschiedlich sind, sonst wird A in A kopiert und anschließend gelöscht. :p

Gruß,
IBV

SeppJ

IBV schrieb:

Ich komme aber nicht umhin die Iteratoren zu dereferenzieren. Irgendwie muss ich ja auf die Vektoren zugreifen die ich vereinigen und löschen will.
Wie wäre die korrekte Umsetzung?

Das Dereferenzieren der Iteratoren ist nicht das Problem. Dadurch erhältst du einen Verweis auf das referenzierte Objekt. Aber dann machst du eine Kopie von diesem Verweis. Benutz nur so etwas wie die Zeile 22. Nicht so wie Zeile 23 oder 19. Dann arbeite mit den Iteratoren.

Außerdem solltest du den Tipp mit dem set ernster nehmen. Das vereinfacht deinen Code wesentlich.

Hi,
könntest du deinen Tipp mit dem set genauer erläutern?

Als Vorteile fallen mir ein:

- keine doppelten Elemente
- Elemente sind sortiert

Inwiefern kommen diese Vorteile zum Tragen? Ich habe auf set verzichtet, weil ich davon ausging, dass die oben genannten Features Performance-Nachteile haben.

Gruß,
IBV

Ich weiß nicht genau, ob und wie ein std::set jetzt die gesamte Sache vereinfacht.
Aber Dein Code würde sich einfacher lesen lassen mit ein paar typedefs oder using Deklarationen.
Beispielsweise using aus C++11

using label = int;
using collision = std::pair<label, label>;

Wenn Du von Java kommst bist Du ja mit einer reichen Standardbibliothek vertraut: schau wo C++ ähnliches bietet um den Algorithmus aus dem Buch zu implementieren.
Dein getLabelSet() z.B. schaut arg umständlich aus.

C++11 nutzen ( auto !) wenn möglich!

Hi,
danke, aber C++11 kann ich aus Kompatibilitätsgründen nicht benutzen.

Gruß,
IBV

SeppJ

IBV schrieb:

Hi,
danke, aber C++11 kann ich aus Kompatibilitätsgründen nicht benutzen.

Gruß,
IBV

Das geht auch mit typedef genau so.

typedef unsigned char Label;
typedef pair<Label, Label> Collision;
// usw.

Ahja, da war was! Thx.

Gruß,
IBV