c++ - boost 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大约一半的 View 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's comment之后，我意识到了什么。问题出在您对 any_range 的使用上。特别是第三个参数，它表示 Reference 参数是一个 const int。在 boost 迭代器外观中，当引用不是真正的引用时，它将使用 std::input_iterator_tag，或者不提供 STL 等效标记。

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

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.

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

无论哪种方式，解决方案是(如果可能的话)将您对 boost::any_range 的使用更改为以下内容:

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

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