c++ - sort - ¿Es una buena práctica falsificar un insertador?

stl c++ functions

Question

Nos enseñan a crear objetos de función para usar algoritmos.

Hay algoritmos que llaman al operator() , como:

• para cada
• find_if
• remove_if
• max_element
• count_if

Estos objetos de función normalmente deben heredar de unary_function o binary_function , para comportarse como una función , un predicado , etc.

Pero los libros generalmente no OutputIterators ejemplos para crear OutputIterators :

Por ejemplo, para recorrer la salida de funciones como std::set_intersection() , tengo que proporcionar un contenedor de destino y luego atravesar el resultado:

std::vector<int> tmp_dest;

std::set_difference (
        src1.begin(), src1.end(), 
        src2.begin(), src2.end(), 
        std::back_inserter(tmp_dest));

std::for_each( tmp_dest.begin(), tmp_dest.end(), do_something );
int res = std::accumulate( tmp_dest.begin(), tmp_dest.end(), 0 );

pero piense que a veces sería más eficiente usar los valores de cada algoritmo, sin almacenarlos primero, como:

std::set_difference (
        src1.begin(), src1.end(), 
        src2.begin(), src2.end(), 
        do_something );

Accumulator accumulate(0);  // inherits from std::insert_iterator ?
std::set_difference (
        src1.begin(), src1.end(), 
        src2.begin(), src2.end(), 
        accumulate );

• ¿Deberíamos generalmente crear clases como este Acumulador ?
• ¿Cómo debería ser su diseño?
• ¿De qué debería heredar? El acumulador podría heredar de insert_iterator , pero en realidad no es un iterador (por ejemplo, no implementa el operator++() )

¿Cuáles son las prácticas ampliamente aceptadas?

Answer 1

El objetivo de los algoritmos que toman un iterador de salida es una secuencia de valores representados por un iterador de salida. Usan iteradores por dos razones:

1. Es muy probable que el resultado se almacene en otro lugar, es decir, un iterador es útil.
2. El protocolo obliga a que cada posición se escriba una sola vez. Esto es más restrictivo que una interfaz de llamada de función, es decir, hay una garantía adicional.

Para algunos algoritmos, se proporcionan ambas versiones, una con una interfaz de llamada de función y otra con una interfaz de iterador. Por ejemplo, esa es la diferencia entre std::for_each() y std::copy() .

En cualquier caso, si todo lo que necesita es tener una función llamada donde se necesita un iterador de salida, simplemente haga que el resto de las operaciones del iterador no sean op-ops y llame la función al asignar el resultado de *it : esto crea un iterador de salida perfectamente valud .

Answer 2

Los siguientes trabajos:

#include <cassert>
#include <algorithm>

class AccumulatorIterator
{
public:
    explicit AccumulatorIterator(int initial) : value(initial) {}

    AccumulatorIterator& operator = (int rhs) { value += rhs; return *this; }
    AccumulatorIterator& operator *() { return *this; }

    AccumulatorIterator& operator ++() { return *this; }
    operator int() const { return value; }
private:
    int value;
};

int main() {
    int first[] = {5,10,15,20,25};
    int second[] = {50,40,30,20,10};

    std::sort(std::begin(first), std::end(first));   //  5 10 15 20 25
    std::sort(std::begin(second), std::end(second)); // 10 20 30 40 50

    const int res = std::set_intersection (std::begin(first), std::end(first),
        std::begin(second), std::end(second), AccumulatorIterator(0));

    assert(res == 10 + 20);
    return 0;
}

Answer 3

Mi opinión sobre esto sería usar Boost (que también muestra las versiones del algoritmo Boost Range de set_difference , aunque fuera de tema):

#include <set>
#include <boost/range/algorithm.hpp>
#include <boost/function_output_iterator.hpp>
#include <cassert>

void do_something(int) {}

int main()
{
    const std::set<int> 
         src1 { 1,2,3 }, 
         src2 { 1,9 };

    unsigned total = 0;

    boost::set_difference(src1, src2, 
                boost::make_function_output_iterator([&](int i) 
                { 
                    total += i*i; 
                }));

    assert(total == 13); // 2*2 + 3*3
}

Véalo en vivo en Coliru

Answer 4

No veo un problema fundamental con esto mientras esté claro para los futuros mantenedores cómo funcionan los códigos y qué hacen.

Probablemente no heredaría una operación de este tipo de ninguna clase estándar (aparte de darle output_iterator_tag ). Ya que estamos tratando con plantillas, no necesitamos tener una interfaz principal para tratar.

Pero tenga en cuenta que su declaración (eg it does not implement operator++() ) no parece ser correcta: pase lo que pase, ya que el "iterador de salida" debe cumplir los requisitos de los iteradores de salida, que incluyen ser copiable, desreferencia- Asignar, e incrementable. Cualquier tipo de objeto que pase necesita cumplir con estos requisitos.

Answer 5

Si desea un iterador de salida que llame a su propia función para cada valor recibido, use el function_output_iterput de Boost.Iterator .