Sign in to follow this  

Me vs. STL : Round 1

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

Hello, I was practicing using basic STL Algorithms that i just learned, and i came across a problem that doesnt make any sense. Problem: - My book is explaining to me about how when you add a new element to a vector with the capacity of any size (in this case 10), it rellocates memory, and the capacity is doubled, but when i put this to the test, i first print the size and capacity (size: 10 | capacity: 10), and I then add a new element. I then print out the new size and capacity (wich prints out size: 11 | capacity: 15). According to my book, the capacity should be 20. Can somebody please explain to me why the new capacity is not 20? Code:
vector<int> ammo(10, 0);

	cout << "Vector 'ammo' size: " << ammo.size() << endl;
	cout << "Vector 'ammo' capacity: " << ammo.capacity() << endl;
	cout << "Add Another Element to 'ammo'." << endl << endl;

	ammo.push_back(0);
	Sleep(7000);

	cout << "Vector 'ammo' new size: " << ammo.size() << endl;
	cout << "Vector 'ammo' new capacity: " << ammo.capacity() << endl;
	cout << "Reserving Additional Memory for Vector 'ammo'." << endl << endl;

	ammo.reserve(30);
	Sleep(7000);

	cout << "Vector 'ammo' size: " << ammo.size() << endl;
	cout << "Vector 'ammo' capacity: " << ammo.capacity() << endl << endl;
	cout << "Press Enter to Exit.";
	cin.get();

	return 0;

- Thanks for any help/suggestions/advice.

Share this post


Link to post
Share on other sites
An implementation is not required to double the capacity of the vector when push_back() is called on a full vector. Multiplying the capacity by 1.5 also gives amortized constant time for push_back. Some implementations actually triple the size instead.

Share this post


Link to post
Share on other sites
The book is slightly incorrect. Not every vector implementation doubles in size. It is up to the implementors to decide precisely how much it will resize. In this case, the implementation sounds like it is increasing by 50%, not 100%.

The standard requires amortized constant insertion/erasure at the end of a vector. The "amortized" part means that most of the time, the insert/erase is constant time, but every once in a while, it takes a little more time. The "every once in a while" isn't precisely defined, though.

[edit]Meh, slow, trying to verify I know what "amortized" means.[/edit]

Share this post


Link to post
Share on other sites
If you happen to want to double it every time, you could write your own code to do that. Using the reserve() function, you could fairly easily double the capacity of the vector.

Share this post


Link to post
Share on other sites
Quote:
Original post by Ezbez
If you happen to want to double it every time, you could write your own code to do that. Using the reserve() function, you could fairly easily double the capacity of the vector.


You *could*, but then you end up writing tracking code (to figure out when to do "your" resize) that duplicates the efforts of the vector's code and defeats the purpose.

I begin to wonder why the template doesn't include a (defaulted) argument for resize factor, or even a templated ResizePolicy. I mean, if it includes an Allocator template... :)

SiCrane: I had no idea that factors other than 1.5 or 2 were at all common. I don't suppose you know where to find a list of the values used by common implementations? This is of course purely out of scientific interest :)

Share this post


Link to post
Share on other sites

This topic is 4203 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this