Cómo desenrollar un bucle corto en C++

Question

Me pregunto cómo conseguir algo como esto:

1. Escribir

   copy(a, b, 2, 3) 
   

2. y luego

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

I sepa que C#defines no se puede usar recursivamente para obtener ese efecto. Pero estoy usando C++, entonces supongo que la meta-programación de plantillas podría ser apropiada.

Sé que hay una biblioteca Boost para eso, pero solo quiero ese truco "simple", y Boost es demasiado "desordenado".

Answer 1

La solución más sencilla para esto es escribir un bucle en el que se conocen los valores de inicio y fin:

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

Creo que esto es mejor que cualquier tipo de mezcla de plantilla/tiempo de ejecución de guardia: El bucle, tal como está escrito, es completamente claro para el optimizador de compiladores, y no hay niveles de llamadas a funciones para buscar lo que está sucediendo.

Answer 2

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

template <class InputIterator> 
vector(InputIterator, InputIterator) 

Creates a vector with a copy of a range. 

Answer 3

C++ meta-programación es recursivo.

Piense en su problema en términos de recursividad. Implementar cajas terminales y cajas no terminales.

Su caja de terminal puede ser 0 o una. Pasar límites como parámetros de plantilla. Utilice una estructura/clase porque permiten la especialización parcial y otras cosas interesantes:

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 4

Probablemente pueda hacer algo como lo siguiente. Según el compilador y la configuración de optimización que use, puede obtener el efecto que está buscando.

Tenga en cuenta que para objetos pequeños como char puede ser más lento que std::copy o memcpy y que para objetos más grandes el costo de un bucle es probable que sea insignificante en comparación con las copias en curso en cualquier caso.

#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 5

Es importante darse cuenta de que el compilador es muy inteligente, y que el truco para desenrollar los bucles mediante la metaprogramación de plantillas probablemente lo retrasará aún más para poder avanzar.

Para aprovechar al máximo sus optimizaciones: controle el desmontaje. Es de esperar que le enseñe más que lanzar plantillas al problema.

Y tenga en cuenta, como dijo Johannes: si el compilador puede ver que está ejecutando un ciclo por un número fijo de veces (o un múltiplo de veces fijo como la variable 4x), puede crear un código muy cercano al óptimo.

Answer 6

No utiliza las plantillas y que no es un "completo" desenrollar, pero se puede desenrollar parcialmente el bucle con algo como esto:

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

Ahora, en este ejemplo particular, los cálculos adicionales implicados probablemente lo hará superan los beneficios de solo desenrollar cuatro elementos a la vez. Debería obtener un beneficio creciente de un número creciente de elementos dentro del bucle superior (en toda la función, reemplace 4 con todos los elementos que está copiando dentro de cada iteración desenrollada manualmente).

Answer 7

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 8

La eliminación de bucles utilizando meta-programación se puede utilizar para crear constexpr (no he medido los tiempos). Tengo un ejemplo en el que se puede utilizar para hacer la combinación de funciones (n, k) un 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 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>...> {};