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

我很困惑，爲什麼最後的答案（選擇如）在這個選擇題錯誤：迭代器如何工作？（可多選）

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

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

回答

相關問題

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