Sortierung eines OBJEKTArrays



  • Hallo,
    es geht um folgendes Array:
    http://img827.imageshack.us/img827/7438/compn.png

    Nun kann es im Programm passieren, dass ein Objekt mitten im Array gelöscht wird mittels:

    delete e[index_];
    e[index_] = NULL;
    

    Ich muss nun gewährleisten dass sich alle Objekte im Array um eins zurückschieben.
    Also es darf keine Lücke entstehen im Array...

    Mir will allerdings kein passender Algorithmus dazu einfallen...steh voll aufm Schlauch 😡 😡 😡 😡



  • e[index_] = e[index_+1];
    e[index_+1] = e[index_+2];
    e[index_+2] = e[index_+3];
    .
    .

    Schwer, oder?



  • Verwende doch einfach einen vector<>, dann brauchst du nichts weiter tun als

    myvector.erase(myvector.begin()+index);
    

  • Mod

    Wenn das Löschen aus der Mitte häufiger vorkommen sollte, dann bietet sich auch an, über eine andere Datenstruktur nachzudenken, z.B. eine doppelt verkettete Liste. Die kann Elemente in konstanter (und kurzer) Zeit entfernen, während ein Array/Vector dafür eine längere und von der Größe abhängige Zeit benötigt.



  • danke für die Infos hat mir sehr geholfen :p



  • Wenn std::vector nicht in Frage kommt und die Objekte nicht sortiert sind kannst du auch folgendes machen:

    void remove( unsigned int Index )
    {
      // Size ist Anzahl der Elemente im Array
      if( Size > 0 && Index < Size )
      {
         arr[Index] = arr[Size -1];
         arr[Size -1] = NULL;
         --Size;
      }
    }
    

    Damit ersetzt du das zu löschende Element durch das letzte im Array und löscht das letzte Element, allerdings geht damit die Sortierung verloren. Wenn die Sortierung allerdings wichtig ist musst du jedes Element eine Position nach unten rutschen lassen, so wie Challenge Accepted es schon gezeigt hat.
    std::vector ist aber mit Sicherheit die bessere Alternative.


Anmelden zum Antworten