iterador "end()" para insertadores posteriores?

Question

Para iteradores como los devueltos por std::back_inserter(), ¿hay algo que se pueda utilizar como un iterador "final"?

esto parece un poco sin sentido al principio, pero tengo una API que es:

template<typename InputIterator, typename OutputIterator> 
void foo(
    InputIterator input_begin, 
    InputIterator input_end, 
    OutputIterator output_begin, 
    OutputIterator output_end 
); 

foo realiza alguna operación en la secuencia de entrada, generando una secuencia de salida. (Longitud del que se sabe que foo pero puede o no ser igual a la longitud de la secuencia de entrada.)

La toma del parámetro output_end es la parte extraña: std::copy no lo hace, por ejemplo, y que asume' No voy a pasarlo basura. foo lo hace para proporcionar verificación de rango: si pasas un rango demasiado pequeño, arroja una excepción, en el nombre de la programación defensiva. (En lugar de sobreescribir potencialmente bits aleatorios en la memoria.)

Ahora, supongamos que quiero pasar foo un insertador posterior, específicamente uno de un std::vector que no tiene límite fuera de las limitaciones de memoria. Todavía necesito un iterador "final", en este caso, algo que nunca se comparará igual. (O, si tuviera un std::vector pero con una restricción en la longitud, ¿quizás a veces podría ser igual?)

¿Cómo hago esto? Tengo la capacidad de cambiar la API de foo. ¿Es mejor no verificar el rango y, en su lugar, proporcionar un medio alternativo para obtener el rango de salida requerido? (Que se necesitaría de todos modos para matrices en bruto, pero no se requiere para insertadores posteriores en un vector). Esto parecería menos robusto, pero estoy luchando para que el trabajo "robusto" (arriba) funcione.

Answer 1

Si foo comprueba que distance(output_begin, output_end) es lo suficientemente grande como para contener los resultados, ¿qué podría usar como un iterador "final"? A back_inserter agrega elementos al final; el distance entre el lugar en el que back_inserter agrega elementos y el final de la secuencia es, por definición, 0.

A foo con la firma std::copy -like foo(InIt, InIt, OutIt) es, en mi opinión, su mejor opción. No es realmente "no robusto". Para la mayoría de los algoritmos, solo desea hacer este tipo de rango comprobando las compilaciones de depuración por motivos de rendimiento, y una implementación decente de la Biblioteca estándar (como la Biblioteca estándar de Visual C++) ya proporcionará una gran cantidad de comprobación de rango en compilaciones de depuración.

Como alternativa, podría crear un back_inserting_foo(InIt, InIt, Container), aunque la creación de un caso especial para esto sería un poco inusual y supone una mayor carga para los usuarios de la función saber qué sobrecarga necesitan para diferentes tipos de iteradores.

Answer 2

Puede evitar cambiar foo() 's API mediante la realización de la comprobación de seguridad sobre la marcha, comprobando que curr_output_iter != output_end antes de cada elemento se escribe (ver más abajo), en lugar de una vez al comienzo con un cheque como distance()James McNellis suggests.

Hacer esto requerirá escribir su propio "adaptador de iterador" para proporcionar un iterador de salida "mejorado" que pueda probar si está al final de su rango válido. Luego, con razón, cambiaría los nombres de tipo de plantilla de OutputIterator a SafeOutputIterator, aunque esto solo sirve como documentación porque es algo que no se puede aplicar en C++.Distinguimos entre pares de iteradores "acotados" y "no acotados": para este último, ningún iterador se comparará igual y, de hecho, el segundo iterador nunca será necesario para nada más que su tipo.

/* Metafunction for determining whether the range has a fixed endpoint. 
* Assume all iterators are bounded except for OutputIterators. */ 
template <typename Tag> 
struct helper { 
    static bool value = true; 
}; 

template <> 
struct helper<output_iterator_tag> { 
    static bool value = false; 
}; 

template <typename It> 
struct is_bounded { 
    static bool value = helper<typename iterator_traits<It>::iterator_category>::value; 
}; 

/* Wraps an output iterator. */ 
template<typename It, bool BOUNDED = is_bounded<It>::value> 
class safe_output_iterator { 
    typedef typename iterator_traits<It>::value_type value_type; 

public: 
    explicit safe_output_iterator(It iter, size_t limit = 0) : iter_(iter), limit_(limit) {} 

    safe_output_iterator& operator++() { /* Preinc */ 
     ++iter_; 
     return *this; 
    } 

    safe_output_iterator operator++(int) { /* Postinc */ 
     safe_output_iterator temp(*this); 
     ++iter_; 
     return temp; 
    } 

    /* Trick: Deferencing returns the same object, so that operator=() works */ 
    safe_output_iterator& operator*() { 
     return *this; 
    } 

    /* Will be called despite "dereferencing" this iterator object */ 
    safe_output_iterator& operator=() { 
     /* Insert check for limit == 0 here if you want */ 
     --limit_; 
     return *_iter; 
    } 

    /* Addition to the OutputIterator concept. */ 
    bool operator==(safe_output_iterator const& x) { 
     return BOUNDED && limit_ == x.limit_; 
    } 

    bool operator!=(safe_output_iterator const& x) { 
     return !(*this == x); 
    } 

private: 
    It iter_; 
    size_t limit_; 
}; 

/* Helper function templates to avoid typing out long typenames */ 

/* Handle iterators */ 
template <typename It> 
safe_output_iterator<It> soi_begin(It it, size_t limit = 0) { 
    return safe_output_iterator<It>(it, limit); 
} 

template <typename It> 
safe_output_iterator<It> soi_end(It it, size_t limit = 0) { 
    return safe_output_iterator<It>(it, limit); 
} 

/* Handle STL containers like vector and list */ 
template <typename C> 
safe_output_iterator<It> soi_begin_cont(C cont) { 
    return safe_output_iterator<typename C::iterator>(cont.begin(), cont.size()); 
} 

template <typename C> 
safe_output_iterator<It> soi_end_cont(C cont) { 
    /* Actually the iterator supplied (here cont.end()) is unimportant... */ 
    return safe_output_iterator<typename C::iterator>(cont.end()); 
} 

Ahora puede escribir código como:

vector<int> u(10, 42), v(ENOUGH_SPACE), w, x(ENOUGH_SPACE); 

// Explicit iterator pair; bounded 
foo(u.begin(), u.end(), soi_begin(v.begin(), ENOUGH_SPACE), soi_end(v)); 

// Explicit iterator pair; unbounded (2nd iterator ignored, but we need the type) 
foo(u.begin(), u.end(), soi_begin(w.back_inserter()), soi_end(w.back_inserter())); 

// Use whole container 
foo(u.begin(), u.end(), soi_begin_cont(x), soi_end_cont(x)); 

la que podrá tomar foo() comprobación antes de cada curr_output_iter != output_end escribir a través de *curr_output_iter, o insertar alternativamente el cheque en safe_output_iterator::operator=(). Este último parece preferible ya que no puede olvidar realizar el control cada vez que se pasa un par de safe_output_iterator a cualquier algoritmo arbitrario (presumiblemente esto es similar a cómo funcionan las versiones de depuración del STL). También puede escribir sobrecargas de soi_begin_cont() y soi_end_cont() para arreglos de tamaño fijo.

Todo esto sería mucho menos engorroso si ranges fueran utilizados por los algoritmos STL en lugar de los pares de iteradores, de esa manera una plantilla de función única podría devolver un rango apropiado que abarcara una matriz completa, por ejemplo.

Answer 3

Como ya he mencionado en un comentario a la respuesta de j_random_hacker, si modifica el algoritmo de tal manera que los iteradores que se le pasan pueden ser de diferentes tipos, por ejemplo,

template <typename InIt1, InIt2, OutIt1, OutIt2> 
void foo(InIt1 in_begin, InIt2 in_end, OutIt1 out_begin, OutIt2 out_end) { } 

a continuación, puede muy fácilmente escribir una back_inserter_end clase que se prueba contra:

class back_inserter_end 
    : std::iterator<std::output_iterator_tag, void> 
{ }; 

bool operator==(back_inserter_end, back_inserter_end) { return true; } 
bool operator!=(back_inserter_end, back_inserter_end) { return false; } 

template <typename Container> 
bool operator==(const back_insert_iterator<Container>&, back_inserter_end) { 
    return false; 
} 

template <typename Container> 
bool operator==(back_inserter_end, const back_insert_iterator<Container>&) { 
    return false; 
} 

template <typename Container> 
bool operator!=(const back_insert_iterator<Container>&, back_inserter_end) { 
    return true; 
} 

template <typename Container> 
bool operator!=(back_inserter_end, const back_insert_iterator<Container>&) { 
    return true; 
} 

entonces usted puede llamar a su algoritmo de "seguro":

foo(it, it, std::back_inserter(v), back_inserter_end()); 

Dentro de su algoritmo "seguro", puede probar si out_it == out_end antes de usar out_it; desde out_it es back_insert_iterator, esta prueba siempre devolverá false (que es el comportamiento deseado).