The std::transform-like function that returns transformed container
Solution 1
Simplest cases: matching container types
For the simple case where the input type matches the output type (which I've since realized is not what you're asking about) go one level higher. Instead of specifying the type T
that your container uses, and trying to specialize on a vector<T>
, etc., just specify the type of the container itself:
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;
}
More complexity: compatible value types
Since you want to try to change the item type stored by the container, you'll need to use a template template parameter, and modify the T
to that which the returned container uses.
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;
}
What of incompatible value types?
This only gets us partway there. It works fine with a transform from signed
to unsigned
but, when resolving with T=int
and U=std::string
, and handling sets, it tries to instantiate std::set<std::string, std::less<int>, ...>
and thus doesn't compile.
To fix this, we want to take an arbitrary set of parameters and replace instances of T
with U
, even if they are the parameters to other template parameters. Thus std::set<int, std::less<int>>
should become std::set<std::string, std::less<std::string>>
, and so forth. This involves some custom template meta programming, as suggested by other answers.
Template metaprogramming to the rescue
Let's create a template, name it replace_type
, and have it convert T
to U
, and K<T>
to K<U>
. First let's handle the general case. If it's not a templated type, and it doesn't match T
, its type shall remain K
:
template <typename K, typename ...>
struct replace_type { using type = K; };
Then a specialization. If it's not a templated type, and it does match T
, its type shall become U
:
template <typename T, typename U>
struct replace_type<T, T, U> { using type = U; };
And finally a recursive step to handle parameters to templated types. For each type in a templated type's parameters, replace the types accordingly:
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 ...>;
};
And finally update transform_container
to use 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;
}
Is this complete?
The problem with this approach is it is not necessarily safe. If you're converting from Container<MyCustomType>
to Container<SomethingElse>
, it's likely fine. But when converting from Container<builtin_type>
to Container<SomethingElse>
it's plausible that another template parameter shouldn't be converted from builtin_type
to SomethingElse
. Furthermore, alternate containers like std::map
or std::array
bring more problems to the party.
Handling std::map
and std::unordered_map
isn't too bad. The primary problem is that replace_type
needs to replace more types. Not only is there a T
-> U
replacement, but also a std::pair<T, T2>
-> std::pair<U, U2>
replacement. This increases the level of concern for unwanted type replacements as there's more than a single type in flight. That said, here's what I found to work; note that in testing I needed to specify the return type of the lambda function that transformed my map's pairs:
// 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 ...
>;
};
What about std::array?
Handling std::array
adds to the pain, as its template parameters cannot be deduced in the template above. As Jarod42 notes, this is due to its parameters including values instead of just types. I've gotten partway by adding specializations and introducing a helper contained_type
that extracts T
for me (side note, per Constructor this is better written as the much simpler typename Container::value_type
and works for all types I've discussed here). Even without the std::array
specializations this allows me to simplify my transform_container
template to the following (this may be a win even without support for 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
}
However the current implementation of transform_container
uses std::inserter
which does not work with std::array
. While it's possible to make more specializations, I'm going to leave this as a template soup exercise for an interested reader. I would personally choose to live without support for std::array
in most cases.
View the cumulative live example
Full disclosure: while this approach was influenced by Ali's quoting of Kerrek SB's answer, I didn't manage to get that to work in Visual Studio 2013, so I built the above alternative myself. Many thanks to parts of Kerrek SB's original answer are still necessary, as well as to prodding and encouragement from Constructor and Jarod42.
Solution 2
Some remarks
The following method allows to transform containers of any type from the standard library (there is a problem with std::array
, see below). The only requirement for the container is that it should use default std::allocator
classes, std::less
, std::equal_to
and std::hash
function objects. So we have 3 groups of containers from the standard library:
-
Containers with one non-default template type parameter (type of value):
-
std::vector
,std::deque
,std::list
,std::forward_list
, [std::valarray
] -
std::queue
,std::priority_queue
,std::stack
-
std::set
,std::unordered_set
-
-
Containers with two non-default template type parameters (type of key and type of value):
-
std::map
,std::multi_map
,std::unordered_map
,std::unordered_multimap
-
-
Container with two non-default parameters: type parameter (type of value) and non-type parameter (size):
std::array
Implementation
convert_container
helper class convert types of known input container type (InputContainer
) and output value type (OutputType
) to the type of the output container(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
function implementation:
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;
}
Example of use
See live example with the following conversions:
-
std::vector<int> -> std::vector<std::string>
, -
std::set<int> -> std::set<double>
, -
std::map<int, char> -> std::map<char, int>
.
Problems
std::array<int, 3> -> std::array<double, 3>
conversion doesn't compile because std::array
haven't insert
method which is needed due to std::inserter
). transform_container
function shouldn't also work for this reason with the following containers: std::forward_list
, std::queue
, std::priority_queue
, std::stack
, [std::valarray
].
Solution 3
Doing this in general is going to be pretty hard.
First, consider std::vector<T, Allocator=std::allocator<T>>
, and let's say your functor transforms T->U
. Not only do we have to map the first type argument, but really we ought to use Allocator<T>::rebind<U>
to get the second. This means we need to know the second argument is an allocator in the first place ... or we need some machinery to check it has a rebind
member template and use it.
Next, consider std::array<T, N>
. Here we need to know the second argument should be copied literally to our std::array<U, N>
. Perhaps we can take non-type parameters without change, rebind type parameters which have a rebind member template, and replace literal T
with U
?
Now, std::map<Key, T, Compare=std::less<Key>, Allocator=std::allocator<std::pair<Key,T>>>
. We should take Key
without change, replace T
with U
, take Compare
without change and rebind Allocator
to std::allocator<std::pair<Key, U>>
. That's a little more complicated.
So ... can you live without any of that flexibility? Are you happy to ignore associative containers and assume the default allocator is ok for your transformed output container?
Solution 4
The major difficulty is to somehow get the container type Container
from Conainer<T>
. I have shamelessly stolen the code from template metaprogramming: (trait for?) dissecting a specified template into types T<T2,T3 N,T4, ...>, in particular, Kerrek SB's answer (the accepted answer), as I am not familiar with template metaprogramming.
#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;
}
I have tested this code with gcc 4.7.2 and clang 3.5 and works as expected.
As Yakk points out, there are quite a few caveats with this code though: "... should your rebind replace all arguments, or just the first one? Uncertain. Should it recursively replace T0
with T1
in later arguments? Ie std::map<T0, std::less<T0>>
-> std::map<T1, std::less<T1>>
?" I also see traps with the above code (e.g. how to deal with different allocators, see also Useless' answer).
Nevertheless, I believe the above code is already useful for simple use cases. If we were writing a utility function to be submitted to boost, then I would be more motivated to investigate these issues further. But there is already an accepted answer so I consider the case closed.
Many thanks to Constructor, dyp and Yakk for pointing out my mistakes / missed opportunities for improvements.
Related videos on Youtube
Michał W. Urbańczyk
Updated on June 30, 2022Comments
-
Michał W. Urbańczyk almost 2 years
I'm trying to implement a function similar to
std::transform
algorithm but instead of taking the output iterator by an argument I want to create and return a container with transformed input elements.Let's say that it's named
transform_container
and takes two arguments: container and functor. It should return the same container type but possibly parametrized by a different element type (the Functor can return element of different type).I'd like to use my function as in the example below:
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.}));
I was able two write two functions — one for
std::set
and one forstd::vector
— that seem to work properly. They are identical, except of the container typename. Their code is listed below.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; }
However, when I attempted to merge them into a single general function that works with any container, I encountered numerous issues. The
set
andvector
are class templates, so my function template must take a template template parameter. Moreover, set and vector templates have a different number of type parameters that needs to be properly adjusted.What is the best way to generalize the two function templates above into a function that works with any compatible container type?
-
Constructor almost 10 yearsUse variadic templates.
-
Michał W. Urbańczyk almost 10 years@Constructor Well, I have tried to no avail. Perhaps I have missed something or got tricked by the syntax — if you know how to do this, please show me how. :) I can accept a template template parameter that is parametrized by the variadic number of parameters but then I don't know how to express the returned type. The usually hidden default container parameters (like allocator) needs to be expressed explicitly and appropriately adjusted — I don't know how to do this in a generic manner.
-
Constructor almost 10 yearsYes, I understand now. I'll think about your problem.
-
Yakk - Adam Nevraumont almost 10 yearsInstead of returning a container of modified type (which, as you'll note below, cannot reasonably be done), how about returning a container-builder that, when converted to a container, builds it? It prevents
auto x = blah()
, butstd::vector<double> y = blah()
works. -
Michał W. Urbańczyk almost 10 years@Yakk Not having to explicitly state the resulting container type was one of the reasons why I wanted to write the
transform_container
function. That way I not only save on typing but also I am able to pass the resulting container as an argument in a function call (and possible have template parameter deduction work on it). The approach you're suggesting has its own merits but I prefer the solutions proposed below — reasonable or not, they provide the functionality I was seeking for. :)
-
-
Constructor almost 10 years
transform_container
can return a container which is parametrized by another type. It is a key point in the current problem. -
Constructor almost 10 yearsThere is an example of using
transform_container
function in the question.std::vector<int>
transforms tostd::vector<std::string>
in it andstd::set<int>
transforms tostd::set<double>
. -
Michael Urman almost 10 years@Constructor Ah, I totally missed that part; I tunnel-visioned on the difference between set and vector, not int and double. I'll revisit.
-
Constructor almost 10 yearsWhy do you set
NewType
template parameter explicitly instead of obtaining it using a functor as OP does in his answer? -
Ali almost 10 years@Constructor Yes, thanks, I have fixed that. By the way,
std::result_of
gives a more readable way of achieving the same thing. -
dyp almost 10 years
std::inserter(nc, std::end(nc))
Why not aback_inserter
? -
Yakk - Adam Nevraumont almost 10 yearsAdd some
template<class T>using foo_t=typename foo<T>::type
to reduce the noise of your return type (tofoo_t<T>
fromtypename foo<T>::type
) -
Yakk - Adam Nevraumont almost 10 yearsSecond, should your rebind replace all arguments, or just the first one? Uncertain. Should it recursively replace
T0
withT1
in later arguments? Iestd::map<T0, std::less<T0>>
->std::map<T1, std::less<T1>>
? hmm -
Jarod42 almost 10 yearsAnd it is not complete: it doesn't handle container like
std::array<T, N>
^_^. -
Michael Urman almost 10 years@Jarod42: I can confirm that, but I don't understand why it can't deduce
const Container<T,Ts...>&
from e.g.std::array<int, 5>
. Researching... -
Jarod42 almost 10 years
5
is not a type but a value. -
Constructor almost 10 years
typename U = std::result_of<Functor(T)>::type
: you forgottypename
keyword. -
Michael Urman almost 10 years@Constructor: I wonder why Visual Studio didn't flag that one. It compiles and works there without it, but did require
typename
on the customreplace_type<...>::type
. -
Constructor almost 10 yearsvc++ allows such non-standard relaxations.
-
Michael Urman almost 10 years@Jarod42 I ended up punting on the
std::array
support. I got the template half working, but it's no longer fully general and I didn't feel like implementing an alternative tostd::inserter
. -
Michał W. Urbańczyk almost 10 yearsThanks! Not supporting
array
is ok, it's quite different from other containers. However, I wasn't able to compile your code with VS 2013, it says itcould not deduce template argument for 'OutputContainer'
. Might be a compiler bug, their C++11 support is quirky — I'll look closer into this tomorrow. -
Michael Urman almost 10 yearsOh man, did I really just implement the long-way around to get
Container::value_type
? When all you have is a template... -
Constructor almost 10 years@Yakk
back_inserter
requirespush_back
method in the passed container.std::inserter
is more appropriate here, because it requiresinsert
method (so it is possible to work withstd::map
,std::set
etc.). -
Constructor almost 10 years@MichałW.Urbańczyk It looks like a bug in vc++.
-
Constructor almost 10 years@MichaelUrman As I can see, yes. :-) But it was not so long and interesting enough, isn't it?
-
Ali almost 10 years@dyp
std::back_inserter
would not work withstd::set
for example. Yes, the missing&
at the parameter passing was a silly typo, fixed, thanks! -
Ali almost 10 years@Yakk Thanks, I reduced the verbosity of the template functions. Your second point is completely valid, I added that to the answer; however, I am no longer motivated to fix those cases. Although it would be nice to have something similar in boost.
-
Michael Urman almost 10 yearsI'm glad I did it, if only so next time maybe I'll remember the simple way. But your post shows I'm not done yet; I'm still trying to figure out how to handle both
std::map
andstd::unordered_map
somewhat generically with my approach. Ah, yours handles it by only specifying the first two template parameters, so default allocators and such! -
Constructor almost 10 years@MichaelUrman Yes, you are right, my solution works with all standard containers (
convert_container
template works even withstd::array
container). I'm now editing my answer to add some explanations. -
Yakk - Adam Nevraumont almost 10 yearsDoes this need a specialization for allocators -- is the right way to turn
allocator<T>
into an allocator forU
isallocator<T>::rebind<U>
orallocator<U>
? -
Constructor almost 10 years@Yakk Are these ways not equivalent? And you possibly meant
allocator<T>::rebind<U>::other
. -
Michael Urman almost 10 years@Yakk Good question. I'm not certain, but I think
rebind
was for simplicity of reusing allocators, particularly before variadic templates (see Why is allocator::rebind necessary?). But if a poorly written allocator could somehow require usingrebind
, then further specialization could be required. -
ildjarn almost 10 yearsYou don't need any complex alternative to
std::inserter
forstd::array<T, N>
, just use aT*
initialized fromstd::array<>::data()
. A pointer is a valid random-access iterator, after all. -
Michael Urman almost 10 years@ildjarn Good call; it's not
std::inserter
that needs to be specialized; it's the code that currently calls it. Any thoughts on whether it's better to create a helper, or to offer an overload totransform_container
? (BTWstd::transform(std::begin(c), std::end(c), &ret[0], f)
in VS 2013 generates a C4996 warning that this call relies on the caller to check that the passed values are correct. Which they are, but I hate triggering this warning.) -
ildjarn almost 10 years@MichaelUrman : A helper function for sure, with two overloads – one general one that uses
std::inserter
, and one overload forstd::array<>
that returnsdata()
. 8ish lines of code total, very painless. -
Michał W. Urbańczyk almost 10 years@Constructor I've checked why the VS 2013 complains — it requires the default parameters to be explicitly listed for a template template parameter usage. GCC accepts the code, reduced example is at link. I'm not sure what is the standard-complaint behavior here. There is question about that link with a statement that default parameters "have to" be explicitly listed but I've seen no reference to standard.
-
Constructor almost 10 years@MichałW.Urbańczyk Your short code sample compiles with gcc 4.8.1 and clang 3.4. I have looked through the 14th chapter of the standard ("Templates"), but didn't find the exact place where such situation is described. I think we should ask a question about this problem.
-
Michał W. Urbańczyk almost 10 years@Constructor Thanks for advice, I just asked the question: stackoverflow.com/q/24017466/2617356