How to combine back_inserter with a transformation, C++

Question

How can I wrap an OutputIterator such as back_inserter_iterator with a transformation? Consider

std::vector<double> xx;
std::vector<double> yy;
std::vector<double> diff;
auto ba = std::back_inserter(diff);
std::set_difference(xx.begin(), xx.end(), yy.begin(), yy.end(), ba);

I would like to apply a free function f(double) or g(std::vector<double>::iterator) before pushing back to the diff vector:

Specifically, how can I store the addresses of the diff elements (or iterators) instead of the elements themeselves.

std::vector<double&> diff;
auto baAdr = ??? std::back_inserter( ??? (diff)); 
std::set_difference(xx.begin(), xx.end(), yy.begin(), yy.end(), baAdr);

For performance reasons (the real data is big) I do not want to construct a temporary vector and std::transform from it. It would also not work for non-copyable, movable types.

I can use boost.

Answer 1

With boost::function_output_iterator:

#include <vector>
#include <algorithm>
#include <boost/function_output_iterator.hpp>

int main() 
{
    std::vector<double> xx;
    std::vector<double> yy;
    std::vector<const double*> diff;  // const pointers, or else you
                                      // need a const_cast in lambda

    std::set_difference(xx.begin(), xx.end(), yy.begin(), yy.end(),
        boost::make_function_output_iterator(
            [&diff](const double& d) { diff.push_back(&d); }
        )
    );
}

Answer 2

There's probably something built in to boost, but here's my hacky attempt to write my own iterator:

template <typename T, typename FN>
struct transform_iterator {
    transform_iterator(T &t, FN fn)
      : _t{t}
      , _fn{std::move(fn)} { }

    transform_iterator<T, FN>& operator * () { return *this; }

    transform_iterator<T, FN>& operator ++ () { return *this; }

    template <typename V>
    transform_iterator<T, FN>& operator = (V const &v) {
        _t.push_back(_fn(v));
        return *this;
    }

    T &_t;
    FN _fn;
};

This will take a function and execute it whenever something tries to assign to the iterator (I think this is how things like back_inserter usually work). A trivial helper function can create the iterators:

template <typename T, typename FN>
auto make_transform_iterator(T &t, FN fn) {
    return transform_iterator<T, FN>{t, std::move(fn)};
};

Lastly, iterator_traits needs to be specialized so transform_iterator will work with algorithms.

namespace std {
    template <typename T, typename FN>
    struct iterator_traits<transform_iterator<T, FN>> {
        using value_type = typename T::value_type;
    };
}

There are more types that need to be set in iterator_traits, but this was sufficient for my testing; your mileage will vary.

My main looks like this:

int main() {
    std::vector<int> xx{1, 2, 3};
    std::vector<int> yy{1, 3, 5};
    std::vector<int> diff;

    auto ba = make_transform_iterator(diff, [](auto v) { return v + 10; });
    std::set_difference(std::begin(xx), std::end(xx),
                        std::begin(yy), std::end(yy),
                        ba);
    for(auto const &v: diff) {
        std::cout << v << '\n';
    }
    return 0;
}

You could expand this to work with generic output iterators instead of just types that support push_back.