7
\$\begingroup\$

The question is follow-up to preprocessing iterator.

Specification:

Given Functor functor (which is Callable) and Iterator iterator (which is OutputIterator), iterator is created that behaves the same as underlying iterator, except it applies a functor to the incoming data and then passes the result into underlying iterator. Input type of the Functor is not required to match value type of the Iterator, but the input should be only single parameter (even defaulted arguments are not allowed).

Code:

#ifndef SUNRISE_TRANSFORM_ITERATOR_HPP
#define SUNRISE_TRANSFORM_ITERATOR_HPP

#include <iterator>

namespace shino
{
    template<typename Functor, typename Iterator>
    class transform_iterator :
            public std::iterator<std::output_iterator_tag,
                    void, void, void, void>
    {
        Functor functor;
        Iterator iterator;
    public:
        transform_iterator(const Functor& f, const Iterator& it) :
                functor(f),
                iterator(it)
        {}

        transform_iterator(Functor&& f, Iterator&& it) :
                functor(f),
                iterator(it)
        {}

        class proxy
        {
            friend class transform_iterator;

            Iterator &iterator;
            Functor &f;
        public:

            template <typename U>
            proxy &operator=(U&& value)
            {
                *iterator = f(std::forward<U>(value));
                return *this;
            }

        private:
            proxy(Iterator &it, Functor &functor) :
                    iterator(it),
                    f(functor)
            {}
        };

        proxy operator*()
        {
            return proxy(iterator, functor);
        }

        transform_iterator &operator++()
        {
            ++iterator;
            return *this;
        }

        transform_iterator operator++(int)
        {
            auto copy = *this;
            ++iterator; //might exhibit different behavior sometimes
            return copy;
        }

        const Iterator& internal_iterator() const
        {
            return iterator;
        }

        const Functor& internal_functor() const
        {
            return functor;
        }

        void swap(transform_iterator& other)
        {
            using std::swap;
            swap(other.functor, functor);
            swap(other.iterator, iterator);
        }
    };

    template<typename Functor, typename Iterator>
    bool operator==(const transform_iterator<Functor, Iterator>& lhs,
                   const transform_iterator<Functor, Iterator>& rhs)
    {
        return lhs.internal_iterator() == rhs.internal_iterator();
    }

    template <typename Functor, typename Iterator>
    bool operator!=(const transform_iterator<Functor, Iterator>& lhs,
                    const transform_iterator<Functor, Iterator>& rhs)
    {
        return !(lhs == rhs);
    }

    template <typename Functor, typename Iterator>
    void swap(shino::transform_iterator<Functor, Iterator>& lhs,
              shino::transform_iterator<Functor, Iterator>& rhs)
    {
        lhs.swap(rhs);
    }

    template <typename Functor, typename Iterator>
    auto transformer(Functor&& f, Iterator&& iterator)
    {
        return transform_iterator<std::remove_const_t<std::remove_reference_t <Functor>>,
                std::remove_const_t<std::remove_reference_t<Iterator>>>(std::forward<Functor>(f),
                                                     std::forward<Iterator>(iterator));
    }
}

#endif //SUNRISE_TRANSFORM_ITERATOR_HPP

I don't have any special concerns, but anything, even small nitpicks are appreciated (I had serious flaw in transformer<>() during implementation, so I want to get rid of all of the dangerous things).

This post shares example code with sliding window, because it is meant to be paired with it:

#include <vector>
#include <iostream>
#include <utility>

template <typename InputIt, typename OutputIt>
std::pair<InputIt, OutputIt> sliding_average(InputIt first, InputIt last,
                    const typename std::iterator_traits<InputIt>::difference_type window_length,
                    OutputIt d_first)
{
    using value_type = typename std::iterator_traits<InputIt>::value_type;
    auto divide = [&window_length](const value_type& value)
    {
        return value / window_length;
    };

    auto iterator = shino::transformer(divide, d_first); //transform_iterator<Functor, Iterator>

    auto result = shino::sliding_window(first, last, iterator, window_length);

    return std::make_pair(result.first, result.second.internal_iterator());
}

The example might not be so appealing, but currently I have lack of imagination to write something wonderful small enough to not be applicable for its own review.

\$\endgroup\$
  • \$\begingroup\$ I have a couple of things to say, but I am not sure if it would be enough for a complete review. You could use EBO or handle functors, which are not Semiregular, adapt iterator categories (if Iterator is RAI make sure to be RAI too, otherwise not), use std::decay_t<T> instead of std::remove_const_t<std::remove_reference_t<T>> and use constraints on your template arguments... \$\endgroup\$ – Maikel Mar 3 '17 at 12:17
  • \$\begingroup\$ @Maikel, with some elaboration it would be a great answer! \$\endgroup\$ – Incomputable Mar 3 '17 at 12:29
  • \$\begingroup\$ Ok, i will write one up. It takes a while. I found a couple of issues. ;-) \$\endgroup\$ – Maikel Mar 3 '17 at 13:33
5
+50
\$\begingroup\$

Lets start with the easy thing...

You are told to take any Callable (also class member pointer(!)) but you only use f(...), which doesn't work for all Callable types. To show you an example which should work according the problem description, but does not:

struct Person
{
    int age_;
    std::string name_;

    int age() const noexcept
    {
        return age_;
    }

    decltype(auto) name() const noexcept
    {
        return name_;
    }
};

int main()
{
    auto vec = std::vector<int>(2);
    Person persons[] = { {24, "Foo"}, {42, "Bar"} };

    auto iter = shino::transform_iterator{&Person::age, vec.begin()};
    std::copy(std::begin(persons), std::end(persons), iter);

    // should print "24\n42\n"
    for (int x : vec) {
        std::cout << x << '\n';
    }
}

Error message:

shino.cpp:37:29: error: called object type 'int (Person::*)() const noexcept' is not a function or function pointer
                *iterator = f(std::forward<U>(value));
                            ^
/usr/local/include/c++/v1/algorithm:1706:19: note: in instantiation of function template specialization 'shino::transform_iterator<int (Person::*)() const noexcept,
      std::__1::__wrap_iter<int *> >::proxy::operator=<Person &>' requested here
        *__result = *__first;
                  ^
/usr/local/include/c++/v1/algorithm:1731:19: note: in instantiation of function template specialization 'std::__1::__copy<Person *, shino::transform_iterator<int (Person::*)()
      const noexcept, std::__1::__wrap_iter<int *> > >' requested here
    return _VSTD::__copy(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
                  ^
shino.cpp:137:7: note: in instantiation of function template specialization 'std::__1::copy<Person *, shino::transform_iterator<int (Person::*)() const noexcept,
      std::__1::__wrap_iter<int *> > >' requested here
        std::copy(std::begin(persons), std::end(persons), iter);
             ^
1 error generated.

So instead of the line

*iterator = f(std::forward<U>(value));

you should use

*iterator = std::invoke(f, std::forward<U>(value));

and the example works! (Proof) Lets tackle the next 'issue'

The problem description says specifically:

Given Functor functor (which is Callable) and Iterator iterator (which is OutputIterator), [a transform_]iterator is created that behaves the same as [the] underlying iterator

This could also mean in my opinion, that if you are given an OutputIterator you shall return one, but if you are given a ForwardIterator, which is just a refinement of OutputIterator, you shall also return a ForwardIterator and so on. And if this shall be production code, than I would also add the requirement, that your code shall not compile for given iterators which only satisfy InputIterator.

So to sum up, since you declare your transform_iterator to always be a an OutputIterator by setting that tag, you can not use it well with the (future) STL whenever it would make sense (well at least when we are going to have Concepts). You do not support BidrectionalIterator or RandomAccessIterator already.

To achieve better compliance with the STL, you could just copy the underlying iterator_tag (if it is not input_iterator_tag) and you could use std::enable_ifs to enable only proper operators. To solve this issue cleanly you have to make bigger changes.

You can look into the libraries ranges-v3 and cmcstl2 for some inspiration. They have fantastic iterator facades, which might go into the standard some day (Ranges-TS).

Next issue: The following does not compile (on clang-5.0-trunk)

int main()
{
    auto vec = std::vector<int>(10);

    auto iter = shino::transformer(
        [](auto i){ return i*i; },
        vec.begin()
    );
    auto end = shino::transformer(
        [](auto i){ return i*i; },
        vec.end()
    );

    std::iota(iter, end, 1);

    for (auto&& x : vec) {
        std::cout << x << '\n';
    }
}

Clang fails to compile, because the two closures have different types

Error message:

shino.cpp:127:2: error: no matching function for call to 'iota'
        std::iota(iter, end, 1);
        ^~~~~~~~~
/usr/local/include/c++/v1/numeric:196:1: note: candidate template ignored: deduced conflicting types for parameter '_ForwardIterator'
      ('transform_iterator<(lambda at shino.cpp:119:3), [...]>' vs. 'transform_iterator<(lambda at shino.cpp:123:3), [...]>')
iota(_ForwardIterator __first, _ForwardIterator __last, _Tp __value_)
^

Since iterator and sentinel can not be different in the current STL algorithms, there is unfortunately not much one can do right now. This will be different in the future. Until then I would suggest adding a function which maps an output range into a transformed output range (ensuring using the same Callable type).

Some more 'nitpicking':

As I already stated in the comments you could use std::decay_t<T> when removing const-qualifiers and references from types. But as shown in my examples, you dont need make_functions anymore with recent compiler versions.

Edit:

I forgot to talk about making your Callable types Semiregular. The thing is, that Iterator types are required to be Regular, ie. DefaultConstructible and EqualityComparable. This means, that as long as your Functor type is not DefaultConstructible you have to wrap it in a std::optional. For this I would define a semiregular_box<T>-type which is T for Semiregular types or a wrapper around std::optional<T> otherwise. You can find a reference implementation in ranges-v3.

\$\endgroup\$
  • \$\begingroup\$ I had to change a lot of stuff. Sorry for that. \$\endgroup\$ – Maikel Mar 3 '17 at 16:32
  • \$\begingroup\$ no worries. Also, you can remove edit heading, since it doesn't really matter much on CR. I can read the edit history anyway. Great answer. The first point allows some crazy things, thank you \$\endgroup\$ – Incomputable Mar 3 '17 at 23:21
  • \$\begingroup\$ Could you please leave a link to the clang-5.0? I tried googling around, but the only thing I found is debian package, which for some reason gets stuck on my ubuntu 16.04 LTS. \$\endgroup\$ – Incomputable Mar 4 '17 at 0:53
  • \$\begingroup\$ Both gcc and clang svn trunk versions are C++17 feature complete and need you to compile from source. See clang.llvm.org/get_started.html for details how to build (and fetch from svn) clang \$\endgroup\$ – Maikel Mar 4 '17 at 3:45
  • \$\begingroup\$ thanks for the link. I've successfully installed it (was messing around with various tools for 4 hours). Though it seems like std::invoke() is not yet implemented. I'm using std::__invoke() for now. \$\endgroup\$ – Incomputable Mar 4 '17 at 11:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.