0

我很困惑为什么这个多项选择题的最终答案（选择 e.）是错误的：

Which of the following statements is the most accurate regarding linked lists?

a. Linked-lists take up more space than STL vectors because they allocate extra storage 
space for future growth.
b. The asymptotic complexity of inserting at the end of a doubly-linked list container 
storing only the pointer to the first element is O(1).
c. A loop in a singly-linked-list can be found in O(log(n)) time and O(n) memory overhead
d. A loop in a singly-linked-list can be found in O(n) time and O(1) memory overhead.
e. The number of elements in a linked-list is end_ptr -start_ptr + 1, where start_ptr points
to the first element in the linked list and end_ptr points to the last item of the linked-list.

也就是说，为什么两者都不是d。和 e。正确的？在什么情况下，迭代器会返回带有 的大小end_ptr-start_ptr+1，在什么情况下不会？选择应该end_ptr-start_ptr改为说明吗？

4

2 回答 2

4

链表不能保证是连续的（事实上，从来都不是——至少在现实世界中不是）。

这意味着减去它们的迭代器不能是一个恒定的时间操作（好吧，它可能是，但不是没有做出不希望的权衡）。

通常，除非它是一个常数时间操作，否则不会在迭代器上定义减号和加号运算符。

此外，即使您可以减去它们，迭代器也会指向最后一个元素，而不是最后一个元素。这意味着length = end - begin. 不需要加一。

例如，使用std::vector：

size_t len = v.end() - v.begin();

（尽管您通常只使用v.size().）

于 2013-02-28T02:05:16.000 回答
1

与向量不同，列表中的项目不存储在连续的位置。所以链表.end() 应该为 null 以标记列表的结尾。这就是为什么您无法通过算术获得列表大小的原因。此外，end 指向一个无效项，即最后一个有效元素之后的一项。

于 2013-02-28T02:05:27.650 回答