Finding Bug in implementation of dynamic array class. Crashes after building list of strings

Question

I have written a DynamicArray class in the past analogous to vector which worked. I have also written as a demo, one where the performance is bad because it has only length and pointer, and has to grow every time. Adding n elements is therefore O(n^2).

The purpose of this code was just to demonstrate placement new. The code works for types that do not use dynamic memory, but with string it crashes and -fsanitize=address shows that the memory allocated in the addEnd() method is being used in printing. I commented out removeEnd, the code is only adding elements, then printing them. I'm just not seeing the bug. can anyone identify what is wrong?

#include <iostream>
#include <string>
#include <memory.h>
using namespace std;

template<typename T>
class BadGrowArray {
private:
  uint32_t size;
  T*       data;
public:
  BadGrowArray() : size(0), data(nullptr) {}
  ~BadGrowArray() {
      for (uint32_t i = 0; i < size; i++)
        data[i].~T();
      delete [] (char*)data;
  }
  BadGrowArray(const BadGrowArray& orig) : size(orig.size), data((T*)new char[orig.size*sizeof(T)]) {
      for (int i = 0; i < size; i++)
        new (data + i) T(orig.data[i]);
  }
  BadGrowArray& operator =(BadGrowArray copy) {
    size = copy.size;
    swap(data, copy.data);
    return *this;
  }
  void* operator new(size_t sz, void* p) {
    return p;
  }
  void addEnd(const T& v) {
     char* old = (char*)data;
     data = (T*)new char[(size+1)*sizeof(T)];
     memcpy(data, old, size*sizeof(T));
     new (data+size) T(v); // call copy constructor placing object at data[size]
     size++;
     delete [] (char*)old;
  }
  void removeEnd() {
     const char* old = (char*)data;
     size--;
     data[size].~T();
     data = (T*)new char[size*sizeof(T)];
     memcpy(data, old, size*sizeof(T));
     delete [] (char*)old;
  }
  friend ostream& operator <<(ostream& s, const BadGrowArray& list) {
      for (int i = 0; i < list.size; i++)
        s << list.data[i] << ' ';
      return s;
  }
};
class Elephant {
    private:
        string name;
    public:
        Elephant() : name("Fred") {}
        Elephant(const string& name) {}
};
int main() {
    BadGrowArray<int> a;
    for (int i = 0; i < 10; i++)
        a.addEnd(i);
    for (int i = 0; i < 9; i++)
        a.removeEnd();
    // should have 0
    cout << a << '\n';

    BadGrowArray<string> b;
    b.addEnd("hello");
    string s[] = { "test", "this", "now" };
    
    for (int i = 0; i < sizeof(s)/sizeof(string); i++)
        b.addEnd(s[i]);
    //  b.removeEnd();
    cout << b << '\n';

    BadGrowArray<string> c = b; // test copy constructor
    c.removeEnd();
    c = b; // test operator =
}

Answer 1

The use of memcpy is valid only for trivially copyable types.

The compiler may even warn you on that, with something like:

warning: memcpy(data, old, size * sizeof(T));
         writing to an object of non-trivially copyable type 'class string'
         use copy-assignment or copy-initialization instead [-Wclass-memaccess]

Note that your code do not move the objects, but rather memcpy them, which means that if they have for example internal pointers that point to a position inside the object, then your mem-copied object will still point to the old location.

Trivially Copyable types wouldn't have internal pointers that point to a position in the object itself (or similar issues that may prevent mem-copying), otherwise the type must take care of them in copying and implement proper copy and assignemnt operations, which would make it non-trivially copyable.

To fix your addEnd method to do proper copying, for non-trivially copyable types, if you use C++17 you may add to your code an if-constexpr like this:

if constexpr(std::is_trivially_copyable_v<T>) {
    memcpy(data, old, size * sizeof(T));
}
else {
    for(std::size_t i = 0; i < size; ++i) {
        new (data + i) T(std::move_if_noexcept(old[i]));
    }
}

In case you are with C++14 or before, two versions of copying with SFINAE would be needed.

Note that other parts of the code may also require some fixes.