-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 :cry:
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.
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.
Re: -Need Help- Doubling Array(s)
1) you are missing:
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.
Re: -Need Help- Doubling Array(s)
Quote:
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. :wave:
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!
Quote:
Consider using std::copy instead.
or using swaps to avoid the copy overhead.