dcsimg
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 4 of 4

Thread: -Need Help- Doubling Array(s)

  1. #1
    Join Date
    Mar 2016
    Posts
    2

    -Need Help- Doubling Array(s)

    Hey guys,
    I'm having some trouble with this program I'm attempting to make. I made a list of people (including their names, their social security number, and a character to insert/delete/retrieve) that is read and input from a file. I have two functions that work with the program while it inserts/deletes users from the array. If the list fills up, I would like to double the array size. Then if the amount of members is 1/4 the total size, it ends up halving the array. Since the halving portion isn't detrimental (having too few members isn't the worst issue), I'm really trying to focus on just getting the double correct first. I've tried a whole bunch of stuff, but can't seem to figure it out. What I currently have is down below, but I've tried different variations. I'm pretty sure I need to do something with the temp array and get the person pointed back towards it, but haven't been able to figure that out (new to C++). If someone can help me with this, I'd be greatly appreciated!
    I know this can be solved (easily) with vectors - however that's not my goal (as I can already do that). I'm trying to use only arrays to solve this issue. That being said, I would clearly need to use pointers in some way to point the original array elsewhere or... IDK! That's why I'm struggling
    Code:
    #include <iostream>
    #include <fstream>
    #include <string.h>
    using namespace std;
    
    struct Information {
      char functionality;
      string SSN;
      string name;
    };
    
    Information* person;
    int numPeople = 1000;
    int numRetrieved = 0;
    int numArray = 0;
    int numInserted = 0;
    int numDeleted = 0;
    
    //What's in here obviously doesn't work - this is just one of the many things I've tried to do to get this problem to work
    void doubleArray(Information *person){
      numPeople = numPeople * 2;
      Information* temp = new Information[numPeople];
      memcpy(temp, person, numPeople/2);
      delete[] person;
      person = temp;
    }
    
    //Currently not using this until I figure out the double...
    void halfArray(Information *person){
      numPeople = numPeople / 2;
    }
    
    void deleteInfo(Information *person, string SSN){
      for(int i = 0; i < numArray; i++){
        if(person[i].SSN == SSN){
          for(int k = i; k < numArray-1; k++){
            person[k].SSN = person[k+1].SSN;
            person[k].name = person[k+1].name;
          } 
          numArray--;
          numDeleted++;
    
          if((numArray+1) < (numPeople / 4)){
            //halfArray(person);
          }
        }
      }
    }
    
    void retrieve(Information *person, string findSSN, int lastPerson){
      for(int i = 0; i < lastPerson; i++){
        if(person[i].SSN == findSSN){
            numRetrieved++;
        }
      }
    }
    
    void insert(Information *person, string SSN, string name){
      if(numArray == (numPeople - 1)){
        doubleArray(person);
      }
    
      bool dontInsert = false;
      for(int i = 0; i <= numArray; i++){
        if(person[i].SSN == SSN){
          dontInsert = true;    
        }
      }
    
      if(dontInsert){
        dontInsert = false;
      }else{
        person[numArray].SSN = SSN;
        person[numArray].name = name;
        numArray++;
        numInserted++;
      }
    }
    
    int main(int argc, char* argv[]) {
        person = new Information[numPeople];
        char firstLetter;
        string SSN, firstName, lastName, name; 
        fstream input(argv[1]);
    
        for(int i = 0; !input.eof(); i++){
            input >> firstLetter >> SSN >> firstName >> lastName;
            name = firstName + " " + lastName;
    
            switch(firstLetter){
                case 'd':{
                    deleteInfo(person, SSN);
                    break;
                }
                case 'i':{
                    insert(person, SSN, name);
                    break;
                }
                case 'r':{
                    retrieve(person, SSN, numArray);
                    break;
                }
            }
        }
        input.close();
    }
    Thanks for your time, and hopefully any of your help! I really do appreciate it.

  2. #2
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    6,919

    Re: -Need Help- Doubling Array(s)

    Code:
    memcpy(temp, person, numPeople/2);
    memcpy() works on bytes. See https://msdn.microsoft.com/en-us/library/dswaw1wk.aspx So you are copying numPeople/2 bytes from person to temp rather than the required number of elements. Consider
    Code:
    memcpy(temp, person, numPeople/2 * sizeof(Information));

    NB It is not really good practice to have a function parameter name the same as of a global variable. The function parameter name hides that of the global name so changes to the value of variable changes the value of the local variable not the global variable. So in this case in doubleArray() the change to person alters the value of the local variable only and not that of the global variable person which is probably not what is required.

    As you are iterating the array within the insert function, you can reduce the overhead of deletion by simply marking a deleted item as deleted rather than shifting down the next elements. Then within insert() you note for insertion position any deleted item found when searching for an item already present and ignore that element. For retrieve you simply ignore elements marked as deleted.
    Last edited by 2kaud; March 4th, 2016 at 06:51 AM. Reason: NB
    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++17 Compiler: Microsoft VS2019 (16.4.0)

  3. #3
    Join Date
    Aug 2000
    Location
    West Virginia
    Posts
    7,716

    Re: -Need Help- Doubling Array(s)

    1) you are missing:

    Code:
    #include <string>
    2) I am not up to date on the latest standard (I think the definition of POD changed) , but
    it seems like using memcpy on objects that contain a std::string is undefined.
    Consider using std::copy instead.
    Last edited by Philip Nicoletti; March 4th, 2016 at 07:33 AM.

  4. #4
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    6,919

    Re: -Need Help- Doubling Array(s)

    2) I am not up to date on the latest standard (I think the definition of POD changed) , but
    it seems like using memcpy on objects that contain a std::string is undefined.
    Consider using std::copy instead.
    Yep. An issue around memory violation would probably have been the OP's next question.

    Doing a memcpy() on a string object will bit copy the object meaning that the source and destination string objects will point to the same memory for the string data. So when the delete[] is invoked the string destructor will be called for the 'from' object which will free the memory. However this is the same memory now being used by the 'to' object. So the memory used by the 'to' object is now invalid. Whoops!

    Consider using std::copy instead.
    or using swaps to avoid the copy overhead.
    Last edited by 2kaud; March 4th, 2016 at 11:50 AM.
    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++17 Compiler: Microsoft VS2019 (16.4.0)

Tags for this Thread

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




On-Demand Webinars (sponsored)