A question regarding reallocation
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 9 of 9

Thread: A question regarding reallocation

  1. #1
    Join Date
    Jul 2005
    Posts
    910

    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.

  2. #2
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,294

    Re: A question regarding reallocation

    Why do you want to know how many reallocations will happen? If that is a concern, then insert a:
    Code:
    v.reserve(1000);
    before the loop, upon which you know that the number of reallocations will be zero.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  3. #3
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,460

    Re: A question regarding reallocation

    Quote Originally Posted by LarryChen View Post
    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. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  4. #4
    Join Date
    Aug 2000
    Location
    West Virginia
    Posts
    7,569

    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.

  5. #5
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,460

    Re: A question regarding reallocation

    Nice one!
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  6. #6
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    3,925

    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.

  7. #7
    Join Date
    Jul 2005
    Posts
    910

    Re: A question regarding reallocation

    Quote Originally Posted by Philip Nicoletti View Post
    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.

  8. #8
    Join Date
    Jan 2009
    Posts
    596

    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.

  9. #9
    Join Date
    Aug 2000
    Location
    West Virginia
    Posts
    7,569

    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
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center