programar - Se explicó la implementación de C++<algorithm>

ejemplos de programas en c++ pdf

Question

Cuando me gustaría saber cómo se podría implementar un algoritmo en la Biblioteca estándar de C ++, siempre miro http://en.cppreference.com/w/cpp/algorithm , que es una gran fuente. Pero a veces no entiendo algunos detalles de implementación y necesitaría alguna explicación sobre por qué algo se hace de esa manera en particular. Por ejemplo, en la implementación de std::copy_n , ¿por qué la primera asignación se realiza fuera del bucle y, por lo tanto, el bucle comienza con 1 ?

template< class InputIt, class Size, class OutputIt>
OutputIt copy_n(InputIt first, Size count, OutputIt result)
{
    if (count > 0) {
        *result++ = *first;
        for (Size i = 1; i < count; ++i) {
            *result++ = *++first;
        }
    }
    return result;
}

Además: ¿Conoce un sitio donde se explican las posibles implementaciones de algoritmos?

Answer 1

Compáralo con la implementación ingenua:

template< class InputIt, class Size, class OutputIt>
OutputIt copy_n(InputIt first, Size count, OutputIt result)
{
  for (Size i = 0; i < count; ++i) {
    *result++ = *first++;
  }
  return result;
}

¡Esta versión hace un incremento más de first !

1. count==0 , ambos hacen 0 incrementos de first .

2. count==1 , su versión hace cero incrementos de first . La versión anterior hace 1.

3. count==2 , su versión hace un incremento de first . La versión anterior hace 2.

Una posibilidad es manejar iteradores que son anulables, pero no incrementables. Al menos en los días de STL, había una distinción. No estoy seguro si los iteradores de entrada tienen esta propiedad hoy.

Here hay un error que parece ocurrir si usa la implementación ingenua, y Here hay alguna documentación que afirma: "La operación de lectura real se realiza cuando el iterador se incrementa, no cuando se elimina la referencia".

Todavía no he rastreado el capítulo y el verso de la existencia de iteradores de entrada no incrementables e imposibles de eliminar. Aparentemente, el estándar detalla cuántas veces copy_n desreferencia los iteradores de entrada / salida, pero no detalla cuántas veces incrementa el iterador de entrada.

La implementación ingenua incrementa el iterador de entrada una vez más que la implementación no ingenua. Si tenemos un iterador de entrada de paso único que lee en ++ con espacio insuficiente, copy_n podría bloquear innecesariamente en entradas posteriores, tratando de leer datos más allá del final de la secuencia de entrada.

Answer 2

Con la implementación ingenua, incrementas el iterador de entrada n veces, no solo n - 1 veces. Esto no solo es potencialmente ineficiente (ya que los iteradores pueden tener tipos arbitrarios y arbitrariamente caros definidos por el usuario), sino que también puede ser totalmente indeseable cuando el iterador de entrada no admite un estado significativo "pasado al final".

Para un ejemplo simple, considere leer n elementos de std::cin :

#include <iostream>    // for std:cin
#include <iterator>    // for std::istream_iterator


std::istream_iterator it(std::cin);
int dst[3];

Con la solución ingenua, el programa bloquea en el incremento final:

int * p = dst;

for (unsigned int i = 0; i != 3; ++i) { *p++ = *it++; }   // blocks!

El algoritmo de la biblioteca estándar no bloquea:

#include <algorithm>

std::copy_n(it, 3, dst);    // fine

Tenga en cuenta que la norma en realidad no habla explícitamente acerca de los incrementos de iterador. Solo dice (25.3.1 / 5) que copy_n(first, n, result) tiene

Efectos: Para cada entero no negativo i < n , realiza *(result + i) = *(first + i) .

Solo hay una nota en 24.2.3 / 3:

Los algoritmos [input-iterator] se pueden usar con istreams como la fuente de los datos de entrada a través de la plantilla de clase istream_iterator .

Answer 3

Debido a la verificación inicial

if (count > 0)

sabemos que el recuento> 0, por lo tanto, el autor de ese código consideró que no tenía que volver a realizar la prueba hasta que alcanzó el valor de 1. Recuerde que "para" ejecuta la prueba condicional al comienzo de cada iteración, no al final.

Size count = 1;
for (Size i = 1; i < count; ++i) {
    std::cout << i << std::endl;
}

no imprimiría nada

Por lo tanto, el código elimina una rama condicional, y si el Tamaño es 1, elimina la necesidad de incrementar / ajustar "primero", por lo que es un pre-incremento.

Answer 4

Eso es solo una implementación. La implementación en GCC 4.4 es diferente (y conceptualmente más simple):

template<typename InputIterator, typename _Size, typename _OutputIterator>
_OutputIterator
copy_n(_InputIterator __first, _Size __n,
     _OutputIterator __result)
{
  for (; __n > 0; --__n)
{
  *__result = *__first;
  ++__first;
  ++__result;
}
  return __result;
}

[Con un poco de handwaving, dado que solo proporcioné la implementación cuando el iterador de entrada es un iterador de entrada , hay una implementación diferente para el caso donde el iterador es un iterador de acceso aleatorio ] Esa implementación tiene un error porque incrementa la entrada iterador una vez más de lo esperado.

La implementación en GCC 4.8 es un poco más complicada:

template<typename _InputIterator, typename _Size, typename _OutputIterator>
_OutputIterator
copy_n(_InputIterator __first, _Size __n,
     _OutputIterator __result)
{
  if (__n > 0)
{
  while (true)
    {
      *__result = *__first;
      ++__result;
      if (--__n > 0)
    ++__first;
      else
    break;
    }
}
  return __result;
}