按顺序比较C++迭代器安全吗？

Question

我正在尝试将C++的反向函数作为练习来实现。练习说明(来自加州理工学院的高级C++课程)暗示您应该使用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上的文档不能保证迭代器可以这样排序。我是否可以相信，这种排序将始终按预期工作，对于STL容器对象v.end()，v.begin()将始终大于v。

(我担心的是，我像一个Haskell程序员一样认为，BidirectionalIterators可以保证具有Eq的属性，可以这么说，但Ord.不是。)

Answer 1

如果有人将空范围(first == last)传递给该算法，则该算法具有未定义的行为，因为在检查该条件之前会减少last。你需要

void my_reverse(BidirectionalIterator first, BidirectionalIterator last) {
    while((first != last) && (first != --last)){
        std::swap(*first, *last);
        first++;
    }
    return;
}

而不是推迟迭代器并对结果调用std::swap，您可以使用std::iter_swap来完成这一切。

void my_reverse(BidirectionalIterator first, BidirectionalIterator last) {
    while((first != last) && (first != --last)){
        std::iter_swap(first, last);
        first++;
    }
    return;
}

Answer 2

也许..。

void my_reverse(BidirectionalIterator first, BidirectionalIterator last)
{
    while (first != last && --last != first)
    {
        std::swap(*first, *last);
        ++first;
    }
}

这里的问题是，每个交换都需要在增量first和递减last (按任一顺序排列)之后完成，但是它们相等的点可能是在只执行了一个这样的操作之后，所以对于每个执行的swap，应该有两个可能中断循环的比较。