c++ - programacion - principales librerias en lenguaje c

¿Por qué no hay transform_if en la biblioteca estándar de C++?

Question

Surgió un caso de uso al querer hacer una copia copy_if (1. factible con copy_if ) pero desde un contenedor de valores a un contenedor de punteros a esos valores (2. doable con transform ).

Con las herramientas disponibles no puedo hacerlo en menos de dos pasos:

#include <vector>
#include <algorithm>

using namespace std;

struct ha { 
    int i;
    explicit ha(int a) : i(a) {}
};

int main() 
{
    vector<ha> v{ ha{1}, ha{7}, ha{1} }; // initial vector
    // GOAL : make a vector of pointers to elements with i < 2
    vector<ha*> ph; // target vector
    vector<ha*> pv; // temporary vector
    // 1. 
    transform(v.begin(), v.end(), back_inserter(pv), 
        [](ha &arg) { return &arg; }); 
    // 2. 
    copy_if(pv.begin(), pv.end(), back_inserter(ph),
        [](ha *parg) { return parg->i < 2;  }); // 2. 

    return 0;
}

Por supuesto, podríamos llamar remove_if en pv y eliminar la necesidad de un temporal, mejor aún, sin embargo, no es difícil implement (para operaciones unarias) algo como esto:

template <
    class InputIterator, class OutputIterator, 
    class UnaryOperator, class Pred
>
OutputIterator transform_if(InputIterator first1, InputIterator last1,
                            OutputIterator result, UnaryOperator op, Pred pred)
{
    while (first1 != last1) 
    {
        if (pred(*first1)) {
            *result = op(*first1);
            ++result;
        }
        ++first1;
    }
    return result;
}

// example call 
transform_if(v.begin(), v.end(), back_inserter(ph), 
[](ha &arg) { return &arg;      }, // 1. 
[](ha &arg) { return arg.i < 2; });// 2.

1. ¿Existe una solución más elegante con las herramientas de biblioteca estándar de C ++ disponibles?
2. ¿Hay alguna razón por la cual transform_if no existe en la biblioteca? ¿La combinación de las herramientas existentes es una solución adecuada y / o se considera que el rendimiento se comporta bien?

Answer 1

Después de solo encontrar esta pregunta nuevamente después de algún tiempo, y al idear una gran cantidad de adaptadores de iteradores genéricos potencialmente útiles, me di cuenta de que la pregunta original no requería NADA más que std::reference_wrapper .

Úsalo en lugar de un puntero, y estás bien:

Vivir en coliru

#include <algorithm>
#include <functional> // std::reference_wrapper
#include <iostream>
#include <vector>

struct ha {
    int i;
};

int main() {
    std::vector<ha> v { {1}, {7}, {1}, };

    std::vector<std::reference_wrapper<ha const> > ph; // target vector
    copy_if(v.begin(), v.end(), back_inserter(ph), [](const ha &parg) { return parg.i < 2; });

    for (ha const& el : ph)
        std::cout << el.i << " ";
}

Huellas dactilares

1 1 

Answer 2

El estándar está diseñado de tal manera que minimice la duplicación.

En este caso particular, puede lograr los objetivos del algoritmo de una manera más legible y concisa con un simple bucle de rango.

// another way

vector<ha*> newVec;
for(auto& item : v) {
    if (item.i < 2) {
        newVec.push_back(&item);
    }
}

He modificado el ejemplo para que compile, agregué algunos diagnósticos y presenté el algoritmo de OP y el mío al lado del otro.

#include <vector>
#include <algorithm>
#include <iostream>
#include <iterator>

using namespace std;

struct ha { 
    explicit ha(int a) : i(a) {}
    int i;   // added this to solve compile error
};

// added diagnostic helpers
ostream& operator<<(ostream& os, const ha& t) {
    os << "{ " << t.i << " }";
    return os;
}

ostream& operator<<(ostream& os, const ha* t) {
    os << "&" << *t;
    return os;
}

int main() 
{
    vector<ha> v{ ha{1}, ha{7}, ha{1} }; // initial vector
    // GOAL : make a vector of pointers to elements with i < 2
    vector<ha*> ph; // target vector
    vector<ha*> pv; // temporary vector
    // 1. 
    transform(v.begin(), v.end(), back_inserter(pv), 
        [](ha &arg) { return &arg; }); 
    // 2. 
    copy_if(pv.begin(), pv.end(), back_inserter(ph),
        [](ha *parg) { return parg->i < 2;  }); // 2. 

    // output diagnostics
    copy(begin(v), end(v), ostream_iterator<ha>(cout));
    cout << endl;
    copy(begin(ph), end(ph), ostream_iterator<ha*>(cout));
    cout << endl;


    // another way

    vector<ha*> newVec;
    for(auto& item : v) {
        if (item.i < 2) {
            newVec.push_back(&item);
        }
    }

    // diagnostics
    copy(begin(newVec), end(newVec), ostream_iterator<ha*>(cout));
    cout << endl;
    return 0;
}

Answer 3

Esta es solo una respuesta a la pregunta 1 "¿Existe una solución más elegante con las herramientas de biblioteca estándar de C ++ disponibles?".

Si puede usar c ++ 17, entonces puede usar std::optional para una solución más simple utilizando solo la funcionalidad de la biblioteca estándar de C ++. La idea es devolver std::nullopt en caso de que no haya mapeo:

Ver en vivo en Coliru

#include <iostream>
#include <optional>
#include <vector>

template <
    class InputIterator, class OutputIterator, 
    class UnaryOperator
>
OutputIterator filter_transform(InputIterator first1, InputIterator last1,
                            OutputIterator result, UnaryOperator op)
{
    while (first1 != last1) 
    {
        if (auto mapped = op(*first1)) {
            *result = std::move(mapped.value());
            ++result;
        }
        ++first1;
    }
    return result;
}

struct ha { 
    int i;
    explicit ha(int a) : i(a) {}
};

int main()
{
    std::vector<ha> v{ ha{1}, ha{7}, ha{1} }; // initial vector

    // GOAL : make a vector of pointers to elements with i < 2
    std::vector<ha*> ph; // target vector
    filter_transform(v.begin(), v.end(), back_inserter(ph), 
        [](ha &arg) { return arg.i < 2 ? std::make_optional(&arg) : std::nullopt; });

    for (auto p : ph)
        std::cout << p->i << std::endl;

    return 0;
}

Tenga en cuenta que acabo de implementar filter_map en C ++ aquí.

Answer 4

La biblioteca estándar favorece los algoritmos elementales.

Los contenedores y los algoritmos deben ser independientes entre sí si es posible.

Del mismo modo, los algoritmos que se pueden componer de algoritmos existentes solo se incluyen raramente, como abreviatura.

Si necesita una transformación si, puede escribirla de forma trivial. Si lo desea / today /, compuesto de ready-mades y no incurre en gastos generales, puede usar una biblioteca de rangos con rangos perezosos , como Boost.Range , por ejemplo:

v | filtered(arg1 % 2) | transformed(arg1 * arg1 / 7.0)

Como @hvd señala en un comentario, transform_if doble resultado en un tipo diferente ( double , en este caso). El orden de la composición es importante, y con Boost Range también puedes escribir:

 v | transformed(arg1 * arg1 / 7.0) | filtered(arg1 < 2.0)

dando como resultado diferentes semánticas. Esto lleva a casa el punto:

tiene muy poco sentido incluir std::filter_and_transform , std::transform_and_filter , std::filter_transform_and_filter etc. etc. en la biblioteca estándar .

Vea una muestra en vivo en Coliru

#include <boost/range/algorithm.hpp>
#include <boost/range/adaptors.hpp>

using namespace boost::adaptors;

// only for succinct predicates without lambdas
#include <boost/phoenix.hpp>
using namespace boost::phoenix::arg_names;

// for demo
#include <iostream>

int main()
{
    std::vector<int> const v { 1,2,3,4,5 };

    boost::copy(
            v | filtered(arg1 % 2) | transformed(arg1 * arg1 / 7.0),
            std::ostream_iterator<double>(std::cout, "/n"));
}

Answer 5

La nueva notación de bucle for de muchas maneras reduce la necesidad de algoritmos que accedan a todos los elementos de la colección donde ahora es más limpio escribir un bucle y colocar la lógica en su lugar.

std::vector< decltype( op( begin(coll) ) > output;
for( auto const& elem : coll )
{
   if( pred( elem ) )
   {
        output.push_back( op( elem ) );
   }
}

¿Realmente proporciona mucho valor ahora para poner en un algoritmo? Si bien sí, el algoritmo hubiera sido útil para C ++ 03 y, de hecho, tenía uno para él, no lo necesitamos ahora, por lo que no hay ninguna ventaja real en agregarlo.

Tenga en cuenta que, en el uso práctico, su código no siempre tendrá el mismo aspecto: no necesariamente tiene las funciones "op" y "pred" y es posible que tenga que crear lambdas para que se "ajusten" a los algoritmos. Si bien es bueno separar las preocupaciones si la lógica es compleja, si solo se trata de extraer un miembro del tipo de entrada y verificar su valor o agregarlo a la colección, una vez más es mucho más sencillo que usar un algoritmo.

Además, una vez que agregue algún tipo de transform_if, debe decidir si aplicar el predicado antes o después de la transformación, o incluso tener 2 predicados y aplicarlo en ambos lugares.

¿Entonces, que vamos a hacer? Añadir 3 algoritmos? (Y en el caso de que el compilador pudiera aplicar el predicado en cualquiera de los extremos del converso, un usuario podría elegir fácilmente el algoritmo incorrecto y el código aún se compilaría, pero produciría resultados incorrectos).

Además, si las colecciones son grandes, ¿el usuario desea realizar un bucle con iteradores o mapear / reducir? Con la introducción de map / reduce usted obtiene aún más complejidades en la ecuación.

Esencialmente, la biblioteca proporciona las herramientas, y se deja al usuario aquí para usarlas para que se ajusten a lo que quieren hacer, y no al revés, como en el caso de los algoritmos. (Vea cómo el usuario anterior intentó torcer las cosas usando la acumulación para adaptarse a lo que realmente quería hacer).

Para un ejemplo simple, un mapa. Para cada elemento daré el valor si la clave es par.

std::vector< std::string > valuesOfEvenKeys
    ( std::map< int, std::string > const& keyValues )
{
    std::vector< std::string > res;
    for( auto const& elem: keyValues )
    {
        if( elem.first % 2 == 0 )
        {
            res.push_back( elem.second );
        }
    }
    return res;
}         

Agradable y sencillo. ¿Fancy ajuste que en un algoritmo transform_if?

Answer 6

Perdón por resucitar esta pregunta después de tanto tiempo. Recientemente tuve un requisito similar. Lo resolví escribiendo una versión de back_insert_iterator que toma un impulso :: opcional:

template<class Container>
struct optional_back_insert_iterator
: public std::iterator< std::output_iterator_tag,
void, void, void, void >
{
    explicit optional_back_insert_iterator( Container& c )
    : container(std::addressof(c))
    {}

    using value_type = typename Container::value_type;

    optional_back_insert_iterator<Container>&
    operator=( const boost::optional<value_type> opt )
    {
        if (opt) {
            container->push_back(std::move(opt.value()));
        }
        return *this;
    }

    optional_back_insert_iterator<Container>&
    operator*() {
        return *this;
    }

    optional_back_insert_iterator<Container>&
    operator++() {
        return *this;
    }

    optional_back_insert_iterator<Container>&
    operator++(int) {
        return *this;
    }

protected:
    Container* container;
};

template<class Container>
optional_back_insert_iterator<Container> optional_back_inserter(Container& container)
{
    return optional_back_insert_iterator<Container>(container);
}

utilizado así:

transform(begin(s), end(s),
          optional_back_inserter(d),
          [](const auto& s) -> boost::optional<size_t> {
              if (s.length() > 1)
                  return { s.length() * 2 };
              else
                  return { boost::none };
          });

Answer 7

Puedes usar copy_if largo. Por qué no? Definir OutputIt (ver copy ):

struct my_inserter: back_insert_iterator<vector<ha *>>
{
  my_inserter(vector<ha *> &dst)
    : back_insert_iterator<vector<ha *>>(back_inserter<vector<ha *>>(dst))
  {
  }
  my_inserter &operator *()
  {
    return *this;
  }
  my_inserter &operator =(ha &arg)
  {
    *static_cast< back_insert_iterator<vector<ha *>> &>(*this) = &arg;
    return *this;
  }
};

y reescribe tu código:

int main() 
{
    vector<ha> v{ ha{1}, ha{7}, ha{1} }; // initial vector
    // GOAL : make a vector of pointers to elements with i < 2
    vector<ha*> ph; // target vector

    my_inserter yes(ph);
    copy_if(v.begin(), v.end(), yes,
        [](const ha &parg) { return parg.i < 2;  });

    return 0;
}

Answer 8

template <class InputIt, class OutputIt, class BinaryOp>
OutputIt
transform_if(InputIt it, InputIt end, OutputIt oit, BinaryOp op)
{
    for(; it != end; ++it, (void) ++oit)
        op(oit, *it);
    return oit;
}

Uso: (Tenga en cuenta que CONDITION y TRANSFORM no son macros, son marcadores de posición para cualquier condición y transformación que desee aplicar)

std::vector a{1, 2, 3, 4};
std::vector b;

return transform_if(a.begin(), a.end(), b.begin(),
    [](auto oit, auto item)             // Note the use of ''auto'' to make life easier
    {
        if(CONDITION(item))             // Here''s the ''if'' part
            *oit++ = TRANSFORM(item);   // Here''s the ''transform'' part
    }
);