Comment résumer des éléments d'un vecteur C++ ?

Question

Quels sont les bonnes façons de trouver la somme de tous les éléments dans un std::vector ?

Supposons que j'ai un vecteur std::vector vector avec quelques éléments dedans. Maintenant je veux trouver la somme de tous les éléments. Quelles sont les différentes façons d'y arriver ?

Answer 1

En fait, il existe plusieurs méthodes.

int sum_of_elems = 0;

C++03

1. Boucle for classique:

    for(std::vector::iterator it = vector.begin(); it != vector.end(); ++it)
        sum_of_elems += *it;

2. Utilisation d'un algorithme standard:

    #include 
   
    sum_of_elems = std::accumulate(vector.begin(), vector.end(), 0);

   Note importante: Le type du dernier argument est utilisé non seulement pour la valeur initiale, mais aussi pour le type du résultat. Si vous mettez un int là-bas, cela accumulera des int même si le vecteur contient des floats. Si vous additionnez des nombres flottants, changez 0 en 0.0 ou 0.0f (merci à nneonneo). Voir aussi la solution C++11 ci-dessous.

C++11 et supérieur

2. b. Garder automatiquement le suivi du type du vecteur même en cas de changements futurs:

    #include 
   
    sum_of_elems = std::accumulate(vector.begin(), vector.end(),
                                   decltype(vector)::value_type(0));

3. Utilisation de std::for_each:

    std::for_each(vector.begin(), vector.end(), [&] (int n) {
        sum_of_elems += n;
    });

4. Utilisation d'une boucle for basée sur une plage (merci à Roger Pate):

    for (auto& n : vector)
        sum_of_elems += n;

C++17 et supérieur

5. Utilisation de std::reduce qui prend également en charge le type de résultat, par exemple si vous avez std::vector, vous obtenez int en tant que résultat. Si vous avez std::vector, vous obtenez float. Ou si vous avez std::vector, vous obtenez std::string (toutes les chaînes concaténées). Intéressant, n'est-ce pas?

   #include        
   
   auto result = std::reduce(v.begin(), v.end());

   Il existe d'autres surcharges de cette fonction que vous pouvez exécuter même en parallèle, au cas où vous auriez une grande collection et que vous vouliez obtenir rapidement le résultat.

Answer 2

Prasoon a déjà proposé une foule de façons différentes (et bonnes) de le faire, dont aucune n'a besoin d'être répétée ici. J'aimerais suggérer cependant une approche alternative pour la vitesse.

Si vous allez faire cela assez souvent, vous pouvez envisager de "sous-classer" votre vecteur afin qu'une somme des éléments soit maintenue séparément (pas vraiment sous-classer le vecteur qui est délicat en raison du manque de destructeur virtuel - je parle plutôt d'une classe qui contient la somme et un vecteur en son sein, has-a plutôt que is-a, et fournit les méthodes ressemblant à un vecteur).

Pour un vecteur vide, la somme est mise à zéro. À chaque insertion dans le vecteur, ajoutez l'élément inséré à la somme. À chaque suppression, soustrayez-le. Fondamentalement, tout ce qui peut changer le vecteur sous-jacent est intercepté pour garantir que la somme reste cohérente.

De cette manière, vous disposez d'une méthode très efficace O(1) pour "calculer" la somme à tout moment (il suffit de retourner la somme actuellement calculée). L'insertion et la suppression prendront un peu plus de temps car vous ajustez le total et vous devez prendre en compte cette perte de performance.

Les vecteurs où la somme est nécessaire plus souvent que le vecteur n'est modifié sont ceux susceptibles de bénéficier de ce schéma, puisque le coût du calcul de la somme est amorti sur tous les accès. Évidemment, si vous avez seulement besoin de la somme toutes les heures et que le vecteur change trois mille fois par seconde, cela ne sera pas approprié.

Quelque chose comme ceci suffirait :

class UberVector:
    private Vector vec
    private int sum

    public UberVector():
        vec = new Vector()
        sum = 0

    public getSum():
        return sum

    public add (int val):
        rc = vec.add (val)
        if rc == OK:
            sum = sum + val
        return rc

    public delindex (int idx):
        val = 0
        if idx >= 0 and idx < vec.size:
            val = vec[idx]
        rc =  vec.delindex (idx)
        if rc == OK:
            sum = sum - val
        return rc

Évidemment, c'est du pseudo-code et vous voudrez peut-être avoir un peu plus de fonctionnalités, mais cela montre le concept de base.

Answer 3

Pourquoi effectuer la sommation vers l'avant lorsque vous pouvez le faire à l'envers? Soit :

std::vector v;     // vecteur à sommer
int sum_of_elements(0); // résultat de la sommation

Nous pouvons utiliser la notation entre crochets, en comptant à rebours :

for (int i(v.size()); i > 0; --i)
    sum_of_elements += v[i-1];

Nous pouvons utiliser la notation entre crochets avec vérification de la portée, en comptant à rebours (au cas où) :

for (int i(v.size()); i > 0; --i)
    sum_of_elements += v.at(i-1);

Nous pouvons utiliser des itérateurs inversés dans une boucle for :

for(std::vector::const_reverse_iterator i(v.rbegin()); i != v.rend(); ++i)
    sum_of_elements += *i;

Nous pouvons utiliser des itérateurs normaux, itérant à rebours, dans une boucle for (oooh, malin!) :

for(std::vector::const_iterator i(v.end()); i != v.begin(); --i)
    sum_of_elements += *(i - 1);

Nous pouvons utiliser accumulate avec des itérateurs inversés :

sum_of_elems = std::accumulate(v.rbegin(), v.rend(), 0);

Nous pouvons utiliser for_each avec une expression lambda en utilisant des itérateurs inversés :

std::for_each(v.rbegin(), v.rend(), [&](int n) { sum_of_elements += n; });

Ainsi, comme vous pouvez le constater, il existe autant de façons de faire la sommation du vecteur à l'envers que de le faire à l'endroit, et certaines de ces méthodes sont bien plus excitantes et offrent beaucoup plus d'opportunités d'erreurs d'un élément.

Answer 4

#inclure
int somme = boost::accumulate(vecteur, 0);

Answer 5

Je suis un utilisateur de Perl, et un jeu que nous avons est de trouver toutes les façons différentes d'incrémenter une variable... ce n'est pas vraiment différent ici. La réponse à combien de façons de trouver la somme des éléments d'un vecteur en C++ est probablement une infinité...

My 2 cents:

En utilisant BOOST_FOREACH, pour se débarrasser de la syntaxe laide de l'itérateur :

sum = 0;
BOOST_FOREACH(int & x, myvector){
  sum += x;
}

en itérant sur les indices (vraiment facile à lire).

int i, sum = 0;
for (i=0; i

`Celui-ci est destructif, accédant au vecteur comme une pile :

while (!myvector.empty()){
   sum+=myvector.back();
   myvector.pop_back();
}`