Implementing Deep Copy
I'm trying to implement deep copy on an array of generic pointers. I've been fighting this for 2+ days and can't for the life of me figure it out!
There is an associated test program provided by my professor but I don't think it's needed here. As for the implementations. See the option below in the code...
Option 1: flat out fails the test, it's a shallow copy.
Option 2: produces a segfault, and I don;t understand why if I'm only dereferencing the pointers.
Option 3: fails the test again. Is it a shallow copy???
Option 4: I can't even get to compile, but I was hoping to allocate a new element and just copy the bits over from the original. The compiler bitches about getting a poiter to a type as opposed to a type or something. So I dereference it as in sizeof(*element) but then it says something about a primary expression.
What am I missing here, I understand what a deep copy is vs a shallow copy. Instead of just copying feilds you need to create new objects and point the new fields to those objects that are of equal value to the original.
Is there something obvious I'm missing or is there really something wrong with my attempted logic here? And how do I fix it?
virtual ConcreteArray<element> *makeDeepCopy() const
{
ConcreteArray* arrayPtr = new ConcreteArray();
int option = 4;
for (size_t index = 0; index < this->size(); ++index)
{
switch (option)
{
case 1:
{
arrayPtr->push_back(*new element);
arrayPtr->at(index) = this->at(index);
break;
}
case 2:
{
arrayPtr->push_back(*new element);
*arrayPtr->at(index) = *this->at(index);
break;
}
case 3:
{
element* E = new element;
*E = this->at(index);
arrayPtr->push_back(*E);
break;
}
case 4:
{
arrayPtr->push_back(*new element);
memcpy(this->at(index), arrayPtr->back(), sizeof(element));
}
default: return nullptr;
}
}
return arrayPtr;
}
For additional info here are the constructors...
template<class element>
class ConcreteArray : public Array<element>
{
private:
/// Default capacity is an arbitrary small value > 0
static const size_t defaultCapacity = 8;
element *m_Data; /// Pointer to storage for elements
size_t m_Size; /// Number of elements stored
size_t m_Capacity; /// Number of elements that can be
public:
////////////////////////////////////////////////////////
/// Default constructor
ConcreteArray() :
m_Size(0),
m_Capacity(ConcreteArray::defaultCapacity)
{
m_Data = new element[m_Capacity];
};
////////////////////////////////////////////////////////
/// Copy Constructor (shallow copy)
ConcreteArray(const ConcreteArray<element> &original) :
m_Size(original.m_Size),
m_Capacity(original.m_Capacity)
{
assert(m_Size <= m_Capacity);
m_Data = new element[m_Capacity];
for(size_t i = 0; i < m_Size; i++)
{
m_Data[i] = original.m_Data[i];
}
};
And also the functions I've called, excluding memcpy()...
////////////////////////////////////////////////////////
/// Returns the number of elements in array
virtual size_t size() const
{
return m_Size;
};
////////////////////////////////////////////////////////
/// Append element at end of array expanding storage for
/// array as necessary
void push_back(element const &anElement)
{
this->insertAt(anElement, this->size());
};
////////////////////////////////////////////////////////
/// The array is extended by inserting element before
/// the element at the specified index increasing the
/// array size by 1.
/// Any existing elements at index and beyond are moved
/// to make space for the inserted element.
/// If index is equal to size(), element is appended to
/// the end of the array.
/// Array storage expands as necessary.
virtual void insertAt(element const &anElement,
size_t index)
{
assert(index <= m_Size);
if(m_Size == (m_Capacity - 1))
{ // Double the amount of memory allocated for
// storing elements
m_Capacity *= 2;
element *newData = new element[m_Capacity];
for(size_t i = 0; i < m_Size; i++)
{
newData[i] = m_Data[i];
}
delete [] m_Data;
m_Data = newData;
}
assert((m_Size + 1) < m_Capacity);
if(index < m_Size)
{ // Move elements after index to make room for
// element to be inserted
for(size_t i = m_Size - 1; i > index; i--)
{
m_Data[i] = m_Data[i-1];
}
}
m_Size++;
m_Data[index] = anElement;
};
////////////////////////////////////////////////////////
/// Returns the element at index
virtual element const &at(size_t index) const
{
assert(index < m_Size);
return m_Data[index];
};
////////////////////////////////////////////////////////
/// Returns the element at index
virtual element &at(size_t index)
{
assert(index < m_Size);
return m_Data[index];
};
The base template class...
//
// Array.h
// Project1
//
#ifndef __Array__Array
#define __Array__Array
#include <stdlib.h> // For size_t
#include <iostream> // std::cout
#include <iterator> // std::iterator, std::input_iterator_tag
#include <sstream>
#include <string>
///////////////////////////////////////////////////////////
/// This class encapsulates an array storing any number of
/// elements limited only by the amount of memory available
/// in the host process and provides access to stored
/// elements via within the array.
template<typename element>
class Array
{
public:
///
/// Virtual Destructor
virtual ~Array() {};
///////////////////////////////////////////////////////////
/// BEGIN Pure virtual member functions to be implemented
/// by concrete subclasses
///////////////////////////////////////////////////////////
////////////////////////////////////////////////////////
/// These member functions each return an iterator to
/// the first element in the array.
virtual element * begin() = 0;
virtual const element * begin() const = 0;
////////////////////////////////////////////////////////
/// These member functions each return an iterator to
/// one index past the end of the array.
virtual element * end() = 0;
virtual const element * end() const = 0;
////////////////////////////////////////////////////////
/// The array is extended by inserting anElement before
/// the element at the specified index increasing the
/// array size by 1. Any existing elements at index
/// and beyond are moved to make space for the inserted
/// element.
/// If index is equal to size(), anElement is appended to
/// the end of the array. Array storage expands as
/// necessary.
virtual void insertAt(element const &anElement,
size_t index) = 0;
////////////////////////////////////////////////////////
/// Remove element at index from array moving all
/// elements after index down one position to fill gap
/// created by removing the element reducing the array
/// size by 1
virtual void removeAt(size_t index) = 0;
////////////////////////////////////////////////////////
/// Returns the number of elements in array
virtual size_t size() const = 0;
////////////////////////////////////////////////////////
/// Sets the element value stored at the specified
/// index. works as long index is less than size().
virtual void setAt(element const &anElement,
size_t index) = 0;
////////////////////////////////////////////////////////
/// Returns a reference to the element at index
virtual element const &at(size_t index) const = 0;
////////////////////////////////////////////////////////
/// Returns a reference to the element at index
virtual element &at(size_t index) = 0;
///////////////////////////////////////////////////////////
/// END Pure virtual member functions to be implemented
/// by concrete
///////////////////////////////////////////////////////////
////////////////////////////////////////////////////////
/// Remove all elements from array and set array's size
/// to 0
void clear()
{
while(0 < this->size())
{
this->pop_back();
}
};
element &back()
{
return at(size() - 1);
}
element const &back() const
{
return at(size() - 1);
}
////////////////////////////////////////////////////////
/// Append element at end of array expanding storage for
/// array as necessary
void push_back(element const &anElement)
{
this->insertAt(anElement, this->size());
};
////////////////////////////////////////////////////////
/// Removes and returns the last element in array
void pop_back()
{
assert(0 < this->size());
this->removeAt(this->size() - 1);
};
////////////////////////////////////////////////////////
/// Appends all elements in a Array to array expanding
/// storage for array as necessary
void append(Array &source)
{
const size_t count = source.size();
for(size_t i = 0; i < count; i++)
{
this->push_back(source.at(i));
}
};
////////////////////////////////////////////////////////
/// Returns a reference to the element at index. This
/// operator enables semantics similar to built-in
/// arrays. e.g.
/// someArray[5] = someArray[6];
element &operator [](size_t index)
{
return this->at(index);
}
////////////////////////////////////////////////////////
/// Returns a reference to the element at index. This
/// operator enables semantics similar to built-in
/// arrays. e.g.
/// someArray[6];
element const &operator [](size_t index) const
{
return this->at(index);
}
////////////////////////////////////////////////////////
/// Returns a string representation of the array's
/// elements
operator std::string() const
{
std::ostringstream tempOStream;
tempOStream << "(";
std::copy(begin(), end(),
std::ostream_iterator<void *>(tempOStream, ", "));
tempOStream << ")n";
return tempOStream.str();
}
};
#endif /* defined(__Arrayy__Array__) */
And also the extending class
//
// ConcreteArray.h
// Project1
//
//
#ifndef __Array__ConcreteArray__
#define __Array__ConcreteArray__
#include "Array.h"
#include <string.h> // For memmove()
#include <stdlib.h> // For calloc(), realloc()
#include <algorithm>
#include <assert.h>
#include <iterator> // std::iterator, std::input_iterator_tag
///////////////////////////////////////////////////////////
/// BEGIN code added for Project 3
///////////////////////////////////////////////////////////
////////////////////////////////////////////////////////
/// NEW IN PROJECT 3
////////////////////////////////////////////////////////
// THIS FUNCTION MUST BE DECLARED BEFORE
// ConcreteArray OR ELSE COMPILER WILL NOT KNOW HOW
// TO COPY elements.
////////////////////////////////////////////////////////
template<typename T>
T *deepCopy(T *original)
{
return original->makeDeepCopy();
}
////////////////////////////////////////////////////////
/// NEW IN PROJECT 3
////////////////////////////////////////////////////////
// THIS FUNCTION MUST BE DECLARED BEFORE
// ConcreteArray OR ELSE COMPILER WILL NOT KNOW HOW
// TO COPY long *.
////////////////////////////////////////////////////////
long *deepCopy(long *original)
{
return new long(*original);
}
///////////////////////////////////////////////////////////
/// END code added for Project 3 (SEE THE
/// Project 3 "To Do" CODE BELOW
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
/// This class encapsulates an array storing any number of
/// elements limited only by the amount of memory available
/// in the host process and provides access to stored
/// elements via index position within the array.
template<class element>
class ConcreteArray : public Array<element>
{
private:
/// Default capacity is an arbitrary small value > 0
static const size_t defaultCapacity = 8;
element *m_Data; /// Pointer to storage for elements
size_t m_Size; /// Number of elements stored
size_t m_Capacity; /// Number of elements that can be
public:
////////////////////////////////////////////////////////
/// Default constructor
ConcreteArray() :
m_Size(0),
m_Capacity(ConcreteArray::defaultCapacity)
{
m_Data = new element[m_Capacity];
};
////////////////////////////////////////////////////////
/// Copy Constructor (shallow copy)
ConcreteArray(const ConcreteArray<element> &original) :
m_Size(original.m_Size),
m_Capacity(original.m_Capacity)
{
assert(m_Size <= m_Capacity);
m_Data = new element[m_Capacity];
for(size_t i = 0; i < m_Size; i++)
{
m_Data[i] = original.m_Data[i];
}
};
////////////////////////////////////////////////////////
/// Destructor
virtual ~ConcreteArray()
{
delete [] m_Data;
m_Size = 0;
};
////////////////////////////////////////////////////////
/// The array is extended by inserting element before
/// the element at the specified index increasing the
/// array size by 1.
/// Any existing elements at index and beyond are moved
/// to make space for the inserted element.
/// If index is equal to size(), element is appended to
/// the end of the array.
/// Array storage expands as necessary.
virtual void insertAt(element const &anElement,
size_t index)
{
assert(index <= m_Size);
if(m_Size == (m_Capacity - 1))
{ // Double the amount of memory allocated for
// storing elements
m_Capacity *= 2;
element *newData = new element[m_Capacity];
for(size_t i = 0; i < m_Size; i++)
{
newData[i] = m_Data[i];
}
delete [] m_Data;
m_Data = newData;
}
assert((m_Size + 1) < m_Capacity);
if(index < m_Size)
{ // Move elements after index to make room for
// element to be inserted
for(size_t i = m_Size - 1; i > index; i--)
{
m_Data[i] = m_Data[i-1];
}
}
m_Size++;
m_Data[index] = anElement;
};
////////////////////////////////////////////////////////
/// Remove element at index from array moving all
/// elements after index one position to fill gap
/// created by removing the element
virtual void removeAt(size_t index)
{
assert(index < m_Size);
if((index + 1) < m_Size)
{ // Move elements to close gap left by removing
// an element
for(size_t i = index + 1; i < m_Size; i++)
{
m_Data[i-1] = m_Data[i];
}
}
m_Size--;
};
////////////////////////////////////////////////////////
/// Returns the number of elements in array
virtual size_t size() const
{
return m_Size;
};
////////////////////////////////////////////////////////
/// Sets the element value stored at the specified
/// index. works as long index is less than size().
virtual void setAt(element const &anElement,
size_t index)
{
assert(index < m_Size);
m_Data[index] = anElement;
};
////////////////////////////////////////////////////////
/// Returns the element at index
virtual element const &at(size_t index) const
{
assert(index < m_Size);
return m_Data[index];
};
////////////////////////////////////////////////////////
/// Returns the element at index
virtual element &at(size_t index)
{
assert(index < m_Size);
return m_Data[index];
};
///////////////////////////////////////////////////////////
/// BEGIN code added for Project 3
///////////////////////////////////////////////////////////
////////////////////////////////////////////////////////
/// NEW IN PROJECT 3
////////////////////////////////////////////////////////
/// Constructor via iterators (shallow copy)
template <class _InputIterator>
ConcreteArray(
_InputIterator start,
_InputIterator end) :
m_Size(0),
m_Capacity(ConcreteArray::defaultCapacity)
{
m_Data = new element[m_Capacity];
for(_InputIterator it(start); it != end; ++it)
{
this->push_back(*it);
}
}
////////////////////////////////////////////////////////
/// NEW IN PROJECT 3
////////////////////////////////////////////////////////
/// Returns a newly allocated array produced by deep
/// copying this.
virtual ConcreteArray<element> *makeDeepCopy() const
{
//////////////////////////////////////
/// ***** TO DO *****
/// Implement deep copy logic here!
//////////////////////////////////////
ConcreteArray* arrayPtr = new ConcreteArray();
int option = 5;
for (size_t index = 0; index < this->size(); ++index)
{
switch (option)
{
case 1:
{
arrayPtr->push_back(*new element);
arrayPtr->at(index) = this->at(index);
break;
}
case 2:
{
arrayPtr->push_back(*new element);
*arrayPtr->at(index) = *this->at(index);
break;
}
case 3:
{
element* E = new element;
*E = this->at(index);
arrayPtr->push_back(*E);
break;
}
case 4:
{
arrayPtr->push_back(*new element);
//memcpy(this->at(index), arrayPtr->back(), sizeof(element));
}
case 5:
{
element* aNewElementPtr = new element;
element origElementPtr = at(index);
*aNewElementPtr = origElementPtr;
}
default: return nullptr;
}
}
return arrayPtr;
}
////////////////////////////////////////////////////////
/// NEW IN PROJECT 3
////////////////////////////////////////////////////////
/// These member functions each return an iterator to
/// the first element in the array.
virtual element * begin()
{
//return nullptr; // Replace this line
return m_Data;
};
////////////////////////////////////////////////////////
/// NEW IN PROJECT 3
virtual const element * begin() const
{
//return nullptr; // Replace this line
return m_Data;
};
////////////////////////////////////////////////////////
/// NEW IN PROJECT 3
////////////////////////////////////////////////////////
/// These member functions each return an iterator to
/// one index past the end of the array.
virtual element * end()
{
//return nullptr; // Replace this line
return m_Data + m_Size;
};
////////////////////////////////////////////////////////
/// NEW IN PROJECT 3
virtual const element * end() const
{
//return nullptr; // Replace this line
return m_Data + m_Size;
};
////////////////////////////////////////////////////////
/// NEW IN PROJECT 3
////////////////////////////////////////////////////////
/// Overloaded assignment operator
ConcreteArray &operator=(
const ConcreteArray &original)
{
if (this != &original) // protect against invalid self-assignment
{
//////////////////////////////////////
/// ***** TO DO *****
/// Implement deep copy logic here!
//////////////////////////////////////
return *original.makeDeepCopy();
}
return *this;
}
};
////////////////////////////////////////////////////////
/// NEW IN PROJECT 3
////////////////////////////////////////////////////////
//
////////////////////////////////////////////////////////
template<typename T>
ConcreteArray<T> *deepCopy(ConcreteArray<T> *original)
{
return original->makeDeepCopy();
}
#endif /* defined(__Array__ConcreteArray__) */
Make a new array with the same size of buffer as the original.
For each corresponding pair of elements in turn, call lhs_element = deepCopy(rhs_element) , where lhs_element is the element in the new array and rhs_element is the element in the original array.
上一篇: C ++编译器'浅'的副本和分配
下一篇: 实施深度复制