提升any_range性能:std :: prev(iterator)与--iterator

Question

我最近开始喜欢自由函数std::next并std::prev显式复制和递增/递减迭代器.现在,我在一个非常具体的案例中看到了奇怪的行为,我很感激任何帮助揭开它的神秘面纱.

我有一个插值/外推功能在boost::any_range一些操作X_type.范围类型的完整定义是:

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

的any_range,在该特定情况下,从所分配的iterator_range保持两个指针到const X_type,作为一个X_type大约一半的视图data()的一个区域vector<char>.

在MSVC 2010中编译我的应用程序,一切正常.在MinGW g ++ 4.7.0中编译相同的代码,它似乎挂在一个特定的位置,然后我缩小到这个(稍微缩写):

// 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);
}

通过在gdb单步调试代码,我发现它没有被卡住,只是走了很长的时间,从单回std::prev电话-这++的libstdc中的条款实施std::advance,最终的+=运营商.

只需将return线替换为:

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

性能再次出色,几乎没有延迟.

我知道使用类型擦除的迭代器(那些any_range)的开销,但即便如此,上面的两个案例真的应该承担这样不同的成本吗？或者我做错了什么？

Answer 1

好吧，在回复SplinterOfChaos 的评论后，我意识到了一些事情。问题出在您对 any_range 的使用上。特别是第三个参数，它指示 Reference 参数是const int. 在 boost 迭代器门面中，当引用不是真正的引用时，它将使用std::input_iterator_tag或不提供 STL 等效标记。

\n\n

这与以下事实有关：严格来说，所有前向、双向和随机访问 STL 迭代器都必须为其引用类型使用真正的引用。从 C++11 标准的 24.2.5 开始：

\n\n

类或内置类型 X 满足前向迭代器的要求，如果

\n\xe2\x80\x94 X 满足输入迭代器的要求 (24.2.3)，

\n\xe2\x80\x94 X 满足 DefaultConstructible 要求 (17.6.3.1)，

\n\xe2\x80\x94如果 X 是可变迭代器，则引用是对 T 的引用；如果 X 是 const 迭代器，则引用是对 const T 的引用，

\n\xe2\x80\x94 表 109 中的表达式有效并具有指定的语义，并且

\n\xe2\x80\x94 X 类型的对象提供多遍保证，如下所述。\n

\n\n

std::input_iterator_tag在这种情况下，当查询其时，它会返回一个iterator_category，这会导致调用std::prev()转向未定义的行为。

\n\n

无论哪种方式，解决方案都是将您的使用更改为（如果可能）boost::any_range：

\n\n

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

\n\n

这将导致它具有iterator_categoryof std::random_access_iterator_tag，并将按照您最初的预期执行操作。

\n