Thread: how to double an array size?

  1. #46
    Registered User
    Join Date
    Apr 2008
    Posts
    20
    okay this is all within the class

  2. #47
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Or you still haven't resolved the delete[] issue properly and each string's destructor has already destroyed the data.

    Can you please post your entire code?

  3. #48
    Registered User
    Join Date
    Apr 2008
    Posts
    20
    Code:
    void extend()
    {
    string *temparray =  new string[max_size*2];
    for(int i = 0; i < max_size; i++)
    {
    temparray[i] = sentence[i];
    }
    delete[] sentence;
    max_size = (max_size*2);
    sentence = new string[max_size*2];
    for(int i = 0; i < max_size; i++)
    {
    sentence[i] = temparray[i];
    }
    }
    this function is declared in the private section of a class and i have a print function that is declared in the public class that consists of the following:

    Code:
    for(int i = 0; i < max_size; i++)
    {
    cout << sentence[i] << " ";
    }
    so for a driver program or soemthing i used a constructor to set the size of sentence to 3 then i asked for user input to put in strings and if the user enters more strings than the size of the array it increases the size of the array by running extend();

    the private data members are:
    string *sentence;
    int max_size;

  4. #49
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Hold up bud, you are making two copies of your array. That is grossly unnecessary.

    Example:
    Code:
    void extend()
    {
      string *temparray =  new string[max_size*2];
      for(int i = 0; i < max_size; i++)
      {
        temparray[i] = sentence[i];
      }
      delete[] sentence;
      max_size = (max_size*2);
      sentence = temparray;
    /* This is all very dubious including the fact you are also making an array that grows exponentially, instead of linearly.
     *
     * sentence = new string[max_size*2];
     *  for(int i = 0; i < max_size; i++)
     *  {
     *   sentence[i] = temparray[i];
     *  }
     */
    }

  5. #50
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    dotz02x, this is the algorithm you are implementing:
    1. Create a new array, twice the size, pointed to by temparray.
    2. Copy from sentence to temparray.
    3. Delete[] sentence.
    4. Create a new array, twice the size, pointed to by sentence.
    5. Copy from temparray to sentence.

    You have a memory leak since you fail to delete[] temparray. Another problem is that max_size tracks the capacity of the array, but what variable tracks how many elements are actually in use?

    Okay, maybe I should not be doing this, but here's an implementation of the algorithm I outlined earlier:
    Code:
    void extend()
    {
        max_size += max_size; // Assume max_size is positive.
        string* temparray = new string[max_size]; // Create a new array twice the size.
    
        // Copy the old array to the new array.
        // Assume the member variable size keeps track of how many elements are in use.
        for (unsigned int i = 0; i < size; ++i)
        {
            temparray[i] = sentence[i];
        }
    
        // Deallocate the old array. (Not strictly true, but anyway.)
        delete[] sentence;
    
        // Point the old array to the new array.
        sentence = temparray;
    }
    Quote Originally Posted by master5001
    This is all very dubious including the fact you are also making an array that grows exponentially, instead of linearly.
    That's fine. In fact, std::vector's push_back() is required to double the size of the vector, so that insertion at the end happens in amortized constant time.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #51
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Quote Originally Posted by laserlight View Post
    dotz02x, this is the algorithm you are implementing:
    1. Create a new array, twice the size, pointed to by temparray.
    2. Copy from sentence to temparray.
    3. Delete[] sentence.
    4. Create a new array, twice the size, pointed to by sentence.
    5. Copy from temparray to sentence.

    You have a memory leak since you fail to delete[] temparray. Another problem is that max_size tracks the capacity of the array, but what variable tracks how many elements are actually in use?

    Okay, maybe I should not be doing this, but here's an implementation of the algorithm I outlined earlier:
    Code:
    void extend()
    {
        unsigned int size = max_size;
        max_size += max_size; // Assume max_size is positive.
        string* temparray = new string[max_size]; // Create a new array twice the size.
    
        // Copy the old array to the new array.
        // Assume the member variable size keeps track of how many elements are in use.
        for (unsigned int i = 0; i < size; ++i)
        {
            temparray[i] = sentence[i];
        }
    
        // Deallocate the old array. (Not strictly true, but anyway.)
        delete[] sentence;
    
        // Point the old array to the new array.
        sentence = temparray;
    }

    That's fine. In fact, std::vector's push_back() is required to double the size of the vector, so that insertion at the end happens in amortized constant time.
    Fixed.

    And in regard to the exponential growth, I am more pointing out the fact that I think he meant for it to double not grow by powers of four. But who am I to say what he means. It would probably be best if it grew by a fixed size though, in my opinion (back to my whole linear point). If your buffer was theoretically 100MB and you call extend, it will jump to 400MB. Or 200MB if you use either of our code.

    [Edit]Ah, I just noticed your comment laser.. I completely ignored them prior. Perhaps he isn't using a variable to track the used size of the array. Again if the OP posted their code in its entirety as I had asked, we'd know.[/Edit]
    Last edited by master5001; 04-25-2008 at 01:26 PM.

  7. #52
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Fixed.
    No, that's wrong. size should be a member variable.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #53
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by laserlight View Post
    That's fine. In fact, std::vector's push_back() is required to double the size of the vector, so that insertion at the end happens in amortized constant time.
    Actually, it amortizes out no matter what factor you expand it by, although the constant of amortization becomes bigger. You could increase by only 1% at a time if you want. It's a tradeoff between the size of the constant and the amount of memory overhead.

  9. #54
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Actually, it amortizes out no matter what factor you expand it by, although the constant of amortization becomes bigger.
    The key word is "factor". If it grew linearly instead, then it would not amortize out, e.g., consider the worst case of increasing the capacity by 1 everytime an element was pushed to the back.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #55
    Registered User
    Join Date
    Apr 2008
    Posts
    20
    okay thank you i believe it is now fixed

  11. #56
    Registered User
    Join Date
    Apr 2008
    Posts
    20
    all i have now is a double free error at the end of my program when it asks if the user wants to end the program and if he answers true then it does but i get a double free or corruption error and i will try to work this out but i think its caused possibly by the deconstructor

  12. #57
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    A factor and exponent are certainly different. Vectors grow by a set factor, his original code was growing by 4 to the nth power.

  13. #58
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by master5001 View Post
    A factor and exponent are certainly different. Vectors grow by a set factor, his original code was growing by 4 to the nth power.
    Eh? He was multiplying by two twice, so same thing as multiplying by 4.

    If you mean that he was getting 4, 16, 64, 256, ..., 4^n, ..., then: well, that's what you're supposed to get when you use a growth factor.

  14. #59
    Registered User
    Join Date
    Apr 2008
    Posts
    20
    okay so i get a double free fault at the end of my program when i use the sentence.~Setence();
    destructor in my program and the destructor contains the following code:

    Code:
    Setence::~Sentence()
    {
    delete[] sentence;
    delete[] bad_words;
    }
    both of them are arrays that have been initialized in the original constructors

  15. #60
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    And can you guarantee that bad_words and sentence don't end up pointing at the same thing? For that matter, can you guarantee that both point to anything valid at the end of the day?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Testing some code, lots of errors...
    By Sparrowhawk in forum C Programming
    Replies: 48
    Last Post: 12-15-2008, 04:09 AM
  2. Replies: 16
    Last Post: 11-23-2007, 01:48 PM
  3. need some help with last part of arrays
    By Lince in forum C Programming
    Replies: 3
    Last Post: 11-18-2006, 09:13 AM
  4. Unknown Math Issues.
    By Sir Andus in forum C++ Programming
    Replies: 1
    Last Post: 03-06-2006, 06:54 PM
  5. Help with an Array
    By omalleys in forum C Programming
    Replies: 1
    Last Post: 07-01-2002, 08:31 AM