迭代器到底是如何工作的？(多项选择)

Question

我不明白为什么最后的答案(选择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来代替？

Answer 1

链接列表不一定是连续的(事实上，从来没有--至少在现实世界中是这样)。

这意味着，减去他们的迭代器不可能是一个固定的时间操作(嗯，可以是这样，但也不能不进行不受欢迎的权衡)。

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

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

例如，使用std::vector

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

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

Answer 2

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