On Mar 26, 1:14 pm, "Thormod Johansen" <t...@invalid.invalidwrote:
I have just read the article about iterators athttp://www.oreillynet.com/pub/a/network/2005/10/18/what-is-iterator-i...
and I am wondering about what is ment by the sentence "list does not provide
random access iterators, though, not because it's impossible to implement,
but because it can't be implemented efficiently."
As I understand it, a vector is a single linked list and list is a double
linked list.
No, a vector is guaranteed to be contiguous memory and is
interoperable with an array. It is not a singly linked list.
Why is it harder to implement a efficient iterator in a double
linked than in a single linked list?
It's not (significantly), but this is irrelevant. See above.
If I have the following requirements for a datastructure - be it vector or
list - which would you consider most efficient (fastest running time):
1 ) Be able to iterate through it looking for a specific value
2 ) Remove an element from the middle of the structure
3 ) Add an element in the front and in the back
I reckon that in the case of 2) a list would be fastest but how about the
two other cases?
If your data is unsorted, then in theory, either std::vector or
std::list would be the same in terms of iteration, but in practice
your hardware cache may give vectors a significant speed improvement.
If it is sorted, you probably want some sort of tree-based structure
like a std::set or std::map.
Removing a given element from a list (or set or map) is O(1) but from
a vector is O(N), and inserting an element at a given point is O(1).
Whereas insertion and deletion are both O(N) for vector (though it
amortizes back-insertions over time).
std::deque, which is something like a cross between a list and a
vector, can insert at the front and back in O(1) but also allows
random access. You may want to look into that.
Cheers! --M