Jump to content
  • Advertisement
Sign in to follow this  
hotdogsayhi

Proper way to use std::vector

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

Advertisement
Vectors give very fast random access, since it's internally represented as an array, and they're fast to add to or remove from the end of the vector.
They're slow to add or remove elements from near the start of the array, since the vector has to shuffle the elements around. It can also be slow to add to a vector that isn't reserved to a large enough size, since the vector will need to resize frequently.
The performance impact from not reserve()ing the vector isn't usually too bad, because the vector won't shrink (I'm not sure if there's anything in the C++ standard that says that though) - which means it'll only resize a few times.

The main thing is that it's fast to add / remove near the end of the vector, but slow to add / remove near the start.

Share this post


Link to post
Share on other sites
Generally the std:: containers (list, vector, etc) are pretty good for the majority of what you would use them for. Performance isn't generally an issue unless what you're writing is running slow, or using what you see to be as too much space.

So, in conclusion: what Steve said, but keep in mind that unless you're having problems, performance of your containers won't be a big deal, and it would probably help you more to look for optimizations in algorithms that you're using in other parts of the program.

Share this post


Link to post
Share on other sites
Evil Steve went over the vector well. To contrast, here is a super quick run-down of three basic standard containers:

vector - random access (fast to look up an element with O(1)), sequential storage insertion and deletion of new elements can be slow if done in the middle or near the beginning of the container (sequential memory must be shuffled to do so. O(n))

list - sequential access (to find the 10th element you must loop through the 9 elements before it to access. O(n)) Non-sequential storage which means that you can easily insert/delete elements anywhere in the list for the same performance (very quick O(1)).

map - simulated random access (fastish lookup with [key] or find O(log n) which is faster than list but slower than vector) removing or insterting takes O(log n) (so not as slow as vector but not as fast as list.)

hash maps are another option if these aren't exactly what you need. Then you can get into trees... That's getting beyond the scope of the question.

Share this post


Link to post
Share on other sites
If you want vectors which remove things at the start of the array you can use a std::deque class which at leaset in vc++ is a rotating queue based on an array.

Share this post


Link to post
Share on other sites
There is a performance issue with very big multidimensional vectors. (Vectors containing vectors which are as big as a physical ram page). When iterating through these types of vectors make sure that you iterate through the internal vectors:

good:
for(x=0;x<1000;x++)
for(y=0;y<100000;y++)
v[x][y]

bad:
for(y=0;y<100000;y++)
for(x=0;x<1000;x++)
v[x][y]

Using the second bad example has a tendency to mess up your memory cache paging algorithms.

Share this post


Link to post
Share on other sites
Quote:
Original post by SillyCow
If you want vectors which remove things at the start of the array you can use a std::deque class which at leaset in vc++ is a rotating queue based on an array.


You can easily remove items from a vector regardless of position (beginning, middle, end) with an iterator. It's just a performance issue if you do it a lot.

Share this post


Link to post
Share on other sites
You've gotten some great, informative replies, but how were you using std::vector anyway? Who told you it would be inefficient? Why?

One bad way to use them is like this:
  std::vector<int> v;
for( int i=0; i < 100; i++ )
v.push_back(i); // Bad because v will have to keep reallocating its contents over and over.
The proper thing to do here is use 100 for the constructor, or v.reserve(100) so enough space is already allocated.
Quote:
Original post by Evil Steve
The performance impact from not reserve()ing the vector isn't usually too bad, because the vector won't shrink (I'm not sure if there's anything in the C++ standard that says that though)

I do believe the standard says something about this. Although, a GotW seemed to suggest that if you don't know how much to allocate, and traversing isn't that big a deal, std::deque might be better.

They're like vectors, only the memory is allocated in blocks so you don't have to reallocate when you overflow, just allocate. But traversing is a lot slower because of the keeping track of blocks and switching when you reach the end.

But, just in case none of our posts have been even close to your assumed problem, please answer my questions above.

Share this post


Link to post
Share on other sites
I wouldn't worry about it I thought the whole point of using vector is to free us from doing all worrying that comes from using arrays improperly?
I"ve seen some game programming books I have prefer error prone arrays over vectors due to performance reasons but I've never really seen any hard evidence(benchmark numbers) myself?

Share this post


Link to post
Share on other sites
Use sites like below to get an idea of what container suits your needs best. Programming problems can be so wide and varied that you need references not just forum boards to determine your best course of action ;).

std::vector

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!