Algoritmo STL para rangos equivalentes

Question

Por definición, el algoritmo std :: equal solo toma un 'último' iterador. Muchas publicaciones en stackoverflow indican que para realizar la equivalencia entre dos rangos, primero se debe verificar que los rangos tengan el mismo tamaño además de llamar a std :: equal. Si los iteradores de acceso aleatorio están disponibles, esto no agrega ninguna sobrecarga de material. Sin embargo, parece que sin los iteradores de acceso aleatorio, el primer fragmento de código, implementado solo con los algoritmos STL existentes, será más lento que el segundo fragmento de código, que representa un algoritmo "equivalente" personalizado (no parte de STL). Mi pregunta es, ¿el fragmento 2 es más eficiente que cualquier algoritmo codificado solo con los algoritmos STL existentes? Si es así, ¿por qué este algoritmo no es parte de STL?

Fragmento 1:

template <typename IITR1, typename IITR2> 
bool equivalent(IITR1 first1, IITR1 last1, IITR2 first2, IITR2 last2) 
{ 
    return distance(first1, last1) == distance(first2, last2) && 
     equal(first1, last1, first2); 
} 

Fragmento 2:

template <typename IITR1, typename IITR2> 
bool equivalent(IITR1 first1, IITR1 last1, IITR2 first2, IITR2 last2) 
{ 
    while (first1 != last1 && first2 != last2) { 
     if (!(*first1 == *first2)) return false; 
     ++first1; ++first2; 
    } 
    return first1 == last1 && first2 == last2; 
} 

Nota: No he comprobado, pero yo sería muy dudoso que el compilador optimizará el fragmento 1 tal que produce código con el mismo rendimiento producido por el fragmento 2.

Para completar, el siguiente fragmento de código es inútil, ya que fallará si los tamaños del rango no son iguales:

template <typename IITR1, typename IITR2> 
bool equivalent(IITR1 first1, IITR1 last1, IITR2 first2, IITR2 last2) 
{ 
    return equal(first1, last1, first2) && equal(first2, last2, first1); 
} 

Answer 1

El primero solo funcionará para los iteradores de reenvío, no para los iteradores de entrada en general.

El rendimiento dependerá del tipo de iterador. El primero es probable que sea más rápido para los iteradores de acceso aleatorio ya que el ciclo principal de equal es más simple que el ciclo principal de su segunda implementación; pero es probable que sea más lento si distance tiene que iterar en todo el rango.

Para admitir los iteradores de entrada, y para obtener el mejor rendimiento en todas las circunstancias, es probable que necesite diferentes especializaciones para diferentes categorías de iteradores. Empezaría por el segundo y me especializaré solo si no es suficiente.

No tengo idea de por qué no está en la biblioteca estándar, pero no se puede esperar que ninguna biblioteca contenga todos los algoritmos posibles.

Answer 2

Es probable que cuando se estaba estandarizando el STL, no se consideró la situación en la que los dos rangos son de acceso no aleatorio pero con longitudes diferentes; y mirando los informes de defectos ya que no parece haber sido una solución muy demandada. Como habrás notado, es bastante fácil escribir tu propia versión que lo haga bien.

Un problema con la actualización de una solución sería decidir si una llamada de cuatro parámetros es una llamada de dos intervalos (it1, it1_end, it2, it2_end) o una versión (it1, it1_end, it2, predicate). Las técnicas para distinguir (SFINAE, enable_if) solo recientemente han estado disponibles.

Tenga en cuenta que Boost.Range tiene una implementación que lo hace bien; ver http://www.boost.org/doc/libs/1_51_0/boost/range/algorithm/equal.hpp para la implementación. También detecta cuando los dos tipos de iterador son de acceso aleatorio y llama a distance para provocar un cortocircuito en el caso en que las longitudes son diferentes.

#include <boost/range/algorithm.hpp> 

boost::equal(boost::make_iterator_range(first1, last1), 
    boost::make_iterator_range(first2, last2));