Как развернуть короткий цикл в C ++

Question

Интересно, как получить что-то вроде этого:

1. запись

   copy(a, b, 2, 3)
   

2. А потом получите

   a[2] = b[2];
   a[3] = b[3];
   a[4] = b[4];
   

Я знаю, что C #defines нельзя использовать рекурсивно для получения этого эффекта. Но я использую C ++, поэтому я полагаю, что метапрограммирование шаблонов может быть уместным.

Я знаю, что для этого есть библиотека Boost , но мне нужен только этот "простой" трюк, а Boost слишком "грязный".

Answer 1

Самое простое решение - написать цикл, в котором известны начальное и конечное значения:

for(int i = 2; i <= 4; i++) {
  a[i]=b[i]; 
}

Я думаю, что это лучше, чем любой вид смеси шаблонов / вызовов времени выполнения: записанный цикл полностью понятен оптимизатору компилятора, и нет никаких уровней вызовов функций для просмотра, чтобы просто посмотреть, что происходит.

Answer 2

C ++ мета-программирование рекурсивно.

Думайте о своей проблеме с точки зрения рекурсии.Реализовать корпус терминала и нетерминал.

Ваш терминал может быть либо 0, либо один.Пропустить пределы в качестве параметров шаблона.Используйте структуру / класс, потому что они допускают частичную специализацию и другие полезные вещи:

template<int from, int to>
struct copy {
    static void apply(source, destination) {
        source[from] = destination[from];
        copy<from+1,to>:: apply(source, destination);
    }
};

// Terminal case
template<int from>
struct copy<from, from> {
    static void apply(source, destination) {
        source[from] = destination[from];
    }
};

Answer 3

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

Имейте в виду, что для небольших объектов, таких как символ, он может быть медленнее, чем std::copy или memcpy, и что для более крупных объектов стоимость цикла, вероятно, будет незначительной по сравнению с копиями, происходящими в любом случае. .

#include <cstddef>

template<std::size_t base, std::size_t count, class T, class U>
struct copy_helper
{
    static void copy(T dst, U src)
    {
        dst[base] = src[base];
        copy_helper<base + 1, count - 1, T, U>::copy(dst, src);
    }
};

template<std::size_t base, class T, class U>
struct copy_helper<base, 0, T, U>
{
    static void copy(T, U)
    {
    }
};

template<std::size_t base, std::size_t count, class T, class U>
void copy(T dst, U src)
{
    copy_helper<base, count, T, U>::copy(dst, src);
}

template void copy<5, 9, char*, const char*>(char*, const char*);

#include <iostream>
#include <ostream>

int main()
{
    const char test2[] = "     , World\n";
    char test[14] = "Hello";

    copy<5, 9>(test, test2);

    std::cout << test;

    return 0;
}

Answer 4

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

Чтобы извлечь выгоду из ваших оптимизаций: следите за разборкой. Мы надеемся, что это научит вас не только бросать шаблоны в проблему.

И обратите внимание, как сказал Йоханнес: если компилятор может видеть, что вы запускаете цикл фиксированное число раз (или фиксированное число раз, подобное переменной 4x), он может создать код, очень близкий к оптимальному.

Answer 5

Развертывание цикла с помощью метапрограммирования может быть использовано для создания constexpr (я не измерял время). У меня есть пример, где его можно использовать, чтобы сделать комбинацию функций (n, k) cosntexpr:

template <size_t N> struct iterate_forward {
    template <class operation> static auto eval(const operation & op)
    {
        iterate_forward<N-1>::eval(op);
        return op(N-1);
    }
};
template <> struct iterate_forward<1>
{
    template <class operation> static auto eval(const operation & op)
    { return op(0); }
};
template <> struct iterate_forward<0>
{
    template <class operation> static auto eval(const operation & op) {}
};
template <size_t N, size_t K> constexpr size_t COMB()
{
    struct ratio
    {
        size_t operator () (size_t i) const { return (res *= (N-i) / (i+1)); }
        mutable size_t res = 1;
    };
    return iterate_forward<K>::eval(ratio());
} 

Answer 6

template <int begin, int end> struct copy_;

template <int end> struct copy_<end, end> {
  template <typename T> static void execute(T& a, T& b)
  {
    a[end] = b[end];
  }
};

template <int begin, int end> struct copy_<begin, end> {
  template <typename T> static void execute(T& a, T& b)
  {
    a[begin] = b[begin];
    copy_<begin+1, end>::execute(a, b);
  }
};

template <int begin, int how_many> struct copy {
  template <typename T> static void execute(T& a, T& b)
  {
    copy_<begin, begin+how_many-1>::execute(a, b);
  }
};

copy<2, 3>::execute(a, b);

Answer 7

Он не использует шаблоны и это не «полная» развертка, но вы можете частично развернуть цикл с помощью чего-то вроде этого:

void copy (SomeType* a, SomeType* b, int start_index, int num_items) {
    int i = start_index;

    while (num_items > 4) {
            a[i+0] = b[i+0];
            a[i+1] = b[i+1];
            a[i+2] = b[i+2];
            a[i+3] = b[i+3];
            i += 4;
            num_items -= 4;
    }
    while (num_items > 0) {
            a[i] = b[i];
            ++i;
            --num_items;
    }
}

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

Answer 8

С http://www.sgi.com/tech/stl/Vector.html:

template <class InputIterator>
vector(InputIterator, InputIterator)

Creates a vector with a copy of a range. 

Answer 9

#define tl template
#define tn typename
#define st struct
#define cl class
#define us using


    template<tn A> st Typ { using type = A; };
    tl<tn T> using GetT = tn T::type;
    tl<tn F, tn ...As> us apply = tn F::tl apply<As...>;
    tl<tn, tn, tn ...> st LoopElements;
    tl<tn, tn> st Loop;
    tl<tn, tn, tn> st VLoop_i;
    tl<tn Sq, tn MF> us VLoop = VLoop_i<GetT<Sq>, Sq, MF>;

    //
    // TY
    //
    template<tn T> struct Ty {
        template<T ...> struct Pack : Typ<T> {};
        tl<tn ...> st Concat_i; tl<tn ...P> us Concat = GetT<Concat_i<P...>>;
        tl<T, int64_t> st Seq_i; tl<T f, T t> us Seq = GetT<Seq_i<f, ((int64_t)(t - f))>>; tl<int64_t, tn> st add;

        template<tl<T ...> tn C, T ...vs, tl<T ...> tn D, T ...ws, tn ...R> st Concat_i<C<vs...>, D<ws...>, R...> : Typ<Concat<C<vs..., ws...>, R...> >{};
        template<tl<T ...> tn C, T ...vs> st Concat_i<C<vs...>> : Typ<C<vs...> >{};

        template<int64_t x, T ...vs> struct add<x, Pack<vs...>> : Typ<Pack<((T)(vs + x))...>> {};
        template<T f, int64_t c> class Seq_i {
            using A = tn Seq_i<f, c/2>::type;
            using B = tn add<c/2, A>::type;
            using C = tn Seq_i<f + c / 2 * 2, c & 1>::type;
        public:
            using type = Concat<A, B, C>;
        };
        tl<T f> st Seq_i<f, 0> : Typ<Pack<>> {};        
        tl<T f> st Seq_i<f, 1> : Typ<Pack<f>> {};
        tl<T f> st Seq_i<f, -1> : Typ<Pack<f>> {};
    };

    //
    // LOOP
    template<size_t i, tn F, tn T> struct LoopElement { LoopElement() { apply<F, T>(); }; };
    template<size_t ...is, tn F, tn ...P> struct LoopElements<Ty<size_t>::Pack<is...>, F, P...> : LoopElement<is, F, P>... {};
    template<tn F, tl<tn ...> cl C, tn ...P> struct Loop<F, C<P...>> : LoopElements<Ty<size_t>::Seq<0, sizeof...(P)>, F, P...> {};

    template<tn T, tl<T ...> cl ST, T ...vs, tn MF> struct VLoop_i<T, ST<vs...>, MF> : LoopElements<Ty<size_t>::Seq<0, sizeof...(vs)>, MF, Val<T, vs>...> {};