Werte-Tabellen vergleichen und zusammenführen



  • Hallo,

    ich lese in diesem Forum seit geraumer Zeit mit und nun auch mein erster Beitrag. Seit geraumer Zeit lerne ich C++.
    Mein Problem:
    Ich hab 2 Tabellen mit zum Teil unterschiedlichen Werten, bei denen die Reihenfolge wichtig ist.
    Diese beiden Tabellen sollen nun vereint werden und die Reihenfolge soll dabei erhalten bleiben.
    Beispiel:

    Tabelle 1:
    7
    4
    76
    2
    4
    6
    Tabelle 2:
    76
    2
    4
    6
    8
    9
    5
    

    Welchen Containertyp könntet ihr mir empfehlen. Ich dachte an Vector, weiß aber nicht, wie es da mit der Geschwindigkeit aussieht, denn am Ende sollen größere Tabellen und mehr Tabellen vereint werden. Set wäre noch eine Idee.
    Vielen Dank für einen Tipp.



  • Du willst die Inhalte hintereinanderhängen mit letztes_Element_Container_1 vor erstem_Element_Container_2?

    vector ist ziemlich ok. Der ist speicherschonend und fürs Lesen schnell. Das Einfügen könnte etwas länger dauern, für das Einfügen am Ende ist das aber kein Ding.

    vector<int> vec1, vec2;
    // insert values
    vec1.insert(vec1.end(), vec2.begin(), vec2.end());
    

    Ansonsten ein Decision Flow Chart: http://linuxsoftware.co.nz/containerchoice.png



  • Danke für die schnelle Antwort.
    Es war nur ein Beispiel wie es seien könnte (scheinbar ein Schlechtes 🤡 ).
    Durchaus können auch beide Tabellen die komplette Werte vom Anfang an enthalten und nur am Ende einen weiteren Wert.
    Ich werde mal anfangen den Pseudo-Code zu schreiben und dann schauen wir mal 😉



  • Achso, du willst keine doppelten Einträge. Und was willst Du bei so was haben?

    19
    23
    2
    5

    19
    23
    7
    2
    5

    Soll der beide Listen in Kombination automatisch zu Liste 2 machen oder wie?



  • also wenn du keine doppelten werte haben willst kannst du ja std::set nehmen



  • unique()



  • Skym0sh0 schrieb:

    also wenn du keine doppelten werte haben willst kannst du ja std::set nehmen

    Ist es dann schneller oder was spricht für std::set?
    Bin noch nicht ganz so vertraut mit den Containerklassen.

    Eisflamme schrieb:

    Achso, du willst keine doppelten Einträge. Und was willst Du bei so was haben?

    19
    23
    2
    5

    19
    23
    7
    2
    5

    Soll der beide Listen in Kombination automatisch zu Liste 2 machen oder wie?

    Das sollte so nicht vorkommen.



  • Skym0sh0 schrieb:

    also wenn du keine doppelten werte haben willst kannst du ja std::set nehmen

    Da würde aber die Reihenfolge zerstört werden, die dem TO ja wichtig ist.

    @TO:
    Kannst Du mal ein Beispiel für zwei Tabellen machen (am besten auch mit gleichen Werten in beiden Tabellen, sofern das vorkommen kann), und dann die zusammengeführte Tabelle zeigen, wie sie aussehen soll?



  • Tachyon schrieb:

    Kannst Du mal ein Beispiel für zwei Tabellen machen (am besten auch mit gleichen Werten in beiden Tabellen, sofern das vorkommen kann), und dann die zusammengeführte Tabelle zeigen, wie sie aussehen soll?

    Tab1:

    24673935
    766939640
    434179167
    25553428
    24673961
    434179168
    449119011
    1196571958
    1196571891
    25553429
    

    Tab2:

    449119011
    1196571958
    1196571891
    25553429
    1196571854
    24673958
    258336940
    25553430
    24673940
    25553431
    24673937
    287763108
    287763107
    24669553
    

    TabGes:

    24673935
    766939640
    434179167
    25553428
    24673961
    434179168
    449119011
    1196571958
    1196571891
    25553429
    1196571854
    24673958
    258336940
    25553430
    24673940
    25553431
    24673937
    287763108
    287763107
    24669553
    

    Tabelle 2 fängt hier z.B. an der 7. Position von Tabelle 1 an. Das Beispiel kann aber auch andersrum kommen, d.h. Tab1 und Tab2 vertauscht.
    Danke und VG



  • Also überlappen sich Tabelle 1 und 2 stets in der Weise, dass es sich quasi um überschneidende Ausschnitte einer ungenannten dritten großen Tabelle handelt?

    Kann es Duplikate geben? Sonst hat man hier ein Problem:

    Tab 1)
    1
    4
    2
    3
    4

    Tab 2)
    4
    2
    4

    Wie soll das gemerged werden?

    Ich denke, vector ist schon ganz gut. Die Frage, die sich hier stellt, ist eher welchen Algorithmus Du anwenden möchtest. Vielleicht lässt sich das gar nicht fehlerfrei umsetzen, das wär schade.



  • Eisflamme schrieb:

    Also überlappen sich Tabelle 1 und 2 stets in der Weise, dass es sich quasi um überschneidende Ausschnitte einer ungenannten dritten großen Tabelle handelt?

    Kann es Duplikate geben? Sonst hat man hier ein Problem:

    Tab 1)
    1
    4
    2
    3
    4

    Tab 2)
    4
    2
    4

    Wie soll das gemerged werden?

    Ich denke, vector ist schon ganz gut. Die Frage, die sich hier stellt, ist eher welchen Algorithmus Du anwenden möchtest. Vielleicht lässt sich das gar nicht fehlerfrei umsetzen, das wär schade.

    Wie ich schon sagte, so etwas sollte nicht vorkommen... Er sollte also prüfen, ob wenigstens 2 Elemente vor dem mergen hintereinander passen, andernfalls vielleicht eine Fehlermeldung ausgeben...



  • Na ja, das waren ja zwei andere Fragestellungen.

    Also die Annahmen sind:
    - es gibt keine doppelten Elemente
    - wenn es eine Dopplung gibt, sollten die Einträge solange übereinstimmen, bis eine der beiden Liste zu Ende ist, der überlappende Teil ist dann das Anhängsel

    Dann:

    typedef vector<int> WhatEverVector;
    typedef WhatEverVector::const_iterator WhatEverVectorIterator;
    
    WhatEverVector merge(const WhatEverVector& v1, const WhatEverVector& v2)
    {
        WhatEverVector r;
    
        // Find Same Element
        WhatEverVectorIterator n, m;
        std::size_t nnum, mnum;
        for(nnum = 0, n = v1.begin(); n != v1.end(); ++n, ++nnum)
            for(mnum = 0, m = v2.begin(); m < v2.end(); ++m, ++mnum)
                if(*n == *m)
                    goto afterLoop;
        afterLoop:
    
        if(m == v2.end())
            throw std::runtime_error("Lists are not mergeable.");
    
        if(nnum >= mnum)
            r.insert(r.begin(), v1.begin(), n);
        else
            r.insert(r.begin(), v2.begin(), m);
    
        const std::size_t MIN_MATCHES = 2;
        // Now, Check if vectors are mergeable
        for(std::size_t counter = 0; nnum < v1.size() && mnum < v2.size() && counter < MIN_MATCHES; ++nnum, ++mnum, ++counter)
            if(v1[nnum] != v2[mnum])
                throw std::runtime_error("Lists are not mergeable");
    
        // If yes, add vector which hasn't been added yet to result
        if(nnum >= mnum)
            r.insert(r.end(), m, v2.end());
        else
            r.insert(r.end(), n, v1.end());
        return r;
    }
    

    Ungetestet, sicherlich nicht super-sauber, bei den copys ist was falsch, für sonstige korrekte Wirkweise garantiere ich ebenfalls nicht, aber ich denke, die Idee kann man nachvollziehen.



  • Danke Eisflamme!
    Hast du das so schnell zusammengebastelt? 😮
    Dafür würde ich Stunden || Tage benötigen...
    Und es sieht sauberer als mein angefangenes Gebastel...

    Danke noch einmal...



  • Is nur hier im Forum hingeklatscht, daher sind da auch sicher viele Flüchtigkeitsfehler drin. Wie gesagt, sollte nur ne Idee sein.



  • Ok, sorry, hab schon nen ersten Fehler gefunden: copy benötigt, dass der Speicher zusätzlich reserviert wurde, sonst dumpts. Daher nutze ich nun insert. Hab Code oben editiert!

    Außerdem sollten die Argumente obv konstante Referenzen sein und der Iterator daher natürlich auch ein const_iterator. Ist editiert.

    Und der dritte Fehler: Das break oben hat ja nur die innere Schleife beendet. Da es kein double-break gibt, bin ich böööööööööööööööööööööööööööööööööööööse und nutze ein goto. Das sollte man aber normalerweise nie machen. Keine Ahnung, mir gefällt das da besser als eine extra bool-Variable, die man nach jedem Durchlauf der inneren Schleife abfragen muss... Aber nimm Dir daran kein Beispiel, gotos sollte man im Normalfall nie benutzen!

    Das ist aber oben jetzt alles reineditiert. Kannst ja sagen, ob Du weitere Fehler findest.

    Kann auch gut sein, dass man das eleganter lösen kann, aber war ja nur so hingeklatscht, hm...



  • Ich hab gerade gesehen, dass du noch einmal alles überarbeitet hast.
    Jetzt läuft es wie eine 1 😉
    Eine Frage:
    Du programmierst unter Windows oder warum meckert g++ bei std::runtime_error?
    Manchmal hat man das Gefühl, dass man in einem Jahr nichts gelernt hat, wenn man sieht, wie schnell und einfach es manchen Leuten von der Hand geht...



  • Geht's, wenn Du <stdexcept> inkludierst?

    Und puh... ich programmiere C++ streng genommen (mit vielen, teilweise über ein Jahr langen Pausen) seit 8 Jahren und ich bin der totale n00b. Mein Codedesign ist schlecht, ich habe hier viele wirklich dumme Flüchtigkeitsfehler eingebaut und ich hänge auch so ständig hier im Forum rum und lese viel.

    Dennoch bin ich ein kleiner Fisch und kaum zu gebrauchen. Glaub mir, wenn man die investierte Zeit in Bezug zur Leistung vergleicht wirst Du deutlich besser als ich abschneiden. Ein Jahr ist ohnehin kurz und die Hauptsache ist dann sowieso, dass es Spaß macht, also schmeiß solche Aussagen direkt übern Kutter.

    Aber es freut mich, dass Dir dieser Codeschnipsel hilft. 🙂



  • Okay,

    ein kleinen Fehler hab ich noch gefunden. Wenn ich die beiden Vektoren vertausche, kommt Bullsh!t raus. Also wenn das erste Element aus Tabelle 1 das vorletzte Element aus Tabelle 2 ist, schreibt er alles stumpf hintereinander (das letzte Element aus Tabelle 1 in diesem Beispiel lässt er dann weg).

    449119011
    1196571958
    1196571891
    25553429
    1196571854
    24673958
    258336940
    25553430
    24673940
    25553431
    24673937
    287763108
    287763107
    24673935
    766939640
    434179167
    25553428
    24673961
    434179168
    449119011
    1196571958
    1196571891
    25553429
    


  • Hm, musste Mal debuggen, ich hab jetzt leider keine Zeit mehr. Vll schau ich nochmal später oder morgen rein. 🙂



  • Eisflamme schrieb:

    Hm, musste Mal debuggen, ich hab jetzt leider keine Zeit mehr. Vll schau ich nochmal später oder morgen rein. 🙂

    Kommando zurück, funktioniert bestens!
    Danke 😃


Anmelden zum Antworten