c++ - suma - Usar un iterador para dividir una matriz en partes con un tamaño desigual

orden de una matriz

Question

Tengo una matriz que necesito dividir en sub-arrays de 3 elementos. Quería hacer esto con iteradores, pero termino iterando más allá del final de la matriz y segfaulting aunque no desreferencia el iterador . dado: auto foo = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; Estoy haciendo:

auto bar = cbegin(foo);

for (auto it = next(bar, 3); it < foo.end(); bar = it, it = next(bar, 3)) {
    for_each(bar, it, [](const auto& i) { cout << i << endl; });
}

for_each(bar, cend(foo), [](const auto& i) { cout << i << endl; });

Ahora puedo resolver esto definiendo un iterador de finish :

auto bar = cbegin(foo);
auto finish = next(cend(foo), -(size(foo) % 3));

for (auto it = next(bar, 3); it != finish; bar = it, it = next(bar, 3)) {
    for_each(bar, it, [](const auto& i) { cout << i << endl; });
}

for_each(bar, finish, [](const auto& i) { cout << i << endl; });
for_each(finish, cend(foo), [](const auto& i) { cout << i << endl; });

Pero esto parece innecesario cuando no desreferencia el iterador . ¿Por qué no puedo hacer la primera versión?

Answer 1

El fallo de segmentación que está viendo proviene de la next comprobación del rango para usted, es una afirmación en su implementación de depuración para comprobar contra el comportamiento indefinido. El comportamiento de los iteradores y punteros no se define más allá del rango asignado, y del elemento "uno pasado": ¿los iteradores superan el comportamiento indefinido del iterador "uno pasado"?

Esto significa que el incremento más allá del elemento "un extremo pasado" es un comportamiento indefinido independiente del uso posterior del iterador . Para tener un comportamiento definido debes usar una solución como tu algoritmo Integer Modulo o similar, pero tendrás que cambiar auto it = next(bar, 3) a algo que se condicionaliza según la disponibilidad de al menos el tamaño de tu sub -array, algo así como: auto it = size(foo) <= 3 ? finish : next(bar, 3) auto it = size(foo) <= 3 ? finish : next(bar, 3) .

Donde esté disponible, la mejor solución que aquí va a causar la iteración menos redundante es rastrear el tamaño restante en el contenedor como un entero que no sufre un comportamiento indefinido cuando cae fuera del rango y "uno más allá del final". Esto se puede lograr mediante:

auto bar = cbegin(foo);

for (auto i = size(foo); i > STEP; i -= STEP) {
    for(auto j = 0; j < STEP; ++j, ++bar) cout << *bar << ''/t'';
    cout << endl;
}

for(auto i = 0; j < STEP; ++j, ++bar) cout << *bar << ''/t'';
cout << endl;

EDITAR: anteriormente había sugerido usar punteros que no están condicionados por Debug, este es un comportamiento indefinido.

El problema es que el next es verificar el rango para ti. Usamos punteros fuera de la memoria asignada todo el tiempo, por ejemplo, nullptr y end , y eso es todo it aquí. Si solo usas la aritmética del puntero C-estilo aquí, estarás bien:

auto bar = cbegin(foo);

for (auto it = bar + 3; it < cend(foo); bar = it, it = bar + 3) {
    for_each(bar, it, [](const auto& i) { cout << i << endl; });
}

for_each(bar, cend(foo), [](const auto& i) { cout << ''/t'' << i << endl; });

Ejemplo en vivo

Alternativamente, si ejecuta la configuración de Release, se deben eliminar las verificaciones de rango, por lo que podrá usar la primera versión de su código.

Answer 2

Existe algún desacuerdo sobre la forma más efectiva de lograr esta iteración a través de particiones de matriz.

Primero, el método del módulo entero de una vez, debe definir el auto size además de los cambios en mi respuesta porque gcc aún no admite el size :

auto foo = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };  
auto size = distance(cbegin(foo), cend(foo));
auto bar = cbegin(foo);
auto finish = prev(cend(foo), size % 3);

for(auto it = size <= 3 ? cend(foo) : next(bar, 3); it != finish; bar = it, it = next(bar, 3)) {
    for_each(bar, it, [](const auto& i) { cout << i << ''/t''; });
    cout << endl;
}

for_each(bar, finish, [](const auto& i) { cout << i << ''/t''; });
cout << endl;
for_each(finish, cend(foo), [](const auto& i) { cout << i << ''/t''; });
cout << endl;

Esto crea 112 líneas de ensamblaje , más notablemente el condicional it != finish genera estas instrucciones:

cmpq    %r12, %r13
je      .L19
movq    %r12, %rbx
jmp     .L10

Segundo, la resta try_advance repetida utilizando try_advance Ben Voigt, pero solo con la especialización de acceso aleatorio porque hay un conflicto de compilación para los iteradores de acceso aleatorio:

auto foo = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };  
auto bar = cbegin(foo);

for (auto it = cbegin(foo), end = cend(foo); try_advance(it, 3, end); bar = it) {
    for_each(bar, it, [](const auto& i) { cout << i << ''/t''; });
    cout << endl;
}

for_each(bar, cend(foo), [](const auto& i) { cout << i << ''/t''; });
cout << endl;

Esto crea 119 líneas de ensamblaje , especialmente el condicional en try_advance : if (end - it < stride) return false; incurre en una iteración por generación del código:

movq    %r12, %rax
subq    %rbp, %rax
cmpq    $11, %rax
ja      .L3

Al cmpq que cmpq es solo una operación de resta y comparación, he escrito un código de marcación: http://coliru.stacked-crooked.com/a/ad869f69c8dbd96f Necesitaba usar Coliru para poder activar la optimización, pero me sigue dando incrementos falsos de mi conteo de pruebas por momentos, no estoy seguro de lo que está pasando allí. Lo que puedo decir es localmente, la resta repetitiva del iterador es siempre más rápida, a veces de manera significativa. Al enterarme de esto, creo que la respuesta de Ben Voigt debe ser marcada como la correcta.

EDITAR:

He hecho un descubrimiento interesante. Es el algoritmo que va primero que siempre pierde. Reescribí el código para cambiar el primer algoritmo en cada pase. Cuando esto se hace, el método de módulo entero siempre supera el método de resta del iterador como se sospecha al mirar el ensamblaje, de nuevo algo sospechoso está sucediendo con Coliru, pero puede tomar este código y ejecutarlo localmente: http: // coliru. stacked-crooked.com/a/eb3e0c70cc138ecf

El siguiente problema es que ambos algoritmos son flojos; en el caso de que el size(foo) sea ​​un múltiplo de 3, asignan un vector vacío al final del vector . Esto requiere una ramificación significativa para el algoritmo de módulo entero para remediar, pero solo los cambios más simples para el algoritmo de resta de repetidor iterativo. Los algoritmos resultantes exhiben efectivamente los mismos números de referencia, pero el borde va a la resta repetida del iterador por simplicidad:

Algoritmo del módulo entero:

auto bar = cbegin(foo);
const auto size = distance(bar, cend(foo));

if (size <= 3) {
    for_each(bar, cend(foo), [](const auto& i) { cout << i << ''/t''; });
    cout << endl;
}
else {
    auto finish = prev(cend(testValues), (size - 1) % 3 + 1);

    for (auto it = next(bar, 3); it != finish; bar = it, advance(it, 3)) {
        for_each(bar, it, [](const auto& i) { cout << i << ''/t''; });
        cout << endl;
    }

    for_each(bar, finish, [](const auto& i) { cout << i << ''/t''; });
    cout << endl;
    for_each(finish, cend(foo), [](const auto& i) { cout << i << ''/t''; });
    cout << endl;
}

Algoritmo de resta de repetidor repetido:

auto bar = cbegin(foo);

for (auto it = cbegin(foo); distance(it, cend(foo)) > 3; bar = it) {
    advance(it, 3);
    for_each(bar, it, [](const auto& i) { cout << i << ''/t''; });
    cout << endl;
}

for_each(bar, cend(foo), [](const auto& i) { cout << i << ''/t''; });
cout << endl;

EDITAR: Lanzar el algoritmo de tamaño restante en el sombrero

Tanto el algoritmo de enteros como los algoritmos de resta repetida anteriores sufren más de una iteración sobre la secuencia de entrada, aparte de ser más lento, esto no es tan grave porque actualmente estamos usando un iterador bidireccional, pero nuestro iterador de entrada no califica para bidireccional Iterador esto sería excesivamente costoso. Independientemente del tipo de iterador, el algoritmo de tamaño restante supera a todos los retadores cada vez en más de 10,000,000 iteraciones de banco de pruebas:

auto bar = cbegin(foo);

for (auto i = size(foo); i > STEP; i -= STEP) {
    for(auto j = 0; j < STEP; ++j, ++bar) cout << *bar << ''/t'';
    cout << endl;
}

for(auto i = 0; j < STEP; ++j, ++bar) cout << *bar << ''/t'';
cout << endl;

Una vez más, he copiado mis pruebas locales en Coliru, lo que da resultados extraños, pero puedes verificarlo localmente: http://coliru.stacked-crooked.com/a/361f238216cdbace

Answer 3

La razón por la que esto está prohibido se cubre bien en su otra pregunta. ¿Los iteradores superan el comportamiento indefinido del iterador de "un extremo"? así que solo abordaré soluciones mejoradas.

Para los iteradores de acceso aleatorio (que debe tener si está usando < ), no hay necesidad alguna para la costosa operación de módulo.

Los puntos sobresalientes son que:

• it + stride falla cuando it acerca el final
• end() - stride falla si el contenedor contiene muy pocos elementos
• end() - it siempre es legal

A partir de ahí, es simple manipulación algebraica para cambiarlo it + stride < end() en una forma legal (restarlo de ambos lados).

El resultado final, que he usado muchas veces:

for( auto it = c.cbegin(), end = c.cend(); end - it >= stride; it += stride )

El compilador puede optimizar esa comparación para compararla con una end - stride * sizeof(*it) si el modelo de memoria es plano: las limitaciones del comportamiento C ++ no se aplican a las operaciones primitivas a las que el compilador convierte C ++.

Por supuesto, puede usar std::distance(it, end) si prefiere usar las funciones nombradas en lugar de operadores, pero eso solo será eficiente para los iteradores de acceso aleatorio.

Para usar con iteradores de reenvío, debe usar algo que combine las condiciones de incremento y terminación como

struct less_preferred { size_t value; less_preferred(size_t v) : value(v){} };

template<typename Iterator>
bool try_advance( Iterator& it, less_preferred step, Iterator end )
{
     while (step.value--) {
         if (it == end) return false;
         ++it;
     }
     return true;
}

Con esta sobrecarga adicional, obtendrá un comportamiento eficiente para los iteradores de acceso aleatorio:

template<typename RandomIterator>
auto try_advance( RandomIterator& it, size_t stride, RandomIterator end )
     -> decltype(end - it < stride) // SFINAE
{
     if (end - it < stride) return false;
     it += stride;
     return true;
}