The C++20 ranges library come with the ability to transform a view; that is, to provide a unary function that is applied to each element of a view, producing a new view.<\/p>\n
std::array<int, 2> a = { 99, 42 };\r\n\r\n\/\/ This range reports values that are one larger than the values\r\n\/\/ in an array. The array values are unchanged.\r\nauto r = a |\r\n std::ranges::views::transform([](int v) { return v + 1; });\r\n\r\n\/\/ This creates a vector from the range\r\nstd::vector v(r.begin(), r.end());\r\n\r\n\/\/ The resulting vector is { 100, 43 }\r\n<\/pre>\nBut what if your code base isn’t ready to move to C++20 yet? For example, you might be a library that wants to support C++17 or even C++14.<\/p>\n
You can take the original iterator and wrap it inside another iterator that overrides the *<\/code> operator so that it applies a transformation to the value before returning it. Note that our transforming iterator cannot support the -><\/code> operator since there is no value object we can return a pointer to; our value is generated on demand. Fortunately, the standard permits us to omit -><\/code> support, provided we define pointer<\/code> as void<\/code>.<\/p>\ntemplate<typename Inner>\r\nstruct Wrap\r\n{\r\n Wrap(Inner const& inner) :\r\n m_inner(inner) {}\r\n Inner m_inner;\r\n};\r\n\r\ntemplate<typename It, typename Transformer>\r\nclass transform_iterator : Wrap<Transformer>\r\n{\r\n It m_it;\r\npublic:\r\n transform_iterator(It const& it,\r\n Transformer const& transformer) :\r\n m_it(it),\r\n Wrap<Transformer>(transformer) {}\r\n\r\n \/\/ copy constructors and assignment operators defaulted\r\n\r\n using difference_type = typename\r\n std::iterator_traits<It>::difference_type;\r\n using value_type = typename std::invoke_result<\r\n Transformer, It>::type;\r\n using pointer = void;\r\n using reference = void;\r\n using iterator_category = std::input_iterator_tag;\r\n\r\n bool operator==(transform_iterator const& other)\r\n { return m_it == other.m_it; }\r\n bool operator!=(transform_iterator const& other)\r\n { return m_it != other.m_it; }\r\n\r\n auto operator*() const { return (*this)(*m_it); }\r\n\r\n auto operator++() { ++m_it; return *this; }\r\n auto operator++(int)\r\n { auto prev = *this; ++m_it; return prev; }\r\n};\r\n\r\n\/\/ For C++14 (no CTAD)\r\ntemplate<typename It, typename Transformer>\r\nauto make_transform_iterator(\r\n It const& it, Transformer const& transformer)\r\n{\r\n return transform_iterator<It, Transformer>\r\n (it, transformer);\r\n}\r\n<\/pre>\nWe can use this transforming iterator like this:<\/p>\n
std::array<int, 2> a = { 99, 42 };\r\n\r\nauto transformer = [](int v) { return v + 1; };\r\n\r\n\/\/ This creates a vector from the array, applying\r\n\/\/ a transformation to each value\r\nstd::vector v(\r\n transform_iterator(a.begin(), transformer),\r\n transform_iterator(a.end(), transformer));\r\n\r\n\/\/ If C++14 (no CTAD)\r\nstd::vector<int> v(\r\n transform_iterator(a.begin(), transformer),\r\n transform_iterator(a.end(), transformer));\r\n\r\n\/\/ The resulting vector is { 100, 43 }\r\n<\/pre>\nThe transformation can even change the type:<\/p>\n
std::array<int, 2> a = { 99, 42 };\r\n\r\nauto transformer = [](int v)\r\n { return std::make_pair(v + 1, v); };\r\n\r\n\/\/ This creates a map from the array\r\nstd::map m(\r\n transform_iterator(a.begin(), transformer),\r\n transform_iterator(a.end(), transformer));\r\n\r\n\/\/ If C++14 (no CTAD)\r\nstd::map<int, int> m(\r\n transform_iterator(a.begin(), transformer),\r\n transform_iterator(a.end(), transformer));\r\n\r\n\/\/ The resulting map is\r\n\/\/ m[100] = 99\r\n\/\/ m[43] = 42\r\n<\/pre>\nThere are some non-obvious pieces of the above transform_We want to accept not just lambdas as transformers, but any Callable. That means that we use std::invoke<\/code> to invoke the transformer on the wrapped iterator. This allows transformers to be function pointers, member function pointers, pointers to member variables, lambdas, or any other class with a public operator()<\/code>. For example:<\/p>\nstruct S\r\n{\r\n int value;\r\n int ValuePlusOne() { return value + 1; };\r\n};\r\n\r\nint ValueMinusOne(S const& s)\r\n{\r\n return s.value - 1;\r\n}\r\n\r\nvoid example()\r\n{\r\n std::array<S, 2> a { 99, 42 };\r\n\r\n \/\/ v1 = { 99, 42 }; - pointer to data member\r\n std::vector<int> v1(\r\n transform_iterator(a.begin(), &S::value),\r\n transform_iterator(a.end(), &S::value));\r\n\r\n \/\/ v2 = { 100, 43 }; - pointer to member function\r\n std::vector<int> v2(\r\n transform_iterator(a.begin(), &S::ValuePlusOne),\r\n transform_iterator(a.end(), &S::ValuePlusOne));\r\n\r\n \/\/ v3 = { 98, 41 }; - pointer to free function\r\n std::vector<int> v3(\r\n transform_iterator(a.begin(), &ValueMinusOne),\r\n transform_iterator(a.end(), &ValueMinusOne));\r\n}\r\n<\/pre>\nThe transform_Transformer<\/code>. This is a space optimization that takes advantage of empty base optimization (EBO): If the Transformer<\/code> is an empty class, then the Wrapped<Transformer><\/code> will also be an empty class, and empty base classes are permitted to occupy zero bytes.\u00b9 (Normally, objects cannot be of size zero.) This means that a transform_We wrap the Transformer<\/code> inside a class because base classes must be classes, but the Transformer<\/code> might not be a class, as we noted above.<\/p>\nA transforming iterator is handy for populating a std::map<\/code> because all three of the major implementations of the C++ standard library optimize the two-iterator insert()<\/code> overload for the case where the items are inserted in increasing key order at the end of map.\u00b2<\/p>\nIn the case where you have two versions of a function, one of which takes a range and another of which takes items one at a time, you can avoid the need for a transforming iterator by turning the problem around: Instead of producing a range of transformed iterators to pass to function, you produce an output iterator that calls the single-parameter version of the function.<\/p>\n
std::vector<int> v;\r\nstd::transform(a.begin(), a.end(), std::back_inserter(v),\r\n transformer);\r\n\r\nstd::map<int, int> m;\r\nstd::transform(a.begin(), a.end(), std::inserter(m, m.end()),\r\n transformer);\r\n<\/pre>\nThis is simpler but has its downsides:<\/p>\n
\n- You lose CTAD, since the compiler cannot infer the template type parameters from the constructor.<\/li>\n
- Repeated single-element function calls may be less efficient than a bulk operation.<\/li>\n<\/ul>\n
For example, inserting a transformed range into a vector is linear in the number of elements inserted plus the number of elements after the insertion point. In other words, inserting n<\/var> new elements in front of k<\/var> existing elements is O<\/var>(n<\/var> + k<\/var>) if you do it in a single call to insert<\/code>:<\/p>\n\/\/ Bulk insert after the first element\r\n\/\/ This takes O(a.size() + v.size() - 1) =\r\n\/\/ O(a.size() + v.size())\r\nv.insert(v.begin() + 1,\r\n transform_iterator(a.begin(), transformer),\r\n transform_iterator(a.end(), transformer));\r\n<\/pre>\nIf you insert one element at a time, then you pay the k<\/var> each time, which results in a running time of n<\/var>\u2009O<\/var>(1 + k<\/var>) = O<\/var>(n<\/var> + nk<\/var>), an extra cost of O<\/var>(nk<\/var>).<\/p>\n\/\/ One-at-a-time insert after the first element\r\n\/\/ This takes O(a.size() + a.size() * (v.size() - 1)) =\r\n\/\/ O(a.size() * v.size())\r\nv.insert(v.begin() + 1,\r\n transform_iterator(a.begin(), transformer),\r\n transform_iterator(a.end(), transformer));\r\n<\/pre>\nBonus chatter<\/b>: The Boost library comes with an implementation of transform_\u00b9 There are other things that could prevent the empty base optimization, but they do not apply here.<\/p>\n
\u00b2 In other words, it’s as if the ranged insertion method were written as<\/p>\n
template&typename Iterator>\r\nvoid insert(Iterator first, Iterator last)\r\n{\r\n for (; first != last; ++first) {\r\n insert(end(), *first);\r\n }\r\n}\r\n<\/pre>\n