开发者

Making a deep copy of a struct...making a shallow copy of a struct

There are questions LIKE this one, but they are not similar enough to my specific question FOR ME to pick up on.

My question is about how to make a deep copy of a struct with pointers as members and how to make a SHALLOW copy of a struct with pointers as members. And then, just for reference, how to make a a deep copy of a struct WITHOUT pointer members and how to make a shallow copy of a struct WITHOUT pointer members (not sure if that last one makes sense).

Let's say we have this:

typedef struct Student
{
    char* first_name; 
    char* last_name; 
    int grade;
    long id;
} Student;

Here is a generic function I made to create a student (the header is being difficult to format):

Student* create_student(const char* first_name, const char* last_name, int grade,long id)

{

   Student *newStudentp = (malloc(sizeof(Student)));

   newStudentp -> last_name = (malloc((strlen(last_name) + 1)  * sizeof(char)));
   newStudentp -> first_name = (malloc((strlen(first_name) + 1)  * sizeof(char)));

   strncpy(newStudentp -> first_name, first_name, strlen(first_name) + 1);
   strncpy(newStudentp -> last_name, last_name, strlen(last_name) + 1);

   newStudentp -> grade = grade;
   newStudentp -> id = id;


   return newStudentp;
}

My attempt to make a deep and a shallow copy;

int main()
{
    Student *s1 = create_Student("Bo","Diddly", 100, 221);
    Student *s2 = create_Student("Leeroy","Jenkins",50,1337);
    memcpy(&s2,&s1,sizeof(Student)); //shallow copy of s1 INTO s2?
    return 0;
}

For deep copies of structs with pointer members I know we must make OUR OWN copy function that does something sensible with pointers. What that sensible thing is...I'm not sure...so here is my attempt at this DEEP copy.

void copy_Student(Student *s1, St开发者_开发知识库udent *s2)
{
   s2 -> grade = s1 -> grade;
   s2 -> id = s1 -> id;
   s2 -> first_name = s1 -> *first_name;
   s2 -> last_name = s1 -> *last_name;

}

The other part of my question (structs WITHOUT pointers as members) can probably just be explained verbally.

EDITED AFTER READING HELPFUL COMMENTS:

Shallow copy: memcpy(s2,s1,sizeof(Student));

Deep copy:

void free_student(Student* stu)
{
    free(stu -> first_name);
    free(stu -> last_name);
}

void copy_Student(Student *s1, Student *s2)
{
    s2 -> grade = s1 -> grade;
    s2 -> id = s1 -> id;
    s2 -> first_name = strdup(s1 -> first_name);
    s2 -> last_name = strdup(s1 -> last_name);
}


The code you have listed as making a shallow copy isn't; it will actually smash the stack and probably crash the program.

Student *s1 = create_Student("Bo","Diddly", 100, 221);
Student *s2 = create_Student("Leeroy","Jenkins",50,1337);
memcpy(&s2,&s1,sizeof(Student)); //shallow copy of s1 INTO s2?

If you had the size right, that would be the same as s2 = s1;. But since you have the size wrong, it is copying too much and will overwrite whatever is in memory after s2. To do a real shallow copy, leave off the &:

memcpy(s2,s1,sizeof(Student)); //shallow copy of s1 INTO s2

The code you have for a deep copy is similarly wrong, but you're on the right track. The basic idea behind a deep copy is that you have to copy each field; for non-pointer types this is the same as a shallow copy, but for pointers you have to do something smarter. The code you posted, however, isn't doing that. Try this instead.

void copy_Student(Student *s1, Student *s2)
{
    s2 -> grade = s1 -> grade;
    s2 -> id = s2 -> id;
    s2 -> first_name = strdup(s1 -> first_name);
    s2 -> last_name = strdup(s1 -> last_name);
}

Note that to avoid memory leaks, you would also need to free the old names from s2 before assigning the new copies, make a free_Student function that would free these names, and also make sure that create_Student copies the names in the first place (or else include "should free" flags so you don't have to copy literal strings).

Now, for a struct without pointers (or other reference types), there is no difference between a deep and a shallow copy because the data structure it itself shallow.


The difference between a shallow copy and a deep copy can be explained in one sentence: A shallow copy copies pointers; a deep copy copies what they point to.

To start with the last part of your question: if there are no pointers, there's no difference between a shallow or a deep copy.

Your attempt to make a shallow copy is technically correct. It's logically wrong, though. Your delete_student() function (the one that frees the mallocs) can't deal with shallow copies. It wouldn't know how many other student copies are still around, and you'd need to delay the free() until the deletion of the last copy.

The deep copy has a very related problem. It's technically incorrect. Strangely enough, your create_student() function shows that you do know how to copy a char* to another one - that has a deep copy of both first_name and last_name. Your copy_Student should do the same.


SLIGHT DISCLAIMER: I'm assuming a 64-bit gcc compiler as far as sizeof() as well as an 8-byte alignment. I also realize this is almost a 7 year old question, but it popped up in my google search as number 1 so I wanted to clarify a few things for others that might stumble upon it. Really I just wanted to comment, but SO requires 50 reputation to do so. So here goes another answer...

I'm not sure what the original poster's understanding of a pointer is, but I know personally I had to internally stop thinking of them as "pointing" to anything and think of them as a "memory address of" something.

The code you have listed as making a shallow copy has a subtle (but potentially catastrophic) oversight.

In your main() function:

Student *s1 = create_Student("Bo","Diddly", 100, 221);
Student *s2 = create_Student("Leeroy","Jenkins",50,1337);
memcpy(&s2,&s1,sizeof(Student)); //shallow copy of s1 INTO s2?

The local (pointer/memory address) variables s1 and s2 are declared (on the stack):

  • Student *s1 (an 8-byte memory address on 64-bit gcc)
  • Student *s2 (an 8-byte memory address on 64-bit gcc)

s1 and s2 being pointers are memory addresses of student structs which happen to be allocated in heap memory due to the fact that your create_Student() function is using malloc() which allocates memory on the heap (heap meaning it will stick around even after create_Student() exits).

Putting an ampersand in front of s1 or s2 is like saying: "Give me the address of the address of my Student struct"

&s1 and &s2 now represent the memory locations (in the stack) of your s1 and s2 pointers (or memory addresses). In other words you are now 2 levels of pointer deep: a pointer to a (stack located) pointer to a (heap located) Student struct.

By specifying memcpy(&s2,&s1,sizeof(Student)) you have asked memcpy to overwrite the stack pointer s2 with the contents (or address) of stack pointer s1 as well as corrupt 24 more bytes of main()'s stack memory that immediately follows the 8 bytes starting at &s2 with the 24 bytes that immediately follows &s1. So to quote Anomie:

If you had the size right, that would be the same as s2 = s1;

So using the same logic of "needing to make a copy of what pointers point to" your copy_Student() DEEP copy might look like:

// I swapped the s1 and s2 arguments with
// target and source for clarity as well as their order
// to more closely mimic memcpy()
void copy_Student(Student *target, Student *source)
{
   if (target!=NULL) free_Student(target); // if target is already allocated, free it...
   assert(source != NULL);

   target->grade = source->grade;
   target->id = source->id;

   target->last_name = (malloc((strlen(source->last_name) + 1)  * sizeof(char)));
   target->first_name = (malloc((strlen(source->first_name) + 1)  * sizeof(char)));

   strncpy(target->first_name, source->first_name, strlen(source->first_name) + 1);
   strncpy(target->last_name, source->last_name, strlen(source->last_name) + 1); 
}


memcpy(&s2,&s1,sizeof(Student)); //shallow copy of s1 INTO s2?

Here you've overwritten the pointer s2 and the pointers within s2 by the corresponding pointer values in s1, so you've leaked memory.

To perform a deep copy you must first free any memory that was being pointed to by the destination structure. Then allocate enough memory to hold the strings pointed to by the source structure. Now, strncpy the strings over.

void copy_Student(Student *s1, Student *s2)
{
   assert( ( s1 != NULL ) && ( s2 != NULL ) );

   if( s2->first_name != NULL ) free( s2->first_name );
   if( s2->last_name != NULL ) free( s2->last_name );

   s2->grade = s1->grade;
   s2->id = s1->id;

   s2->last_name = (malloc((strlen(s1->last_name) + 1)  * sizeof(char)));
   s2->first_name = (malloc((strlen(s1->first_name) + 1)  * sizeof(char)));

   strncpy(s2-> first_name, s1->first_name, strlen(s1->first_name) + 1);
   strncpy(s2-> last_name, s1->last_name, strlen(s1->last_name) + 1); 
}


Instead of thinking about it as a copy, why don't you create a new struct but with the same parameters as the one you want to duplicate? It is a subtle difference but, you have the code already:

Student *s2 = create_Student("Leeroy","Jenkins",50,1337);
Student *wiper = create_Student(s2->first_name, s2->last_name, 
                                               s2->grade, s2->id);

the wiper struct has a clone of s2.

To make a shallow copy, do as you are doing with s1 and s2 (the memcpy), or simply:

s2 = malloc(sizeof(Student));
*s2 = *s1


Instead of this:

newStudentp -> last_name = (malloc((strlen(last_name) + 1)  * sizeof(char)));

do:

newStudentp -> last_name = strdup (last_name);

Your deep copy wants to do something similar (not exactly what cnicutar suggested):

s2->first_name = strdup (s1->first_name);

The problem with cnicutar's suggestion is that it needs to manually allocate the buffer before the strcpy.

And if I remember correctly:

*s2 = *s1;

will do a shallow copy.

Of course, in both the deep and shallow copies you must make sure that you free the destination pointers, otherwise you'll get a memory leak. But even freeing the pointers can lead to problems if you deep copy to a structure that was previously shallow copied to.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜