居然看到一篇和“古老，但很神奇”如出一辙的文章！
 |
yushih
2008-02-25
|
|
yushih
2008-02-26
“古老，但很神奇”的地址是http://www.javaeye.com/topic/90813
楼主的代码有点丑化c/c++哦，我用c++这么写不也挺简洁的嘛：
template<typename InputIterator, typename Function>
void visit_last_n2(InputIterator begin, InputIterator end, int n, Function f)
{
InputIterator t = begin;
advance(t, n);
struct True { bool operator()(InputIterator::value_type&, InputIterator::value_type&){ return true;} };
for_each(mismatch(t, end, begin, True()).second, end, f);
}
如果不要求“一次遍历”还可以更简单一点：
template<typename InputIterator, typename Function>
void visit_last_n1(InputIterator begin, InputIterator end, int n, Function f)
{
advance(begin, distance(begin, end)-n);
for_each(begin, end, f);
}
其实原文里 引用 用两根指针，第一根先出发，相距 n 步后第二根出发。然后同时步进，直到第一根指针达到末尾，然后用 func() 函数对第二个指针开始的子链表进行例遍 的方法也把两个指针从头移到尾了，所以就指针操作来说，两种方法的复杂性是一样的。第二种还有个好处，就是把链表换成一个random accessible sequence,比如数组，vector,deque,这个函数照样可用，而且是optimal。
如果用boost也能写出一个一行代码的解答来吧。 还有我认为“老农”的算法不是最优的。可以先用一个指针从头跑到尾，每经历n/(C-1)个结点将其值记录进一个大小为C(C>=2)的circular buffer。这样第二根指针不用从头开始，可以利用circular buffer中记录的位置，从很靠近需访问节点的位置开始走。 |
