CODEWITHSUNDEEP
c++linked-list
Bob John
Bob John

Reputation: 3878

How exactly do iterators work? (multiple-choice)

I'm confused as to why the final answer (selection e.) is false in this multiple choice question:

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.

That is, why aren't both d. and e. correct? In what instances would an iterator return the size with end_ptr-start_ptr+1, and in what instances would it not? Should the choice have stated end_ptr-start_ptr instead?

Upvotes: 0

Views: 184

Answers (2)

perreal
perreal

Reputation: 97948

Unlike vectors, the items in a list are not stored in continuous locations. So a linked list.end() should be null to mark the end of the list. That is why you cannot get the list size by arithmetic. Also, the end points to an invalid item, one item past the last valid element.

Upvotes: 1

Corbin
Corbin

Reputation: 33447

Linked lists are not guaranteed to be contiguous (and in fact, never are -- at least not in a real-world scenario).

This means that subtracting their iterators cannot be a constant time operation (well, it could be, but not without making undesirable tradeoffs).

Typically the minus and plus operators are not defined on iterators unless it's a constant time operation.

Also, even if you could subtract them, iterators point one past the last element, not at the last element. This means that length = end - begin. There's no need for plus one.

For example, with a std::vector:

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

(Though you would usually just use v.size().)

Upvotes: 4

Related Questions