Trying to create copy function in a vector class

问题:

I am working on implementing a vector class but cannot figure out how to write a function to copy one vector into another.

template <class T> class Vec {

public:
//TYPEDEFS
    typedef T* iterator;
    typedef const T* const_iterator;
    typedef unsigned int size_type;

//CONSTRUCTOS, ASSIGNMENT OPERATOR, & DESTRUCTOR
    Vec() {this->create(); }
    Vec(size_type n, const T& t = T()) { this->create(n, t); }
    Vec(const Vec& v) { copy(v); }
    Vec& operator=(const Vec& v);
    ~Vec() { delete [] m_data; }

//MEMBER FUNCTIONS AND OTHER OPERATORS
    T& operator[] (size_type i) { return m_data[i]; }
    const T& operator[] (size_type i) const { return m_data[i]; }
    void push_back (const T& t);
    iterator erase(iterator p);
    void resize(size_type n, const T& fill_in_value = T());
    void clear() { delete [] m_data; create(); }
    bool empty() const { return m_size == 0; }
    size_type size() const { return m_size; }

//ITERATOR OPERATIONS
    iterator begin() { return m_data; }
    const_iterator begin() const { return m_data; }
    iterator end() { return m_data + m_size; }
    const_iterator end() const { return m_data + m_size; }

private:
//PRIVATE MEMBER FUNCTIONS
    void create();
    void create(size_type n, const T& val);
    void copy(const Vec<T>& v);

//REPRESENTATION
    T *m_data;      //point to first location inthe allocated array
    size_type m_size;   //number of elements stored in the vector
    size_type m_alloc;  //number of array locations allocated, m_size <= m_alloc
};

//create an empty vector (null pointers everywhere)
template <class T> void Vec<T>::create() {
    m_data = NULL;
    m_size = m_alloc = 0;   //no memory allocated yet
}

//create a vector with size n, each location having the given value
template <class T> void Vec<T>::create(size_type n, const T& val) {
    m_data = new T[n];
    m_size = m_alloc = n;
    for (T* p = m_data; p != m_data + m_size; ++p)
        *p = val;
}   

//assign one vector to another, avoiding duplicate copying
template <class T> Vec<T>& Vec<T>::operator=(const Vec<T>& v) {
    if (this != &v) {
        delete [] m_data;
        this -> copy(v);
    }
    return *this;
}

This is the first things I came up with:

template <class T> void Vec<T>::copy(const Vec<T>& v) {

     m_size = m_alloc = v.size();
     m_data = &v;

}

I got an error about incompatible types...OK, makes sense that they are incompatible. So I take out the 'const' and now it works.

template <class T> void Vec<T>::copy(Vec<T>& v) {

     m_size = m_alloc = v.size();
     m_data = &v[0];

}

I am guessing this isn't entirely correct or good form. I'm not sure. And now I get an error about the pointer being freed not having been allocated (but it compiles, runs, and copies the vector successfully at least now). So I would say I am not really understanding passing variables/arrays/vectors/things by reference, and also dynamic allocation of memory. My question is: how can I improve the copy function that I have written to either not compare two incompatible variables, or to successfully allocate the pointer dynamically to the new vector so that I don't get that malloc error?

回答1:

You need to do deep-copy of the elements, not simply assign the pointer m_data:

// precondition: `m_data` is not allocated
template <class T> void Vec<T>::copy(const Vec<T>& v) {
    m_data = new T[v.size()];
    m_size = m_alloc = v.size();
    for (size_t ii = 0; ii < m_size; ++ii)
        m_data[ii] = v[ii];
}

回答2:

For your copy-constructor to be safe it needs to fail when the copy can't be made.

Vec<T>::Vec(const Vec<T>& o):m_size(o.m_size), m_alloc(o.m_size), m_data(new T()){
    std::copy( o.m_data, o.m_data+o.m_size, m_data);
}

The copy-constructor should be able to replace any Vec<T>::copy member.

The assignment is easily handled by introducing a swap function. This is exception safe.

void Vec<T>::swap(Vec<T>& rhs){
   std::swap(m_data, rhs.m_data);
   std::swap(m_size, rhs.m_size);
   std::swap(m_capacity, rhs.m_capacity);
}

With the exception safe Copy & swap & idiom it becomes:

Vec<T>& Vec<T>::operator = (const Vec<T>& rhs){
   Vec<T> cpy=rhs;
   swap( this, cpy);
   return *this;
}

回答3:

Note that there is an issue with exception safety with the previous answer given. The simple fix is to allocate first.

// precondition: `m_data` is not allocated
template <class T> void Vec<T>::copy(const Vec<T>& v) {
    m_data = new T[v.size()];
    m_size = m_alloc = v.size();
    for (size_t ii = 0; ii < m_size; ++ii)
        m_data[ii] = v[ii];
}

The other issue with your code is operator=, which is not exception safe. You deleted m_data before allocating again with new[]. If new[] fails, you've corrupted your object.

Once you have the fix to copy as above, then operator = can be written in terms of the copy constructor:

template <class T> Vec<T>& Vec<T>::operator=(const Vec<T>& v) 
{
    // construct a temporary
    Vec<T> temp = v;

    // set the members
    m_size = m_alloc = temp.size();
    delete [] m_data;
    m_data = temp.m_data;

    // Now set temp.m_data to 0, so that destruction of temp doesn't delete
    // our memory
    temp.m_data = 0;
    return *this;
}

Basically, we construct a temporary from v, delete the this->m_data and then assign the elements of temp to this. Then we remove the guts of temp by setting the temp.m_data data to NULL. This needs to be done so that when temp dies, we don't want to delete the data we assigned to this.

Note that if the first line Vec<T> temp = v; throws an exception, no harm to this is done, thus exception safety is provided.

Here is the copy/swap idiom, as suggested by Captain Giraffe:

template <class T> class Vec {
//...
  void swap(Vec<T>& left, Vec<T>& right);
//..
};

template <class T> void Vec<T>::swap(Vec<T>& left, Vec<T>& right)
{
    std::swap(left.m_size, right.m_size);
    std::swap(left.m_alloc, right.m_alloc);
    std::swap(left.m_data, right.m_data);
}

template <class T> Vec<T>& Vec<T>::operator=(const Vec<T>& v)
{
    // construct a temporary
    Vec<T> temp = v;
    swap(*this, temp);
    return *this;
}

The difference here is that we're swapping the members of temp with this. Since temp will now contain the pointer that this used to have, when temp dies, it will be calling delete on this "old" data.