Jump to content
  • Advertisement
Sign in to follow this  
dmatter

vector vs deque for unknown growth

This topic is 4862 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

Recently when I have the chance I've been working my ABT spatial partitioning system to make it efficient and flexible but all the way through I've been annoyed in the way I handle the event when a face needs to be split. Currently I use a vector to hold all the vertices for the polygon soup that goes into the function to be partitioned, when finished the vertices would be split up into many VBs in the leaf nodes of the ABT, but when a face needs to be split there isn't enough space in the array to store the newly created vertices so the vector must resize itself (very slow). Now I tried estimating the number of extra vertices that would be generated and reserving them in advance (and it works to some extent but not very practical) and I tried switching to a list (but decided I didn't want the memory overhead - I would rather waste time than memory since its a pre-process and memory could potentially become limited for other reasons.) All over the web I hear that a deque is like a vector that allows efficient insertion at the beginning. But i'm sure i read somewhere that a deque is also more efficient for an unknown amount of growth than a vector but I can't remember where. So would a deque be the container of choice here - or should I stick with estimating the number of vertices that would be genererated? Thanks for any insight you can render unto moi [grin]

Share this post


Link to post
Share on other sites
Advertisement
Here is a good (but little dated) article about the difference between std::vector & std::deque, to summaries it, both vector & deque are random accessible containers. The difference between the two is vector is guaranteed to store elements in memory contiguously as of C++03 TC1 (but imps did it before it was a requirement besides) while deque is not however deque is much better a growing than vector as it doesn't suffer from reallocations & internal copying hence deque has no and does not need a *reserve* method.

Note that most imps of std::vector do try to be efficient as possible when it comes to growing, typically you'll find it will allocate (not allocate & construct, just allocate) memory by 1.5 - 2 times its size when it has reached it's capacity but you still may have the internal copying going which may or may not be an issue. Still deque is better at growing than vector.

std::deque is an excellent in between of std::vector and std::list.

Another idea is to use pooled allocators, for example using boost::pool_allocator with std::vector and boost::fast_pool_allocator with std::deque. This sounds like it could perfectly match your problem, and it does make a very significant difference over using std::allocator the default allocator type used.


Edit by Fruny - Made the link point to the correct GotW article.

[Edited by - snk_kid on July 24, 2005 9:43:36 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by snk_kid

Edit by Fruny - Made the link point to the correct GotW article.


Whoops [embarrass][lol]

Share this post


Link to post
Share on other sites
Some experts think that the common advice "when you don't know better, use a vector", should really be "when you don't know better, use a deque". I've found that when loading data from a file, filling a deque is faster than filling a vector. Outside of the structural difference snk_kid mentioned, accessing the data in a deque is more expensive than accessing the data in a vector. So will creating the deque in the first place.

Fortunately for you, deque and vector offer the same interface! That means that which appropriate typedefs, you'll be able to try one or the other without affecting the rest of your code. Benchmarking and profiling to find the best solution should therefore be a simple enough task. Now, get back to work. *cracks whip*. [evil]

Share this post


Link to post
Share on other sites
Sorry for the delayed response.

I definately prefer the deque now :)

Am I right that a deque is basically a dynamic array of fixed arrays?
If so then that saves me some effort because I was thinking of writing a 'larray' container (list array - or singly linked list of arrays) but a deque is better anyway.

Thanks for the responses - and those boost allocators look interesting

Share this post


Link to post
Share on other sites
Quote:
Original post by dmatter
Am I right that a deque is basically a dynamic array of fixed arrays?


That's a common implementation, yes.

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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!