3. std::vector kopieren - was passiert da eigentlich?

std::vector kopieren - was passiert da eigentlich?

  • P

    Hi,

    Ich arbeite momentan viel mit std::vector-Datenstrukturen, die viele Elemente enthalten (~100.000+). Nun möchte ich einige Elemente im std::vector durch andere Elemente ersetzen, d.h. Formal das Element an Stelle i durch das Element e ersetzen:

    Bei [1,2,3,4,5] möchte ich z.B. 3 durch 10 ersetzen, also [1,2,10,4,5] haben. Wichtig ist dabei, dass sich die Positionen der anderen Elemente nicht ändert.

    Welche Methode ist hier nun eleganter und vorallem effizienter:
    (1) Das Element an der Stelle i löschen und e an dieser Stelle einfügen
    -> Sollte e dann kopiert werden oder sollte e tatsächlich das Element sein?
    (2) Das Element an der Stelle i einfach ändern, sodass es dieselben Werte wie e hat (erfordert dann setter o.Ä.)

    Konkret sieht die Datenstruktur/Funktion wie folgt aus:

    std::vector<myElement> elements;

void updateElement(const std::vector<MyElement*> &elementsToChange);

    Momentan ändere ich das Element einfach an der Stelle i, d.h. ich verwende Methode (2). Dabei kam mir eine weitere Frage auf:

    Die Klasse MyElement enthält wiederum std::vector-en, die ich kopieren muss. Das tue ich momentan mit dem Aufruf:

    // In Klassendef: 
std::vector<nocheEineKlasse> someOtherVector;

// Funktion zum kopieren
void copyVector(const MyElement &ele) {
someOtherVector = std::vector<nocheEineKlasse>(ele.someOtherVector.begin(), ele.someOtherVector.end());
 //...
}

    Bin mir nicht 100%ig sicher, ob der Aufruf so compiliert wird - habe das gerade aus dem Kopf getippt, da ich nicht zu Hause bin. Ich denke/hoffe jedoch, dass die Idee klar wird.
    Hierbei frage ich mich nun, was genau passiert:
    someOtherVector wird im c'tor von MyElement mit dem STL- Standard c'tor aufgerufen (d.h. kein new verwendet). Die alten Elemente im std::vector werden damit dann doch ungültig und einfach gelöscht, oder?
    Die neuen Elemente in someOtherVector werden durch Aufruf des copy c'tors von nochEineKlasse erschaffen und dann einfach eingefügt oder werden die Klassen anders kopiert?

    Viele Grüße

    Pille

    0
  • Mod

    Erste Frage: Nimm unbedingt die Methode 2! Wie kommst du auf die Idee, dass zu ändern eines Elementes eine andere Methode in Frage kommt als, nun ja, das Element zu ändern? Bei Methode 1 müssten alle nachfolgenden Elemente um 1 nach vorne verschoben werden und dann wieder um 1 nach hinten geschoben. Das würde bei großen vectoren furchtbar lange dauern. Bei Methode 2 ist gar kein Overhead da, bloß die gewünschte Änderung.

    Zweite Frage: Auf der rechten Seite erstellst du einen neuen, temporären vector mit dem Inhalt von ele.someOtherVector. Alles in ele.someOtherVector bleibt weiterhin dort, aber es werden Kopien davon gemacht. Sodann wird dieser temporäre vector dem this->someOtherVector zugewiesen. Dann wird der temporäre vector wieder zerstört. Sehr ineffizient. Typisches Beispiel für

    Bjarne Stroustrup schrieb:

    C makes it easy to shoot yourself in the foot; C++ makes it harder, but when you do it blows your whole leg off.

    Nimm assign:

    #include <iostream>
#include <vector>

using namespace std;

struct Foo
{
  int i;
  Foo(int i): i(i) { cout << "Neu erstellt mit i = " << i << '\n'; }
  Foo(const Foo &foo): i(foo.i) { cout << "Kopie erstellt mit i = " << i << '\n'; }
  const Foo& operator=(const Foo& foo) {i = foo.i; cout << "Zuweisung mit i = " << i << '\n'; return *this;}
  ~Foo() { cout << "Zerstört mit i = " << i << '\n'; }
};

int main()
{
  cout << "Erstelle drei leere vectoren a,b,c.\n";
  vector<Foo> a,b,c;
  for (int i = 0 ;i < 5; ++i)
    {
      cout << "Erstelle ein Foo("<<i<<") und kopiere es in a.\n";
      a.push_back(Foo(i));
    }
  cout << "Erstelle temporären vector und kopiere ihn nach b\n";
  b = vector<Foo>(a.begin(), a.end());
  cout << "Weise c direkt den Inhalt von a zu\n";
  c.assign(a.begin(), a.end());
  cout << "Zerstöre alles.\n";
}
    0
  • Mod

    Noch ein wichtiger Nachtrag: Falls du den Beispielcode mit einem C++11-Compiler übersetzt, wirst du feststellen, dass die Methode mit dem temporären vector genau das gleiche tut wie das assign. Das liegt da dran, dass in C++11 das temporäre Objekt gemoved werden kann (einfach gesagt: b übernimmt einfach die internen Datenstrukturen des temporären Objekts).

    Das soll aber kein Freibrief sein, hier nicht assign zu benutzen. Dies ist schließlich das, was du hier willst. Die Move-Variante macht es dir hier nur schwieriger, dir das Bein abzuschießen. Eigentlich ist das Moven eher für Fälle gedacht, wo es keine (oder nur umständliche) Alternativen zum temporären Objekt gibt.

    edit: Für Leute ohne C++11-Compiler:
    C++98:
    http://ideone.com/KHEJC
    C++11:
    http://ideone.com/Ytzav

    Man beachte auch die Wachstumsstrategie des vectors, der bei size ==1, 2 und 4 reallokiert.

    0
  • P

    Hi!

    SeppJ schrieb:

    Erste Frage: Nimm unbedingt die Methode 2! Wie kommst du auf die Idee, dass zu ändern eines Elementes eine andere Methode in Frage kommt als, nun ja, das Element zu ändern? Bei Methode 1 müssten alle nachfolgenden Elemente um 1 nach vorne verschoben werden und dann wieder um 1 nach hinten geschoben. Das würde bei großen vectoren furchtbar lange dauern. Bei Methode 2 ist gar kein Overhead da, bloß die gewünschte Änderung.

    Ich hatte schon vermutet, dass beim löschen+kopieren im std::vector Daten hin und hergeschoben werden, habs aber nicht auf anhieb in der Referenz gefunden. Danke für die Bestätigung!

    SeppJ schrieb:

    Zweite Frage: Auf der rechten Seite erstellst du einen neuen, temporären vector mit dem Inhalt von ele.someOtherVector. Alles in ele.someOtherVector bleibt weiterhin dort, aber es werden Kopien davon gemacht. Sodann wird dieser temporäre vector dem this->someOtherVector zugewiesen. Dann wird der temporäre vector wieder zerstört. Sehr ineffizient.

    Danke für die Erklärung, das macht es aufjedenfall deutlich was passiert. Ich hatte assign gesehen, aber nicht wirklich gecheckt, dass das hilfreich sein kann - danke für den Tipp. Werde ich heute abend mal ausprobieren 🙂

    Gruß

    Pille

    0
Anmelden zum Antworten