-
June 17th, 2013, 12:50 PM
#1
A question regarding reallocation
Here is the code,
Code:
vector<int> v;
for(int i = 0;i<1000;++i)
v.push_back(i);
Is it possible to know how many reallocations happen during the loop? Thanks.
-
June 17th, 2013, 01:07 PM
#2
Re: A question regarding reallocation
Why do you want to know how many reallocations will happen? If that is a concern, then insert a:
before the loop, upon which you know that the number of reallocations will be zero.
-
June 17th, 2013, 02:17 PM
#3
Re: A question regarding reallocation
Originally Posted by LarryChen
Is it possible to know how many reallocations happen during the loop? Thanks.
Yes it's possible to determine this - but it's a real hack and not recommended. You need to modify the STL vector header for push_back. Do not try this at home unless you absolutely know what you are doing and all usual precautions are taken!
On my system, the answer is 18.
As laserlight asked, why do you want to know? A more pertinent question might be 'How do I know how many elements are used in the vector'. If this is known then the vector can be pre-sized to reduce/eliminate reallocations. The size() class function returns the actual number of elements in the vector.
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
June 17th, 2013, 05:14 PM
#4
Re: A question regarding reallocation
You can use the capacity() function to determine if a reallocation occurred:
Code:
vector<int> v;
size_t saved_capacity = v.capacity();
int number_of_reallocations = 0;
for (int i=0; i<1000; ++i)
{
v.push_back(i);
size_t current_capacity = v.capacity();
if (current_capacity != saved_capacity)
{
++number_of_reallocations;
saved_capacity = current_capacity;
}
}
On my system, (VC 2010), the answer is also 18.
-
June 18th, 2013, 05:23 AM
#5
Re: A question regarding reallocation
Nice one!
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
June 18th, 2013, 09:01 AM
#6
Re: A question regarding reallocation
But as stated... don't worry about it, assume that the designers of the lib tried their best to find a good balance between performance (as few reallocations as possible) and memory usage (as few excess as possible).
if you know you'll need a certain amount of items, reserve that amount.
if you know there'll be between X and Y items, then reserve at least X, at most Y, but you probably want to find some "magic" amount in between that'll give you the best case scenario. This'll be different for each case so nobody here can help, knowing what you're making and how your datasets will behave is the only thing that'll help you here.
if you don't trust the standard lib... then make your own.
-
June 18th, 2013, 02:32 PM
#7
Re: A question regarding reallocation
Originally Posted by Philip Nicoletti
You can use the capacity() function to determine if a reallocation occurred:
Code:
vector<int> v;
size_t saved_capacity = v.capacity();
int number_of_reallocations = 0;
for (int i=0; i<1000; ++i)
{
v.push_back(i);
size_t current_capacity = v.capacity();
if (current_capacity != saved_capacity)
{
++number_of_reallocations;
saved_capacity = current_capacity;
}
}
On my system, (VC 2010), the answer is also 18.
This is what I am looking for. Thanks.
-
June 19th, 2013, 10:58 AM
#8
Re: A question regarding reallocation
@LarryChen: Don't assume the answer will always be the same as this, though. On my system (Ubuntu Linux using g++ 4.2.3) the following code (Philip Nicoletti's code with some output added):
Code:
#include <vector>
#include <iostream>
using namespace std;
int main()
{
vector<int> v;
size_t saved_capacity = v.capacity();
int number_of_reallocations = 0;
for (int i=0; i<1000; ++i)
{
v.push_back(i);
size_t current_capacity = v.capacity();
if (current_capacity != saved_capacity)
{
++number_of_reallocations;
saved_capacity = current_capacity;
cout << "Reallocation at I = " << i << "\tCapacity\t" << current_capacity << endl;
}
}
cout << endl << "Total reallocations = " << number_of_reallocations << endl;
return 0;
}
Gives the following output:
Code:
Reallocation at I = 0 Capacity 1
Reallocation at I = 1 Capacity 2
Reallocation at I = 2 Capacity 4
Reallocation at I = 4 Capacity 8
Reallocation at I = 8 Capacity 16
Reallocation at I = 16 Capacity 32
Reallocation at I = 32 Capacity 64
Reallocation at I = 64 Capacity 128
Reallocation at I = 128 Capacity 256
Reallocation at I = 256 Capacity 512
Reallocation at I = 512 Capacity 1024
Total reallocations = 11
I.e. there are 11 reallocations, and the capacity is doubled each time a reallocation is required.
It would be interesting to see what strategy the VC 2010 implementation is using to take 18 reallocations.
-
June 19th, 2013, 11:31 AM
#9
Re: A question regarding reallocation
VC 2010 : 1,2,3,4,5,6,9,13,19,28,42,63,94,211,316,474,711,1066
I know I did this before with VC version 6, and it doubled each time.
edit: so it is using 1.5 as the factor in each case (with a minimum increase
of 1 in the case of 1 to 2).
Last edited by Philip Nicoletti; June 19th, 2013 at 11:38 AM.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|