Como posso evitar loops “for” com uma condição “if” dentro deles com C ++?

111

Com quase todo o código que escrevo, frequentemente estou lidando com problemas de redução de conjuntos em coleções que acabam resultando em condições ingênuas "se" dentro delas. Aqui está um exemplo simples:

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

Com linguagens funcionais, posso resolver o problema reduzindo a coleção para outra coleção (facilmente) e, em seguida, realizar todas as operações em meu conjunto reduzido. Em pseudocódigo:

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

E em outras variantes C, como C #, eu poderia reduzir com uma cláusula where como

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

Ou melhor (pelo menos aos meus olhos)

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

Reconheço que estou fazendo muita mistura de paradigmas e estilo subjetivo / baseado em opinião, mas não posso deixar de sentir que estou perdendo algo realmente fundamental que poderia me permitir usar essa técnica preferida com C ++. Alguém poderia me esclarecer?

Darkenor
fonte
7
Fora da funcionalidade da biblioteca padrão C ++, você pode tentar std::copy_if, mas as seleções não são preguiçosas
milleniumbug
14
Você pode estar interessado em range-v3 . Ele também deve chegar ao C ++ como um TS e, com sorte, padronizado em uma versão futura.
NathanOliver
12
Sinto a necessidade de salientar que o ifinterior de um que forvocê mencionou não é apenas funcionalmente equivalente aos outros exemplos, mas também provavelmente seria mais rápido em muitos casos. Também para alguém que afirma gostar de estilo funcional, o que você está promovendo parece ir contra o querido conceito de pureza da programação funcional, uma vez que DoStuffclaramente tem efeitos colaterais.
Pharap
60
Nunca entendi realmente por que as pessoas associam a combinação de toda a lógica em uma única linha para que pareça melhor ou mais legível. Seu snippet C ++ no topo é de longe o mais legível para mim de todas as suas possibilidades. E uma vez que a eficiência não será alterada, não consigo entender por que você prefere não escrever isso, a menos que esteja sendo pago pelo número de linhas de código que exclui.
Cody Gray
10
@CodyGray Concordo: é apenas açúcar sintático. E o título da pergunta é enganoso, porque é muito diferente, evitando ramificações e escondendo -as sob abstração.
edmz

Respostas:

99

IMHO é mais simples e mais legível usar um loop for com um if dentro dele. No entanto, se isso for irritante para você, você pode usar um for_each_ifcomo este abaixo:

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

Caso de uso:

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

Demonstração ao vivo

101010
fonte
10
Isso é excepcionalmente inteligente. Também concordarei que não é simples e provavelmente usarei apenas as condições if ao programar C ++ que é consumido por outras pessoas. Mas é exatamente disso que preciso para meu uso pessoal! :)
Darkenor
14
@Default Passar pares de iteradores em vez de contêineres é C ++ mais flexível e idiomático.
Mark B
8
@Slava, em intervalos gerais não reduzem o número de algoritmos. Por exemplo, você ainda precisa find_ife findse eles funcionam em faixas ou pares de iteradores. (Existem algumas exceções, como for_eache for_each_n). A maneira de evitar escrever novos algos para cada espirro é usar operações diferentes com os algoritmos existentes, por exemplo, em vez de for_each_ifincorporar a condição ao chamável passado para for_each, por exemplofor_each(first, last, [&](auto& x) { if (cond(x)) f(x); });
Jonathan Wakely
9
Vou ter que concordar com a primeira frase: A solução padrão para-se é muito mais legível e fácil de trabalhar. Acho que a sintaxe lambda e o uso de um modelo definido em outro lugar apenas para lidar com um loop simples irritaria ou possivelmente confundiria outros desenvolvedores. Você está sacrificando localidade e desempenho por ... o quê? Ser capaz de escrever algo em uma linha?
user1354557
45
Cough @Darkenor, geralmente programação " excepcionalmente inteligente" deve ser evitada porque irrita todos os outros, incluindo o seu futuro eu.
Ryan
48

Boost fornece intervalos que podem ser usados ​​com base em intervalo para. Os intervalos têm a vantagem de não copiar a estrutura de dados subjacente, eles apenas fornecem uma 'visualização' (ou seja begin(), end()para o intervalo e operator++(), operator==()para o iterador). Isso pode ser do seu interesse: 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
fonte
1
Posso sugerir usar o exemplo de OPs, ou seja, is_even=> condition, input=> myCollectionetc.
Padrão de
Esta é uma resposta excelente e, definitivamente, o que estou procurando fazer. Vou adiar a aceitação, a menos que alguém venha com uma maneira compatível com o padrão de fazer isso que usa execução preguiçosa / adiada. Votado.
Darkenor
5
@Darkenor: se Boost for um problema para você (por exemplo, você está proibido de usá-lo devido à política da empresa e sabedoria do gerente), posso apresentar uma definição simplificada de filtered()para você - dito isso, é melhor usar uma biblioteca com suporte do que algum código ad-hoc.
Lorro
Concordo totalmente com você. Eu aceitei por causa da maneira compatível com o padrão que veio primeiro, porque a questão era voltada para o próprio C ++, não para a biblioteca boost. Mas isso é realmente excelente. Além disso - sim, infelizmente trabalhei em muitos lugares que baniram o Boost por razões absurdas ...
Darkenor
@LeeClagett:? .
Lorro
44

Em vez de criar um novo algoritmo, como faz a resposta aceita, você pode usar um existente com uma função que aplique a condição:

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

Ou se você realmente deseja um novo algoritmo, pelo menos reutilize for_eachlá em vez de duplicar a lógica de iteração:

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
fonte
Muito melhor e mais claro para usar a biblioteca padrão.
anônimo
4
Porque std::for-each(first, last, [&](auto& x) {if (p(x)) op(x); });é totalmente mais simples do que for (Iter x = first; x != last; x++) if (p(x)) op(x);}?
user253751
2
@immibis reutilizar a biblioteca padrão tem outros benefícios, como verificação de validade do iterador ou (em C ++ 17) ser muito mais fácil de paralelizar, simplesmente adicionando mais um argumento: std::for_each(std::execution::par, first, last, ...);Quão fácil é adicionar essas coisas a um loop escrito à mão?
Jonathan Wakely
1
#pragma omp parallel for
Mark K Cowan
2
@mark, desculpe, alguma peculiaridade aleatória de seu código-fonte ou cadeia de construção fez com que a extensão do compilador paralela não padrão irritantemente frágil gerasse aumento de desempenho zero sem diagnóstico.
Yakk - Adam Nevraumont
21

A ideia de evitar

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

construções como um antipadrão é muito amplo.

É perfeitamente normal processar vários itens que correspondem a uma determinada expressão de dentro de um loop, e o código não pode ficar muito mais claro do que isso. Se o processamento ficar muito grande para caber na tela, esse é um bom motivo para usar uma sub-rotina, mas ainda assim o condicional é melhor colocado dentro do loop, ou seja,

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

é amplamente preferível a

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

Ele se torna um antipadrão quando apenas um elemento corresponderá, porque então seria mais claro pesquisar primeiro o elemento e executar o processamento fora do loop.

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

é um exemplo extremo e óbvio disso. Mais sutil e, portanto, mais comum, é um padrão de fábrica como

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

Isso é difícil de ler, porque não é óbvio que o código do corpo será executado apenas uma vez. Nesse caso, seria melhor separar a pesquisa:

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();

Ainda existe um ifdentro de a for, mas a partir do contexto fica claro o que ele faz, não há necessidade de alterar este código a menos que a pesquisa mude (por exemplo, para a map), e é imediatamente claro que create_object()é chamado apenas uma vez, porque é não dentro de um loop.

Simon Richter
fonte
Eu gosto disso, como uma visão geral ponderada e equilibrada, mesmo que em certo sentido se recuse a responder à pergunta feita. Eu acho que o for( range ){ if( condition ){ action } }estilo torna mais fácil ler as coisas uma por vez e usa apenas o conhecimento das construções básicas da linguagem.
PJTraill
@PJTraill, a forma como a pergunta foi formulada me lembrou do discurso de Raymond Chen contra o antipadrão for-if , que foi cultuado pela carga e de alguma forma se tornou um absoluto. Concordo totalmente que for(...) if(...) { ... }muitas vezes é a melhor escolha (é por isso que qualifiquei a recomendação de dividir a ação em uma sub-rotina).
Simon Richter
1
Obrigado pelo link, que esclareceu as coisas para mim: o nome “ para-se ” é enganoso e deve ser algo como “ para-todos-se-um ” ou “ evasão de pesquisa ”. Isso me lembra a forma como a inversão de abstração foi descrita pela Wikipedia em 2005 como quando alguém “ cria construções simples sobre complexas (unidades)” - até que eu as reescrevi! Na verdade, eu nem me apressaria em consertar a forma de pesquisa-processo-saída de for(…)if(…)…se fosse o único lugar que a pesquisa ocorreu.
PJTraill de
17

Aqui está um rápido relativamente mínimo filter função .

É preciso um predicado. Ele retorna um objeto de função que leva um iterável.

Ele retorna um iterável que pode ser usado em um for(:)loop.

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

Eu peguei atalhos. Uma biblioteca real deve fazer iteradores reais, não ofor(:) pseudo-fascades qualificantes que eu fiz.

No ponto de uso, tem a seguinte aparência:

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

o que é muito bom e imprime

1
3
5

Exemplo vivo .

Há uma proposta de adição ao C ++ chamada Rangesv3 que faz esse tipo de coisa e muito mais. boosttambém tem faixas / iteradores de filtro disponíveis. boost também tem ajudantes que tornam a escrita do texto acima muito mais curta.

Yakk - Adam Nevraumont
fonte
15

Um estilo que é usado o suficiente para ser mencionado, mas não foi mencionado ainda, é:

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

  DoStuff();
}

Vantagens:

  • Não altera o nível de indentação de DoStuff();quando a complexidade da condição aumenta. Logicamente, DoStuff();deve estar no nível superior do forloop, e está.
  • De imediato deixa claro que o loop itera sobre os SOMETHINGs da coleção, sem exigir que o leitor verifique se não há nada após o fechamento }do ifbloco.
  • Não requer bibliotecas ou macros ou funções auxiliares.

Desvantagens:

  • continue, como outras instruções de controle de fluxo, é mal utilizado de maneiras que levam a códigos difíceis de seguir, tanto que algumas pessoas se opõem a qualquer uso deles: há um estilo válido de codificação que alguns seguem que evita continue, que evita breakoutros que não em a switch, que evita returnoutros que não no final de uma função.

fonte
3
Eu diria que em um forloop que se estende por muitas linhas, um "se não, continue" de duas linhas é muito mais claro, lógico e legível. Dizendo imediatamente "pule isto se" depois que a forinstrução for bem lida e, como você disse, não indente os aspectos funcionais restantes do loop. Se o continueestiver mais abaixo, no entanto, alguma clareza será sacrificada (ou seja, se alguma operação sempre será realizada antes da ifinstrução).
anônimo
11
for(auto const &x: myCollection) if(x == something) doStuff();

Parece muito com uma forcompreensão específica de C ++ para mim. Para você?

bipll
fonte
Eu não acho que a palavra-chave auto estava presente antes do c ++ 11, então não diria que é um c ++ muito clássico. Se eu puder fazer uma pergunta aqui no comentário, "auto const" diria ao compilador que ele pode reorganizar todos os elementos como quiser? Talvez seja mais fácil para o compilador planejar evitar ramificações se for esse o caso.
mathreadler
1
@mathreadler Quanto antes as pessoas pararem de se preocupar com o "c ++ clássico", melhor. C ++ 11 foi um evento macroevolucionário para a linguagem e tem 5 anos: deve ser o mínimo que almejamos. De qualquer forma, o OP marcou isso e C ++ 14 (ainda melhor!). Não, auto constnão tem qualquer relação com a ordem de iteração. Se você pesquisar com base em intervalos for, verá que basicamente faz um loop padrão de begin()para end()com desreferenciação implícita. Não há como quebrar as garantias de pedido (se houver) do contêiner sendo iterado; teria sido ridicularizado na face da Terra
sublinhado_d
1
@mathreadler, na verdade era, apenas tinha um significado bem diferente. O que não estava presente é o alcance para ... e qualquer outro recurso distinto do C ++ 11. O que eu quis dizer aqui foi que range-fors, std::futures, std::functions, mesmo aqueles fechamentos anônimos são muito bons em C ++ na sintaxe; cada linguagem tem sua própria linguagem e, ao incorporar novos recursos, tenta fazê-los imitar a antiga e conhecida sintaxe.
bipll
@underscore_d, um compilador tem permissão para realizar quaisquer transformações desde que a regra de as-if seja obedecida, não é?
bipll
1
Hmmm, e o que isso significa?
bipll de
7

Se DoStuff () fosse dependente de i de alguma forma no futuro, eu proporia esta variante garantida de mascaramento de bits sem ramificação.

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();

Onde popcount é qualquer função que faz uma contagem da população (contagem do número de bits = 1). Haverá alguma liberdade para colocar restrições mais avançadas com i e seus vizinhos. Se isso não for necessário, podemos remover o loop interno e refazer o loop externo

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

seguido por um

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

Além disso, se você não se importar em reordenar a coleção, std :: partition é barato.

#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
fonte
Mas std::partitionreordena o contêiner.
celtschk
5

Estou pasmo com a complexidade das soluções acima. Eu ia sugerir um simples, #define foreach(a,b,c,d) for(a; b; c)if(d)mas tem alguns déficits óbvios, por exemplo, você deve se lembrar de usar vírgulas em vez de ponto-e-vírgulas em seu loop, e você não pode usar o operador vírgula em 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
fonte
3
A complexidade de algumas respostas só é alta porque elas mostram primeiro um método genérico reutilizável (que você faria apenas uma vez) e, em seguida, o usam. Não é eficaz se você tiver um loop com uma condição if em todo o aplicativo, mas muito eficaz se acontecer milhares de vezes.
gnasher729
1
Como a maioria das sugestões, isso torna mais difícil, não mais fácil, identificar a faixa e a condição de seleção. E o uso de uma macro aumenta a incerteza sobre quando (e com que frequência) as expressões são avaliadas, mesmo se não houver surpresas aqui.
PJTraill
2

Outra solução caso os i: s sejam importantes. Este constrói uma lista que preenche os índices para os quais chamar doStuff (). Mais uma vez, o ponto principal é evitar a ramificação e trocá-la por custos aritméticos canalizáveis.

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.

A linha "mágica" é a linha de carregamento do buffer que calcula aritmeticamente se deve manter o valor e permanecer na posição ou contar a posição e adicionar valor. Portanto, trocamos um ramo potencial por algumas lógicas e aritméticas e talvez algumas ocorrências de cache. Um cenário típico em que isso seria útil seria se doStuff () fizesse uma pequena quantidade de cálculos pipelináveis ​​e qualquer ramificação entre as chamadas pudesse interromper esses pipelines.

Então, apenas faça um loop no buffer e execute doStuff () até chegarmos a cnt. Desta vez, teremos o i atual armazenado no buffer para que possamos usá-lo na chamada de doStuff () se precisarmos.

mathreadler
fonte
1

Pode-se descrever seu padrão de código como a aplicação de alguma função a um subconjunto de um intervalo, ou em outras palavras: aplicá-lo ao resultado da aplicação de um filtro a todo o intervalo.

Isso é possível da maneira mais direta com a biblioteca de intervalos-v3 de Eric Neibler ; embora seja um pouco desagradável, porque você deseja trabalhar com índices:

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

Mas se você estiver disposto a renunciar aos índices, você obterá:

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

que é melhor IMHO.

PS - A biblioteca de intervalos está indo principalmente para o padrão C ++ em C ++ 20.

einpoklum
fonte
0

Vou apenas mencionar Mike Acton, ele definitivamente diria:

Se você tiver que fazer isso, você terá um problema com seus dados. Classifique seus dados!

v.oddou
fonte