一道题和STL的list

发表于   |   分类于 ，   |  

算法课老师留了一道思考题，对长度为n的数组循环移位k。

老师没有说限制条件。照这样的话，随便搞一个新的数组也行，岂不就没意思了。由于没什么好的想法，后来在网上找到了一个。

  • 假定数组是v[0…n-1]
  • 首先是k %= n
  • 然后依次翻转v[0…k-1], v[k…n-1], v[0…n-1]即可

然后我就想用模板，这样可以适用多种容器。由于一时忘了algorithm
里面有reverse，就自己写了个。


template<typename Iterator>
void reverse_impl(Iterator beg, Iterator end)
{
    for(std::advance(end, -1); std::distance(beg, end) > 0; std::advance(beg, 1), std::advance(end, -1))
    {
        std::swap(*beg, *end);
    }
}

template<typename T>
void my_reverse(int k, T &v)
{
    k %= v.size();
    auto beg = v.begin(), end = v.end(), adv = beg;
    std::advance(adv, k);
    reverse_impl(beg, adv);
    reverse_impl(adv, end);
    reverse_impl(v.begin(), v.end());
}
//std::list il = {1, 2, 3, 4, 5, 6, 7, 8};
//my_reverse(3, il);

前面用vector检查都没问题，结果list时候就结果不对。本来我用advance，distance就是为了针对list这种不支持随机访问的迭代器的。。。结果看起来只做了前两步，最后一步漏掉了。结果输出之后才发现其实是因为最后一步做了两次。我发现两个迭代器的差变化为7, 5, 3, 1, 8, 6, 4, 2, 0，并没有按我想象的在中间停下。查了下STL源码剖析，发现是因为list是双向链表，且为了满足STL“前闭后开”的区间要求，在list的“末尾”会有一个空白节点，这样5-8的差距比前面的1-4多1就有了解释。可见链表中元素被我交换了两次，相当于没有交换。同时如下所示，在取节点数据时候取的就是尾后迭代器的前一个节点的数据。


reference back() { return *(--end()); }

总结

再一次映证了不要自己造轮子的道理(就是因为自己菜造出来不对)，不过也是自己没想到algorithm里面有。同时在使用STL的时候需要关注其实现，在遇到奇奇怪怪的问题时候起码能够有点反应。

参考资料

  1. 侯捷. STL 源码剖析[M]. 华中科技大学出版社, 2002.