为什么std :: list :: reverse有O(n)复杂度？

Question

为什么std::listC++标准库中的类的反向函数具有线性运行时？我认为对于双向链表,反向函数应该是O(1).

反转双向链表应该只涉及切换头指针和尾指针.

Answer 1

假设,reverse可能是O(1).那里(再次假设)可能是一个布尔列表成员,指示链表的方向当前是否与创建列表的原始方向相同或相反.

不幸的是,这会降低基本上任何其他操作的性能(尽管不会改变渐近运行时).在每个操作中,需要咨询布尔值以考虑是否遵循链接的"下一个"或"上一个"指针.

由于这可能被认为是一种相对不常见的操作,因此标准(不规定实现,仅复杂性)指定复杂性可以是线性的.这允许"下一个"指针始终明确地表示相同的方向,从而加速了常见操作.

Answer 2

这可能是Ø(1)如果该列表将存储允许调换"的含义的标志prev"和" next"指针每个节点都有.如果反转列表将是一个频繁的操作,这样的添加可能实际上是有用的,我不知道为什么实现它将被当前标准禁止.但是,拥有这样一个标志会使列表的普通遍历更加昂贵(如果只是一个常数因素),而不是

current = current->next;

在operator++列表迭代器中,你会得到

if (reversed)
  current = current->prev;
else
  current = current->next;

这不是你决定轻易添加的东西.鉴于列表通常比反转更频繁地遍历,标准强制执行此技术是非常不明智的.因此,允许反向操作具有线性复杂性.不过请注意,即牛逼 ∈ Ô(1)⇒ 牛逼 ∈ Ø(ñ),因此,如前所述,实现您"优化"技术将被允许.

如果你来自Java或类似的背景,你可能想知道为什么迭代器每次都必须检查标志.难道我们不是有两个不同的迭代器类型,无论从公共基类派生,并有std::list::begin与std::list::rbegin多态返回相应的迭代器？虽然可能,这会使整个事情变得更糟,因为推进迭代器将是一个间接(难以内联)函数调用.在Java中,你无论如何都会定期支付这个价格,但这又是许多人在性能至关重要时为C++提供的原因之一.

正如Benjamin Lindley在评论中所指出的,由于reverse不允许使迭代器无效,标准允许的唯一方法似乎是将指针存储回迭代器内的列表,这会导致双间接内存访问.

Answer 3

当然,因为所有支持双向迭代器的容器都有rbegin()和rend()的概念,这个问题没有实际意义吗？

构建一个反转迭代器并通过它访问容器的代理是微不足道的.

这种非操作确实是O(1).

如:

#include <iostream>
#include <list>
#include <string>
#include <iterator>

template<class Container>
struct reverse_proxy
{
    reverse_proxy(Container& c)
    : _c(c)
    {}

    auto begin() { return std::make_reverse_iterator(std::end(_c)); }
    auto end() { return std::make_reverse_iterator(std::begin(_c)); }

    auto begin() const { return std::make_reverse_iterator(std::end(_c)); }
    auto end() const { return std::make_reverse_iterator(std::begin(_c)); }

    Container& _c;
};

template<class Container>
auto reversed(Container& c)
{
    return reverse_proxy<Container>(c);
}

int main()
{
    using namespace std;
    list<string> l { "the", "cat", "sat", "on", "the", "mat" };

    auto r = reversed(l);
    copy(begin(r), end(r), ostream_iterator<string>(cout, "\n"));

    return 0;
}

预期产量:

mat
the
on
sat
cat
the

鉴于此,在我看来,该标准委员会并没有花时间去责成O(1)反向排序的容器,因为它不是必需的,标准库在很大程度上是建立在强制的原则唯一就是绝对必要的,同时避免重复.

只是我的2c.

Answer 4

因为它必须遍历每个节点(n总计)并更新其数据(更新步骤确实如此O(1)).这使得整个操作O(n*1) = O(n).