Archived

This topic is now archived and is closed to further replies.

haro

Resizing of STL in Microsoft Implementation???

Recommended Posts

I had assumed that Microsoft would implement a vector to resize itself by at least a factor of 2 whenever it reached its max capacity. This seems to be untrue. The vector was apparently resizing itself by only 1 each time it added an item, so I was having to copy all data every insertion. I solved the issue by just manually resizing the vector, but this seems silly. I thought it was the standard of vector/arraylist type containers to resize by a factor of 2x whenever capacity is reached. Am I missing something here? If not, could somebody recommend a more typical STL implementation than the default MS one? [edited by - haro on May 6, 2003 2:46:02 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by stefu
use reserve() to reserve space for vector!


Yah, that's what I meant by resizing the "array". Edited that. But, I don't know how large the vector will end up being. 20, 200 or even 2000000 units large. So I end up having to check its current members versus total capacity every single time I add an item, whereas code for that would seem to be more appropriate inside the vector class itself...



[edited by - haro on May 6, 2003 2:48:30 PM]

Share this post


Link to post
Share on other sites
Then again, if I''m using a vector and I just happen to add one more item to the vector and it doubles in capacity, that might really through off my performance...

Share this post


Link to post
Share on other sites
How do you know it resized every time? Try this out:

I got 29.

  
#include <vector>
#include <iostream>

using namespace std;

int main()
{
vector<int> p(1);
int* last = &p[0];
int counter = 0;
for(int i=0;i<100000;i++)
{
p.push_back(5);
if(last != &p[0])
{
counter++;
last = &p[0];
}

}
cout<<counter<<endl;
}

Share this post


Link to post
Share on other sites
Just checked the code. MS resizes by a factor of 1/2.


So vector of size 60 has new capacity of 90 on the end.

Ok, MUCH better than no resizing. =)

Share this post


Link to post
Share on other sites
I seem to recall some performance benchmarks that showed that resizing with 1.5x original size performed better than resizing with 2x the original size, so that makes sense to me.

Share this post


Link to post
Share on other sites
quote:
Original post by sjelkjd
I seem to recall some performance benchmarks that showed that resizing with 1.5x original size performed better than resizing with 2x the original size, so that makes sense to me.


Probably so. I''m a bit too quick to judge.

Share this post


Link to post
Share on other sites