C++

Forum

 
 
A transform_iterator implementation

TheToaster (628)
I came across the following code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
 
#include <memory>
#include <iterator>
#include <typeindex>

/* Tiny transform_iterator for C++. Copyright 2018 © Joel Yliluoma - http://iki.fi/bisqwit/
 * License: MIT

   Example WITHOUT transform_iterator:

      template<typename Func>
      std::vector<int> make_transformed_vector(const std::vector<int>& model, Func&& func)
      {
          std::vector<int> result; // Create named temporary
          std::transform(model.begin(), model.end(), std::back_inserter(result), std::forward<Func>(func));
          return result;
      }
      int main()
      {
          std::vector<int> test{6,10,5};
          std::vector<int> test2 = make_transformed_vector(test, [&](int v) { return v*2; });
          for(auto d: test2) std::printf("%d\n", d);
      }

   Example use, WITH transform_iterator:

      #include "transform_iterator.hh"
      template<typename Func>
      std::vector<int> make_transformed_vector(const std::vector<int>& model, Func&& func)
      {
          // Look ma, no named temporaries!
          return std::vector<int> ( make_transform_iterator(model.begin(), model.end(), std::forward<Func>(func)),
                                    transform_iterator<int>() ); // int is the return type of the functor.
      }
      int main()
      {
          std::vector<int> test{6,10,5};
          std::vector<int> test2 = make_transformed_vector(test, [&](int v) { return v*2; });
          for(auto d: test2) std::printf("%d\n", d);
      }

   Another example:

      std::vector<int> values{1,2,3,4};
      // Initialize a std::map with string values corresponding to each int key from values
      std::map<int, std::string> ints
      {
          make_transform_iterator(values.begin(),values.end(),
                                  [&](int v){return std::pair(v,std::to_string(v)); }),
          transform_iterator<std::pair<int,std::string>>{}
      };

 */

template<typename R>
struct transform_iterator
{
public:
    using iterator_category = std::input_iterator_tag;
    using value_type        = std::decay_t<R>;
    using difference_type   = std::ptrdiff_t;
    using pointer           = value_type*;
    using reference         = value_type&;
    using const_pointer     = const value_type*;
    using const_reference   = const value_type&;
private:
    struct transform_iterator_base
    {
        virtual ~transform_iterator_base() = default;
    protected:
        transform_iterator_base() = default;
    private:
        friend struct transform_iterator<R>;
        virtual bool is_end() const = 0;
        virtual bool eq(const transform_iterator_base&) const = 0;
        virtual void delta(std::ptrdiff_t) = 0;
        virtual R ref() const = 0;
        virtual transform_iterator_base* clone() const = 0;
    };

    std::unique_ptr<transform_iterator_base> ptr {};
public:
    transform_iterator() = default;
    transform_iterator(const transform_iterator& b) : ptr(b.ptr ? b.ptr->clone() : nullptr) {}
    transform_iterator(transform_iterator&& b) = default;
    transform_iterator& operator= (transform_iterator&& p) = default;
    transform_iterator& operator= (const transform_iterator& b)
    {
        if(this != &b) ptr.reset(b.ptr ? b.ptr->clone() : nullptr);
        return *this;
    }

    bool operator!=(const transform_iterator<R>& b) const { return !operator==(b); }
    bool operator==(const transform_iterator<R>& b) const
    {
        return ptr ? (b.ptr ? ptr->eq(*b.ptr) : ptr->is_end())
                   : (b.ptr ? b.ptr->is_end() : true);
    }
    R operator* () const                { return ptr->ref(); }
    transform_iterator<R>& operator++() { if(ptr) ptr->delta(1); return *this; }
    transform_iterator<R>& operator--() { if(ptr) ptr->delta(-1); return *this; }
    transform_iterator<R>& operator+=(std::ptrdiff_t p) { if(ptr) ptr->delta(p); return *this; }
    transform_iterator<R>& operator-=(std::ptrdiff_t p) { if(ptr) ptr->delta(-p); return *this; }
    transform_iterator<R> operator++(int) { transform_iterator<R> result(*this); ++*this; return result; }
    transform_iterator<R> operator--(int) { transform_iterator<R> result(*this); --*this; return result; }
    transform_iterator<R> operator+(std::ptrdiff_t p) const { transform_iterator<R> result(*this); result+=p; return result; }
    transform_iterator<R> operator-(std::ptrdiff_t p) const { transform_iterator<R> result(*this); result-=p; return result; }


private:
    transform_iterator(transform_iterator_base* p) : ptr(p) {}

    template<typename I, typename F>
    friend auto make_transform_iterator(const I& begin,const I&,F&& func) -> transform_iterator<decltype(func(*begin))>;

    template<typename I, typename F>
    struct transform_iterator_spec final: public transform_iterator_base
    {
        transform_iterator_spec(const I& b, const I& e, F&& f) : transform_iterator_base(),
                                                                 cur(b), end(e), func(std::forward<F>(f)) {}
    private:
        // These should be never invoked, but I guess defaults are fine nonetheless
        transform_iterator_spec(transform_iterator_spec&&) = default;
        transform_iterator_spec(const transform_iterator_spec&) = default;
        transform_iterator_spec& operator=(transform_iterator_spec&&) = default;
        transform_iterator_spec& operator=(const transform_iterator_spec&) = default;
    private:
        bool eq(const transform_iterator_base& b) const override { return std::type_index(typeid(*this)) == std::type_index(typeid(b))
                                                                       && cur == ((const transform_iterator_spec<I,F>&)b).cur; }
        bool is_end() const override                             { return cur == end; }
        void delta(std::ptrdiff_t by) override                   { std::advance(cur, by); }
        R ref() const override                                   { return func(*cur); }
        transform_iterator_base* clone() const override { return new transform_iterator_spec<I,F>(cur,end,std::forward<F>(func)); }
    private:
        I cur, end;
        F&& func;
    };
};

template<typename I, typename F>
auto make_transform_iterator(const I& begin, const I& end, F&& func)
    -> transform_iterator<decltype(func(*begin))>
{
    using R = decltype(func(*begin));
    return new typename transform_iterator<R>::template transform_iterator_spec<I,F>(begin, end, std::forward<F>(func));
}


What I am slightly confused about is why the author needed to create a private class transform_iterator_base (and thus transform_iterator_spec) rather than just implementing everything in transform_iterator itself. What is the benefit of this?

Furthermore, shouldn't the proper return type of the ref function be value_type? Since R could be a reference and thus be a dangling reference returned from the functor?

Finally, what exactly does this line achieve in operator==? I can't exactly follow what is going on in this code:
1
2
 
        return ptr ? (b.ptr ? ptr->eq(*b.ptr) : ptr->is_end())
                   : (b.ptr ? b.ptr->is_end() : true);
mbozzi (3932)
Firstly, Joel Yliluoma makes awesome stuff. I'm glad to see his work here.
What I am slightly confused about is why the author needed to create a private class transform_iterator_base (and thus transform_iterator_spec) rather than just implementing everything in transform_iterator itself. What is the benefit of this?

The guts of transform_iterator erases the types F and I from its interface. This makes the iterator SCARY, independent of the sequence it traverses. (See n2911 https://wg21.link/n2911 )

Finally, what exactly does this line achieve in operator==?
If ptr is not null, the transform_iterator is nonsingular: it's associated with an iterator sequence. Otherwise the iterator adapter is singular (a sentinel: see http://eel.is/c++draft/iterators#iterator.requirements.general-7 ).

Here's a table of return values for operator==:
|                | b: nonsingular               | b: singular                  |
|----------------+------------------------------+------------------------------|
| a: nonsingular | ptr->eq(*b.ptr)              | whether a made it to the end |
| a: singular    | whether b made it to the end | true                         |
ptr->eq(*b.ptr) is true if the iterators adapt the same type of range iterator with the same type of function object and the current adapted iterators compare equal.

Furthermore, shouldn't the proper return type of the ref function be value_type? Since R could be a reference and thus be a dangling reference returned from the functor?

There's no dangling reference. func(*cur) isn't a local variable. R just reflects its value category - just as if the return type was the placeholder decltype(auto) instead.

Additionally, I find it questionable that a reference to the function object is stored. This is contrary to existing practice, has negative performance implications, and makes the interface more challenging to use properly.
If value semantics were supported, the user could always pass std::ref(func) if reference semantics were desired.

Oh, also there's missing includes: typeinfo, utility, cstddef.
Last edited on
TheToaster (628)
Huh, I've never head of this SCARY code thing. Is this a popular idiom? Where is that n2911 pdf from and where can I learn about this and other idioms in more detail?
dhayden (5798)
91 lines of template code, all to avoid a local variable? Copy elision will make the local go away anyway. It's not just SCARY, it's scary. All that complication for basically no benefit whatsoever. If someone did this at work, I'd probably recommend remedial action.
mbozzi (3932)
Is [SCARY] a popular idiom?

Iterators in the standard library & most of the iterators in the newer Boost libraries are SCARY. I wouldn't really consider this a shining example, however. Because this design unavoidably relies on runtime polymorphism, most of the benefits of the approach are reduced or perhaps even lost. What's left is the SCARY-like compatibility between iterators adapting different ranges with different function objects.

Where is that n2911 pdf from?
You can form a citation with the information inside the paper. The paper is called n2911 because it's one of the ISO C++ committee's formally numbered papers.

91 lines of template code, all to avoid a local variable?

Honestly, I miss transform_iterator and think a version of it should have been part of C++ for a long time.

Last edited on
TheToaster (628)
Thank you. I assume with C++20 ranges I assume this is mostly obsolete
mbozzi (3932)
Yes, subsumed by std::views::transform_view.
Topic archived. No new replies allowed.