Liste von Objekten

drakon schrieb:

Grundsätzlich gilt aber, dass die std::list stark ist, wenn es darum geht Elemente einzufügen, und zu löschen (O(1)) (an beliebigen Stellen). std::vector ist vor allem gut, wenn es um Wahlfreien Zugriff (O(1)) (random access) geht und auch sortieren ist schnell machbar (O(logn)).

Wie schneller? Man kann Listen auch in O(n*log n) der Zeit sortieren. Habe neulich erst just for fun Merge-Sort auf einer einfach verketteten Liste implementiert. Der Merge-Sort wird auch garantiert on O(n*log n) der Zeit fertig (worst case). Ob's im kontreten Fall schneller oder langsamer ist, kann man nicht ohne weiteres sagen. Während beim Sortieren eines Vektors Elemente umkopiert bzw vertauscht werden, werden bei den Listen einfach nur ein paar Zeiger umgebogen. Auf der anderen Seite können natürlich die Knoten irgendwie "durcheinander" im Speicher liegen, was den Zugriff verlangsamen kann. ...

Leon222 schrieb:

Also ich kann mir das mit er Kopie grade irgendwie nicht richtig vorstellen. Und ja in der Uni haben wir vorerst nur Java ;-).

In C++ funktioniert das mit Klassentypen ähnlich wie bei int, double u.s.w. und der Objekt-Begriff wird anders gefasst:

int i = 23; // i bezeichnet direkt ein Objekt vom Typ int.
            // Es wird mit dem Wert 23 initialisiert.

int j = i;  // j bezeichnet direkt ein Objekt vom Typ int.
            // Es wird mit dem Wert von i initialisiert.

j++;        // Der Wert von j wurde um 1 erhöht.

cout << i;  // gibt immer noch 23 aus

Das gleiche kann man jetzt zB mit string machen:

string i = "dings";
string j = i;
j += "bums";
cout << i;  // gibt immer noch "dings" aus
cout << j;  // gibt "dingsbums" aus

string ist ein benutzerdefinierter Typ, nämlich eine Klasse. Das gleiche kann man mit anderen benutzerdefinierten Typen machen:

struct bdt {
  string foo;
  double bar;
};

int main() {
  bdt o;
  o.foo = "123";
  o.bar = 3.14;
  bdt q = o; // q ist ein zweites Objekt mit seinen eigenen Datenelementen.
  o.foo = "xxx";
  cout << q.foo; // gibt immer noch "123" aus
}

...eigentlich ganz einfach und schön regulär.

Bei Java spielen Klassentypen allerdings eine Sonderrolle. Wenn Du

MeineJavaKlasse x = null;

schreibst, dann ist x nur eine Java-Referenz. Man kann x jetzt noch auf ein Objekt zeigen lassen. Aber x ist -- nach Java-Terminologie -- kein Objekt, sondern eine Referenz. Java lässt Dich Objekte also nicht direkt "in Variablen halten", sondern zwingt Dich, sie per new zu erzeugen und über Java-Referenzen zu erreichen. Wenn Du in C++ Zeiger willst, musst Du das extra sagen. Dafür gibt es eine Syntax. Wenn Du in C++ allerdings per new Objekte im Freispeicher anlegst, dann bist erstmal Du dafür verantwortlich, das Ding wieder irgendwann zu löschen. Es gibt keine Gargage-Collection in C++ -- jedenfalls nicht von Haus aus. Man kommt aber oft um new/delete rum, wenn man die Verwaltung von Resourcen (wie Speicher eine ist) delegiert. Statt selbst new/delete zu benutzen, kann man zB ein Container-Objekt dazu beauftragen, Objekte zu verwalten. Man muss dabei aber ein bischen aufpassen. Wenn Du Dir zB Schüler-Objekte in einem Vektor merkst, Dir einen Zeiger auf ein Schüler-Objekt holst und ein neues Schülerobjekt zum Vektor hinzufügst, dann kann es sein, dass der Zeiger nicht mehr gültig ist, weil der Vektor die Objekte in einen größeren Puffer umkopieren musste. Bei einer std::list passiert das zB nicht so schnell.

Ja bei statischen Objekten ist mir das Kopieren klar. Aber ich meinte, wenn ich jetzt z.B. um bei dem Beispiel von Oben mit den Schülern bleibe. Wenn ich da ein neues Objekt erstelle, was dann in die Liste soll. Wie geht das als Kopie? Ich habe doch darauf nur einen Zeiger. Und mit der Liste/Vektor Diskussion, weiß ich jetzt gar nciht mehr, was ich am einfachsten für kleine Projekte nehme. Ich möchte wie gesagt einfach Objekte hinzufügen und löschen allerdings nciht nur das erste bzw. das letzte, sonder ein beliebiges. Und Operationen mit allen Objekten durchführen.

Ach ja ich würde jetzt in der Klasse Schule eine Methode machen, die einen neuen Schüler erstellen kann. Also So was in der Art, wie es von L33TF4N gepostet wurde. Ich weiß eben nur nicht, wie man das per Kopie machen will.

Leon222 schrieb:

Ja bei statischen Objekten ist mir das Kopieren klar.

In C++ gibt es drei Speicherklassen: statisch, automatisch und "dynamisch" (Freispeicher). Mit dem Kopieren hat das aber nichts zu tun.

Leon222 schrieb:

Aber ich meinte, wenn ich jetzt z.B. um bei dem Beispiel von Oben mit den Schülern bleibe. Wenn ich da ein neues Objekt erstelle, was dann in die Liste soll. Wie geht das als Kopie? Ich habe doch darauf nur einen Zeiger.

Dann hast Du schon etwas falsch gemacht, wenn Du "doch darauf nur einen Zeiger" hast.

#include <string>
#include <list>
#include <iostream>

struct dings
{
  string bums;

  dings() {} // default constructor

  explicit dings(string b) : bums(b) {}
};

template<class Iter>
void dings_sequenz_anzeigen(Iter beg, Iter end)
{
  while (beg!=end) {
    std::cout << ' ' << beg->bums;
    ++beg;
  }
  std::cout << '\n';
}

int main()
{
  list<dings> l;

  l.push_back( dings("123") );

  l.push_back( dings() );
  l.back().bums = "234";

  dings d ("999");
  l.push_back(d);

  d.bums = "9191";
  l.push_back(d);

  dings_sequenz_anzeigen(l.begin(),l.end());
}

Naja ich meinte dynamisch mit new erzeugt Objekte.

void addSchueler(int id)
    {
        m_schueler.push_back(new Schueler(id));
    }

Wie sollte man das mit einer Kopie realisieren?

Leon222 schrieb:

Naja ich meinte dynamisch mit new erzeugt Objekte.
void addSchueler(int id)
 {
     m_schueler.push_back(new Schueler(id)); 
 }
Wie sollte man das mit einer Kopie realisieren?

Ich verstehe nicht, was Du meinst, verstehe Dein Problem nicht. Ich weiß nicht, was Du wissen willst.

SeppJ schrieb:

Im übrigen: Du brauchst keine Zeiger. Hast du früher zufällig mal Java programmiert? In C++ macht man das was du da zeigst eigentlich mit Kopien. Die dynamische Verwaltung ist genau das, wozu die Container gut sind. Du musst gar nicht mehr selbst mit new/delete arbeiten.

Das meinte ich. Ich will eben zur Laufzeit Objekte anlegen. Eben z.B. mit einer methode neuerSchueler. Aber wie bitte soll das ohne new mit Kopien gehen?

Leon222 schrieb:

Ich will eben zur Laufzeit Objekte anlegen. Eben z.B. mit einer methode neuerSchueler. Aber wie bitte soll das ohne new mit Kopien gehen?

Du siehst wohl den Wald vor lauter Bäumen nicht. Guck Dir nochmal ganz genau mein letztes Codebeispiel an.

Leon222 schrieb:

Ich will eben zur Laufzeit Objekte anlegen. Eben z.B. mit einer methode neuerSchueler. Aber wie bitte soll das ohne new mit Kopien gehen?

Du siehst wohl den Wald vor lauter Bäumen nicht. Guck Dir nochmal ganz genau mein letztes Codebeispiel an.

Nein so richtig sehe ich das noch nciht. heißt das ich kann einfach schreiben:

void addSchueler(int id)
    {
        m_schueler.push_back(Schueler(id));
    }

l'abra d'or

Leon222 schrieb:

Nein so richtig sehe ich das noch nciht. heißt das ich kann einfach schreiben:
void addSchueler(int id)
    {
        m_schueler.push_back(Schueler(id));
    }

Genau! Dann muss m_schueler aber als std::list<Schueler> deklariert sein, bei der Zeigervariante mit new wäre es ja std::list<Schueler*> .

Gut das war mir bisher nciht bekannt, dass das ohne new geht. Hat es denn einen Vorteil, dass ganze ohne Zeiger zu realisieren? Und ist nun List oder Vektor besser für mein Vorhaben. Was ich jetzt so gelesen habe würde ich List den Vorzug geben.

Nexus

Leon222 schrieb:

Gut das war mir bisher nciht bekannt, dass das ohne new geht. Hat es denn einen Vorteil, dass ganze ohne Zeiger zu realisieren?

Der Vorteil besteht darin, dass du keine manuelle Speicherverwaltung mehr hast.

Leon222 schrieb:

Und ist nun List oder Vektor besser für mein Vorhaben. Was ich jetzt so gelesen habe würde ich List den Vorzug geben.

Dazu wurde dir schon zwei Mal eine Antwort gegeben (SeppJ und drakon).

Naja mir wurden halt mehrmals die Vor und Nachteile der beiden Klassen genannt. Ich wollte nur nochmal wissen, ob ich das jetzt richtig interpretiert habe, und List für mich das beste ist.

Nexus

Wie erwähnt ist das schwer zu sagen, ohne genau zu wissen, welche Operationen wie häufig vorkommen und ob besondere Anforderungen (z.B. Gültigkeit der Iteratoren) gestellt werden. Nimm fürs Erste einmal std::vector , für die meisten Fälle ist er am geeignetsten.

Also ich wollte erst einmal ein kleines Testprojekt machen wo ich wie schon geschrieben Objekte in die Liste einfüge, und anhand der id wieder lösche. Ansonsten werden die Objekte nur für eine Methode gebraucht und dort soll eine Variable aller Objekte aufsummiert werden. Also z.B. den Durchschnitt aller Gesamtnoten der Schüler berechnen. Da sollte bald die Liste besser sein.

Worüber ich mir jetzt noch Gedanken mache ist die Nummerierung der Objekte. Ich wollte das ja erst mit new machen. Da hätte ich die Nummerierung der Klasse Schüler überlassen. Dort 2 static Variablen letzte id und anzahl. und eine normale Variable id. Beim Erzeugen eines neuen Objektes wird id der wert ++letzteid zugewiesen. Aber das klappt ja jetzt durch das kopieren nicht mehr, oder?

Nexus

Kannst du als Nummer nicht den Index des Containers (in dem Fall std::vector ) verwenden? Oder wofür brauchst du die Nummerierung genau?

Also die Nummerierung des Vektor ist vlt zwecks löschen nciht so gut, oder? Also die Nummerierung benötige ich um das Objekt zu löschen. Also z.B. Schüler mit Nummer 14546 löschen.

Nexus

Entweder du gibst der Schüler-Klasse diese Eigenschaft und führst im Container eine lineare Suche durch, oder du bildest Schlüssel-Wert-Paare mit Nummern als Schlüsseln und Schülern als Werten. Dazu kannst du std::map verwenden.

Dravere

Klingt mir danach, dass du eine std::map benötigst.

Oder falls du Boost bereits verwendest und die ID nicht doppelt speichern willst (also als Key und im Objekt selber), dann gäbe es Boost.MultiIndex:

class pupil
{
private:
  int id_;
  // usw.

public:
  int get_id() const { return id_; }
  // usw.
};

// ...

typedef boost::multi_index::multi_index_container
<
  pupil,
  boost::multi_index::indexed_by
  <
    boost::multi_index::const_mem_fun<pupil, int, &pupil::get_id>
  >
> pupil_set;

// ...

multi_index_container braucht aber etwas Zeit, bis man das Ding schlucken kann

Grüssli