我正在尝试实现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 ){
这似乎也起作用。但这让我有点紧张,因为BidirectionalIterator的文档并不能保证迭代器可以这样排序。我可以相信这种排序将始终按预期工作,并且对于STL容器对象v
,v.end()
将始终大于v.begin()
吗?
(我的担忧来自于像Haskell程序员一样认为双向迭代程序保证具有Eq的属性,可以说,但不具有Ord的属性。)
双向迭代器(不是随机访问迭代器)不支持operator<
。尝试将std::list
迭代器传递给您的函数,您会发现它无法编译。他们之所以不支持这项行动,正是因为这项行动会非常昂贵。
就使用distance
:而言
如果我没有记错的话,每走一步的呼叫距离都会使这成为O(n^2)算法。
您是正确的1。这不是实现反向算法的好方法。不需要获取迭代器之间的距离。您可以只使用operator!=
和/或operator==
来完成,它们都是O(1)。
1.除非您通过随机访问迭代器,否则在这种情况下,distance将使用operator-
,并且算法将是O(n),正如预期的那样
如果有人将空范围(first == last
)传递给您的算法,则您的算法具有未定义的行为,因为您在检查该条件之前递减last
。你需要
void my_reverse(BidirectionalIterator first, BidirectionalIterator last) {
while((first != last) && (first != --last)){
std::swap(*first, *last);
first++;
}
return;
}
您可以使用std::iter_swap
来完成这一切,而不是延迟迭代器并对结果调用std::swap
。
void my_reverse(BidirectionalIterator first, BidirectionalIterator last) {
while((first != last) && (first != --last)){
std::iter_swap(first, last);
first++;
}
return;
}
也许。。。
void my_reverse(BidirectionalIterator first, BidirectionalIterator last)
{
while (first != last && --last != first)
{
std::swap(*first, *last);
++first;
}
}
这里的问题是,每个交换都需要在递增first
和递减last
(按任意顺序)之后进行,但它们彼此相等的点可能是在只执行了一个这样的操作之后,因此对于执行的每个swap
,应该有两个比较,可能会从循环中中断。