473,288 Members | 1,794 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,288 software developers and data experts.

Vector and list iterators and efficiency

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
2 2796
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
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 thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

5
by: john smith | last post by:
HI, when I try the following code, I get a segfault when compiled with VC.NET and g++ under cygwin. #1 vector<int> vi; #2 vector<int>::iterator ii = vi.begin(); #3 vi.reserve(10); #4 ...
14
by: Jim West | last post by:
I'm curious why I might be getting such a large performance difference between using a map iterator and a vector iterator. This is a computational electromagnetics code where I have to separate...
11
by: Richard Thompson | last post by:
I've got a memory overwrite problem, and it looks as if a vector has been moved, even though I haven't inserted or deleted any elements in it. Is this possible? In other words, are there any...
3
by: codefixer | last post by:
Hello, I am trying to understand if ITERATORS are tied to CONTAINERS. I know the difference between 5 different or 6(Trivial, on SGI). But what I fail to understand is how can I declare all 5...
13
by: zaineb | last post by:
Hi, This is a follow-up of sort of this thread:...
23
by: Sanjay Kumar | last post by:
Folks, I am getting back into C++ after a long time and I have this simple question: How do pyou ass a STL container like say a vector or a map (to and from a function) ? function: ...
9
by: Christian Chrismann | last post by:
Hi, I've a runtime problem with STL vectors. Here is the simplified version of the code: template <class Tclass A { ... private: vector<T*myvector; typename vector<T*>::itarator mIt;
13
by: smp | last post by:
Does anyone know why making a vector of pointers is so much less efficient than a vector of objects? For a simple example: int num = 20; vector<int*v_int_ptr; v_int_ptr.reserve(num); ...
16
by: xyz | last post by:
I have to run the simulation of a trace file around (7gb contains 116million entries)... presently i am using vector iterators to check the conditions in my program..... it is taking 2 days to...
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: Aftab Ahmad | last post by:
So, I have written a code for a cmd called "Send WhatsApp Message" to open and send WhatsApp messaage. The code is given below. Dim IE As Object Set IE =...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.