Public Group

Me vs. STL : Round 1

This topic is 4508 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

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;



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 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.

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

Share on other sites
Agony & SiCrane,

Thanks for the clarification. [smile]

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 on other sites
Quote:
 Original post by EzbezIf 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 :)

1. 1
Rutin
28
2. 2
3. 3
4. 4
5. 5

• 13
• 11
• 10
• 13
• 20
• Forum Statistics

• Total Topics
632952
• Total Posts
3009428
• Who's Online (See full list)

There are no registered users currently online

×