Vector and list iterators and efficiency

[Thormod Johansen]

Hi,

I have just read the article about iterators at
http://www.oreillynet.com/pub/a/network/2005/10/18/what-is-iterator-in-c-plus-plus.html?page=last
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. Why is it harder to implement a efficient iterator in a double
linked than in a single linked list?

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?

Best regards.

 

[Victor Bazarov]

I have just read the article about iterators at
http://www.oreillynet.com/pub/a/network/2005/10/18/what-is-iterator-in-c-plus-plus.html?page=last
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

Incorrect. A vector is very much like an array in C++.

and list is a
double linked list. Why is it harder to implement a efficient
iterator in a double linked than in a single linked list?

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?

When 1) is concerned, they are the same. Adding to front of a vector
is expensive.

V

 

[mlimber]

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