在动态数组 class 的实现中发现 Bug。构建字符串列表后崩溃

Question

我过去写过一个 DynamicArray class 类似于有效的向量。我还写了一个演示，其中性能很差，因为它只有长度和指针，并且每次都必须增长。因此添加 n 个元素是 O(n^2).

这段代码的目的只是为了展示新的放置。该代码适用于不使用动态内存的类型，但对于字符串它会崩溃并且 -fsanitize=address 显示在 addEnd() 方法中分配的内存正在打印中使用。我注释掉了 removeEnd，代码只是添加元素，然后打印它们。我只是没有看到错误。谁能找出问题所在？

#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

memcpy 的使用仅对 trivially copyable 类型有效。

编译器甚至可能会就此警告您，例如：

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]

请注意，您的代码不会移动对象，而是 memcpy 它们，这意味着如果它们具有例如指向对象内部某个位置的内部指针，那么您的 mem-copied对象仍将指向旧位置。

Trivially Copyable 类型不会有指向对象本身位置的内部指针（或可能阻止 mem-copying 的类似问题），否则类型必须在复制时处理它们并实施适当的复制和赋值操作，这将使它 non-trivially 可复制。

为了修复 addEnd 方法以进行正确的复制，对于 non-trivially 可复制类型，如果您使用 C++17，您可以在代码中添加这样的 if-constexpr：

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]));
    }
}

如果您使用的是 C++14 或更早版本，则需要两个版本的 SFINAE 复制。

请注意，代码的其他部分可能也需要一些修复。

在动态数组 class 的实现中发现 Bug。构建字符串列表后崩溃

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

c++

templates

placement-new