Why does the reverse function for the std::list class in the C++ standard library have linear runtime? I would think that for doubly-linked lists the reverse function should have been O(1).
为什么std的反向函数是::c++标准库中的list类有线性运行时?我认为双链表的逆函数应该是O(1)。
Reversing a doubly-linked list should just involve switching the head and the tail pointers.
颠倒双链表只需要切换头部和尾部指针。
7 个解决方案
#1
182
Hypothetically, reverse could have been O(1). There (again hypothetically) could have been a boolean list member indicating whether the direction of the linked list is currently the same or opposite as the original one where the list was created.
假设，反向可以是O(1)。这里(再次假设)可能是一个布尔列表成员，指示链表的方向是否与创建列表的原始列表相同或相反。
Unfortunately, that would reduce the performance of basically any other operation (albeit without changing the asymptotic runtime). In each operation, a boolean would need to be consulted to consider whether to follow a "next" or "prev" pointer of a link.
不幸的是，这将减少基本上任何其他操作的性能(尽管不改变渐近运行时)。在每个操作中，需要考虑一个布尔值，以考虑是否遵循链接的“下一个”或“prev”指针。
Since this was presumably considered a relatively infrequent operation, the standard (which does not dictate implementations, only complexity), specified that the complexity could be linear. This allows "next" pointers to always mean the same direction unambiguously, speeding up common-case operations.
由于这可能被认为是一个相对不常见的操作，标准(不指定实现，只有复杂性)，指定复杂性可以是线性的。这允许“下一个”指针始终指向相同的方向，加速了常见的操作。
#2
58
It could be O(1) if the list would store a flag that allows swapping the meaning of the “prev” and “next” pointers each node has. If reversing the list would be a frequent operation, such an addition might be in fact useful and I don't know of any reason why implementing it would be prohibited by the current standard. However, having such a flag would make ordinary traversal of the list more expensive (if only by a constant factor) because instead of
如果列表中存储的标志允许交换“prev”和“下一个”指针的含义，则可以是O(1)。如果倒转这个列表会是一个频繁的操作，这样的加法实际上是有用的，而且我不知道为什么要执行它会被当前的标准所禁止。然而，拥有这样的标志会使列表的普通遍历变得更加昂贵(如果仅仅是一个常量)，因为它不是。
current = current->next;
in the operator++ of the list iterator, you would get
在列表迭代器的运算符++中，您将得到。
if (reversed)
current = current->prev;
else
current = current->next;
which is not something you'd decide to add easily. Given that lists are usually traversed much more often than they are reversed, it would be very unwise for the standard to mandate this technique. Therefore, the reverse operation is allowed to have linear complexity. Do note, however, that t ∈ O(1) ⇒ t ∈ O(n) so, as mentioned earlier, implementing your “optimization” technically would be permitted.
这不是你想要轻易添加的东西。考虑到这些清单通常比它们被撤销的次数要多的多，因此，将这种技术授权给标准是非常不明智的。因此，逆向操作被允许具有线性复杂度。做笔记,t∈O(1)⇒∈O(n)所以,正如前面提到的,在技术上实现你的“优化”将是允许的。
If you come from a Java or similar background, you might wonder why the iterator has to check the flag each time. Couldn't we instead have two distinct iterator types, both derived from a common base type, and have std::list::begin and std::list::rbegin polymorphically return the appropriate iterator? While possible, this would make the whole thing even worse because advancing the iterator would be an indirect (hard to inline) function call now. In Java, you're paying this price routinely anyway, but then again, this is one of the reasons many people reach for C++ when performance is critical.
如果您来自Java或类似的背景，您可能会奇怪为什么迭代器每次都要检查标记。我们不能有两个截然不同的迭代器类型，它们都来自一个通用的基类型，并且有std::开始和std::列表::rbegin多态返回适当的迭代器?尽管可能，这将使整个事情变得更糟，因为推进迭代器将是一个间接的(难以内联的)函数调用。在Java中，无论如何你都要按惯例支付这个价格，但是，这也是很多人在性能很关键的时候使用c++的原因之一。
As pointed out by Benjamin Lindley in the comments, since reverse is not allowed to invalidate iterators, the only approach permitted by the standard seems to be to store a pointer back to the list inside the iterator which causes a double-indirect memory access.
正如Benjamin Lindley在评论中指出的那样，由于反向不允许对迭代器无效，标准所允许的唯一方法似乎是将指针存储回迭代器中的列表，从而导致双间接内存访问。
#3
37
Surely since all containers that support bidirectional iterators have the concept of rbegin() and rend(), this question is moot?
当然，既然所有支持双向迭代器的容器都有rbegin()和rend()的概念，那么这个问题就没有意义了吗?
It's trivial to build a proxy that reverses the iterators and access the container through that.
构建一个反转迭代器并通过它访问容器的代理是很简单的。
This non-operation is indeed O(1).
这个非操作确实是O(1)。
such as:
如:
#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;
}
expected output:
预期的输出:
mat
the
on
sat
cat
the
Given this, it seems to me that the standards committee have not taken time to mandate O(1) reverse-ordering of the container because it's not necessary, and the standard library is largely built on the principle of mandating only what is strictly necessary while avoiding duplication.
鉴于此，在我看来，标准委员会并没有花时间来强制执行该容器的逆向排序，因为这是不必要的，而标准库很大程度上是建立在强制要求的原则之上的，只有在避免重复的情况下，才会有严格的必要。
Just my 2c.
只是我的2摄氏度。
#4
18
Because it has to traverse every node (n total) and update their data (the update step is indeed O(1)). This makes the whole operation O(n*1) = O(n).
因为它必须遍历每个节点(n total)并更新它们的数据(更新步骤确实是O(1))。这使得整个操作O(n*1) = O(n)。
#5
2
It also swaps previous and next pointer for every node. Thats why it takes Linear. Although it can be done in O(1) if the function using this LL also takes information about LL as input like whether it is accessing normally or reverse.
它还为每个节点交换前面和下一个指针。这就是为什么它是线性的。虽然可以在O(1)中完成，但如果使用这个函数的函数也会将LL的信息作为输入，比如它是正常访问还是反向访问。
#6
1
Only an algorithm explanation. Imagine you have an array with elements, then you need to inverted it. The basic idea is to iterate on each element changing the element on the first position to the last position, the element on second position to penultimate position, and so on. When you reach at the middle of the array you'll have all elements changed, thus in (n/2) iterations, which is considered O(n).
只有一个算法的解释。假设你有一个元素的数组，然后你需要把它倒过来。基本思想是对每个元素进行迭代，将第一个位置的元素改为最后一个位置，第二个位置的元素到倒数第二个位置，以此类推。当你到达数组的中间时，所有元素都会被改变，因此在(n/2)迭代中，被认为是O(n)。
#7
1
It is O(n) simply because it needs to copy the list in reverse order. Each individual item operation is O(1) but there are n of them in the entire list.
它是O(n)仅仅是因为它需要以相反的顺序复制列表。每个单独的项目操作是O(1)，但在整个列表中有n个。
Of course there are some constant-time operations involved in setting up the space for the new list, and changing pointers afterwards, etc. The O notation doesn't consider individual constants once you include a first-order n factor.
当然，在为新列表设置空间以及之后更改指针等方面，也有一些常量时间操作。O符号在包含一阶n因子后不会考虑单个常量。
#1
182
Hypothetically, reverse could have been O(1). There (again hypothetically) could have been a boolean list member indicating whether the direction of the linked list is currently the same or opposite as the original one where the list was created.
假设，反向可以是O(1)。这里(再次假设)可能是一个布尔列表成员，指示链表的方向是否与创建列表的原始列表相同或相反。
Unfortunately, that would reduce the performance of basically any other operation (albeit without changing the asymptotic runtime). In each operation, a boolean would need to be consulted to consider whether to follow a "next" or "prev" pointer of a link.
不幸的是，这将减少基本上任何其他操作的性能(尽管不改变渐近运行时)。在每个操作中，需要考虑一个布尔值，以考虑是否遵循链接的“下一个”或“prev”指针。
Since this was presumably considered a relatively infrequent operation, the standard (which does not dictate implementations, only complexity), specified that the complexity could be linear. This allows "next" pointers to always mean the same direction unambiguously, speeding up common-case operations.
由于这可能被认为是一个相对不常见的操作，标准(不指定实现，只有复杂性)，指定复杂性可以是线性的。这允许“下一个”指针始终指向相同的方向，加速了常见的操作。
#2
58
It could be O(1) if the list would store a flag that allows swapping the meaning of the “prev” and “next” pointers each node has. If reversing the list would be a frequent operation, such an addition might be in fact useful and I don't know of any reason why implementing it would be prohibited by the current standard. However, having such a flag would make ordinary traversal of the list more expensive (if only by a constant factor) because instead of
如果列表中存储的标志允许交换“prev”和“下一个”指针的含义，则可以是O(1)。如果倒转这个列表会是一个频繁的操作，这样的加法实际上是有用的，而且我不知道为什么要执行它会被当前的标准所禁止。然而，拥有这样的标志会使列表的普通遍历变得更加昂贵(如果仅仅是一个常量)，因为它不是。
current = current->next;
in the operator++ of the list iterator, you would get
在列表迭代器的运算符++中，您将得到。
if (reversed)
current = current->prev;
else
current = current->next;
which is not something you'd decide to add easily. Given that lists are usually traversed much more often than they are reversed, it would be very unwise for the standard to mandate this technique. Therefore, the reverse operation is allowed to have linear complexity. Do note, however, that t ∈ O(1) ⇒ t ∈ O(n) so, as mentioned earlier, implementing your “optimization” technically would be permitted.
这不是你想要轻易添加的东西。考虑到这些清单通常比它们被撤销的次数要多的多，因此，将这种技术授权给标准是非常不明智的。因此，逆向操作被允许具有线性复杂度。做笔记,t∈O(1)⇒∈O(n)所以,正如前面提到的,在技术上实现你的“优化”将是允许的。
If you come from a Java or similar background, you might wonder why the iterator has to check the flag each time. Couldn't we instead have two distinct iterator types, both derived from a common base type, and have std::list::begin and std::list::rbegin polymorphically return the appropriate iterator? While possible, this would make the whole thing even worse because advancing the iterator would be an indirect (hard to inline) function call now. In Java, you're paying this price routinely anyway, but then again, this is one of the reasons many people reach for C++ when performance is critical.
如果您来自Java或类似的背景，您可能会奇怪为什么迭代器每次都要检查标记。我们不能有两个截然不同的迭代器类型，它们都来自一个通用的基类型，并且有std::开始和std::列表::rbegin多态返回适当的迭代器?尽管可能，这将使整个事情变得更糟，因为推进迭代器将是一个间接的(难以内联的)函数调用。在Java中，无论如何你都要按惯例支付这个价格，但是，这也是很多人在性能很关键的时候使用c++的原因之一。
As pointed out by Benjamin Lindley in the comments, since reverse is not allowed to invalidate iterators, the only approach permitted by the standard seems to be to store a pointer back to the list inside the iterator which causes a double-indirect memory access.
正如Benjamin Lindley在评论中指出的那样，由于反向不允许对迭代器无效，标准所允许的唯一方法似乎是将指针存储回迭代器中的列表，从而导致双间接内存访问。
#3
37
Surely since all containers that support bidirectional iterators have the concept of rbegin() and rend(), this question is moot?
当然，既然所有支持双向迭代器的容器都有rbegin()和rend()的概念，那么这个问题就没有意义了吗?
It's trivial to build a proxy that reverses the iterators and access the container through that.
构建一个反转迭代器并通过它访问容器的代理是很简单的。
This non-operation is indeed O(1).
这个非操作确实是O(1)。
such as:
如:
#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;
}
expected output:
预期的输出:
mat
the
on
sat
cat
the
Given this, it seems to me that the standards committee have not taken time to mandate O(1) reverse-ordering of the container because it's not necessary, and the standard library is largely built on the principle of mandating only what is strictly necessary while avoiding duplication.
鉴于此，在我看来，标准委员会并没有花时间来强制执行该容器的逆向排序，因为这是不必要的，而标准库很大程度上是建立在强制要求的原则之上的，只有在避免重复的情况下，才会有严格的必要。
Just my 2c.
只是我的2摄氏度。
#4
18
Because it has to traverse every node (n total) and update their data (the update step is indeed O(1)). This makes the whole operation O(n*1) = O(n).
因为它必须遍历每个节点(n total)并更新它们的数据(更新步骤确实是O(1))。这使得整个操作O(n*1) = O(n)。
#5
2
It also swaps previous and next pointer for every node. Thats why it takes Linear. Although it can be done in O(1) if the function using this LL also takes information about LL as input like whether it is accessing normally or reverse.
它还为每个节点交换前面和下一个指针。这就是为什么它是线性的。虽然可以在O(1)中完成，但如果使用这个函数的函数也会将LL的信息作为输入，比如它是正常访问还是反向访问。
#6
1
Only an algorithm explanation. Imagine you have an array with elements, then you need to inverted it. The basic idea is to iterate on each element changing the element on the first position to the last position, the element on second position to penultimate position, and so on. When you reach at the middle of the array you'll have all elements changed, thus in (n/2) iterations, which is considered O(n).
只有一个算法的解释。假设你有一个元素的数组，然后你需要把它倒过来。基本思想是对每个元素进行迭代，将第一个位置的元素改为最后一个位置，第二个位置的元素到倒数第二个位置，以此类推。当你到达数组的中间时，所有元素都会被改变，因此在(n/2)迭代中，被认为是O(n)。
#7
1
It is O(n) simply because it needs to copy the list in reverse order. Each individual item operation is O(1) but there are n of them in the entire list.
它是O(n)仅仅是因为它需要以相反的顺序复制列表。每个单独的项目操作是O(1)，但在整个列表中有n个。
Of course there are some constant-time operations involved in setting up the space for the new list, and changing pointers afterwards, etc. The O notation doesn't consider individual constants once you include a first-order n factor.
当然，在为新列表设置空间以及之后更改指针等方面，也有一些常量时间操作。O符号在包含一阶n因子后不会考虑单个常量。