Maximale Größe von std::vector

[mowo*fs*]

Hallo,

ich hab ein Programm geschrieben, das Meßdaten aus einer Datei einließt
und dann verarbeitet. Es funktioniert wunderbar, wenn die Dateien klein genug sind. Hatte bis jetzt immer so 200-300 Mb.
Jetzt hab ich aber mit Dateien um 1 GB zu tun und das Programm bricht nach einiger
Zeit mit:

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
Aborted

ab. (Nach dem es 38805510 Zeilen eingelesen hat.)
Die Datei einthält zwei Spalten. Der Wert jeder Spalte wird jeweils in einen
std::vector eingelesen. Kann es sein, dass man irgendwann an eine Grenze der
Vectorgröße stößt? Oder was könnte das problem sein?

Danke,
Moritz

[pumuckl]

Jein. Es ist nicht die Größe des Vector an sich, sondern das Problem ist, dass im vector alle Daten an einem Stück in den Speicher geschrieben werden müssen. Und so große Specherbrocken scheint dein Betriebssystem dem Programm nicht zu gönnen.
Du könntest es mit anderen Containern versuchen (z.B. deque) oder dir Gedanken darüber machen ob du wirklich ALLE Daten auf einmal im Speicher halten musst.

[Bulli]

Der Vector kann soviel Elemente verwalten, wie size_t auf deinem Compiler groß ist. Unter einem 32-Bit System für gewöhnlich 4 Mrd. Elemente.

bad_alloc ist eine Standard-Exception von C++, und sagt, dass das anfordern von Speicher mittels new fehlgeschlagen ist (der Vector macht ja intern bei Bedarf new). Das kann z.B. sein, das einfach nicht genug Speicher mehr frei ist.

Du kannst das bad_alloc natürlich mit einem try-catch abfangen! Dann muß dein Programm nicht hart terminiert werden.

Jetzt hab ich aber mit Dateien um 1 GB zu tun... Nach dem es 38805510 Zeilen eingelesen hat.

Ehm, also 1 GB ist schon ordentlich! 38805510 Zeilen ist aber keine Größenangabe! Eine Zeile könnte auch 100 MByte groß sein.
Du mußt bedenken, wieviel Bytes eine Zeile groß ist. Oder anders gefragt: wie ist vector definiert? Ein vector<int> würde bei 38805510 alleine schon 38805510*8*4 Bytes Hauptspeicher fressen: 1.241.776.320 Bytes. Wenn du vector<string> hast, und jeder String unterschiedlich groß ist...

Vector ist bestimmt am wenigsten schuld!

[asc]

Bulli schrieb:

Der Vector kann soviel Elemente verwalten, wie size_t auf deinem Compiler groß ist. Unter einem 32-Bit System für gewöhnlich 4 Mrd. Elemente.

Nein. Zu der reinen Größe von size_t muss man immer auch immer berücksichtigen welche Voraussetzungen unter dem Betriebssystem gelten. z.B. ist unter Windows 32 Bit zwar 4 GB die Theoretische Obergrenze, aber gleichzeitig darf ein Prozess soviel ich weiß auch nur 2 GB verwenden. Und wenn der Vector kopiert wird, ist das Bereits mit 1 GB recht schnell erreicht

mowo(fs) schrieb:

ich hab ein Programm geschrieben, das Meßdaten aus einer Datei einließt und dann verarbeitet.

Ich kenne keinen einzigen Fall wo man tatsächlich eine Liste von dieser Größe im Speicher halten muss. Häufig betrachtet man in solchen Fällen eher ein Teil der Daten, und niemals das Gesamte (File Mapping etc.). Sehr häufig reichen dabei sogar deutlich kleinere Häppchen als 100+ MB (eher im einstelligen Bereich).

cu André

[Dravere]

@Bulli, asc,
Darf ich euch da beide ein wenig korrigieren? std::size_t sagt überhaupt nichts über die maximale Anzahl Elemente aus. Es ist nicht mal garantiert, dass std::vector<T>::size_type ein typedef auf std::size_t ist. Es ist zwar oft so, aber im Standard steht nichts dazu, bzw. es steht nur, dass std::vector<T>::size_type ein unsigned integral sein muss.
Und std::vector<T>::size_type sagt per Standard nichts über die maximale Anzahl erlaubter Elemente aus. Dazu ist std::vector<T>::max_size() da.
http://www.cplusplus.com/reference/stl/vector/max_size.html

Grüssli

[mowo*fs*]

Ok, danke schonmal.
Ich verwende Kubuntu 8.10 32 Bit auf nem Core2Duo mit 2,66 GHz und 4 Gb Arbeitsspeicher.
Die Vectoren sind vom Typ vector<double>.
Und ich brauche alle Daten im Arbeitsspeicher, da sie die Grundlage für eine Monte Carlo Simulation bilden.
Ich brauche immer alle Elemente von a bis b, wobei a,b Zufallszahlen zwischen 0 und der Anzahl der Elemente sind.
Irgendjemand ne Idee, wie ich das jetzt umsetzen kann?

[Dravere]

mowo(fs) schrieb:

Irgendjemand ne Idee, wie ich das jetzt umsetzen kann?

Wie es schonmal gesagt wurde, probier es einmal mit einer std::deque :
http://www.cplusplus.com/reference/stl/deque/

Hat die gleiche Schnittstelle wie ein std::vector , allerdings ein wenig langsamere Zugriffzeiten, weil es den Speicher nicht in einem Block hält sondern in mehreren. Vielleicht ist es so deinem System möglich, genügend Speicher anzubieten.

Grüssli

[The-Kenny]

Speicher die Dateien in mehreren Vektoren, dann sind sie nicht mehr an einem Stück im Speicher. So umgehst du die genannte Größenbegrenzung für Chunks.

Oder nimm nen anderen Container, der die Daten nicht in einem Stück speichert.

Oder lese die Daten On-The-Fly, also immer nur den Teil den du brauchst.

[Nexus]

@ Dravere
Soviel ich weiss, ist size_type bei Containern ein Typedef auf size_type des benutzten Allokators (hab ich zumindest hier gehört). Beim Standardallocator sollte es mit std::size_t übereinstimmen.

@ The Kenny
Schön, dass du die Erkenntnisse dieses Threads nochmals zusammenfasst. :p

[Dravere]

Nexus schrieb:

@ Dravere
Soviel ich weiss, ist size_type bei Containern ein Typedef auf size_type des benutzten Allokators (hab ich zumindest hier gehört). Beim Standardallocator sollte es mit std::size_t übereinstimmen.

So leid es mir tut, aber da irrt sich Shade of Mine einmal. Es stimmt zwar, dass beim default allocator size_type ein typedef auf size_t ist, aber es ist nicht im Standard definiert, dass der size_type eines vector s auch ein typedef auf den size_type des allocator s ist.

In "23.2.4 Template class vector" Abschnitt 2 steht das folgende:

// ...
typedef /*implementation defined*/ size_type; // See 23.1
typedef /*implementation defined*/ difference_type; // See 23.1
// ...

Und in "23.1 Table 65 - Container Requirements" steht, dass size_type ein unsigned integral type sein soll, welcher jegliche positive Darstellung von difference_type aufnehmen kann.
Und difference_type ist ein signed integral type , welcher die Differenz von zwei Iteratoren aufnehmen können muss.

Mehr gibt es dazu nicht im C++ Standard 98.

Aber nebst diesem Körnerpicken, muss man natürlich schon sagen, dass die meisten Implementation es so handhaben, wie Shade Of Mine es sagt. Es steht halt einfach nicht im Standard, dass es so sein muss.

Grüssli

[Nexus]

Okay, danke. Aber welchen Sinn hat dann das size_type des Allokators, wenn der Container nicht darauf abgestimmt sein muss? Damit geht ja jede Aussagekraft verloren...

[Dravere]

Nexus schrieb:

Okay, danke. Aber welchen Sinn hat dann das size_type des Allokators, wenn der Container nicht darauf abgestimmt sein muss? Damit geht ja jede Aussagekraft verloren...

Das stimmt nicht ganz. size_type ist indirekt an den Allokator gebunden über difference_type , bzw. der Abstand von den Iteratoren. Wieso man die Bindung nicht stärker gemacht hat, weiss ich auch nicht. Mir leuchten sowieso einige Dinge im Standard nicht ganz ein (wie zum Beispiel signed -> unsigned standardisiert, unsigned -> signed nicht ganz standardisiert ).

Vielleicht weiss jemand anderes mehr dazu...

Grüssli

[holy shit!]

Bulli schrieb:

Der Vector kann soviel Elemente verwalten, wie size_t auf deinem Compiler groß ist.

std::cout << sizeof(std::size_t);

4

[prochecker]

hm... ich kann bei dem Problem leider nicht helfen, aber ich habe noch eine andere Frage dazu:
Ist es nicht unüblich "std::cout" schreiben? Ist es nicht üblicher, wenn man am Anfang vor "int main()" schreibt "using namespace std;" Dann muss man nicht mehr "std::cout" schreiben, sondern einfach nur "cout"? Liege ich da richtig? Ich bin erst seit ca. 1 Monat in der C++ Welt und kenne mich daher noch relativ wenig aus...

mfg

[holy shit!]

prochecker schrieb:

Ist es nicht unüblich "std::cout" schreiben?

nein.

Ist es nicht üblicher, wenn man am Anfang vor "int main()" schreibt "using namespace std;" Dann muss man nicht mehr "std::cout" schreiben, sondern einfach nur "cout"? Liege ich da richtig?

genauer: man muss es in alle übersetzungseinheiten schreiben, in denen man auf std::verzichten will. ein nichttriviales programm besteht üblicherweise aus mehr als nur main().

ist letzlich eine geschmacksfrage. ich verzichte in der regel auf using namespace, weil das mehrtippen nicht ins gewicht fällt, bzw. der gewinn an klarheit imho wesentlich mehr wiegt.

[prochecker]

ein nichttriviales programm besteht üblicherweise aus mehr als nur main().

Bei meinen kleinen Taschenrechnerprogrammen schon

Also ich verwende lieber using namespace std; weiß auch nicht warum Viel mehr Tipparbeit finde ich es nicht, aber es ist übersichtlicher für mich,...

mfg

[Bulli]

prochecker schrieb:

hm... ich kann bei dem Problem leider nicht helfen, aber ich habe noch eine andere Frage dazu:
Ist es nicht unüblich "std::cout" schreiben? Ist es nicht üblicher, wenn man am Anfang vor "int main()" schreibt "using namespace std;" Dann muss man nicht mehr "std::cout" schreiben, sondern einfach nur "cout"? Liege ich da richtig? Ich bin erst seit ca. 1 Monat in der C++ Welt und kenne mich daher noch relativ wenig aus...

Man benutzt das eine dann wenn es sinnvoll ist. Genauso bei dem anderen.
std::XYZ schreibe ich z.B. immer, wenn ich es selten brauche. Wenn ich aber sehr viel Sachen aus dem std-Namespace benutze, schreibe ich using namespace. Mna muß halt abwegen.

Manchmal muß man aber std::XYZ explizit benutzen, weil XYZ schon woanders existiert. Und genau dafür sind Namespaces da: um Namenskonflickte zu vermeiden!

[Dravere]

prochecker schrieb:

Also ich verwende lieber using namespace std; weiß auch nicht warum Viel mehr Tipparbeit finde ich es nicht, aber es ist übersichtlicher für mich,...

Bis du dann sowas hast:

#include <algorithm>

using namespace std;

int max(int lhs, int rhs)
{
  return lhs > rhs ? lhs : rhs;
}

int main()
{
  cout << max(4, 223) << endl;
  return 0;
}

Ups, der Kompiler weiss nicht welches max .
using namespace hebelt den Sinn von Namensräumen aus. Man sollte es meiner Meinung nach nur mit Bedacht einsetzen, möglichst in Scopes und auf GAR KEINEN FALL in Headern. Für lange Namen, bzw. stark verschachtelte Namensräume, gibt es ja noch die Zuweisung:

namespace ba = boost::asio;

// Verwende ba, als würdest du boost::asio schreiben.

Allerdings auch hier würde ich die gleichen Regeln wie bei using namespace hinsetzen.

In Scope bedeutet übrigens sowas:

void foo()
{
  using namespace std;
  // ...
} // using namespace std, gilt nur bis hier.

Edit: Das nächste Mal bitte einen eigenen Thread eröffnen

Grüssli

[drakon]

Also ich setze unsing nur da ein, wo es für die Lesbarkeite des Programmes wirkklich nötig ist. Da kann es enorm viel helfen,wen man nicht dauernd so etwas hat:

myEngine::myMathLib::myVector v;
v += myEngine::myMathLib::myVector (4,1,3) - myEngine::myMathLib::myVector(myEngine::myMathLib::myInteger(3),2,1);

Da hat man die ganze Zeile voll Zeugs, die nicht von Interesse sind und den eigentlichen Code kann man kaum sehen. Hier kann man gut using einsetzen, da es sehr unwahrscheinlich ist, dass man am genau gleichen Ort unterschiedliche Typen braucht, die gleich heissen.

[holy shit!]

ist es denn nun tatsächlich so, dass ein std::vector auf meinen compiler nur 4 elemente speichern kann, wenn size_t eine größe von 4 hat?