Transfer semantics
See also: Pick Behaviour Explained
Deep copy semantics
Talking about transfer semantics, we are interested in passing values from one place to another, e.g
int a, b;
a = b;
Here we transfer the value of variable b to variable a. We do this by using the implicit assignment operator of type int. This assignment operator passes value of source to target while preserving value of source. This kind of transfer semantics we call deep copy. For large number of types, deep copy is good choice as default transfer semantics. However there are types where preserving source is not that important and dropping this feature has advantages. Consider this simple 'container'
class IntArray {
int count;
int *array;
void Copy(const IntArray& src) {
array = new int[count = src.count];
memcpy(array, src.array, count * sizeof(int));
}
public:
int& operator[](int i) { return array[i]; }
int GetCount() const { return count; }
IntArray(int n) { count = n; array = new int[n]; }
IntArray(const IntArray& src) { Copy(src); }
IntArray& operator=(const IntArray& src)
{ delete[] array; Copy(src) }
~IntArray() { delete[] array; }
};
This shows typical implementation of container class with deep copy transfer semantics. Now consider we want to have a function which returns an IntArray
IntArray MakeArray(int n) {
IntArray a(n);
for(int i = 0; i < n; i++)
a[i] = i;
return a;
}
and see what happens if we use this function
IntArray y = MakeArray(1000);
Problem here is that IntArray copy constructor will be invoked to copy created IntArray to temporary object and to copy this temporary object to target y. (Some really good C++ compilers might elide these copy constructors in this simple case, but there are other cases where this is not possible). And all these deep copies are made to preserve the value of the source object that is destroyed just one step later anyway.
Pick semantics
If we don't need to preserve the source value we could simply copy the array member of the source object to the target and somehow disallow delete in ~IntArray of the source object. And in fact, we rarely need deep copies of containers. This is why we have introduced pick transfer semantics. Let us rewrite IntArray with it
class IntArray {
int count;
mutable int *array;
void Pick(pick_ IntArray& src) {
count = src.count;
array = src.array;
src.array = NULL;
}
public:
int& operator[](int i) { return array[i]; }
int GetCount() const { return count; }
IntArray(int n) { count = n; array = new int[n]; }
IntArray(pick_ IntArray& src) { Pick(src); }
IntArray& operator=(pick_ IntArray& src)
{ if(array) delete[] array;
Pick(src) }
~IntArray() { if(array) delete[] array; }
};
With pick semantics, no unnecessary copying is made and we are free to use such container as return value. What has to be explained here is 'pick_'. The problem is that C++ disallows binding temporaries to non-const references - and that is unfortunately just the thing we need to do here, as we need to change the source temporary returned from a function. C++ allows only one possibility for temporary to be passed - via const reference. But using const reference in interface would be pretty misguiding here, as what we do is quite opposite - we change parameter. That is why we decided to
#define pick_ const
Yes, this is very ugly, but unfortunately this is best option that the current C++ provides. There are efforts to introduce pick-related changes in a future version of C++, but for now we have to live with this.
Pick caveats
Now let us look in pick semantics little bit deeper. One thing is apparent - if a type has default pick transfer semantics, one has to be cautious when using copy constructor or operator=
IntArray a = MakeArray(100);
IntArray b = a; // ATTENTION: a is now picked !
a[3] = 10; //illegal !
This example shows one important aspect of pick semantics that we use throughout our code: after being picked, number of operations that can be performed on source is limited. In most cases, only allowed operations here are operator= and destructor. Real containers add some more (we will provide common list of allowed operations later), but operations accessing or changing data of picked object are always disallowed.
In fact, we had a choice here - alternative approach could be to simply reset the source to some default state - such as in std::auto_ptr. However several years of practice in using pick semantics taught us that accessing or changing data in picked object is almost always error and usually hard to spot one. So we made them illegal and we are also checking for such logic errors in debug mode.
Optional deep copy
Now we have efficient way of transferring values without copying the internal data at the price of invalidating the source object. But what if we would like to preserve source in some cases? No problem, we can simply add alternative methods for the optional deep copy. Unlike normal deep copy and pick semantics, where signatures of methods are dictated by C++ (that is, operator= and copy constructor), here we can choose names of methods ourselves. Anyway, it is a good idea to standardize them. We selected (for type T)
T(const T&, int)
to be the signature of the optional deep copy constructor. We have to distinguish it from pick constructor T(pick_ T&) and we can do it only by adding a parameter. It could be anything, but int somewhat resembles solution for postfix operator++. We also need optional deep copy assignment, so we overload
T& operator<<=(const T&)
as the optional deep copy operator. Now we can improve our simple container class to include optional deep copy semantics
class IntArray {
int count;
mutable int *array;
void Pick(pick_ IntArray& src) {
count = src.count;
array = src.array;
src.array = NULL;
}
void Copy(const IntArray& src) {
array = new int[count = src.count];
memcpy(array, src.array, count * sizeof(int));
}
public:
int& operator[](int i) { return array[i]; }
int GetCount() const { return count; }
IntArray(int n) { count = n; array = new int[n]; }
IntArray(pick_ IntArray& src) { Pick(src); }
IntArray& operator=(pick_ IntArray& src)
{ if(array) delete[] array;
Pick(src) }
IntArray(const IntArray& src, int) { Copy(src); }
IntArray& operator<<=(const IntArray& src)
{ if(array) delete[] array;
Copy(src) }
~IntArray() { if(array) delete[] array; }
};
With optional deep copy we have full control of transfer
IntArray a = MakeArray(100);
IntArray b(a, 1); // deep copy
a[3] = 10; //legal
b <<= a; // deep copy
IntArray c(a); // pick
a = b; // pick - now b is picked, a and c contain MakeArray(100)
Uniform access to deep copy
But we need even more. Consider this example with real NTL container :
Vector< IntArray > x, y;
....
// put something to y
....
x <<= y;
Here we are deep-copy assigning container of pick with optional deep-copy types to another container. During this operation we need deep copies of each individual element of y. The problem is that we need the Vector container to work with both normal deep copy types and with optional deep-copy types. We need an uniform way to invoke the deep-copy constructor whether it has T(const T&) or T(const T&, int) signature. The solution is to provide two additional functions
void DeepCopyConstruct(void *p, const T& x);
T *DeepCopyNew(const T& x);
DeepCopyConstruct constructs a new deep copy of x at the given memory address (much like placement operator new does), DeepCopyNew constructs a new deep copy of x on the heap (like normal new). Now we can provide default versions of these functions that will be used for types with default deep copy
template <class T>
inline void DeepCopyConstruct(void *p, const T& x) {
::new(p) T(x);
}
template <class T>
inline T *DeepCopyNew(const T& x) {
return new T(x);
}
For types with optional deep copy we simply provide specialized version
void DeepCopyConstruct(void *p, const IntArray& x) {
::new(p) IntArray(x, 1);
}
IntArray *DeepCopyNew(const IntArray& x) {
return new IntArray(x, 1);
}
Making things easy
Now there exists a way how to deep copy objects of both default and optional deep copy semantics. Anyway, this might seem pretty annoying - you have to implement two methods and two global functions to get optional deep copy semantics working. Fortunately, it is possible to automatize this work by using DeepCopyOption base
class IntArray : DeepCopyOption<IntArray> {
int count;
mutable int *array;
void Pick(pick_ IntArray& src) {
count = src.count;
array = src.array;
src.array = NULL;
}
void Copy(const IntArray& src) {
array = new int[count = src.count];
memcpy(array, src.array, count * sizeof(int));
}
public:
int& operator[](int i) { return array[i]; }
int GetCount() const { return const; }
IntArray(int n) { count = n; array = new int[n]; }
IntArray(pick_ IntArray& src) { Pick(src); }
IntArray& operator=(pick_ IntArray& src)
{ if(array) delete[] array;
Pick(src) }
IntArray(const IntArray& src, int) { Copy(src); }
~IntArray() { if(array) delete[] array; }
};
Using DeepCopyOption template all you must provide is optional deep copy constructor - and template generates rest of methods and functions automatically.
Changing default semantics
If for some reason you need version of optional deep copy type with default deep copy, you can easily create it with WithDeepCopy template
IntArray a = MakeArray(100);
WithDeepCopy<IntArray> b(a); // b now has deep copy semantics
a[3] = 10; //legal
b = a; // deep copy
a = b; // pick
b[4] = 1; // illegal
Polymorphic deep copy
Now there is one last type of transfer semantics. Some of containers allow storing polymorphic elements. E.g. Array allows storing object of type derived from basic element type. This causes new problems in situation when we want to create deep copy of such container - what we need is polymorphic deep copy of elements. Problem is solved by already introduced DeepCopyNew
class Base : PolyDeepCopyNew<Base> {
....
public:
....
virtual Base *Copy() const { return new Base(*this); }
};
class Derived : Base {
....
public:
....
virtual Base *Copy() const { return new Derived(*this); }
};
....
Array<Base> a;
a.Add(new Base);
a.Add(new Derived);
Array<Base> b(a, 1); // deep copy using Copy members
PolyDeepCopyNew base class creates appropriate DeepCopyNew specialization based on Copy virtual method. We call this transfer method polymorphic deep copy.
|
