285 votes

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

Quelles 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 vecteur avec quelques éléments dedans. Maintenant je veux trouver la somme de tous les éléments. Quelles sont les différentes façons de le faire ?

2 votes

"Combien"? Vraiment? Cette question semble trop vague. :p Il serait peut-être plus utile de demander une bonne façon de le faire.

3 votes

Que voulez-vous dire quand vous dites "fonction similaire à?" Cherchez-vous un remplacement pour std::accumulate dans Boost? (Si oui, pourquoi?) Cherchez-vous des fonctions qui font quelque chose de similaire à std::accumulate? (Si oui, quoi?)

4 votes

Si vous voulez quelque chose de similaire à std::accumulate, vous voulez probablement que cela soit différent d'une manière ou d'une autre (sinon vous pourriez simplement utiliser std::accumulate); quelles différences de std::accumulate recherchez-vous?

482voto

Prasoon Saurav Points 47488

En fait, il existe plusieurs méthodes.

int sum_of_elems = 0;

C++03

  1. Boucle classique for :

     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à, cela accumulera des entiers même si le vecteur contient des flottants. Si vous faites la somme de nombres à virgule flottante, changez 0 en 0.0 ou 0.0f (merci à nneonneo). Voir également la solution C++11 ci-dessous.

C++11 et supérieur

  1. b. Suivi automatique du type de vecteur même en cas de modifications futures:

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

     std::for_each(vector.begin(), vector.end(), [&] (int n) {
         sum_of_elems += n;
     });
  3. Utilisation d'une boucle basée sur une plage (merci à Roger Pate):

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

C++17 et au-delà

  1. Utilisation de std::reduce qui prend également en charge le type de résultat, par exemple si vous avez std::vector, vous obtenez int comme 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 souhaitiez obtenir le résultat rapidement.

7 votes

Bien sûr, en C++03 vous pouvez utiliser std::for_each avec un foncteur, il suffit juste de définir plus de lignes de code que la lambda C++0x.

8 votes

Pourquoi vos exemples lambda utilisent-ils for_each? accumulate serait plus concis (même s'il n'a pas besoin du lambda)

4 votes

@jalf : ton point est correct, j'aurais dû utiliser accumulate à l'intérieur de for_each mais n'est pas cet exemple utile (à des fins d'apprentissage) car il montre que nous pouvons également avoir des lambdas imbriquées :-)

35voto

paxdiablo Points 341644

Prasoon a déjà proposé toute une série 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 rapidité.

Si vous allez faire cela assez souvent, vous devriez envisager de "sous-classer" votre vecteur afin qu'une somme des éléments soit maintenue séparément (pas réellement sous-classer le vecteur ce qui est risqué en raison du manque d'un destructeur virtuel - je parle plutôt d'une classe qui contient la somme et un vecteur à l'intérieur, a plutôt que est-un, et fournit des méthodes similaires à celles d'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-la. Fondamentalement, tout ce qui peut changer le vecteur sous-jacent est intercepté pour garantir que la somme est maintenue de manière cohérente.

De cette manière, vous disposez d'une méthode très efficace en 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 lorsque vous ajusterez 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 est modifié sont ceux qui bénéficieront probablement de ce schéma, car le coût du calcul de la somme est amorti sur tous les accès. De toute évidence, si vous avez seulement besoin de la somme toutes les heures et que le vecteur change trois mille fois par seconde, cela ne conviendra pas.

Quelque chose comme ceci suffirait :

classe UberVecteur:
    privé Vector vec
    privé int somme

    public UberVecteur():
        vec = new Vector()
        somme = 0

    public getSomme():
        return somme

    public ajouter(int val):
        rc = vec.ajouter(val)
        if rc == OK:
            somme = somme + val
        return rc

    public supprIndex(int idx):
        val = 0
        if idx >= 0 et idx < vec.taille:
            val = vec[idx]
        rc =  vec.supprIndex (idx)
        if rc == OK:
            somme = somme - val
        return rc

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

7 votes

Intéressant, mais faites attention car std::vector n'est pas destiné à l'héritage.

7 votes

Désolé, j'aurais dû être plus clair - vous pourriez créer votre propre classe avec les mêmes méthodes que le vecteur qui maintenait un has-a vecteur en lui, plutôt que d'être une sous-classe appropriée ( `is-a ).`

0 votes

@paxdiablo : Très bien avec le has-a.

23voto

James McNellis Points 193607

Pourquoi effectuer la sommation en avant quand vous pouvez le faire en arrière? Donné :

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

Nous pouvons utiliser la méthode de l'indexation, en comptant à rebours :

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

Nous pouvons utiliser la méthode de "l'indexation" vérifiée avec des limites, en comptant à rebours (au cas où) :

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

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

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

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

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

Nous pouvons utiliser accumulate avec des itérateurs inverses :

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

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

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

Donc, comme vous pouvez le voir, il y a autant de façons de sommer le vecteur en arrière que de le faire en avant, et certaines de ces façons sont beaucoup plus excitantes et offrent beaucoup plus d'opportunités d'erreurs de décalage d'un élément.

38 votes

Et pourquoi ne pas également parcourir le vecteur en ajoutant un nombre premier avec l'opérateur modulo pour permettre le rebouclage? :-)

3 votes

@paxdiablo Vous devez seulement être relativement premier par rapport à v.size().

0 votes

Msandiford: non seulement. @paxdiablo: vous devez être relativement premier si vous voulez accéder à tous les éléments. marcher de +7 dans un vecteur de taille 7 ne vous donnera pas grand-chose...

17voto

rafak Points 3310
#inclure
int somme = boost::accumulate(vector, 0);

0 votes

Merci pour la réponse. BTW quelle est la différence entre std::accumulate et boost::accumulate en termes de complexité temporelle?

1 votes

Le temps de complexité est le même pour la fonction std et la fonction boost accumulate -- linéaire. Dans ce cas, boost::accumulate est juste plus facile à taper que d'envoyer manuellement le début et la fin. Il n'y a pas de différence réelle.

7 votes

boost::accumulate n'est qu'un wrapper autour de std::accumulate.

5voto

kriss Points 10450

Je suis un utilisateur de Perl, et dans un jeu auquel nous jouons, c'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é...

Mon avis :

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;
}

Itérer 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();
}`

0 votes

Pourquoi dites-vous que l'itération sur les indices est inefficace ? Quels sont vos arguments pour le dire ?

0 votes

@bobobobo : eh bien, inefficace est probablement excessif. Vous devez à la fois calculer la position des données effectives à partir du vecteur et incrémenter le compteur, mais l'une de ces deux opérations devrait suffire, mais le coût du désabonnement des itérateurs pourrait même être pire. Je vais donc supprimer le mot.

0 votes

Un compilateur d'optimisation peut optimiser la variable d'index et simplement utiliser une incrémentation de pointeur s'il le souhaite. (Il peut faire en sorte que la condition de sortie de la boucle soit une comparaison de pointeurs contre start + length). Les itérateurs réels doivent également être entièrement optimisés. Rappelez-vous, ce n'est pas du perl; il est entièrement compilé en langage d'assemblage, pas interprété.

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X