Замена многомерного цикла for на основанный на диапазоне цикл for

У меня есть класс Vec3.
Каков наилучший способ заменить цикл, как

for (int x = 20; x < 25; x++)
for (int y = 40; y < 45; y++)
for (int z = 2; z < 4; z++) doStuff({x,y,z});

с чем-то вроде этого:

for(Vec3 v: Vec3range({20,40,2}, {25,45,4}))
doStuff(v);

без каких-либо затрат времени выполнения?

6

Решение

Это самая простая реализация, которой я мог бы управлять:

#include <iostream>
#include <tuple>

using namespace std;

using tuple_3d = tuple<int, int, int>;

struct range_3d;

struct range_3d_iterator
{
const range_3d& c;
tuple_3d i;

bool operator!=(const range_3d_iterator& other)
{ return get<0>(i) != get<0>(other.i) && get<1>(i) != get<1>(other.i) && get<2>(i) != get<2>(other.i); }

tuple_3d operator*() const
{ return make_tuple(get<0>(i), get<1>(i), get<2>(i)); }

const range_3d_iterator& operator++();
};

struct range_3d
{
tuple_3d s;
tuple_3d e;

range_3d_iterator begin() const
{ return { *this, s }; }

range_3d_iterator end() const
{ return { *this, e }; }
};

const range_3d_iterator& range_3d_iterator::operator++()
{
++get<2>(i);
if (get<2>(i) == get<2>(c.e))
{
get<2>(i) = get<2>(c.s);
++get<1>(i);
if (get<1>(i) == get<1>(c.e))
{
get<1>(i) = get<1>(c.s);
++get<0>(i);
}
}
return *this;
}

int main(void)
{
for (auto&& v : range_3d{ make_tuple(20, 40, 2), make_tuple(25, 45, 4) })
cout << get<0>(v) << ' ' << get<1>(v) << ' ' << get<2>(v) << endl;
}

Присвоение имен немного дерьмо, но, кроме этого, концепция проста. range_3d простой класс, который поддерживает begin(), end() чтобы получить диапазон для работы цикла, то «умность» находится в range_3d_iterator который будет повторять кортеж. Учитывая способ, которым я использовал здесь кортеж, тривиально распространиться на произвольные измерения …

TBH, оригинал цикла довольно ясен … ИМО!

1

Другие решения

Для этого я написал итерация и объединение адаптер в моем функциональная библиотека сноска:

#include <fn.h>
#include <iostream>

int main() {
using std; using fn;

for (auto &&values : combine(seq(20,25), seq(40,45), seq(2,4))) {
int x, y, z;
tie(x, y, z) = values;
cout << x << ", " << y << ", " << z << "\n";
// or in your case: doStuff({x, y, z});
}
}

Выход:

20, 40, 2
20, 40, 3
20, 41, 2
20, 41, 3
...
24, 43, 2
24, 43, 3
24, 44, 2
24, 44, 3

Вот, seq(a, b) возвращает неявный диапазон, который перебирает значения [a, b) (т.е. первый включительно, второй эксклюзив). (Третий параметр может указывать шаг, и существуют более сложные альтернативы для большего контроля над итерацией.)

Функция combine(ranges...) возвращает неявный диапазон, который перебирает все комбинации из заданных диапазонов (где первый считается «наиболее значимым», похожим на ваш «самый внешний» цикл). Его итератор разыменовывает к std::tuple удерживая текущую комбинацию.

Этот кортеж затем связывается в теле цикла с некоторыми переменными. (К сожалению, не существует «автоматической привязки» для цикла, основанного на диапазоне, как for(tie(auto x, auto y, auto z) : ...).)


Реализация:

seq()

Это довольно просто: это функция, возвращающая объект адаптера, который имеет begin() а также end() функции. Они возвращают пользовательский итератор, который увеличивает текущее значение в operator++ и возвращает его в operator*,

combine()

Это более интересно: он возвращает объект адаптера, который содержит диапазоны, предоставляемые в качестве аргументов combine в кортеже Итератор этого адаптера содержит итераторы для обернутых диапазонов в элементе кортежа, но три раза: текущую позицию, начало и конец, вы скоро поймете, почему.

operator++ из итератора, скорее всего, наиболее интересный: он реализован рекурсивно с использованием шаблонов variadic_ops.h, va_next_combination() и это дается триплетам итераторов (для каждого диапазона текущий, начало и конец):

// base case
inline bool va_next_combination() {
return true;
}

// recursive case
template<typename Head, typename ...Tail>
inline bool va_next_combination(std::tuple<Head&,Head&,Head&> && curr_and_begin_and_end, std::tuple<Tail&,Tail&,Tail&> &&...t) {
// advance the "tail" to its next combination and check if it had an overflow
if (va_next_combination(std::forward<std::tuple<Tail&,Tail&,Tail&>>(t)...)) {
// advance the "head" iterator
++std::get<0>(curr_and_begin_and_end);
// check if the "head" just overflow
bool at_end = (std::get<0>(curr_and_begin_and_end) == std::get<2>(curr_and_begin_and_end));
// if it did, put it back to the beginning and report the overflow
if (at_end) std::get<0>(curr_and_begin_and_end) = std::get<1>(curr_and_begin_and_end);
return at_end;
} else {
// "tail" didn't overflow, so we do nothing and no overflow should be reported
return false;
}
}

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

Это в основном то, как работают механические счетчики, если вы начинаете с условия «если» на самом глубоком уровне рекурсии.

2

template<size_t N>
using indexes=std::array<size_t,N>;

template<size_t N>
void advance( indexes<N>& in, indexes<N-1> const& limit, size_t amt=1 );

который находит индекс amt дальше, оборачиваясь на пределе.

Затем напишите объект диапазона. Здесь хранятся лимит и два итератора, b и e. begin возвращается b, а также end e,

Итераторы имеют указатель на диапазон, из которого они получены, и массив значений. Oни ++ с помощью next выше. Напишите обычный шаблонный пример итератора.

Ваша функция, вероятно, должна быть:

template<size_t N>
multi_range_t<N> multi_range( indexes<N> start, indexes<N> finish );

который требует от вас пройти N,

Наконец, напишите копию ctor для Vec3 от std::array<3,T>,

Вы, вероятно, можете сделать это легче, сделав его 3 вместо N, но только на ощупь.

1
По вопросам рекламы ammmcru@yandex.ru
Adblock
detector