c++ - program - La función std:: transform-like que devuelve el contenedor transformado
stl c++ 11 (4)
Estoy tratando de implementar una función similar al algoritmo std::transform pero en lugar de tomar el iterador de salida por un argumento que quiero crear y devolver un contenedor con elementos de entrada transformados.
Digamos que se llama transform_container y toma dos argumentos: container y functor. Debería devolver el mismo tipo de contenedor pero posiblemente parametrizado por un tipo de elemento diferente (el Functor puede devolver un elemento de diferente tipo).
Me gustaría utilizar mi función como en el siguiente ejemplo:
std::vector<int> vi{ 1, 2, 3, 4, 5 };
auto vs = transform_container(vi, [] (int i) { return std::to_string(i); });
//vs will be std::vector<std::string>
assert(vs == std::vector<std::string>({"1", "2", "3", "4", "5"}));
std::set<int> si{ 5, 10, 15 };
auto sd = transform_container(si, [] (int i) { return i / 2.; });
//sd will be of type std::set<double>
assert(sd == std::set<double>({5/2., 10/2., 15/2.}));
Pude escribir dos funciones, una para std::set y otra para std::vector , que parecen funcionar correctamente. Son idénticos, excepto el nombre de tipo del contenedor. Su código se enumera a continuación.
template<typename T, typename Functor>
auto transform_container(const std::vector<T> &v, Functor &&f) -> std::vector<decltype(f(*v.begin()))>
{
std::vector<decltype(f(*v.begin()))> ret;
std::transform(std::begin(v), std::end(v), std::inserter(ret, ret.end()), f);
return ret;
}
template<typename T, typename Functor>
auto transform_container(const std::set<T> &v, Functor &&f) -> std::set<decltype(f(*v.begin()))>
{
std::set<decltype(f(*v.begin()))> ret;
std::transform(std::begin(v), std::end(v), std::inserter(ret, ret.end()), f);
return ret;
}
Sin embargo, cuando intenté fusionarlos en una sola función general que funciona con cualquier contenedor, encontré numerosos problemas. El set y el vector son plantillas de clase, por lo que mi plantilla de función debe tomar un parámetro de plantilla de plantilla. Además, las plantillas de conjunto y vector tienen un número diferente de parámetros de tipo que deben ajustarse correctamente.
¿Cuál es la mejor manera de generalizar las dos plantillas de funciones anteriores en una función que funciona con cualquier tipo de contenedor compatible?
Algunas observaciones
El siguiente método permite transformar contenedores de cualquier tipo de la biblioteca estándar (hay un problema con std::array , ver más abajo). El único requisito para el contenedor es que debe utilizar objetos de función std::allocator classes, std::less , std::equal_to y std::hash std::equal_to . Entonces tenemos 3 grupos de contenedores de la biblioteca estándar:
Contenedores con un parámetro de tipo de plantilla no predeterminada (tipo de valor):
-
std::vector,std::deque,std::list,std::forward_list, [std::valarray] -
std::queue,std::priority_queue,std::stack -
std::set,std::unordered_set
-
Contenedores con dos parámetros de tipo de plantilla no predeterminados (tipo de clave y tipo de valor):
-
std::map,std::multi_map,std::multi_map,std::multi_map
-
Contenedor con dos parámetros no predeterminados: parámetro de tipo (tipo de valor) y parámetro no de tipo (tamaño):
-
std::array
-
Implementación
convert_container helper class convierte tipos de tipo de contenedor de entrada conocido ( InputContainer ) y tipo de valor de salida ( OutputType ) al tipo de contenedor de salida ( typename convert_container<InputContainer, Output>::type ):
template <class InputContainer, class OutputType>
struct convert_container;
// conversion for the first group of standard containers
template <template <class...> class C, class IT, class OT>
struct convert_container<C<IT>, OT>
{
using type = C<OT>;
};
// conversion for the second group of standard containers
template <template <class...> class C, class IK, class IT, class OK, class OT>
struct convert_container<C<IK, IT>, std::pair<OK, OT>>
{
using type = C<OK, OT>;
};
// conversion for the third group of standard containers
template
<
template <class, std::size_t> class C, std::size_t N, class IT, class OT
>
struct convert_container<C<IT, N>, OT>
{
using type = C<OT, N>;
};
template <typename C, typename T>
using convert_container_t = typename convert_container<C, T>::type;
Implementación de la función transform_container :
template
<
class InputContainer,
class Functor,
class InputType = typename InputContainer::value_type,
class OutputType = typename std::result_of<Functor(InputType)>::type,
class OutputContainer = convert_container_t<InputContainer, OutputType>
>
OutputContainer transform_container(const InputContainer& ic, Functor f)
{
OutputContainer oc;
std::transform(std::begin(ic), std::end(ic), std::inserter(oc, oc.end()), f);
return oc;
}
Ejemplo de uso
Ver ejemplo en vivo con las siguientes conversiones:
-
std::vector<int> -> std::vector<std::string>, -
std::set<int> -> std::set<double>, -
std::map<int, char> -> std::map<char, int>.
Problemas
std::array<int, 3> -> std::array<double, 3> conversión no se compila porque std::array no tiene insert método que es necesario debido a std::inserter ). transform_container función transform_container no debería funcionar también por este motivo con los siguientes contenedores: std::forward_list , std::queue , std::priority_queue , std::stack , [ std::valarray ].
Casos más simples: tipos de contenedores coincidentes
Para el caso simple donde el tipo de entrada coincide con el tipo de salida (que he observado que no es lo que está preguntando) vaya un nivel más alto. En lugar de especificar el tipo T que usa su contenedor, y tratando de especializarse en un vector<T> , etc., simplemente especifique el tipo del contenedor en sí:
template <typename Container, typename Functor>
Container transform_container(const Container& c, Functor &&f)
{
Container ret;
std::transform(std::begin(c), std::end(c), std::inserter(ret, std::end(ret)), f);
return ret;
}
Más complejidad: tipos de valores compatibles
Dado que desea intentar cambiar el tipo de elemento almacenado por el contenedor, deberá usar un parámetro de plantilla de plantilla y modificar la T que utiliza el contenedor devuelto.
template <
template <typename T, typename... Ts> class Container,
typename Functor,
typename T, // <-- This is the one we''ll override in the return container
typename U = std::result_of<Functor(T)>::type,
typename... Ts
>
Container<U, Ts...> transform_container(const Container<T, Ts...>& c, Functor &&f)
{
Container<U, Ts...> ret;
std::transform(std::begin(c), std::end(c), std::inserter(ret, std::end(ret)), f);
return ret;
}
¿Qué hay de tipos de valores incompatibles?
Esto solo nos lleva a la mitad allí. Funciona bien con una transformación de signed a unsigned pero cuando se resuelve con T=int y S=std::string , y el manejo de conjuntos, intenta instanciar std::set<std::string, std::less<int>, ...> y por lo tanto no compila.
Para solucionar esto, queremos tomar un conjunto arbitrario de parámetros y reemplazar instancias de T con U , incluso si son los parámetros de otros parámetros de plantilla. Por lo tanto, std::set<int, std::less<int>> debe convertirse en std::set<std::string, std::less<std::string>> , y así sucesivamente. Esto implica alguna meta programación personalizada de plantillas, como lo sugieren otras respuestas.
Plantilla de metaprogramación para el rescate
replace_type una plantilla, replace_type nombre replace_type , y replace_type que convierta T a U , y K<T> a K<U> . Primero manejemos el caso general. Si no es un tipo de plantilla, y no coincide con T , su tipo seguirá siendo K :
template <typename K, typename ...>
struct replace_type { using type = K; };
Luego una especialización. Si no es un tipo de plantilla, y coincide con T , su tipo se convertirá en U :
template <typename T, typename U>
struct replace_type<T, T, U> { using type = U; };
Y finalmente un paso recursivo para manejar los parámetros a los tipos de plantilla. Para cada tipo en los parámetros de un tipo de plantilla, reemplace los tipos en consecuencia:
template <template <typename... Ks> class K, typename T, typename U, typename... Ks>
struct replace_type<K<Ks...>, T, U>
{
using type = K<typename replace_type<Ks, T, U>::type ...>;
};
Y finalmente actualiza transform_container para usar replace_type :
template <
template <typename T, typename... Ts> class Container,
typename Functor,
typename T,
typename U = typename std::result_of<Functor(T)>::type,
typename... Ts,
typename Result = typename replace_type<Container<T, Ts...>, T, U>::type
>
Result transform_container(const Container<T, Ts...>& c, Functor &&f)
{
Result ret;
std::transform(std::begin(c), std::end(c), std::inserter(ret, std::end(ret)), f);
return ret;
}
¿Está completo?
El problema con este enfoque es que no es necesariamente seguro. Si está convirtiendo de Container<MyCustomType> a Container<SomethingElse> , es probable que esté bien. Pero al convertir de Container<builtin_type> a Container<SomethingElse> es plausible que otro parámetro de plantilla no se convierta de builtin_type a SomethingElse . Además, contenedores alternativos como std::map o std::array traen más problemas a la fiesta.
Manejar std::map y std::unordered_map no es tan malo. El problema principal es que replace_type necesita reemplazar más tipos. No solo hay un reemplazo T -> U , sino también un reemplazo std::pair<T, T2> -> std::pair<U, U2> . Esto aumenta el nivel de preocupación por los reemplazos de tipo no deseado ya que hay más de un tipo en vuelo. Dicho esto, esto es lo que encontré para trabajar; tenga en cuenta que en las pruebas necesitaba especificar el tipo de retorno de la función lambda que transformó los pares de mi mapa:
// map-like classes are harder. You have to replace both the key and the key-value pair types
// Give a base case replacing a pair type to resolve ambiguities introduced below
template <typename T1, typename T2, typename U1, typename U2>
struct replace_type<std::pair<T1, T2>, std::pair<T1, T2>, std::pair<U1, U2>>
{
using type = std::pair<U1, U2>;
};
// Now the extended case that replaces T1->U1 and pair<T1,T2> -> pair<T2,U2>
template <template <typename...> class K, typename T1, typename T2, typename U1, typename U2, typename... Ks>
struct replace_type<K<T1, T2, Ks...>, std::pair<const T1, T2>, std::pair<const U1, U2>>
{
using type = K<U1, U2,
typename replace_type<
typename replace_type<Ks, T1, U1>::type,
std::pair<const T1, T2>,
std::pair<const U1, U2>
>::type ...
>;
};
¿Qué pasa con std :: array?
El manejo de std::array aumenta el dolor, ya que los parámetros de su plantilla no se pueden deducir en la plantilla anterior. Como señala Jarod42, esto se debe a sus parámetros que incluyen valores en lugar de solo tipos. He llegado parcialmente añadiendo especializaciones e introduciendo un tipo_contenedor auxiliar que extrae T para mí (nota al margen, por Constructor, esto está mejor escrito como el tipo de nombre mucho más typename Container::value_type y funciona para todos los tipos que he discutido aquí). Incluso sin las especializaciones std::array esto me permite simplificar mi plantilla transform_container a lo siguiente (esto puede ser una ganancia incluso sin soporte para std::array ):
template <typename T, size_t N, typename U>
struct replace_type<std::array<T, N>, T, U> { using type = std::array<U, N>; };
// contained_type<C>::type is T when C is vector<T, ...>, set<T, ...>, or std::array<T, N>.
// This is better written as typename C::value_type, but may be necessary for bad containers
template <typename T, typename...>
struct contained_type { };
template <template <typename ... Cs> class C, typename T, typename... Ts>
struct contained_type<C<T, Ts...>> { using type = T; };
template <typename T, size_t N>
struct contained_type<std::array<T, N>> { using type = T; };
template <
typename Container,
typename Functor,
typename T = typename contained_type<Container>::type,
typename U = typename std::result_of<Functor(T)>::type,
typename Result = typename replace_type<Container, T, U>::type
>
Result transform_container(const Container& c, Functor &&f)
{
// as above
}
Sin embargo, la implementación actual de transform_container usa std::inserter que no funciona con std::array . Si bien es posible hacer más especializaciones, voy a dejar esto como un ejercicio de sopa de plantilla para un lector interesado. Yo personalmente elegiría vivir sin soporte para std::array en la mayoría de los casos.
Ver el ejemplo en vivo acumulativo
Divulgación completa: si bien este enfoque fue influenciado por la cita de Ali de la respuesta de Kerrek SB, no logré que eso funcionara en Visual Studio 2013, así que construí la alternativa anterior yo mismo. Muchas gracias a las partes de la respuesta original de Kerrek SB todavía son necesarias, así como a los estímulos y estímulos de Constructor y Jarod42.
Hacer esto en general va a ser bastante difícil.
Primero, considere std::vector<T, Allocator=std::allocator<T>> , y digamos que su functor transforma T->U No solo tenemos que mapear el primer argumento de tipo, sino que realmente deberíamos usar Allocator<T>::rebind<U> para obtener el segundo. Esto significa que necesitamos saber que el segundo argumento es un asignador en primer lugar ... o necesitamos alguna maquinaria para comprobar que tiene una plantilla de miembro de rebind y usarla.
A continuación, considere std::array<T, N> . Aquí tenemos que saber que el segundo argumento debe copiarse literalmente a std::array<U, N> . Quizás podamos tomar parámetros sin tipo sin cambio, volver a vincular los parámetros de tipo que tengan una plantilla de miembro de reenlace, y reemplazar literalmente T con U ?
Ahora, std::map<Key, T, Compare=std::less<Key>, Allocator=std::allocator<std::pair<Key,T>>> . Deberíamos tomar Key sin cambios, reemplazar T por U , tomar Compare sin cambios y volver a vincular el Allocator a std::allocator<std::pair<Key, U>> . Eso es un poco más complicado.
Entonces ... ¿puedes vivir sin esa flexibilidad? ¿Estás contento de ignorar los contenedores asociativos y asumir que el asignador predeterminado está bien para tu contenedor de salida transformado?
La principal dificultad es obtener de alguna manera el Contenedor tipo Container de Conainer<T> . He robado descaradamente el código de la metaprogramación de plantillas: (¿rasgo de?) Diseccionar una plantilla específica en tipos T <T2, T3 N, T4, ...> , en particular, la respuesta de Kerrek SB (la respuesta aceptada), como lo soy no está familiarizado con la metaprogramación de plantillas.
#include <algorithm>
#include <cassert>
#include <type_traits>
// stolen from Kerrek SB''s answer
template <typename T, typename ...>
struct tmpl_rebind {
typedef T type;
};
template <template <typename ...> class Tmpl, typename ...T, typename ...Args>
struct tmpl_rebind<Tmpl<T...>, Args...> {
typedef Tmpl<Args...> type;
};
// end of stolen code
template <typename Container,
typename Func,
typename TargetType = typename std::result_of<Func(typename Container::value_type)>::type,
typename NewContainer = typename tmpl_rebind<Container, TargetType>::type >
NewContainer convert(const Container& c, Func f) {
NewContainer nc;
std::transform(std::begin(c), std::end(c), std::inserter(nc, std::end(nc)), f);
return nc;
}
int main() {
std::vector<int> vi{ 1, 2, 3, 4, 5 };
auto vs = convert(vi, [] (int i) { return std::to_string(i); });
assert( vs == std::vector<std::string>( {"1", "2", "3", "4", "5"} ) );
return 0;
}
He probado este código con gcc 4.7.2 y clang 3.5 y funciona como se esperaba.
Como Yakk señala , sin embargo, hay algunas advertencias con este código: "... ¿Debería su reenlace reemplazar todos los argumentos, o solo el primero? Incierto. ¿Debería reemplazar recursivamente T0 por T1 en los argumentos posteriores? std::map<T0, std::less<T0>> -> std::map<T1, std::less<T1>> ? " También veo trampas con el código anterior (por ejemplo, cómo tratar con diferentes asignadores, ver también la respuesta de Useless ).
Sin embargo, creo que el código anterior ya es útil para casos de uso simple. Si estuviéramos escribiendo una función de utilidad para enviar para impulsar, entonces estaría más motivado para investigar más estos problemas. Pero ya hay una respuesta aceptada, por lo que considero cerrado el caso.
Muchas gracias a Constructor, dyp y Yakk por señalar mis errores / oportunidades perdidas de mejoras.