Proper way to use std::vector
Author
Someone told me of i use std::vector wrongly, the performance will be affected.
Do anyone know what is it?
VS2008,C++
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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:
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.
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.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.
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?
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?
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
std::vector
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
