La fonction std :: transform-like qui retourne le conteneur transformé

Question

Je suis en train de mettre en œuvre une fonction similaire std::transform algorithme, mais au lieu de prendre la sortie itérateur par un argument que je veux créer et retourner un récipient avec de l'transforme des éléments d'entrée.

Disons que c'est nommée transform_container et prend deux arguments: le conteneur et de foncteur. Il doit renvoyer le même type de conteneur mais peut-être paramétrés par un autre type d'élément (le Foncteur pouvez retourner élément de type différent).

Je voudrais utiliser ma fonction comme dans l'exemple ci-dessous:

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.}));

J'ai été en mesure d'écriture deux de deux fonctions, l'une pour std::set et l'autre pour std::vector - qui semblent fonctionner correctement. Ils sont identiques, à l'exception du conteneur typename. Leur code est indiqué ci-dessous.

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;
}

Cependant, quand j'ai essayé de les fusionner en un seul général de la fonction qui fonctionne avec n'importe quel conteneur, j'ai rencontré de nombreux problèmes. L' set et vector sont des modèles de classe, donc mon modèle de fonction doit prendre un modèle de paramètre du modèle. En outre, le décor et le vecteur des modèles ont un nombre différent de paramètres de type qui doit être correctement ajusté.

Quelle est la meilleure façon de généraliser les deux modèles de fonction ci-dessus dans une fonction qui fonctionne avec n'importe quel type de conteneur?

Answer 1

Cas les plus simples: faire correspondre les types de conteneurs

Pour le cas simple où l'entrée type correspond au type de sortie (que j'ai sinced réalisée n'est pas ce que vous demandez à propos de), remonter d'un niveau plus élevé. Au lieu de spécifier le type T que votre conteneur utilise, et en essayant de se spécialiser sur un vector<T>, etc., il suffit de spécifier le type du conteneur lui-même:

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;
}

Plus de complexité: compatible avec types de valeur

Puisque vous voulez essayer de changer le type d'élément stocké par le conteneur, vous aurez besoin d'utiliser un modèle de paramètre du modèle, et de modifier l' T que le retour de l'conteneur utilise.

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;
}

Ce que de l'incompatibilité des types de valeur?

Cela ne nous amène à moitié là. Il fonctionne très bien avec une transformation de l' signed de unsigned mais lorsque résolu avec T=int et S=std::string, et la manipulation d'ensembles, il tente d'instancier std::set<std::string, std::less<int>, ...> et n'a donc pas à compiler.

Pour résoudre ce problème, nous voulons prendre un ensemble arbitraire de paramètres et de remplacer les occurrences de T avec U, même si elles sont les paramètres à d'autres paramètres du modèle. Ainsi, std::set<int, std::less<int>> devrait devenir std::set<std::string, std::less<std::string>>, et ainsi de suite. Cela implique une certaine personnalisé modèle de méta-programmation, comme suggéré par d'autres réponses.

Modèle de métaprogrammation à la rescousse

Nous allons créer un modèle, nommez - replace_type, et de la convertir T de U, et K<T> de K<U>. Laissez-moi d'abord traiter le cas général. Si ce n'est pas basé sur un modèle de type, et il n'est pas adapté T, son type doit demeurer K:

template <typename K, typename ...>
struct replace_type { using type = K; };

Puis d'une spécialisation. Si ce n'est pas basé sur un modèle de type, et il ne correspond T, son type est devenue U:

template <typename T, typename U>
struct replace_type<T, T, U> { using type = U; };

Et enfin une étape récursive pour gérer les paramètres basés sur des modèles types. Pour chaque type basé sur un modèle du type de paramètres, de remplacer les types en conséquence:

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 ...>;
};

Et enfin la mise à jour transform_container utilisation 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-ce terminé?

Le problème avec cette approche est qu'il n'est pas nécessairement sans danger. Si vous êtes à la conversion de Container<MyCustomType> de Container<SomethingElse>, il est probable amende. Mais lors de la conversion de Container<builtin_type> de Container<SomethingElse> il est plausible qu'un autre paramètre de modèle ne devrait pas être converti à partir d' builtin_type de SomethingElse. En outre, de l'alternance des conteneurs comme std::map ou std::array apporter plus de problèmes à la partie.

Manutention std::map et std::unordered_map n'est pas trop mauvais. Le principal problème est qu' replace_type besoin de remplacer plusieurs types. Non seulement est-il un T -> U de remplacement, mais également une std::pair<T, T2> -> std::pair<U, U2> de remplacement. Cela augmente le niveau de préoccupation pour les indésirables de type remplacements comme il n'y a plus qu'un seul type de vol. Cela dit, voici ce que j'ai trouvé pour travailler; à noter que dans les essais j'ai besoin de spécifier le type de retour de la fonction lambda qui a transformé ma carte de paires:

// 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'en est std::array?

Manutention std::array s'ajoute à la douleur, comme son modèle les paramètres ne peuvent pas être déduites dans le modèle ci-dessus. Comme Jarod42 notes, c'est en raison de ses paramètres, y compris les valeurs, plutôt que de simplement les types. J'ai pris de cours par l'ajout de spécialisations et de l'introduction d'un helper contained_type que des extraits T pour moi (note de côté, par le Constructeur, c'est mieux écrit que le beaucoup plus simple typename Container::value_type et fonctionne pour tous les types que j'ai parlé ici). Même sans l' std::array spécialisations cela me permet de simplifier mon transform_container modèle à la suivante (cela peut être une victoire, même sans l'appui d' 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
}

Toutefois, l'implémentation actuelle de l' transform_container utilise std::inserter qui ne fonctionne pas avec std::array. Alors qu'il est possible de faire plus de spécialisations, je vais laisser cela comme un modèle de la soupe de l'exercice pour un lecteur intéressé. J'ai personnellement choisi de vivre sans l'appui d' std::array dans la plupart des cas.

Afficher le cumul des vis par exemple

---

La divulgation complète: bien que cette approche a été influencé par Ali citant des Kerrek SB réponse, je n'ai pas réussi à obtenir que cela fonctionne dans Visual Studio 2013, de sorte que j'ai construit au-dessus de rechange moi-même. Merci beaucoup pour les pièces de Kerrek SB réponse originale à cette question sont encore nécessaires, ainsi que pour les pousser et les encouragements de Constructeur et Jarod42.

Answer 2

Quelques remarques

La méthode suivante permet de transformer des conteneurs de n'importe quel type de la bibliothèque standard (il y a un problème avec std::array, voir ci-dessous). La seule exigence pour le conteneur, c'est qu'il doit utiliser la valeur par défaut std::allocator classes, std::less, std::equal_to et std::hash de la fonction des objets. Nous avons donc 3 groupes de conteneurs de la bibliothèque standard:

1. Conteneurs avec un non-modèle par défaut paramètre de type (type de valeur):

   • std::vector, std::deque, std::list, std::forward_list, [std::valarray]
   • std::queue, std::priority_queue, std::stack
   • std::set, std::unordered_set

2. Conteneurs avec deux non-modèle par défaut des paramètres de type (type de clé et le type de valeur):

   • std::map, std::multi_map, std::unordered_map, std::unordered_multimap

3. Conteneur avec deux non-paramètres par défaut: paramètre de type (type de valeur) et non de type paramètre (taille):

   • std::array

La mise en œuvre

convert_container classe d'aide convertir les types connus d'entrée type de conteneur (InputContainer) et la valeur de sortie de type (OutputType) pour le type de conteneur de sortie(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;

transform_container fonction de mise en œuvre:

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;
}

Exemple d'utilisation

Voir l' exemple vivant avec les conversions suivantes:

• std::vector<int> -> std::vector<std::string>,
• std::set<int> -> std::set<double>,
• std::map<int, char> -> std::map<char, int>.

Problèmes

std::array<int, 3> -> std::array<double, 3> conversion ne se compile pas, car std::array n'ont pas insert méthode qui est nécessaire en raison d' std::inserter). transform_container fonction ne devrait pas travailler aussi pour cette raison avec les conteneurs suivants: std::forward_list, std::queue, std::priority_queue, std::stack, [std::valarray].

Answer 3

Ce faisant , en général, va être assez dur.

Tout d'abord, considérons std::vector<T, Allocator=std::allocator<T>>, et disons que votre foncteur transforme T->U. Non seulement nous avons à la carte le premier type d'argument, mais vraiment, nous devrions utiliser Allocator<T>::rebind<U> pour le second. Cela signifie que nous avons besoin de connaître le second argument est un allocateur de la première place ... ou nous avons besoin de quelques machines pour vérifier qu'il a un rebind membre modèle et l'utiliser.

Ensuite, envisager std::array<T, N>. Ici, nous avons besoin de connaître le deuxième argument doit être copié littéralement à notre - std::array<U, N>. Nous pouvons peut-être prendre le non-type de paramètres, sans changement, de relier les paramètres de type qui ont une reliaison membre de modèle, et de le remplacer littérale T avec U?

Maintenant, std::map<Key, T, Compare=std::less<Key>, Allocator=std::allocator<std::pair<Key,T>>>. Nous devrions prendre en Key sans modifier, de remplacer T avec U, prennent Compare sans changement et relier Allocator de std::allocator<std::pair<Key, U>>. C'est un peu plus compliqué.

Alors ... pouvez-vous vivre sans un de la flexibilité? Êtes-vous heureux d'ignorer les conteneurs associatifs et d'assumer la valeur par défaut de l'allocateur est ok pour votre transformé conteneur de sortie?

Answer 4

La difficulté majeure est d'obtenir en quelque sorte le type de conteneur Container de Conainer<T>. J'ai volé sans vergogne le code à partir du modèle de la métaprogrammation: (trait?) la dissection d'un modèle spécifié dans les types de T<T2,T3 N,T4, ...>, en particulier, Kerrek SB réponse (la accepté de répondre), comme je ne suis pas familier avec le modèle de la métaprogrammation.

#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;
}

J'ai testé ce code avec gcc 4.7.2 et clang 3.5 et fonctionne comme prévu.

Comme Yakk souligne, il ya quelques mises en garde avec ce code, bien que: "... si votre réassocier remplacer tous les arguments, ou juste le premier? Incertaine. Faut-il remplacer de manière récursive T0 avec T1 plus tard arguments? Ie std::map<T0, std::less<T0>> -> std::map<T1, std::less<T1>>?" Je vois aussi des pièges avec le code ci-dessus (par exemple, la façon de traiter avec différents allocateurs, voir aussi Inutile de réponse).

Néanmoins, je crois que le code ci-dessus est déjà utile pour des cas d'utilisation simples. Si nous avons écrit une fonction d'utilité à être soumis à coup de pouce, je serais plus motivé pour étudier ces questions plus en détail. Mais il y a déjà accepté de réponse, je considère que l'affaire est close.

---

Merci beaucoup pour le Constructeur, dpj et Yakk pour souligner mes erreurs / de manquer des occasions d'amélioration.