Werte unbekannter Anzahl speichern

[lyrichter]

Hallo liebe C++-Community!

Ich möchte mir gerade Kenntnisse in C++ aneignen und bin dabei auf ein Problem gestoßen, das ich mit meinen Quellen bisher nicht selbst lösen konnte.

Und zwar sollen in einem Programm mehrere Werte auf irgendeine Weise gespeichert und am Ende alle ausgegeben werden. Allerdings ist vorher nicht bekannt, wie viele Werte gespeichert werden sollen.

Das konkrete Beispiel, welches mich auf das Problem aufmerksam gemacht hat, war die Aufgabe, alle Primzahlen in einem bestimmten Bereich auszugeben. Ich kann den Bereich durchlaufen, jede Zahl testen, mir auch die Anzahl an Primzahlen ausgeben lassen - aber wie kann ich die Zahlen speichern, die als Primzahl identifiziert werden?

In Python hätte ich das Problem mit einer Liste gelöst, in C++ dachte ich deshalb zuerst an ein Array, doch die Größe des Arrays muss ja schon bei der Erzeugung festgelegt werden. Da ich diese zu diesem Zeitpunkt noch nicht kenne, erscheint mir das ungünstig. Ich könnte ein sehr großes Array erzeugen, das ich dann nicht ganz ausnutze, aber das kommt mir weder sehr elegant noch effizient vor. Dynamische Speicher und Pointer klangen für mich zuerst nach einer Lösung, aber wenn ich mich nicht täusche, kann man auch mit dieser Methode kein Array mit einer variablen Größe festlegen, oder?
Und was mich endgültig verwirrt hat, war die Tatsache, dass zu große Indizes bei Arrays nicht zu Fehlermeldungen führen und auf den ersten Blick völlig problemlos funktionieren. Das muss doch aber einen Haken haben, oder?

Viele Grüße und schon einmal vielen Dank für das Lesen meiner Frage!

[Ein ehemaliger Benutzer]

Doch kann man. Entweder man nimmt std::vector oder boost::array oder alternativ und falls vorhanden std::tr1::array. DAmit umgeht man auch sämtliche Pointer-Probleme, da sich diese Container selber um ihren Speicher kümmern. Es gibt viele versch. Container und jeder is auf eine andere Art von Speicherung spezialisiert.

Beispiele:
std::vector, std::list, std::deque, std::map

edit:
Beispiel zum testen und selberkompilieren

#include <vector>
#include <iostream>
#include <string>
#include <sstream>

int main()
{
    std::vector<std::string> vec;

    for ( int i = 0; i <= 10; i++ )
    {
        std::stringstream ss;
        ss << "Item Nr. " << i;
        vec.push_back(ss.str());        
    }

    for ( int i = 0; i <= 10; i++ )
    {
       std::cout << vec[i] << std::endl;
    }
}

rya.

[player424]

Das was du suchst ist dynamische Speicherverwaltung. In C++ stehen dafür die oben genannten Container zur Verfügung.

std::vector = Dynamisches Array, welches bei einer Speicheranforderung einen größeren Speicherblock anfordert, alle Werte aus dem alten Speicher umkopiert und diesen freigibt.

std::list = Verkettete Liste

[krümelkacker]

lyrichter schrieb:

Hallo liebe C++-Community!

Hallo, lyrichter! Ein für die toll formulierte Frage!

lyrichter schrieb:

Und zwar sollen in einem Programm mehrere Werte auf irgendeine Weise gespeichert und am Ende alle ausgegeben werden. Allerdings ist vorher nicht bekannt, wie viele Werte gespeichert werden sollen.
[...]
In Python hätte ich das Problem mit einer Liste gelöst,...

Wie Du richtig festgestellt hast, bietet C++ solche Datenstrukturen nicht als eingebaute Typen an. Aber C++ ist mächtig und flexibel genug, dass solche Datenstrukturen sehr effizient selbst in C++ implementiert werden können. Die Standardbibliothek bietet beispielsweise std::vector, std::deque und std::list zum Speichern von Sequenzen mit unterschiedlichen Vor- und Nachteilen. In Deinem Fall würde ich wahrscheinlich std::vector nehmen.

lyrichter schrieb:

Und was mich endgültig verwirrt hat, war die Tatsache, dass zu große Indizes bei Arrays nicht zu Fehlermeldungen führen und auf den ersten Blick völlig problemlos funktionieren. Das muss doch aber einen Haken haben, oder?

Der "Haken" ist, dass das nicht erlaubt ist. Das Motto der Sprachen C und C++ heißt: "Trust the programmer", was soviel heißt wie "Der Programmierer weiß schon, was er tut". Das hat natürlich positive (Performanz) als auch negative Implikationen (Unerlaubte Vorgänge führen entweder zu Abstürzen oder zu anderen "komischen Effekten" im späteren Programmverlauf). Zumindest ist das der Fall bei den low-level Sprachmerkmalen, wie Arrays. Wenn Du Dir eine eigene Datenstruktur programmierst, kannst Du natürlich zusätzliche Überprüfungen einbauen, damit Du Benutzungsfehler früh erkennen kannst. Einige Compiler-Hersteller bieten sogar einen Debug-Modus für die Standardbibliothek an, der solche Überprüfungen bei std::vector, std::list, etc macht. Ich würde Dir empfehlen, Dich mit der Standardbibliothek und der Dokumentation Deines Compilers intensiver auseinander zu setzen. Falls Du G++ verwendest, ist das hier der richtige Link dazu.

Gruß,
kk

[seldon]

krümelkacker schrieb:

In Deinem Fall würde ich wahrscheinlich std::vector nehmen.

Für mich klingt das eigentlich eher nach einem Fall für std::deque. Wenn vorher nicht bekannt ist, wie groß die Liste wird, müsste std::vector seinen Inhalt alle Nase lang verlegen.

Funktionsweisen der üblichsten Sequenzen kurz erläutert:

1. std::vector

| 2 | 3 | 5 | 7 | 11 |   |   |
+---+---+---+---+----+---+---+

std::vector ist ein ziemlich einfaches, dynamisches Array. Er fordert eine gewisse Menge Speicher an, legt die Daten flach hintereinander da hinein, und wenn der Platz aufgebraucht ist, fordert er einen größeren Speicherblock an anderer Stelle an, kopiert seine Daten da hinein und benutzt fortan den. Solange Speicher vorhanden ist, ist das Anhängen an einen Vektor trivial (halt in den nächsten freien Speicherplatz reinschreiben); ist das nicht der Fall, kann es recht teuer werden (und unangenehme Auswirkungen auf die Fragmentation des Heaps haben). Dementsprechend ist ein Vektor vor allem dann ideal, wenn du vorher abschätzen kannst, wie viele Elemente du brauchen wirst. Diese Abschätzung muss nicht zur Compilezeit geschehen - man kann zur Laufzeit dynamisch Speicher reservieren - aber performancetechnisch ist es ideal, wenn man vor Benutzung des Vektors weiß, wie groß er einmal werden wird.

2. std::deque

+---+   +---+   +----+
                  |   |   | 3 |   | 11 |
                  +---+   +---+   +----+
                  |   |   | 5 |   |    |
                  +---+   +---+   +----+
                  | 2 |   | 7 |   |    |
                  +---+   +---+   +----+
                    ^       ^       ^
                    |       |       |
+-------+-------+-------+-------+-------+-------+-------+

std::deque (double-ended queue) verlangt, dass Operationen an beiden Enden des Containers konstante Laufzeitkomplexität haben. Häufig wird das wie im obrigen Diagramm implementiert, in gewisser Weise wie ein Vektor von Vektoren, der seine Daten in der Mitte speichert. Der Vorteil dieses Layouts ist, dass die eigentlichen Daten nie verlegt werden müssen; ist einer der Endbuffer voll, wird einfach ein weiterer davor bzw. dahinter gehängt. Relokation ist nur dann notwendig, wenn der Zeigerbuffer auf einer Seite überläuft, und dann muss nur das Zeigerarray verschoben werden - die eigentlichen Daten bleiben, wo sie sind (gerade bei komplexen Datentypen ein Vorteil). std::deque reagiert sehr viel gutmütiger als std::vector auf unbekannte Längen, allerdings ist die Dereferenzierung etwas weniger performant.

3. std::list

+---+   +---+   +---+   +---+   +----+
N -->|   |-->|   |-->|   |-->|   |-->|    |--> N
I    | 2 |   | 3 |   | 5 |   | 7 |   | 11 |    I
L <--|   |<--|   |<--|   |<--|   |<--|    |<-- L
     +---+   +---+   +---+   +---+   +----+

std::list implementiert eine doppelt verkettete Liste. Wenn man die Stelle einmal hat, an der man etwas machen will, sind so ziemlich alle Operationen in konstanter Zeit möglich (Splicing mal außen vorgelassen, und auch da kann es sein), aber Elemente in der Mitte muss man ggf. halt in linearer Zeit suchen. Auch ist ein gewisser Speicher- und Laufzeitoverhead dadurch vorhanden, dass jedes Element seine eigene Buchführung mitschleppt und für jedes Element wieder an den Heap gegangen werden muss.

Wenn du vorher weißt, wie viele Primzahlen du speichern willst, nimm std::vector, ansonsten rate ich zu std::deque. Das ist aber natürlich nur meine Meinung.

[krümelkacker]

std::vector<>::push_back hat immerhin amortisiert konstante Laufzeit.

[lyrichter]

krümelkacker schrieb:

Ein für die toll formulierte Frage!

Und ein (etwas versprätetes) für alle tollen Antworten, nicht nur von krümelkacker! Mein Problem ist damit gelöst