Как с помощью C ++ избежать циклов for с условием «if» внутри них?

111

Почти со всем кодом, который я пишу, я часто сталкиваюсь с проблемами сокращения наборов в коллекциях, которые в конечном итоге заканчиваются наивными условиями «если» внутри них. Вот простой пример:

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

С функциональными языками я могу решить проблему, уменьшив коллекцию до другой коллекции (легко), а затем выполнить все операции с моим сокращенным набором. В псевдокоде:

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

И в других вариантах C, таких как C #, я мог бы сократить с помощью предложения where, например

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

Или лучше (по крайней мере, на мой взгляд)

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

По общему признанию, я много смешиваю парадигмы и стиль, основанный на субъективном мнении, но я не могу не чувствовать, что мне не хватает чего-то действительно фундаментального, что позволило бы мне использовать этот предпочтительный метод с C ++. Может ли кто-нибудь просветить меня?

Даркенор
источник
7
Из стандартной библиотеки C ++ вы можете попробовать std::copy_if, но выбор не ленив
milleniumbug
14
Возможно, вас заинтересует range-v3 . Он также должен появиться на C ++ как TS и, надеюсь, стандартизирован в будущем выпуске.
NathanOliver
12
Я считаю необходимым указать, что ifвнутренняя часть, которую forвы упомянули, не только в значительной степени функционально эквивалентна другим примерам, но также, вероятно, во многих случаях будет быстрее. Также для тех, кто утверждает, что любит функциональный стиль, то, что вы продвигаете, кажется, идет вразрез с очень любимой концепцией чистоты функционального программирования, поскольку DoStuffявно имеет побочные эффекты.
Pharap
60
Я никогда толком не понимал, почему люди связывают, объединяя всю логику в одну строку, что делает ее как-то лучше или более читаемой. Ваш фрагмент C ++ на самом верху , безусловно, является для меня наиболее читаемым из всех ваших возможностей. А поскольку эффективность не изменится, я не могу понять, почему вы предпочли бы не писать об этом, если только вам не платят за количество строк кода, которые вы удаляете.
Коди Грей
10
@CodyGray Согласен: это просто синтаксический сахар. И заголовок вопроса вводит в заблуждение, потому что он совсем другой, избегая ветвления и скрывая его под абстракцией.
edmz

Ответы:

99

ИМХО более прямолинейно и читабельно использовать цикл for с if внутри него. Однако, если вас это раздражает, вы можете использовать такой, for_each_ifкак показано ниже:

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

Вариант использования:

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

Живая демонстрация

101010
источник
10
Это исключительно умно. Я также согласен с тем, что это непросто, и я, вероятно, просто буду использовать условия if при программировании C ++, которые используются другими. Но это именно то, что мне нужно для личного пользования! :)
Darkenor
14
@Default Передача пар итераторов, а не контейнеров, является более гибким и идиоматическим способом C ++.
Mark B
8
@Slava, вообще диапазоны не уменьшат количество алгоритмов. Например, вам все еще нужно , find_ifи findработают ли они на полигонах или пары итераторов. (Есть несколько исключений, например, for_eachи for_each_n). Способ избежать написания новых алгоритмов для каждого чиха - использовать разные операции с существующими алгоритмами, например, вместо того, чтобы for_each_ifвстраивать условие в вызываемый объект, переданный for_each, например,for_each(first, last, [&](auto& x) { if (cond(x)) f(x); });
Джонатан Уэйкли
9
Придется согласиться с первым предложением: стандартное решение for-if гораздо более читабельно и с ним легче работать. Я думаю, что лямбда-синтаксис и использование шаблона, определенного где-то еще, только для обработки простого цикла, раздражают или, возможно, сбивают с толку других разработчиков. Вы жертвуете местностью и производительностью ради ... чего? Возможность написать что-то одной строкой?
user1354557
45
Кашель @Darkenor, как правило , « исключительно умное» программирование следует избегать , потому что это раздражает дерьмо из всех остальных , включая ваше будущее себя.
Райан
48

Boost предоставляет диапазоны, которые можно использовать для. Диапазоны имеют то преимущество , что они не копируют , лежащие в основе структуры данных, они просто обеспечивают «вид» (то есть begin(), end()для диапазона и operator++(), operator==()для итератора). Это может вас заинтересовать: 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
источник
1
Могу я предложить вместо этого использовать пример OP, т.е. is_even=> condition, input=> myCollectionи т. Д.
По умолчанию
Это отличный ответ, и я определенно хочу это сделать. Я собираюсь воздержаться от принятия, если кто-то не сможет предложить стандартный способ сделать это, использующий ленивое / отложенное выполнение. Upvoted.
Darkenor
5
@ Darkenor: Если Boost - проблема для вас (например, вам запрещено использовать его из-за политики компании и мудрости менеджера), я могу предложить вам упрощенное определение filtered()для вас - при этом лучше использовать поддерживаемая библиотека, чем какой-то специальный код.
lorro
Полностью с вами согласен. Я согласился с этим, потому что сначала появился стандартный способ, потому что вопрос касался самого C ++, а не библиотеки boost. Но это действительно отлично. Также - да, я, к сожалению, работал во многих местах, которые запрещали Boost по абсурдным причинам ...
Darkenor
@LeeClagett:? .
lorro
44

Вместо создания нового алгоритма, как это делает принятый ответ, вы можете использовать существующий с функцией, которая применяет условие:

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

Или, если вам действительно нужен новый алгоритм, по крайней мере, используйте его повторно for_eachвместо дублирования логики итерации:

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); });
  }
Джонатан Уэйкли
источник
Намного лучше и понятнее использовать стандартную библиотеку.
анонимный
4
Потому что std::for-each(first, last, [&](auto& x) {if (p(x)) op(x); });все проще, чем for (Iter x = first; x != last; x++) if (p(x)) op(x);}?
user253751
2
@immibis повторное использование стандартной библиотеки имеет и другие преимущества, такие как проверка допустимости итератора или (в C ++ 17) его намного проще распараллелить, просто добавив еще один аргумент: std::for_each(std::execution::par, first, last, ...);насколько легко добавить эти вещи в рукописный цикл?
Джонатан Уэйкли
1
#pragma omp parallel for
Mark K Cowan
2
@mark извините, из-за какой-то случайной причуды вашего исходного кода или цепочки сборки это раздражающе хрупкое параллельное нестандартное расширение компилятора генерирует нулевой прирост производительности без диагностики.
Yakk - Adam Nevraumont
21

Идея избежать

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

конструкции как антипаттерн слишком широки.

Совершенно нормально обрабатывать несколько элементов, которые соответствуют определенному выражению изнутри цикла, и код не может быть намного яснее этого. Если обработка становится слишком большой и не помещается на экране, это хороший повод для использования подпрограммы, но все же условное выражение лучше всего помещать внутри цикла, т. Е.

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

намного предпочтительнее

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

Он становится антипаттерном, когда будет соответствовать только один элемент, потому что тогда будет проще сначала найти элемент и выполнить обработку вне цикла.

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

является крайним и очевидным примером этого. Более тонким и, следовательно, более распространенным является заводской шаблон, например

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

Это трудно прочитать, потому что не очевидно, что основной код будет выполнен только один раз. В этом случае лучше разделить поиск:

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

ifВнутри a все еще есть for, но из контекста становится ясно, что он делает, нет необходимости изменять этот код, если только поиск не изменится (например, на a map), и сразу становится ясно, что create_object()вызывается только один раз, потому что это не внутри петли.

Саймон Рихтер
источник
Мне нравится этот вдумчивый и сбалансированный обзор, даже если он в каком-то смысле отказывается отвечать на поставленный вопрос. Я считаю, что for( range ){ if( condition ){ action } }-стиль позволяет легко читать вещи по частям за раз и использует только знания основных языковых конструкций.
PJTraill
@PJTraill, формулировка вопроса напомнила мне напыщенную речь Рэймонда Чена против антипаттерна «если бы» , который был культивирован и каким-то образом стал абсолютом. Я полностью согласен, что for(...) if(...) { ... }часто это лучший выбор (поэтому я уточнил рекомендацию разбить действие на подпрограмму).
Саймон Рихтер
1
Спасибо за ссылку, которая прояснила мне ситуацию: название « for-if » вводит в заблуждение и должно быть чем-то вроде « for-all-if-one » или « lookup-избегание ». Это напоминает мне способ, которым инверсия абстракций была описана в Википедии в 2005 году, когда « создают простые конструкции поверх сложных (уже существующих)» - пока я не переписал это! На самом деле, я бы даже не стал спешить с исправлением формы поиска-процесса-выхода, for(…)if(…)…если бы это был единственный поиск места.
PJTraill
17

Вот небольшая относительно минимальная filterфункция.

Требуется предикат. Он возвращает объект функции, который принимает итерацию.

Он возвращает итерацию, которую можно использовать в for(:)цикле.

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

Я пошел короткими путями. Настоящая библиотека должна создавать настоящие итераторы, а не for(:)те псевдофасады, которые я делал.

На момент использования это выглядит так:

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

что довольно приятно, и печатает

1
3
5

Живой пример .

Существует предлагаемое дополнение к C ++ под названием Rangesv3, которое делает такие вещи и многое другое. boostтакже доступны диапазоны фильтров / итераторы. У boost также есть помощники, которые делают написание вышеупомянутого намного короче.

Якк - Адам Неврамонт
источник
15

Один стиль, который используется достаточно, чтобы упомянуть, но еще не упоминался, это:

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

  DoStuff();
}

Преимущества:

  • Не меняет уровень отступа DoStuff();при увеличении сложности условия. По логике, он DoStuff();должен быть на верхнем уровне forцикла, и это так.
  • Сразу становится ясно , что цикл перебирает SOMETHINGс коллекцией, не требуя от читателя , чтобы убедиться , что нет ничего после закрытия }этого ifблока.
  • Не требует никаких библиотек, вспомогательных макросов или функций.

Недостатки:

  • continue, как и другие операторы управления потоком, неправильно используется таким образом, что приводит к настолько сложному для понимания коду, что некоторые люди выступают против их любого использования: существует допустимый стиль кодирования, которому некоторые следуют, который избегает continue, который избегает, breakкроме в switch, что позволяет избежать, returnкроме как в конце функции.

источник
3
Я бы сказал, что в forцикле, состоящем из многих строк, двухстрочное «если нет, продолжить» намного яснее, логичнее и читабельнее. Сразу же скажите «пропустите это, если» после того, как forоператор будет хорошо читаться и, как вы сказали, не отступает от остальных функциональных аспектов цикла. Однако, если значение continueнаходится ниже, некоторая ясность принесена в жертву (т.е. если какая-то операция всегда будет выполняться перед ifоператором).
анонимный
11
for(auto const &x: myCollection) if(x == something) doStuff();

forДля меня это очень похоже на понимание C ++ . Тебе?

двуполый
источник
Я не думаю, что ключевое слово auto присутствовало до C ++ 11, поэтому я бы не сказал, что это очень классический C ++. Если я могу задать вопрос здесь, в комментарии, скажет ли "auto const" компилятору, что он может переставлять все элементы по своему усмотрению? Возможно, компилятору будет проще спланировать избежание ветвления, если это так.
mathreadler
1
@mathreadler Чем раньше люди перестанут беспокоиться о "классическом C ++", тем лучше. C ++ 11 был макроэволюционным событием для языка и ему 5 лет: это должен быть минимум, к которому мы стремимся. Во всяком случае, OP пометил это и C ++ 14 (даже лучше!). Нет, не auto constимеет никакого отношения к порядку итераций. Если вы посмотрите на ранжированный for, вы увидите, что он в основном выполняет стандартный цикл от begin()до end()с неявным разыменованием. Невозможно нарушить гарантии упорядочивания (если таковые имеются) контейнера, по которому выполняется итерация; над этим бы посмеялись с лица Земли
underscore_d
1
@mathreadler, на самом деле это было так, просто оно имело совсем другое значение. То, что не было, - это диапазон для ... и любая другая особенность C ++ 11. Я имел в виду, что range-for, std::futures, std::functions, даже эти анонимные замыкания очень хорошо сочетаются с синтаксисом C ++; у каждого языка есть свой собственный язык, и при включении новых функций он пытается заставить их имитировать старый хорошо известный синтаксис.
bipll
@underscore_d, компилятор может выполнять любые преобразования при соблюдении правила as-if, не так ли?
bipll
1
Хммм, а что под этим может подразумеваться?
bipll
7

Если DoStuff () будет как-то зависеть от i в будущем, я бы предложил этот гарантированный вариант битовой маскировки без ветвлений.

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

Где popcount - это любая функция, выполняющая подсчет населения (количество бит = 1). Будет некоторая свобода устанавливать более сложные ограничения с i и их соседями. Если в этом нет необходимости, мы можем разделить внутренний цикл и переделать внешний цикл.

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

за которым следует

for(int i=0;i<times;i++)
   DoStuff();
математик
источник
6

Кроме того, если вам не нужно переупорядочивать коллекцию, std :: partition стоит недорого.

#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
}
Лорето
источник
Но std::partitionпереупорядочивает контейнер.
celtschk
5

Я в восторге от сложности вышеуказанных решений. Я собирался предложить простой, #define foreach(a,b,c,d) for(a; b; c)if(d)но у него есть несколько очевидных недостатков, например, вы должны помнить, что в вашем цикле нужно использовать запятые вместо точки с запятой, и вы не можете использовать оператор запятой в aили 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;
}
Ян Парберри
источник
3
Сложность некоторых ответов высока только потому, что они сначала показывают универсальный метод многократного использования (который вы бы сделали только один раз), а затем использовали его. Неэффективно, если у вас есть один цикл с условием if во всем приложении, но очень эффективно, если это происходит тысячу раз.
gnasher729
1
Как и в большинстве предложений, это усложняет, а не упрощает определение диапазона и условия выбора. А использование макроса увеличивает неопределенность в отношении того, когда (и как часто) выражения оцениваются, даже если здесь нет никаких сюрпризов.
PJTraill
2

Другое решение в случае, если i: s важны. Он формирует список, который заполняет индексы, для которых вызывается doStuff (). Опять же, главное - избежать разветвления и обменять его на конвейерные арифметические затраты.

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.

«Магическая» линия - это линия загрузки буфера, которая арифметически вычисляет, нужно ли сохранять значение и оставаться в позиции или подсчитывать позицию и добавлять значение. Поэтому мы меняем потенциальную ветвь на некоторую логику и арифметику и, возможно, на некоторые попадания в кеш. Типичный сценарий, когда это было бы полезно, - если doStuff () выполняет небольшой объем конвейерных вычислений, и любая ветвь между вызовами может прервать эти конвейеры.

Затем просто переберите буфер и запускайте doStuff (), пока не дойдете до cnt. На этот раз у нас будет текущий i, сохраненный в буфере, поэтому мы можем использовать его в вызове doStuff (), если нам понадобится.

математик
источник
1

Можно описать ваш шаблон кода как применение некоторой функции к подмножеству диапазона, или, другими словами: применение его к результату применения фильтра ко всему диапазону.

Этого можно достичь самым простым способом с помощью библиотеки Эрика Нейблера range -v3 ; хотя это немного раздражает, потому что вы хотите работать с индексами:

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

Но если вы готовы отказаться от индексов, вы получите:

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

что приятнее ИМХО.

PS - Библиотека диапазонов в основном входит в стандарт C ++ в C ++ 20.

einpoklum
источник
0

Упомяну только Майка Эктона, он обязательно скажет:

Если вам нужно это сделать, у вас проблемы с вашими данными. Сортируйте свои данные!

v.oddou
источник