Improve the performance of any_range: std :: prev (iterator) vs --iterator

Question

Recently, I began to prefer the free functions std::next and std::prev to explicitly copy and increase / decrease iterators. Now I see strange behavior in a rather specific case, and I would appreciate any help in demystifying it.

I have an interpolation / extrapolation function working on boost::any_range some X_type . Full range type definition:

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

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

Compiling my application in MSVC 2010, everything works fine. Compiling the same code in MinGW g ++ 4.7.0, it seemed to hang in one specific place, which I 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); } 

While executing the code in gdb, I found that it was not stuck, it just took a lot of time to return from the only call to std::prev , which in libstdC ++ is implemented in terms of std::advance and, ultimately, += .

Just replacing the return string with:

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

Performance is great again, and there is virtually no lag.

I am aware of the overhead of using style- any_range iterators (those of any_range ), but even in this case, two cases above that really have to bear such different costs? Or am I doing something wrong?

Answer 1

Well, after responding to SplinterOfChaos comment, I understood something. The problem is that you are using any_range. In particular, the third argument, which indicates that the Reference argument is const int . In the iterator accelerator phase, when the link is not a real link, it will either use std::input_iterator_tag or not provide an equivalent STL tag.

This is due to the fact that, strictly speaking, all STL iterators with direct, bidirectional and random access must use a real link for their reference type. From 24.2.5 of the C ++ 11 standard:

A class or built-in type X satisfies the requirements of an advanced iterator if

- X satisfies the requirements of the input iterator (24.2.3),

- X satisfies the requirements of DefaultConstructible (17.6.3.1),

- if X is a mutable iterator, the link is a reference to T; if X is an iterator of const, the link is a reference to const T ,

- the expressions in table 109 are valid and have the specified semantics, and

- Type X facilities offer a multi-pass warranty, described below.

In this case, it returns std::input_iterator_tag when requested for its iterator_category , which causes std::prev() to be called in the direction of Undefined Behavior.

In any case, the solution is to change (if possible) your use of boost::any_range as follows:

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

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