How to deep clone interconnected objects in C#?

Question

What is the best way to deep clone an interconnected set of objects? Example:

class A {
    B theB; // optional
    // ...
}

class B {
    A theA; // optional
    // ...
}

class Container {
    A[] a;
    B[] b;
}

The obvious thing to do is walk the objects and deep clone everything as I come to it. This creates a problem however -- if I clone an A that contains a B, and that B is also in the Container, that B will be cloned twice after I clone the Container.

The next logical step is to create a Dictionary and look up every object before I clone it. This seems like it could be a slow and ungraceful solution, however.

Any thoughts?

Answer 1

The dictionary solution you suggested is the best I know of. To optimize further, you could use object.GetHashCode() to get a hash for the object, and use that as the dictionary key. Should be fast unless you're talking about huge object trees (10s to 100s of thousands of objects).

Answer 2

Not that I am familiar with C#, but typically any type of crawling of a graph for some sort of processing will require a lookup table to stop processing an object due to cyclic references. So I would think you will need to do the same here.

Answer 3

Its not an elegant solution for sure, but it isn't uncommon to use a dictionary (or hashmap). One of the benefits is that a hashmap has a constant lookup time, so speed does not really suffer here.

Answer 4

maybe create a bit flag to indicate whether this object has been cloned before.

Answer 5

Another possible solution you could investigate is serializing the objects into a stream, and then reconstructing them from that same stream into new instances. This often works wonders when everything else seems awfully convoluted and messy.

Marc