Multimap - zwei Einträge mit selbem Key



  • Hallo alle miteinander, ich habe folgendes Problem :

    Ich berechne Streuungen in einem physikalischen System und ordne dafür die kommenden Streuevents in einer Multimap an, wobei der Key (als Double) mit der Zeit des Streuelements belegt wird.(das zweite Element eines Multimap-Eintrags ist eine Struktur mit allen möglichen Informationen zu einer Streuung). Nun ist es natürlich höchst unwahrscheinlich, dass zwei komplett identische Streuzeiten vorkommen, doch in der Tat kommt dies vor, da ich Trillionen von Streuungen berechne. Dabei kommt es zu einem Problem :

    Wenn nun eine neue Streuung berechnet wird, die denselben Key wie eine bereits existente Streuung besitzt, so überschreibt die neue Streuung eine andere existente, welche aber keineswegs überschrieben werden darf. Ich habe bereits überprüft, ob ich irgendwo im Code diesen Eintrag ausversehen manuell mit erase lösche, dies ist aber nicht der Fall.

    Die Einsortierung der Einträge erfolgt mit insert.

    Weiß nun jemand von euch vielleicht, weshalb diese unbeabsichtigte Löschung sich ereignen könnte ? Das Problem ist, dass ich nicht herausfinden konnte, auf welche Art und Weise die Multimap genau mit doppelten Keys verfährt. Ich habe in Erfahrung bringen können, dass zumindest die Reihenfolge der Einsortierung mit dem neuen Standard durch die Reihenfolge der Verwendung im Programm bestimmt ist, mehr aber bisher leider nicht.

    Ich benutze übrigens den C++0x-Standard.

    Ich danke schon einmal für eventuelle Antworten. 🙂


  • Mod

    so überschreibt die neue Streuung eine andere existente, welche aber keineswegs überschrieben werden darf.

    Unmöglich. Die Daseinsberechtigung einer Multimap besteht darin, mehrere identische Keys haben zu können. Wenn du std::multimap verwendest, dann muss irgendwo in deinem Programm ein Fehler sein.

    Kannst du ein reduziertes Beispiel posten?

    Das Problem ist, dass ich nicht herausfinden konnte, auf welche Art und Weise die Multimap genau mit doppelten Keys verfährt.

    Auf dieser Referenz findest du viele Antworten:

    std::multimap schrieb:

    The order of the key-value pairs whose keys compare equivalent is the order of insertion and does not change.

    std::multimap::insert schrieb:

    1-2) inserts value. If the container has elements with equivalent key, inserts at the upper bound of that range.



  • Hallo Arcoth,

    Das ist auch eigentlich der Grund, weshalb die Multimap in dem Programm verwendet wird ^^. Dennoch ist es in der Tat so, dass genau dann, wenn dieser doppelte Key-Eintrag einsortiert wird, der Eintrag direkt dahinter verschwindet. Ich probiere mal, den dafür relevanten Teil aus dem Programm in reduzierter Form zu posten :

    // Deklarationen etc.
    
    vector<struct s_qpart> conf;
    multimap<double,struct s_sct> list;
    struct s_sct sct_event = (*list.begin()).second;                      				
    int index1 = sct_event.p1-1;                        			
    int index2 = sct_event.p2-1;                          	        	 
    double epsilon = 0.001;
    multimap<double, struct s_sct>::iterator k; 
    multimap<double, struct s_sct>::iterator j1; 
    multimap<double, struct s_sct>::iterator j2; 
    multimap<double, struct s_sct>::iterator pointer=list.end();
    
    .
    .
    .
    
    // Hier ist der einzige Ort, an dem manuell Streuevents geloescht werden
    
    list.erase(list.begin());						
    if(conf[index1].tleft>0)                                            
    {
      j1 = list.lower_bound(conf[index1].tleft-epsilon);
      if(j1!=list.begin()){j1--;}
      j2 = list.upper_bound(conf[index1].tleft+epsilon);
      if(j2!=list.end()){j2++;}
      for(k=j1;k!=j2;++k)
        {
          if((*k).second.p1==sct_event.p2){pointer=k;}
        }
      list.erase(pointer);   
    }
    pointer=list.end();
    
    // Dann dasselbe ab dem auesseren if noch einmal mit einer anderen Bedingung.
    .
    .
    .
    // Die Initialisierung neuer Elemente erfolgt dann im Folgenden durch die Funktion setvals, welche in der Struktur selbst definiert ist :
    
    void setvals(double s_tm, double s_posm, int s_p1, int s_p2, int s_sct_index)
    {
    	this->tm = s_tm;
    	this->posm = s_posm;
    	this->p1 = s_p1;
    	this->p2 = s_p2;
    	this->sct_index = s_sct_index;
    }
    // Dadurch wird dann die Struktur sct_event aktualisiert.
    // Danach wird die Multimap aktualisiert:
    
    list.insert(pair<double,struct s_sct>(ttsc+time, sct_event));
    

    An anderen Stellen wird nichts mehr an der Streuliste geändert.

    Wie gesagt : Ich habe schon abgefragt, ob an den erase-Stellen die entsprechende Streuung gelöscht wird. Dies ist aber zu keinem Zeitpunkt der Fall, dennoch verschwindet der Eintrag.

    Es sollte vielleicht noch erwähnt werden, dass, falls in Zeile 29 die Bedingung während der gesamten for-Schleife nicht erfüllt wird, es eine Fehlerausgabe gibt. Also der Fall ist abgedeckt.


  • Mod

    j1 = list.lower_bound(conf[index1].tleft-epsilon);
      if(j1!=list.begin()){j1--;} // ?????????????????????
      j2 = list.upper_bound(conf[index1].tleft+epsilon);
      if(j2!=list.end()){j2++;} // ?????????????????????
    

    Nebenbei bemerkt gibt es noch equal_range.



  • Das j1-- bzw. j2++ dient nur dazu, den Bereich noch etwas zu vergrößern.

    Naja das equal_range sollte ja nichts ändern. Zumal, wie gesagt, die besagte Streuung nicht durch das folgende erase gelöscht wird, das heißt, an dieser Stelle tritt der Fehler eigentlich nicht auf.



  • Hier einmal zum Nachverfolgen der Fehler in Textformat.

    Diejenige Streeuung welche verschwindet, findet zur Zeit 51667.1970751985 zwischen den Teilchen 2335841 und 2335842 statt.

    Die Streuliste zum letzten Zeitpunkt, bevor die Streuung geloescht wird, ist verkuerzt :

    key: 51626.5846575899 p1: 2557142 p2: 2557143
    key: 51626.5849913251 p1: 1932026 p2: 1932027
    .
    .
    .
    key: 51667.1968127370 p1: 1636161 p2: 1636162
    key: 51667.1970751985 p1: 2335841 p2: 2335842 !!!!!! (Diese Streuung)
    key: 51667.1971918319 p1: 1771049 p2: 1771050

    Die Streuliste zur naechsten Zeit ist :

    key: 51626.5849913251 p1: 1932026 p2: 1932027
    .
    .
    .
    key: 51667.1968127370 p1: 1636161 p2: 1636162
    key: 51667.1968127370 p1: 2557141 p2: 2557142
    key: 51667.1971918319 p1: 1771049 p2: 1771050

    Man sieht also, dass an die Stelle der geloeschten Streuung die Streuung tritt, welche denselben Key wie die Streuung davor besitzt.



  • Zeig mal die komplette Funktion zum Löschen. Die Klammern stimmen da nicht so recht.

    Ansonsten:

    Arcoth schrieb:

    Kannst du ein reduziertes Beispiel posten?

    (Kompilierbares Minimalbeispiel bei dem der Fehler noch auftritt.)

    Versuch mal diesen Fehler weiter einzugrenzen... wann genau (Funktion, nicht nur "irgendwann in einem Zeitschritt"... was auch immer da alles passiert) tritt der Fehler auf? Veränderst du Elemente?



  • Ein kompilierbares Beispiel, bei dem der Fehler auftritt, kann ich hier leider nicht posten. Das Programm umfasst insgesamt 9 laengere Dateien und 7 davon sind notwendig, um das Programm reproduzierbar laufen lassen zu koennen. Das wuerde hier wohl den Rahmen sprengen, selbst wenn ich einige Teile noch streichen koennte. Dazu dauert es noch etwa eine halbe Stunde Laufzeit bis dieser Fehler auftritt.

    Ok, in der Tat, die Klammern stimmen so nicht. Ich habe vergessen, eine unnoetige Klammer zu entfernen. Das aendere ich in dem betreffenden Post.
    Der Loeschteil ist bis auf einige Fehlerausgaben komplett, da wird sonst nicht auf die Liste zugegriffen.

    In diesem einen Zeitschritt greift der Code wirklich ausschliesslich in dem geposteten Teil schreibend auf die Streuliste zu. Das heisst, in einem Zeitschritt werden in der Streuliste maximal drei Eintraege willentlich geloescht (und diese willentliche Loeschung loescht nicht die besagte Streuung) und zwei Eintraege werden eingefuegt. Das Einfuegen geschieht ausschliesslich ueber insert, derart wie im Codeausschnitt beschrieben. Eine Aenderung der Eintraege an sich erfolgt zu keinem Zeitpunkt.

    Vielleicht sollte ich noch erwaehnen, dass dieser Fehler in wenigen Runs auftritt. Wenn ich das Programm 100 mal parallel laufen lasse, ereignet sich der Fehler lediglich in jedem fuenfhundertsten bis zwanzigsten (je nach Systemgroesse) Durchlauf, sprich sehr selten, was in mir eben die Vermutung verursacht, dass es auf irgendeine Art und Weise mit den doppelten Keys zu tun hat.
    Dazu kommt noch, dass der Fehler ein Anderer ist, wenn der alte C++-Standard verwendet wird. Den Fehler im alten Standard habe ich aber nicht eingrenzen koennen, da der Fehler dort trotz gleichen Seeds der Zufallszahlen nicht reproduzierbar ist, aus welchem Grunde auch immer.



  • UPDATE :

    Es scheint nun so, dass der Fehler nicht mehr auftritt, wenn man

    list.insert(pair<double,struct s_sct>(ttsc+time,sc_event) );
    

    ersetzt durch:

    multimap<double, struct s_sct>::iterator insrt;
    insrt=list.insert(pair<double,struct s_sct>(ttsc+time,sc_event) );
    

    Das ist zwar schoen, dass das Problem damit geloest scheint, aber hat jemand von euch eine Idee, weshalb der Fehler dadurch verschwindet ? Der neue Iterator insrt wird weiter nicht verwendet. Er wurde nur aus Verzweiflung benutzt ^^.

    Es wurde zuvor nichts weiter mit dem Rueckgabewert von insert getan. Kann es sein, dass dadurch aus irgendeinem Grunde auf den problematischen Listenplatz gezeigt und dadurch an dieser Stelle eingefuegt wurde ?


  • Mod

    hat jemand von euch eine Idee, weshalb der Fehler dadurch verschwindet ?

    Wenn der Fehler tatsächlich genau dadurch verschwindet, gibt es zwei Möglichkeiten:

    • Es gibt einen Bug in der Implementierung von multimap / im Compiler
    • Irgendwo in deinem Programm gibt es UB/IB - irgendeinen Ausdruck welcher vom Standard kein genau definiertes Verhalten zugeschrieben bekommt.

    Übrigens:

    list.insert(pair<double,struct s_sct>(ttsc+time,sc_event) );
    

    ➡

    list.emplace( ttsc+time, sc_event );
    

    Und du könntest an diversen Stellen auto verwenden, statt die Typen von Iteratoren explizit auszuschreiben.



  • Danke fuer den Tipp mit emplace 😉

    Hmm okay, UB/IB ... das kann ja noch lustig werden ^^.
    Nunja, wenigstens ist der Fehler entschwunden. Sollte ich noch weitere Fehler entdecken, werde ich mich im Laufe der Zeit hier noch einmal melden.\

    Auf Jedenfall noch einmal Danke fuer die Hilfe.



  • Wenn du dich auf die Gleichheit bei double verlässt, hast du verloren.
    Kannst du dein Problem nicht ohne double lösen?
    Wenn nicht, nimm wenigstens ein userdefined compare in deine Defintion mit auf.
    multimap ist Schrott, ein Widerspruch in sich, genauso wie multiset.
    Nimm eine unordered_map mit einem vector (von struct) als value, das ist übersichtlicher und 100x performanter.



  • Ich verlasse mich ja gar nicht auf die Gleichheit. Die Gleichheit ist vielmehr ein sehr seltenes Nebenprodukt, was scheinbar zu Problemen fuehrt.

    Danke fuer den Tipp, werde ich mal ausprobieren.

    Ach, ich lese grade, dass einerseits in der unordered_map keine zwei gleichen Keys erlaubt sind und dass andererseits die Iteration ueber Listenelemente dabei ineffizient ist. Zweiteres geschieht aber oefters mal und die Gleichheit zweier keys laesst sich bei Trillionen von Streuungen nicht gaenzlich vermeiden. Bzw du schreibst "mit einem vector von struct als key". Das ist auch etwas problematisch, da das Programm aktuell darauf basiert, dass die Listenelemente tatsaechlich nach der Zeit geordnet sind. Bei nem vector als key waere das ja nicht mehr gewaehrleistet.

    Weshalb denkst du denn, dass Multimap ein Widerspruch in sich ist ?


Log in to reply