c++ - 按顺序比较 C++ 迭代器是否安全

Question

我正在尝试将 C++ 的反向函数作为练习来实现。练习说明(来自 Caltech 的高级 C++ 类(class))提示您应该使用 distance 函数，它计算两个迭代器之间的项目数。使用这个提示，我编写了下面的函数，它似乎可以工作:

template <typename BidirectionalIterator>
void my_reverse(BidirectionalIterator first, BidirectionalIterator last) {
    last--; // input "last" is one past the end
    while( first != last && distance(first, last) > 1 ){
        std::swap(*first, *last);
        first++;
        last--;
    }
    return;
}

但我对这种方法有一个问题:如果我没记错的话，在每一步调用 distance 会使它成为一个 O(n^2) 算法。所以我用以下内容替换了 while 条件:

    while( first < last ){

这似乎也有效。但这让我有点紧张，因为关于 BidirectionalIterators 的文档并不能保证迭代器可以这样排序。我能相信这个顺序将始终按预期工作吗，并且 v.end() 对于 STL 容器对象 将始终大于 v.begin() >v?

(我的担忧来自于像 Haskell 程序员一样思考双向迭代器保证具有 Eq 的属性，可以这么说，但不是 Ord。)

Answer 1

双向迭代器(不是随机访问迭代器)不支持operator< .尝试传递 std::list你的函数的迭代器，你会看到它无法编译。他们不支持这个操作的原因正是因为它会非常昂贵。

至于使用distance :

if I'm not mistaken, calling distance at each step makes this an O(n^2) algorithm.

你是对的¹。这不是实现反向算法的好方法。无需获取迭代器之间的距离。您可以只使用 operator!= 来做到这一点和/或 operator== , 都是 O(1)。

<子>1。除非你传递随机访问迭代器，在这种情况下 distance 将使用 operator- ，并且算法将如预期的那样为 O(n)。