迭代器如何工作？（可多选）

我很困惑，为什么最后的答案（选择如）在这个选择题错误：迭代器如何工作？（可多选）

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而不是？

来源

2013-02-28 Bob John

这个问题从哪里来？它是在谈论'std :: list'，还是*任何链接列表？ – 2013-02-28 02:04:34

因为指向链表中每个元素的指针是相互独立的内存位置，所以如果你认为（e）*是远程*准确的，你可能会考虑一个向量而不是列表。它不应该成为你回答这个问题的候选人名单。 – WhozCraig 2013-02-28 02:06:13

为什么（d）应该是准确的？ ISTR你需要O（n^2）时间来做O（1）存储。 – 2013-02-28 02:20:38

链接列表不保证是连续的（事实上，从来不是 - 至少不是在真实世界的情况下）。

这意味着减去它们的迭代器不能是一个常量时间操作（当然，它可能是，但不是没有不必要的折衷）。

通常，除非是恒定时间操作，否则负号和加号操作符在迭代器上没有定义。

而且，即使你能减去他们，迭代器指向一个过去的最后一个元素，而不是在最后一个元素。这意味着length = end - begin。没有必要加上一个。

例如，一个std::vector：

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

（虽然你通常只使用v.size()）

来源

2013-02-28 02:05:16 Corbin

你是什么意思“不保证连续？” – 2013-02-28 02:08:52

@BobJohn列表背后的记忆并不像一个向量中的一个巨块，而是链接在一起的链接，链的每个部分都指向某个内存。链接列表在实践中从不连续。这会让你引入过于怪异的折衷（更不用说将它们称为“链接”列表就没有意义）。 – Corbin 2013-02-28 02:11:36

谢谢！那么，除了矢量之外，还有哪些其他容器*保证是连续的？阵列怎么样？ – 2013-02-28 02:12:24

与载体，在列表中的项目没有存储在连续的位置。所以链接的list.end（）应该为null来标记列表的末尾。这就是为什么你无法通过算术得到列表大小的原因。此外，结尾指向一个无效的项目，一个项目超过最后一个有效元素。

来源

2013-02-28 02:05:27 perreal

迭代器如何工作？ （可多选）

回答

相关问题

迭代器如何工作？（可多选）