Hält bool[100] das, was es verspricht?

[volkard]

es ist so, daß &pointer[1] und &pointer[2] zwei verschiedene adressen sein müssen. und weil der rechner nur ganze bytes adressieren kann, geht ein ganzes byte drauf.

lustigerweise ist vector<bool> aber so gestrickt, wie du es anscheinend suchst. der benutzt nur ein bit pro bool. http://www.oop-mit-cpp.de/stdbib_html/p18.html

[BOOLy]

sizeof(bool) ergibt bei mir 1 (also 4 Bit).
Allerdings ermöglicht ein vector<bool> ja Zugriff auf einzelne bits. Wird ein vector<bool> anders behandelt als ein bool array? Und ist die größe von bool nun Compielrabhängig oder vom Standard vorgeschrieben (bzw. wo kann man sowas nachgucken?)

[BOOLy]

*edit: Hab meinen Post geschrieben während Volkard geantwortet hat. Damit ist meine Frage geklärt, danke!

[SideWinder]

Nachtrag:

sizeof(bool) ergibt bei mir 1 (also 4 Bit).

=> 8 Bit!

Grüße

[BOOLy]

mein ich doch!!!!!!

[volkard]

nachgucken kann man das im c++-standard. ich hab die datei auf der platte. anscheinend gibts aber entwürfe im netz, die auch was taugen, wie http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1905.pdf

fußnote 74 auf seite 89:
sizeof(bool) is not required to be 1.

wobei die 1 ja gemessen ist in char. ein char wiederum muß nicht ein byte sein. und ein byte muß nicht 8 bit haben, aber das weißt du ja selber mit deinem 4-bit-prozessor. siehe 5.3.3

du kannst doch da also nicht drauf verlassen. aber du kannst es feststellen und reagieren. natürlich mit sizeof. und zum beispiel guck dir mal numeric_limits in der gegend von kapitel 18.2 an.

ja, der vector<bool> hat innen nicht einfach nur ein bool-array, sondern vermutlich ein unsigned-int-array und kitzelt die bits mit & und | und >> und << und ~ und so raus. aber wie immer gibt der standard kein versprechen, wie der vector<bool> innendrin aussieht, sondern nur, was die funktionen machen müssen.

[BOOLy]

Der Grund meiner Frage war eigentlich, wie man große Zahlen im Arbeitsspeicher anlegen kann, um effizient (sowohl von der Zeit als auch vom benötigten Speicherplatz) damit zu rechnen.
Vector weist ja im Vergleich zu arrays relativ starke Performanceschwächen auf.
Theoretisch könnte man ja einfach ein char array erstellen, wobei der reservierte Bereich genug Bits für die Zahl enthält. Allerdings kann man ja zB. die Shiftoperatoren (Multiplikation und Division mit 2^n) nur auf die Integrierten Zahlentypen anwenden.
Kurz gesagt habe ich also keine Ahnung, wie man große Zahlen effizient binär anlegen und damit rechnen kann.
Kennt sich jemand mit dem Thema aus und hat Tipps? Mir geht es in erster Line wirklich erstmal um die Grundlagen der internen Darstellung solcher Zahlen. Ich habe schon Klassen zum Rechnen großer Zahlen mit short arrays geschrieben, wobei die Zahlen dann dezimal gespeichert wurden, zB short arr[3] = {1,2,3};
Aber das ist weder besonders effizient noch platzsparend...

[NimmDenReleaseMode]

BOOLy schrieb:

Der Grund meiner Frage war eigentlich, wie man große Zahlen im Arbeitsspeicher anlegen kann, um effizient (sowohl von der Zeit als auch vom benötigten Speicherplatz) damit zu rechnen.
Vector weist ja im Vergleich zu arrays relativ starke Performanceschwächen auf.

Du auch.

[hustbaer]

volkard schrieb:

ein char wiederum muß nicht ein byte sein.

char und byte sind nicht gleichbedeutend, aber gleich gross (wenn es um Standard C++ geht).

Das byte ist einfach die Representation eines char im C++ Speichermodell.

Es gilt immer sizeof(char) == 1 (und sizeof zählt bytes !)

1.7 - 1
3.9 - 4
3.9.1 - 1
5.3.3 - 1
...

Leider muss man ziemlich viele Paragraphen "verketten", um zu dem Schluss zu kommen. Die Jungs hätten das wohl besser explizit reinschreiben sollen.

p.S.: es sei denn, natürlich, ich hätte die Stelle einfach übersehen wo's klar und deutlich geschrieben steht.

[tntnet]

BOOLy schrieb:

Vector weist ja im Vergleich zu arrays relativ starke Performanceschwächen auf.

Wo kommen nur immer diese Gerüchte auf? Ein std::vector ist einfach ein Template, welches ein Array verwaltet. Und die Methoden sind in der Regel inline. Ein vector ist genau so schnell wie ein Array. Nur sicherer in der Benutzung.

Wobei das natürlich implementierungsabhängig ist. Es gibt Implementierungen, die im Debug-Build alles mögliche prüfen. Dann ist ein Vector bei vielen Operationen langsamer. Ausser man programmiert diese Prüfungen genau so in sein Array.

[volkard]

BOOLy schrieb:

Theoretisch könnte man ja einfach ein char array erstellen, wobei der reservierte Bereich genug Bits für die Zahl enthält. Allerdings kann man ja zB. die Shiftoperatoren (Multiplikation und Division mit 2^n) nur auf die Integrierten Zahlentypen anwenden.

aber ein char IST ein integraler typ!
klar kannst du char nehmen.
und es wäre keine schlechte idee, auf tntnet zu hören und vector<unsigned char> zu nehmen.
aber unsigned short ist noch toller, dann kannst du noch zweo shorts multiplizieren und das ergebnis paßt in einen unsigned int.

[Mitleid]

tntnet schrieb:

Ein vector ist genau so schnell wie ein Array. Nur sicherer in der Benutzung.

Weil die Algorithmen und die Logik, welche das vector-Objekt sicherer machen alle keine Resourcen verbrauchen, oder?

[rüdiger]

Du willst also Bignums implementieren. Dann wäre es recht ungünstig vector<bool> zu nehmen. Volkard hat schon recht, dass short den Vorteil hat, das du die Multiplikation in ein int packen kannst. Aber short Multiplikation ist halt verschwenderisch. Wenn du es wirklich effizient machen willst, dann solltest du einen Datentyp nehmen, der so groß ist, wie die Register auf deiner Plattform (typischerweise trifft das auf std::size_t zu). Nur hier hast du ein Problem, dass du einen Datentyp brauchst, der das Produkt/Summe aufnehmen kann. Wenn dein Compiler den TR1 kann, dann kannst du auf 32 Bit Systemen _ULonglong (oder unsigned long long) nehmen, aber bei 64 Bit Systemen ist _ULonglong leider oft auch nur 64Bit breit. Beim GCC hast du zwar __int128_t, aber das ist leider eine GCC eigene Erweiterung.

Wenn du Boost benutzt, kannst du hier mit Boost.Integer prima benutzen.

zB short arr[3] = {1,2,3};

und du solltest keine 10er sondern eine 2er Basis nehmen!

Vector weist ja im Vergleich zu arrays relativ starke Performanceschwächen auf.

Wurde zwar schon ein paar mal gesagt. Aber noch mal: Nö, das kann man so allgemein nicht sagen!

[volkard]

Mitleid schrieb:

tntnet schrieb:

Ein vector ist genau so schnell wie ein Array. Nur sicherer in der Benutzung.

Weil die Algorithmen und die Logik, welche das vector-Objekt sicherer machen alle keine Resourcen verbrauchen, oder?

so ist es.
es gibt nicht viele sprachen, die das versprechen können, aber c++ gehört dazu.

[BOOLy]

Hm, ich hätte nicht gedacht das ein kleiner Satz so ein Flamewar startet. Ich hatte mich eigentlich auf eine Aussage aus dem C++ Primer bezogen. Da heißt es in der Einleitung zu Arrays (S.143)

Moderne C++ Programme sollten Vektoren und Iteratoren den maschinennahen Arrays und Zeigern fast immer vorziehen. Gut gestaltete Programme verwenden die Letztgenannten nur noch innerhalb von Klassenimplementierungen, wo es auf Geschwindigkeit ankommt.

Und auf S.144:

Arrays sollten auf die inneren Bereiche von Programmen beschränkt bleiben und nur dort zum Einsatz kommen, wo Leistungsprüfungen ergeben, dass Vektoren nicht die erforderliche Geschwindigkeit bieten.

Ist diese Aussage dann schlichtweg falsch?

[volkard]

für kleine arrays dynamischer auf dem stack und für arrays bekannter größe innerhalb von klassen oder auf dem stack können sie schneller als vector sein. die arrays bekannteer größe gibts demnächst auch als standard-klasse. kleine arrays dynamischer auf dem stack sind eine gcc-erweiterung, die vom standard gar nicht abgedeckt ist und auf anderen compilern auch nicht geht.

[asc]

Mitleid schrieb:

Weil die Algorithmen und die Logik, welche das vector-Objekt sicherer machen alle keine Resourcen verbrauchen, oder?

Ich hatte hier im Forum mal meine Tests aufgeführt. Im Reinen Zugriff - sofern man std::vector sinnvoll verwendet (reserve...) sind die Unterschiede nicht messbar. Nur beim Anlegen (Wegen Initialisierung) gab es Unterschiede.

Getestet hatte ich damals auf entweder VC2005 oder VC2008 mit "#define SECURE_SCL 0"

[rüdiger]

BOOLy schrieb:

Hm, ich hätte nicht gedacht das ein kleiner Satz so ein Flamewar startet. Ich hatte mich eigentlich auf eine Aussage aus dem C++ Primer bezogen. Da heißt es in der Einleitung zu Arrays (S.143)

Moderne C++ Programme sollten Vektoren und Iteratoren den maschinennahen Arrays und Zeigern fast immer vorziehen. Gut gestaltete Programme verwenden die Letztgenannten nur noch innerhalb von Klassenimplementierungen, wo es auf Geschwindigkeit ankommt.

Und auf S.144:

Arrays sollten auf die inneren Bereiche von Programmen beschränkt bleiben und nur dort zum Einsatz kommen, wo Leistungsprüfungen ergeben, dass Vektoren nicht die erforderliche Geschwindigkeit bieten.

Ist diese Aussage dann schlichtweg falsch?

Die Aussage ist richtig. Deine Interpretation ist falsch. Die sagen ja eben nicht aus, dass ein vector langsamer als ein Array ist. Wovon sie sprechen sind ja Ausnahmen und die ermittelt man durch eine Leistungsprüfung (=> nachmessen). Ansonsten sollte man immer einen vector nehmen.

Wobei ein vector ist ja auch kein Array. std::tr1::array ist ein Container, der ein Array darstellt. std::vector hat ja eine Speicherverwaltung etc.