Comment puis-je éviter les boucles «for» avec une condition «if» à l'intérieur avec C ++?

111

Avec presque tout le code que j'écris, je suis souvent confronté à des problèmes de réduction d'ensembles sur des collections qui finissent par se retrouver avec des conditions naïves «si» à l'intérieur. Voici un exemple simple:

for(int i=0; i<myCollection.size(); i++)
{
     if (myCollection[i] == SOMETHING)
     {
           DoStuff();
     }
}

Avec les langages fonctionnels, je peux résoudre le problème en réduisant la collection à une autre collection (facilement) et ensuite effectuer toutes les opérations sur mon ensemble réduit. En pseudocode:

newCollection <- myCollection where <x=true
map DoStuff newCollection

Et dans d'autres variantes C, comme C #, je pourrais réduire avec une clause where comme

foreach (var x in myCollection.Where(c=> c == SOMETHING)) 
{
   DoStuff();
}

Ou mieux (du moins à mes yeux)

myCollection.Where(c=>c == Something).ToList().ForEach(d=> DoStuff(d));

Certes, je fais beaucoup de mélange de paradigmes et de style subjectif / basé sur l'opinion, mais je ne peux m'empêcher de penser qu'il me manque quelque chose de vraiment fondamental qui pourrait me permettre d'utiliser cette technique préférée avec C ++. Quelqu'un pourrait-il m'éclairer?

Darkenor
la source
7
En dehors de la fonctionnalité de bibliothèque standard C ++, vous pouvez essayer std::copy_if, mais les sélections ne sont pas paresseuses
milleniumbug
14
Vous pourriez être intéressé par range-v3 . Il devrait également arriver en C ++ en tant que TS et, espérons-le, normalisé dans une prochaine version.
NathanOliver
12
Je ressens le besoin de souligner que l' ifintérieur d'un que forvous mentionnez n'est pas seulement à peu près équivalent sur le plan fonctionnel aux autres exemples, mais qu'il serait probablement aussi plus rapide dans de nombreux cas. Aussi pour quelqu'un qui prétend aimer le style fonctionnel, ce que vous promouvez semble aller à l'encontre du concept de pureté très apprécié de la programmation fonctionnelle depuisDoStuff il a clairement des effets secondaires.
Pharap
60
Je n'ai jamais vraiment compris pourquoi les gens lient en combinant toute la logique sur une seule ligne, cela donne un aspect plus ou moins lisible. Votre extrait de code C ++ tout en haut est de loin le plus lisible pour moi de toutes vos possibilités. Et comme l'efficacité ne changera pas, je ne peux pas comprendre pourquoi vous préférez ne pas écrire cela, à moins que vous ne soyez payé par le nombre de lignes de code que vous supprimez.
Cody Gray
10
@CodyGray D'accord: c'est juste du sucre syntaxique. Et le titre de la question est trompeur, car il est très différent d' éviter la ramification et de le cacher sous abstraction.
edmz

Réponses:

99

IMHO, il est plus simple et plus lisible d'utiliser une boucle for avec un if à l'intérieur. Cependant, si cela vous ennuie, vous pouvez en utiliser un for_each_ifcomme celui ci-dessous:

template<typename Iter, typename Pred, typename Op> 
void for_each_if(Iter first, Iter last, Pred p, Op op) {
  while(first != last) {
    if (p(*first)) op(*first);
    ++first;
  }
}

Cas d'utilisation:

std::vector<int> v {10, 2, 10, 3};
for_each_if(v.begin(), v.end(), [](int i){ return i > 5; }, [](int &i){ ++i; });

Démo en direct

101010
la source
10
C'est exceptionnellement intelligent. Je conviendrai également que ce n'est pas simple et j'utiliserai probablement des conditions if lors de la programmation du C ++ consommé par d'autres. Mais c'est exactement ce dont j'ai besoin pour mon usage personnel! :)
Darkenor
14
@Default Passer des paires d'itérateurs plutôt que des conteneurs est à la fois plus flexible et idiomatique en C ++.
Mark B du
8
@Slava, en général, les plages ne réduiront pas le nombre d'algorithmes. Par exemple, vous avez encore besoin find_ifet findqu'ils travaillent sur des plages ou des paires de itérateurs. (Il existe quelques exceptions, telles que for_eachet for_each_n). Le moyen d'éviter d'écrire de nouveaux algos pour chaque éternuement est d'utiliser différentes opérations avec les algos existants, par exemple au lieu d' for_each_ifintégrer la condition dans l'appelable passé à for_each, par exemplefor_each(first, last, [&](auto& x) { if (cond(x)) f(x); });
Jonathan Wakely
9
Je vais devoir être d'accord avec la première phrase: la solution standard pour-si est beaucoup plus lisible et plus facile à utiliser . Je pense que la syntaxe lambda et l'utilisation d'un modèle défini ailleurs juste pour gérer une simple boucle irriteraient ou pourraient confondre les autres développeurs. Vous sacrifiez la localité et la performance pour ... quoi? Être capable d'écrire quelque chose en une seule ligne?
user1354557
45
Cough @Darkenor, généralement une programmation " exceptionnellement intelligente" est à éviter car elle dérange la merde de tout le monde, y compris votre futur moi.
Ryan
48

Boost fournit des plages qui peuvent être utilisées avec des plages basées sur. Les plages ont l'avantage de ne pas copier la structure de données sous-jacente, elles fournissent simplement une «vue» (c'est-à-dire begin(), end()pour la plage et operator++(), operator==()pour l'itérateur). Cela pourrait vous intéresser: http://www.boost.org/libs/range/doc/html/range/reference/adaptors/reference/filtered.html

#include <boost/range/adaptor/filtered.hpp>
#include <iostream>
#include <vector>

struct is_even
{
    bool operator()( int x ) const { return x % 2 == 0; }
};

int main(int argc, const char* argv[])
{
    using namespace boost::adaptors;

    std::vector<int> myCollection{1,2,3,4,5,6,7,8,9};

    for( int i: myCollection | filtered( is_even() ) )
    {
        std::cout << i;
    }
}
Lorro
la source
1
Puis-je suggérer d'utiliser l'exemple des OP à la place, c'est-à-dire is_even=> condition, input=> myCollectionetc.
Par défaut le
C'est une très bonne réponse et certainement ce que je cherche à faire. Je vais attendre d'accepter à moins que quelqu'un ne puisse trouver un moyen conforme standard de le faire qui utilise une exécution paresseuse / différée. J'ai voté pour.
Darkenor
5
@Darkenor: Si Boost est un problème pour vous (par exemple, vous êtes interdit de l'utiliser en raison de la politique de l'entreprise et de la sagesse du gestionnaire), je peux vous proposer une définition simplifiée de filtered()- cela dit, il est préférable d'utiliser une lib prise en charge que du code ad hoc.
lorro
Totalement d'accord avec toi. Je l'ai accepté parce que la manière conforme aux normes est venue en premier parce que la question était orientée vers C ++ lui-même, pas la bibliothèque boost. Mais c'est vraiment excellent. Aussi - oui, j'ai malheureusement travaillé dans de nombreux endroits qui ont interdit Boost pour des raisons absurdes ...
Darkenor
@LeeClagett:? .
lorro
44

Au lieu de créer un nouvel algorithme, comme le fait la réponse acceptée, vous pouvez utiliser un algorithme existant avec une fonction qui applique la condition:

std::for_each(first, last, [](auto&& x){ if (cond(x)) { ... } });

Ou si vous voulez vraiment un nouvel algorithme, au moins le réutiliser for_eachau lieu de dupliquer la logique d'itération:

template<typename Iter, typename Pred, typename Op> 
  void
  for_each_if(Iter first, Iter last, Pred p, Op op) {
    std::for_each(first, last, [&](auto& x) { if (p(x)) op(x); });
  }
Jonathan Wakely
la source
Bien mieux et plus clair pour utiliser la bibliothèque standard.
anonyme le
4
Parce que std::for-each(first, last, [&](auto& x) {if (p(x)) op(x); });c'est totalement plus simple que for (Iter x = first; x != last; x++) if (p(x)) op(x);}?
user253751
2
@immibis réutiliser la bibliothèque standard présente d'autres avantages, tels que la vérification de la validité de l'itérateur, ou (en C ++ 17) être beaucoup plus facile à paralléliser, simplement en ajoutant un argument supplémentaire: std::for_each(std::execution::par, first, last, ...);est-il facile d'ajouter ces choses à une boucle manuscrite?
Jonathan Wakely
1
#pragma omp parallèle pour
Mark K Cowan
2
@mark désolé, une bizarrerie aléatoire de votre code source ou de votre chaîne de construction a fait que l'extension de compilateur parallèle non standard, extrêmement fragile, ne génère aucune amélioration des performances sans diagnostic.
Yakk - Adam Nevraumont
21

L'idée d'éviter

for(...)
    if(...)

construit comme un anti-modèle est trop large.

Il est tout à fait correct de traiter plusieurs éléments qui correspondent à une certaine expression à l'intérieur d'une boucle, et le code ne peut pas être beaucoup plus clair que cela. Si le traitement devient trop volumineux pour tenir à l'écran, c'est une bonne raison d'utiliser un sous-programme, mais le conditionnel est toujours mieux placé à l'intérieur de la boucle, c'est-à-dire

for(...)
    if(...)
        do_process(...);

est largement préférable à

for(...)
    maybe_process(...);

Cela devient un anti-modèle lorsqu'un seul élément correspondra, car il serait alors plus clair de rechercher d'abord l'élément et d'effectuer le traitement en dehors de la boucle.

for(int i = 0; i < size; ++i)
    if(i == 5)

en est un exemple extrême et évident. Plus subtil, et donc plus courant, est un modèle d'usine comme

for(creator &c : creators)
    if(c.name == requested_name)
    {
        unique_ptr<object> obj = c.create_object();
        obj.owner = this;
        return std::move(obj);
    }

C'est difficile à lire, car il n'est pas évident que le code du corps ne sera exécuté qu'une seule fois. Dans ce cas, il serait préférable de séparer la recherche:

creator &lookup(string const &requested_name)
{
    for(creator &c : creators)
        if(c.name == requested_name)
            return c;
}

creator &c = lookup(requested_name);
unique_ptr obj = c.create_object();

Il y a toujours un ifdans un for, mais à partir du contexte, il devient clair ce qu'il fait, il n'est pas nécessaire de changer ce code à moins que la recherche ne change (par exemple en a map), et il est immédiatement clair que ce create_object()n'est appelé qu'une seule fois, car il est pas dans une boucle.

Simon Richter
la source
J'aime cela, comme une vue d'ensemble réfléchie et équilibrée, même si elle refuse en un sens de répondre à la question posée. Je trouve que le for( range ){ if( condition ){ action } }-style facilite la lecture des choses un morceau à la fois et n'utilise que la connaissance des constructions de base du langage.
PJTraill
@PJTraill, la façon dont la question a été formulée m'a rappelé la diatribe de Raymond Chen contre l' anti-modèle pour-si , qui a été cultivée dans le fret et est devenue en quelque sorte un absolu. Je suis tout à fait d'accord que for(...) if(...) { ... }c'est souvent le meilleur choix (c'est pourquoi j'ai qualifié la recommandation de diviser l'action en un sous-programme).
Simon Richter
1
Merci pour le lien, qui a clarifié les choses pour moi: le nom " pour-si " est trompeur, et devrait être quelque chose comme " pour-tout-si-un " ou " recherche-évitement ". Cela me rappelle la façon dont l'inversion de l'abstraction a été décrite par Wikipédia en 2005 comme quand on « crée des constructions simples sur des complexes » - jusqu'à ce que je les réécrive! En fait, je ne me précipiterais même pas pour corriger la forme de recherche-processus-sortie de for(…)if(…)…si c'était le seul endroit où la recherche avait eu lieu.
PJTraill
17

Voici une fonction rapide relativement minimale filter.

Il faut un prédicat. Il renvoie un objet fonction qui prend un itérable.

Il renvoie un itérable qui peut être utilisé dans une for(:)boucle.

template<class It>
struct range_t {
  It b, e;
  It begin() const { return b; }
  It end() const { return e; }
  bool empty() const { return begin()==end(); }
};
template<class It>
range_t<It> range( It b, It e ) { return {std::move(b), std::move(e)}; }

template<class It, class F>
struct filter_helper:range_t<It> {
  F f;
  void advance() {
    while(true) {
      (range_t<It>&)*this = range( std::next(this->begin()), this->end() );
      if (this->empty())
        return;
      if (f(*this->begin()))
        return;
    }
  }
  filter_helper(range_t<It> r, F fin):
    range_t<It>(r), f(std::move(fin))
  {
      while(true)
      {
          if (this->empty()) return;
          if (f(*this->begin())) return;
          (range_t<It>&)*this = range( std::next(this->begin()), this->end() );
      }
  }
};

template<class It, class F>
struct filter_psuedo_iterator {
  using iterator_category=std::input_iterator_tag;
  filter_helper<It, F>* helper = nullptr;
  bool m_is_end = true;
  bool is_end() const {
    return m_is_end || !helper || helper->empty();
  }

  void operator++() {
    helper->advance();
  }
  typename std::iterator_traits<It>::reference
  operator*() const {
    return *(helper->begin());
  }
  It base() const {
      if (!helper) return {};
      if (is_end()) return helper->end();
      return helper->begin();
  }
  friend bool operator==(filter_psuedo_iterator const& lhs, filter_psuedo_iterator const& rhs) {
    if (lhs.is_end() && rhs.is_end()) return true;
    if (lhs.is_end() || rhs.is_end()) return false;
    return lhs.helper->begin() == rhs.helper->begin();
  }
  friend bool operator!=(filter_psuedo_iterator const& lhs, filter_psuedo_iterator const& rhs) {
    return !(lhs==rhs);
  }
};
template<class It, class F>
struct filter_range:
  private filter_helper<It, F>,
  range_t<filter_psuedo_iterator<It, F>>
{
  using helper=filter_helper<It, F>;
  using range=range_t<filter_psuedo_iterator<It, F>>;

  using range::begin; using range::end; using range::empty;

  filter_range( range_t<It> r, F f ):
    helper{{r}, std::forward<F>(f)},
    range{ {this, false}, {this, true} }
  {}
};

template<class F>
auto filter( F&& f ) {
    return [f=std::forward<F>(f)](auto&& r)
    {
        using std::begin; using std::end;
        using iterator = decltype(begin(r));
        return filter_range<iterator, std::decay_t<decltype(f)>>{
            range(begin(r), end(r)), f
        };
    };
};

J'ai pris des raccourcis. Une vraie bibliothèque devrait faire de vrais itérateurs, pas lesfor(:) pseudo-façades qualifiantes que j'ai faites.

Au point d'utilisation, cela ressemble à ceci:

int main()
{
  std::vector<int> test = {1,2,3,4,5};
  for( auto i: filter([](auto x){return x%2;})( test ) )
    std::cout << i << '\n';
}

ce qui est plutôt sympa et imprime

1
3
5

Exemple en direct .

Il y a un ajout proposé à C ++ appelé Rangesv3 qui fait ce genre de chose et plus encore. boosta également des gammes de filtres / itérateurs disponibles. boost a également des aides qui rendent l'écriture de ce qui précède beaucoup plus courte.

Yakk - Adam Nevraumont
la source
15

Un style qui est assez utilisé pour être mentionné, mais qui n'a pas encore été mentionné, est:

for(int i=0; i<myCollection.size(); i++) {
  if (myCollection[i] != SOMETHING)
    continue;

  DoStuff();
}

Avantages:

  • Ne modifie pas le niveau d'indentation DoStuff();lorsque la complexité des conditions augmente. Logiquement, DoStuff();devrait être au niveau supérieur de la forboucle, et c'est le cas.
  • Indique immédiatement que la boucle itère sur les SOMETHINGs de la collection, sans exiger du lecteur qu'il vérifie qu'il n'y a rien après la fermeture }du ifbloc.
  • Ne nécessite aucune bibliothèque ou macros ou fonctions d'assistance.

Désavantages:

  • continue, Comme d' autres instructions de contrôle de flux, obtient mal utilisé dans les chemins qui mènent à coder en dur à suivre tant que certaines personnes sont opposés à toute utilisation d'entre eux: il y a un style valide de codage que certains suivi qui évite continue, qui évite breakautre que en a switch, cela évite returnautrement qu'à la fin d'une fonction.

la source
3
Je dirais que dans une forboucle qui s'étend sur de nombreuses lignes, un "sinon, continue" sur deux lignes est beaucoup plus clair, logique et lisible. Dire immédiatement «sauter ceci si» après que l' forinstruction se lit bien et, comme vous l'avez dit, n'indente pas les aspects fonctionnels restants de la boucle. Si le continueest plus bas, cependant, une certaine clarté est sacrifiée (c'est-à-dire si une opération sera toujours effectuée avant l' ifinstruction).
anonyme le
11
for(auto const &x: myCollection) if(x == something) doStuff();

Cela ressemble beaucoup à une forcompréhension spécifique au C ++ . À toi?

bipll
la source
Je ne pense pas que le mot-clé auto était présent avant le c ++ 11, donc je ne dirais pas que c'est du c ++ très classique. Si je peux poser une question ici dans le commentaire, "auto const" dira-t-il au compilateur qu'il peut réorganiser tous les éléments comme il le souhaite? Il sera peut-être plus facile pour le compilateur de prévoir d'éviter les branchements si tel est le cas.
mathreadler
1
@mathreadler Plus tôt les gens cesseront de s'inquiéter du "c ++ classique", mieux ce sera. C ++ 11 était un événement macroévolutionnaire pour le langage et a 5 ans: ce devrait être le minimum auquel nous aspirons. Quoi qu'il en soit, l'OP a marqué cela et C ++ 14 (encore mieux!). Non, auto constn'a aucune incidence sur l'ordre d'itération. Si vous recherchez à distance for, vous verrez qu'il fait essentiellement une boucle standard de begin()à end()avec un déréférencement implicite. Il n'y a aucun moyen que cela puisse briser les garanties de commande (le cas échéant) du conteneur en cours d'itération; il aurait été ri de la face de la Terre
underscore_d
1
@mathreadler, en fait, cela avait juste une signification très différente. Ce qui n'était pas présent, c'est range-for ... et toute autre fonctionnalité distincte de C ++ 11. Ce que je voulais dire ici, c'est que range-fors, std::futures, std::functions, même ces fermetures anonymes sont très bien C ++ dans la syntaxe; chaque langue a son propre langage et, lorsqu'elle intègre de nouvelles fonctionnalités, elle essaie de les faire imiter l'ancienne syntaxe bien connue.
bipll
@underscore_d, un compilateur est autorisé à effectuer toutes les transformations à condition que la règle as-if soit respectée, n'est-ce pas?
bipll
1
Hmmm, et que peut-on signifier par là?
bipll
7

Si DoStuff () dépendait d'une manière ou d'une autre de i dans le futur, je proposerais cette variante de masquage de bits sans branche garantie.

unsigned int times = 0;
const int kSize = sizeof(unsigned int)*8;
for(int i = 0; i < myCollection.size()/kSize; i++){
  unsigned int mask = 0;
  for (int j = 0; j<kSize; j++){
    mask |= (myCollection[i*kSize+j]==SOMETHING) << j;
  }
  times+=popcount(mask);
}

for(int i=0;i<times;i++)
   DoStuff();

Où popcount est une fonction faisant un comptage de population (nombre de bits de comptage = 1). Il y aura une certaine liberté pour mettre des contraintes plus avancées avec i et leurs voisins. Si cela n'est pas nécessaire, nous pouvons dénuder la boucle intérieure et refaire la boucle extérieure

for(int i = 0; i < myCollection.size(); i++)
  times += (myCollection[i]==SOMETHING);

suivi d'un

for(int i=0;i<times;i++)
   DoStuff();
mathreadler
la source
6

De plus, si vous ne vous souciez pas de réorganiser la collection, std :: partition est bon marché.

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

void DoStuff(int i)
{
    std::cout << i << '\n';
}

int main()
{
    using namespace std::placeholders;

    std::vector<int> v {1, 2, 5, 0, 9, 5, 5};
    const int SOMETHING = 5;

    std::for_each(v.begin(),
                  std::partition(v.begin(), v.end(),
                                 std::bind(std::equal_to<int> {}, _1, SOMETHING)), // some condition
                  DoStuff); // action
}
Loreto
la source
Mais std::partitionréorganise le conteneur.
celtschk
5

Je suis impressionné par la complexité des solutions ci-dessus. J'allais suggérer un simple #define foreach(a,b,c,d) for(a; b; c)if(d)mais il a quelques déficits évidents, par exemple, vous devez vous rappeler d'utiliser des virgules au lieu de points-virgules dans votre boucle, et vous ne pouvez pas utiliser l'opérateur virgule dans aou c.

#include <list>
#include <iostream>

using namespace std; 

#define foreach(a,b,c,d) for(a; b; c)if(d)

int main(){
  list<int> a;

  for(int i=0; i<10; i++)
    a.push_back(i);

  for(auto i=a.begin(); i!=a.end(); i++)
    if((*i)&1)
      cout << *i << ' ';
  cout << endl;

  foreach(auto i=a.begin(), i!=a.end(), i++, (*i)&1)
    cout << *i << ' ';
  cout << endl;

  return 0;
}
Ian Parberry
la source
3
La complexité de certaines réponses n'est élevée que parce qu'elles montrent d'abord une méthode générique réutilisable (ce que vous ne feriez qu'une seule fois), puis l'utilisent. Pas efficace si vous avez une boucle avec une condition if dans toute votre application mais très efficace si cela se produit mille fois.
gnasher729
1
Comme la plupart des suggestions, cela rend plus difficile, pas plus facile, l'identification de la plage et la condition de sélection. Et l'utilisation d'une macro augmente l'incertitude sur le moment (et la fréquence) des expressions sont évaluées, même s'il n'y a pas de surprises ici.
PJTraill
2

Une autre solution au cas où les i: s seraient importants. Celui-ci construit une liste qui remplit les index pour lesquels appeler doStuff (). Encore une fois, le point principal est d'éviter le branchement et de l'échanger contre des coûts arithmétiques pipelinables.

int buffer[someSafeSize];
int cnt = 0; // counter to keep track where we are in list.
for( int i = 0; i < container.size(); i++ ){
   int lDecision = (container[i] == SOMETHING);
   buffer[cnt] = lDecision*i + (1-lDecision)*buffer[cnt];
   cnt += lDecision;
}

for( int i=0; i<cnt; i++ )
   doStuff(buffer[i]); // now we could pass the index or a pointer as an argument.

La ligne «magique» est la ligne de chargement de la mémoire tampon qui calcule arithmétiquement s'il faut garder la valeur et rester en position ou compter la position et ajouter de la valeur. Nous échangeons donc une branche potentielle contre certaines logiques et arithmétiques et peut-être quelques hits de cache. Un scénario typique dans lequel cela serait utile est si doStuff () effectue une petite quantité de calculs pipelinables et que toute branche entre les appels pourrait interrompre ces pipelines.

Ensuite, faites une boucle sur le tampon et exécutez doStuff () jusqu'à ce que nous atteignions cnt. Cette fois, nous aurons le courant i stocké dans le tampon afin que nous puissions l'utiliser dans l'appel à doStuff () si nous en avons besoin.

mathreadler
la source
1

On peut décrire votre modèle de code comme appliquant une fonction à un sous-ensemble d'une plage, ou en d'autres termes: l'appliquer au résultat de l'application d'un filtre à l'ensemble de la plage.

Ceci est réalisable de la manière la plus simple avec la bibliothèque range-v3 d'Eric Neibler ; même si c'est un peu une horreur, parce que vous voulez travailler avec des indices:

using namespace ranges;
auto mycollection_has_something = 
    [&](std::size_t i) { return myCollection[i] == SOMETHING };
auto filtered_view = 
    views::iota(std::size_t{0}, myCollection.size()) | 
    views::filter(mycollection_has_something);
for (auto i : filtered_view) { DoStuff(); }

Mais si vous êtes prêt à renoncer aux indices, vous obtiendrez:

auto is_something = [&SOMETHING](const decltype(SOMETHING)& x) { return x == SOMETHING };
auto filtered_collection = myCollection | views::filter(is_something);
for (const auto& x : filtered_collection) { DoStuff(); }

ce qui est plus agréable à mon humble avis.

PS - La bibliothèque de plages entre principalement dans le standard C ++ en C ++ 20.

einpoklum
la source
0

Je mentionnerai juste Mike Acton, il dirait certainement:

Si vous devez le faire, vous avez un problème avec vos données. Triez vos données!

v.oddou
la source