Was sind die guten Möglichkeiten, um die Summe aller Elemente in a zu finden std::vector
?
Angenommen, ich habe einen Vektor std::vector<int> vector
mit einigen Elementen. Jetzt möchte ich die Summe aller Elemente finden. Was sind die verschiedenen Möglichkeiten für das gleiche?
std::accumulate
in Boost? (Wenn ja, warum?) Suchen Sie nach Funktionen, die etwas Ähnliches bewirkenstd::accumulate
? (Wenn ja, was?)std::accumulate
, möchten Sie vermutlich auch, dass es in gewisser Hinsicht anders ist (andernfalls könnten Sie es einfach verwendenstd::accumulate
). Welche Unterschiedestd::accumulate
suchen Sie?Antworten:
Eigentlich gibt es einige Methoden.
C ++ 03
Klassiker für Loop:
Verwenden eines Standardalgorithmus:
Wichtiger Hinweis: Der Typ des letzten Arguments wird nicht nur für den Anfangswert verwendet, sondern auch für den Typ des Ergebnisses . Wenn Sie dort ein int einfügen, werden Ints akkumuliert, selbst wenn der Vektor float hat. Wenn Sie Gleitkommazahlen summieren, wechseln Sie
0
zu0.0
oder0.0f
(dank nneonneo). Siehe auch die C ++ 11-Lösung unten.C ++ 11 und höher
b. Automatische Verfolgung des Vektortyps auch bei zukünftigen Änderungen:
Verwenden von
std::for_each
:Verwenden einer bereichsbasierten for-Schleife (danke an Roger Pate):
quelle
std::for_each
einen Funktor verwenden. Die Definition erfordert nur mehr Codezeilen als das C ++ 0x-Lambda.for_each
?accumulate
wäre prägnanter (auch wenn es das Lambda nicht braucht)accumulate
innenfor_each
aber ist nicht dieses Beispiel nützlich (zum Zweck Lernen) , da es zeigt , dass wir auch verschachtelte lambdas haben :-)accumulate
. Der Typ des letzten Arguments wird nicht nur für den Anfangswert verwendet, sondern auch für den Typ des Ergebnisses. Wenn Sie dort ein setzenint
, wirdint
s auch dann akkumuliert , wenn der Vektor hatfloat
. Das Ergebnis kann auf subtile Weise falsch sein, und der Compiler wandelt das Ergebnis wieder in einen Float um, ohne es Ihnen mitzuteilen.for_each
wenn Sie habenaccumulate
?Der einfachste Weg ist die Verwendung
std:accumuate
vonvector<int> A
:quelle
Prasoon hat bereits eine Reihe verschiedener (und guter) Möglichkeiten angeboten, von denen keine hier wiederholt werden muss. Ich möchte jedoch einen alternativen Ansatz für die Geschwindigkeit vorschlagen.
Wenn Sie vorhaben , dieses ziemlich viel zu tun, können Sie „sub-classing“ Ihr Vektor so dass eine Summe von Elementen zu prüfen , ist separat gepflegt (nicht eigentlich Unterklassierungsvektor, der iffy aufgrund des Fehlens von a virtueller Destruktor - Ich spreche eher von einer Klasse, die die Summe und einen Vektor enthält,
has-a
als vonis-a
vektorähnlichen Methoden.Für einen leeren Vektor wird die Summe auf Null gesetzt. Fügen Sie bei jeder Einfügung in den Vektor das einzufügende Element zur Summe hinzu. Subtrahieren Sie es bei jedem Löschen. Grundsätzlich alles abgefangen den zugrunde liegenden Vektor ändern kann, um sicherzustellen, dass die Summe konsistent bleibt.
Auf diese Weise haben Sie eine sehr effiziente O (1) -Methode zum "Berechnen" der Summe zu jedem Zeitpunkt (geben Sie einfach die aktuell berechnete Summe zurück). Das Einfügen und Löschen dauert etwas länger, wenn Sie die Gesamtsumme anpassen, und Sie sollten diesen Leistungseinbruch berücksichtigen.
Vektoren, bei denen die Summe häufiger benötigt wird als der Vektor geändert wird, profitieren wahrscheinlich von diesem Schema, da die Kosten für die Berechnung der Summe über alle Zugriffe abgeschrieben werden. Wenn Sie nur die Summe jede Stunde benötigen und sich der Vektor dreitausend Mal pro Sekunde ändert, ist dies natürlich nicht geeignet.
So etwas würde ausreichen:
Das ist natürlich Pseudocode und Sie möchten vielleicht etwas mehr Funktionalität, aber es zeigt das Grundkonzept.
quelle
std::vector
nicht für Unterklassen gedacht ist.has-a
Vektor darin beibehält , anstatt eine richtige Unterklasse zu sein (is-a
).operator[](int)
nichtWarum die Summierung vorwärts durchführen, wenn Sie sie rückwärts ausführen können ? Gegeben:
Wir können Subskription verwenden und rückwärts zählen:
Wir können bereichsüberprüfte "Subskriptionen" verwenden, die rückwärts zählen (nur für den Fall):
Wir können Reverse-Iteratoren in einer for-Schleife verwenden:
Wir können Vorwärtsiteratoren verwenden, die rückwärts in einer for-Schleife iterieren (oooh, knifflig!):
Wir können
accumulate
mit Reverse-Iteratoren verwenden:Wir können
for_each
mit einem Lambda-Ausdruck unter Verwendung von Umkehriteratoren verwenden:Wie Sie sehen, gibt es also genauso viele Möglichkeiten, den Vektor rückwärts zu summieren wie den Vektor vorwärts, und einige davon sind viel aufregender und bieten weitaus größere Möglichkeiten für Fehler, die nacheinander auftreten.
quelle
v.size()
.quelle
boost::accumulate
ist nur eine Hülle herumstd::accumulate
.#include <numeric>
undstd::accumulate(v.begin(), v.end(), (int64_t)0);
. Beachten Sie, dass der Typ des anfänglichen Akkumulatorwerts als Akkumulatortyp verwendet wird. Wenn Sie also 8-Bit-Elemente zu einem 64-Bit-Ergebnis zusammenfassen möchten, gehen Sie wie folgt vor.Man kann auch verwendet werden,
std::valarray<T>
wie diesEinige finden diesen Weg möglicherweise nicht effizient, da die Größe von
valarray
so groß sein muss wie die Größe des Vektors, und die Initialisierungvalarray
wird ebenfalls Zeit in Anspruch nehmen.Verwenden Sie es in diesem Fall nicht und nehmen Sie es als eine weitere Möglichkeit, die Sequenz zusammenzufassen.
quelle
Nur C ++ 0x:
Dies ähnelt dem an anderer Stelle erwähnten BOOST_FOREACH und hat den gleichen Vorteil der Klarheit in komplexeren Situationen im Vergleich zu Stateful-Funktoren, die mit accumulate oder for_each verwendet werden.
quelle
for (int n : v) sum += n;
infor (auto n : v) sum += n;
es mit jeder Vektor - Vorlage arbeiten. Ich wusste, dass sich OP auf den Vektor <int> bezieht, aber dieser Weg ist etwas allgemeiner :-)Ich bin ein Perl-Benutzer. Ein Spiel, das wir haben, besteht darin, alle Möglichkeiten zu finden, um eine Variable zu erhöhen. Das ist hier nicht wirklich anders. Die Antwort darauf, wie viele Möglichkeiten es gibt, die Summe der Elemente eines Vektors in C ++ zu finden, ist wahrscheinlich
an infinity
...Meine 2 Cent:
Verwenden Sie BOOST_FOREACH, um sich von der hässlichen Iteratorsyntax zu befreien:
Iteration auf Indizes (sehr einfach zu lesen).
Dieser andere ist destruktiv und greift wie ein Stapel auf einen Vektor zu:
quelle
start + length
). Tatsächliche Iteratoren sollten ebenfalls vollständig optimiert werden. Denken Sie daran, es ist nicht Perl; Es ist vollständig zu asm kompiliert und nicht interpretiert.quelle
int
Indizierung von astd::vector
ist im Allgemeinen nicht sicher.v.size()
ist möglicherweise größer als der höchste Wert, in dem gespeichert werden kannint
(beachten Sie, dass bei einigen Zielplattformen und Compilernsize_of(int) < size_of(size_t)
). In diesem Fall läuft Ihr Code über den Index. std :: vector <T> :: size_type sollte bevorzugt werden.Es ist leicht. C ++ 11 bietet eine einfache Möglichkeit, Elemente eines Vektors zusammenzufassen.
quelle