9

我最近开始更喜欢自由函数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这种特殊情况下，从 a 中分配了iterator_range两个指向 的指针const X_type，这用作 aX_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）的开销，但即便如此，上述两种情况真的应该承担如此不同的成本吗？还是我做错了什么？

4

1 回答 1

4

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

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

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

— X 满足输入迭代器 (24.2.3) 的要求，

— X 满足 DefaultConstructible 要求 (17.6.3.1)，

—如果 X 是可变迭代器，则引用是对 T 的引用；如果 X 是 const 迭代器，则 reference 是对 const T 的引用，

— 表 109 中的表达式是有效的并具有指定的语义，并且

— X 类型的对象提供多次通过保证，如下所述。

在这种情况下，std::input_iterator_tag当查询它时它会返回一个iterator_category，这会导致调用std::prev()转向Undefined Behavior。

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

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

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

于 2012-11-06T22:53:29.977 回答