Jump to content
  • Advertisement
Sign in to follow this  
crucifer

Fastest list/vector/queue ?

This topic is 4731 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I am currently coding in C++ and I need some storage solution (list/vector/queue ... etc) that can do : -inserts values at random locations -read values at random locations -pop of the first or last values Preferably, if I could do any of these operations in O(1), I would be glad. Anybody has a guess ?

Share this post


Link to post
Share on other sites
Advertisement
A list is better for inserting at random locations
A vector is better for accessing random locations

When you insert and delete from a vector, it has to copy every element of the vector and reposition it. So its not that effecient to do that.
A list is maintained as pointers, it is not contiguous in memory. If you insert randomly into a list all it has to do is change a few pointers.

To access data in a list it has to traverse to that location.
To access data in a vector is instant because that element is a fixed offset from the beginning of the vector.

Share this post


Link to post
Share on other sites
double queued list is only a list that's bidirectionnal ... how is it going to help me to do random reads and random inserts ?

list & double chained list :
<edit>a read = O(n)</edit>
an insert = O(log(n)) + rebalancing of the tree (cause a list with STL is a tree).

a vector :
a read = O(1)
an insert = O(n) + A LOT of memory changes

Share this post


Link to post
Share on other sites
I was looking for some type of storage or maybe some type of combination of storages that could give me the best performance for ALL the operations.

BUT ... in case no one has a better idea, here is an approximate ratio of the type of operations I can do on my storage (wich can contain up to ~10,000 values)

-reads = 90% of the operations (binary search)
-insert = 3%
-pop front = 7%

keep in mind that even if the 3% is very small, moving 10,000 values in the ram is very long ... and thus, the vector is probably the worst solution.

In 1st position, I'm guessing that the list would be the champion ?

Share this post


Link to post
Share on other sites
-inserts values at random locations
-read values at random locations
-pop of the first or last values

deque will require O(n) to insert at random locations, as will vector. deque is really about order n/2 because it shifts up or down depending on which is closer.

reading values at random locations: meaning you have an index number? list will be slow at this because you need to iterate through it. vector and deque are O(1).

pop off first or last: deque does this in O(1), vector would be O(n) for popping off the front.

I recommend a deque. It isn't as simple as a list that has pointers for going forward and backward.

deque info

Share this post


Link to post
Share on other sites

nprz
Quote:
reading values at random locations: meaning you have an index number? list will be slow at this because you need to iterate through it. vector and deque are O(1).


Hmmm ... that's very interesting ... how can deque be O(1) for random read ?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!