Explicación de la implementación de C++

Cuando me gusta 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 la implementación y necesitaría alguna explicación de por qué se hace algo 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?

Author: Christian Ammer, 2013-07-16
Source

4 answers

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 desreferenciables, pero no incrementable. 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.

Aquí es un error que parece ocurrir si se utiliza la implementación ingenua, y Aquí es alguna documentación que afirma "La operación de lectura real se realiza cuando el iterador se incrementa, no cuando se desreferenciaen."

Todavía no he rastreado el capítulo-y-verso para la existencia de desreferenciable, no-incrementable iteradores de entrada. Aparentemente, el estándar detalla cuántas veces copy_n desreferencian 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 una sola pasada que lee en ++ con espacio insuficiente, copy_n podría bloquear innecesariamente en la entrada adicional, tratando de leer los datos más allá del final del flujo de entrada.

 20
Author: Yakk - Adam Nevraumont,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-07-16 12:30:19

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, ya que solo proporcioné la implementación cuando el iterador de entrada es un iterador de entrada , hay una implementación diferente para el caso en que el iterador es un iterador de acceso aleatorio ] Que la implementación tiene un error en que incrementa el iterador de entrada una vez más de lo esperado.

La aplicación en el CCG 4.8 es un poco más complicado:

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;
}
 13
Author: David Rodríguez - dribeas,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-07-15 20:59:16

Con la implementación ingenua, se incrementa 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 directamente indeseable cuando el iterador de entrada no admite un estado significativo "pasado-el-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 se bloquea en el incremento final: 

int * p = dst;

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

El algoritmo estándar de la biblioteca no bloquea: 

#include <algorithm>

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

Tenga en cuenta que el estándar en realidad no habla explícitamente de incrementos de iteradores. 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: {[12]]}

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

 7
Author: Kerrek SB,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-07-15 21:25:45

Debido a la comprobación inicial

if (count > 0)

Sabemos que count > 0, por lo tanto, el autor de ese código sintió que no necesitaba probar contra count nuevamente hasta que alcanzara el valor de 1. Recuerde que " for " ejecuta la prueba condicional al principio 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 tanto, es un pre-incremento.

 1
Author: kfsone,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-07-15 20:42:51