Boost any_range performance: std::prev(iterator) versus --iterator

Question

I've recently begun to prefer the free functions std::next and std::prev to explicitly copying and incrementing/decrementing iterators. Now, I am seeing weird behavior in a pretty specific case, and I would appreciate any help demystifying it.

I have an interpolation/extrapolation function operating on a boost::any_range of some X_type. The full definition of the range type is:

boost::any_range <
    const X_type,
    boost::random_access_traversal_tag,
    const X_type,
    std::ptrdiff_t
>

The any_range, in this particular case, is assigned from an iterator_range holding two pointers to const X_type, which serves as an X_type view of about half of the data() area of a vector<char>.

Compiling my application in MSVC 2010, everything works just fine. Compiling the same code in MinGW g++ 4.7.0, it seemed to hang in one particular location, which I've then narrowed down to this (slightly abbreviated):

// Previously ensured conditions:
// 1) xrange is nonempty;
// 2) yrange is the same size as xrange.

auto x_equal_or_greater =
    std::lower_bound(std::begin(xrange),std::end(xrange),xval);

if (x_equal_or_greater == std::end(xrange))
{
    return *yit_from_xit(std::prev(x_equal_or_greater),xrange,yrange);
}

Stepping through the code in gdb, I found out it wasn't getting stuck, just taking a very long time to return from the single std::prev call - which in libstdc++ is implemented in terms of std::advance and ultimately the += operator.

By merely replacing the return line with:

auto xprev=x_equal_or_greater;
--xprev;
return *yit_from_xit(xprev,xrange,yrange);

Performance is great again, and there's virtually no delay.

I am aware of the overhead of using type-erased iterators (those of any_range), but even so, are the two cases above really supposed to carry such different costs? Or am I doing something wrong?

Answer 1

Okay, after responding to SplinterOfChaos's comment, I realized something. The problem is in your use of the any_range. In particular, the 3rd argument, which indicates that the Reference argument is a const int. In the boost iterator facade, when the reference is not a real reference, it will either use std::input_iterator_tag, or not provide an STL equivalent tag.

It has to do with the fact, that strictly speaking, all forward, bidirectional, and random access STL iterators must use a real reference for their reference type. From 24.2.5 of the C++11 standard:

A class or a built-in type X satisfies the requirements of a forward iterator if

— X satisfies the requirements of an input iterator (24.2.3),

— X satisfies the DefaultConstructible requirements (17.6.3.1),

— if X is a mutable iterator, reference is a reference to T; if X is a const iterator, reference is a reference to const T,

— the expressions in Table 109 are valid and have the indicated semantics, and

— objects of type X offer the multi-pass guarantee, described below.

In this case, it's returning an std::input_iterator_tag when queried for its iterator_category, which causes the call to std::prev() veer into Undefined Behavior.

Either way, the solution is to change (if possible) your use of boost::any_range to the following:

  boost::any_range <
        const X_type,
        boost::random_access_traversal_tag,
        const X_type&,
        std::ptrdiff_t
    >

This will cause it to have an iterator_category of std::random_access_iterator_tag, and will perform the operation as you originally expected.