# Vector and list iterators and efficiency

Discussion in 'C++' started by Thormod Johansen, Mar 26, 2007.

1. ### Thormod JohansenGuest

Hi,

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

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.
Thormod Johansen, Mar 26, 2007

2. ### Victor BazarovGuest

Thormod Johansen wrote:
> 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
--
Victor Bazarov, Mar 26, 2007

3. ### mlimberGuest

On Mar 26, 1:14 pm, "Thormod Johansen" <> wrote:
> 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

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

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
mlimber, Mar 26, 2007