transform_iterator not preserving bidirectionality of std::map iterator

[JonT <jon@…>]

Using transform_iterator on std::map iterator does not seem to preserve bidirectionality.

map::iterator itend = data.end();
XIt xend = boost::make_transform_iterator(itend,xfunc());
XIt xlast = xend;
--xlast;
assert(xend != xlast); // succeeds !
xlast = xend;
std::advance(xlast,-1);
assert(xend != xlast); // fails !

See also ​StackOverflow Issue 8783048 for longer (compilable) example.

[jeffrey.hellrung]

Actually there's a couple things going on here. At least for the referenced StackOverflow question, the poster is "lying" about the result of XFunc. The correct way to define XFunc is as

template <typename Pt>
struct XFunc
{
    typedef typename Pt::first_type & result_type;

    result_type operator()(const Pt &p) { return p.first; }
};

and then the example code works.

However, more fundamentally, if your composition function does *not* return a genuine C++ reference (which was what was being told to transform_iterator prior to the above change), there's not a whole lot iterator_facade can do strictly within the constraints of the C++ standard: ISO/IEC 14882:2003(E) 24.1.3 describes the requirements of Forward iterators (of which Bidirectional iterators are a refinement), and the relevant requirement in this case is that "*a" returns a genuine C++ reference (not a proxy reference, not by-value). This is (IMHO) a deficiency in the STL categorization of iterators, hence the rationale for Boost's separate traversal and access tags.

The immediate workaround is to override transform_iterator's deduction mechanism for the iterator_category typedef by explicitly providing it. A more long-term workaround is to drum up support within the C++ community for a change in the standard wording and/or support within the Boost community for a change in the behavior of iterator_facade to conform more to "common sense" than to the strict word of the standard.