为什么std :: list :: reverse具有O（n）的复杂性？
为什么C ++标准库中std::list类的反向函数具有线性运行时？ 我认为对于双向链表，反向函数应该是O（1）。
倒转一个双向链表只需要切换头部和尾部的指针。
假设， reverse可能是O（1） 。 在那里（又假设）可能是一个布尔列表成员，指示链表的方向是否与创build列表的原始方向相同或相反。
不幸的是，这会降低基本上任何其他操作的性能（尽pipe不会改变渐近运行时间）。 在每个操作中，需要查询布尔值来考虑是否遵循链接的“下一个”或“前一个”指针。
由于这可能被认为是相对不经常的操作，所以标准（并不指定实现，只是复杂性）规定复杂性可以是线性的。 这允许“下一个”指针总是明确地表示相同的方向，加快了常见的操作。
如果列表存储一个允许交换每个节点具有的“ prev ”和“ next ”指针的含义的标志，则可能是O （1）。 如果颠倒名单是一个频繁的操作，那么这样的增加可能实际上是有用的，我不知道为什么实施它会被当前的标准所禁止 。 然而，拥有这样一个标志会使列表中的普通遍历更加昂贵（如果仅仅是一个常数），而不是
current = current->next;
在列表迭代器的operator++中，你会得到
if (reversed) current = current->prev; else current = current->next;
这不是你想要添加的东西。 鉴于列表通常经过的次数往往比颠倒的次数要多，因此标准强制使用这种技术是非常不明智的。 因此，允许反向操作具有线性复杂度。 但是，请注意，如前所述，t∈O（1）⇒t∈O（ n ）所以在技术上实现你的“优化”是允许的。
如果您来自Java或类似的背景，您可能会想知道为什么迭代器每次都必须检查标志。 难道我们不能有两个不同的迭代器types，都来自一个共同的基本types，并有std::list::begin和std::list::rbegin多态返回适当的迭代器？ 尽pipe可能，但这会使整个事情变得更糟，因为推进迭代器现在是间接的（难以内联的）函数调用。 在Java中，无论如何你都要付出这样的代价，但是再一次，这是许多人在性能至关重要时达到C ++的原因之一。
正如Benjamin Lindley在评论中指出的那样，由于reverse不允许使迭代器无效，所以标准允许的唯一方法似乎是将指针存储在迭代器内部的列表中，从而导致双重间接内存访问。
当然，因为所有支持双向迭代器的容器都有rbegin（）和rend（）这个概念，所以这个问题是没有意义的。
构build一个反转迭代器并通过它访问容器的代理是微不足道的。
这个非操作确实是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）容器的反向sorting，因为这是不必要的，而标准库大部分是build立在只强制要求的原则基础上的避免重复。
只是我的2C。
因为它必须遍历每个节点（总共n个）并更新它们的数据（更新步骤确实是O(1) ）。 这使得整个操作O(n*1) = O(n) 。
它还交换每个节点的上一个和下一个指针。 这就是为什么它需要线性。 虽然在O（1）中可以完成，但是如果使用这个LL的函数也把LL作为input的信息，比如它是正在访问还是正在访问。
只有一个algorithm解释。 想象一下，你有一个元素的数组，然后你需要倒置它。 基本思想是迭代每个元素，将第一个位置上的元素更改为最后一个位置，将第二个元素上的元素更改为倒数第二个位置，依此类推。 当你到达数组的中间时，你将会改变所有的元素，因此在（n / 2）迭代中被认为是O（n）。
它只是O（n），因为它需要以相反的顺序复制列表。 每个单独的项目操作是O（1），但是在整个列表中有n个。
当然，有一些恒定时间操作涉及为新列表设置空间，以及之后改变指针等等。一旦包含一阶n因子，O符号不考虑个别常量。
