By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
435,619 Members | 1,534 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 435,619 IT Pros & Developers. It's quick & easy.

Vector and list iterators and efficiency

P: n/a
Hi,

I have just read the article about iterators at
http://www.oreillynet.com/pub/a/netw...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.

Mar 26 '07 #1
Share this Question
Share on Google+
2 Replies


P: n/a
Thormod Johansen wrote:
I have just read the article about iterators at
http://www.oreillynet.com/pub/a/netw...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
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
Mar 26 '07 #2

P: n/a
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

Mar 26 '07 #3

This discussion thread is closed

Replies have been disabled for this discussion.