代码之家 › 专栏 › 技术社区 › Dov

如何实现高效的添加C++模板列表类

placement-new templates c++

Dov · 技术社区 · 6 年前

假设我们有一个模板化C++列表类。是的,向量是存在的,但关键是要知道如何处理这个问题。

构造函数分配一个由n个类型为t的对象组成的块,但由于这些对象尚未使用而未初始化。

在Add方法中,我们希望在一个新对象中复制,但是使用运算符==是不可能的,因为运算符==首先销毁已经初始化的对象。如何将一个对象复制到[使用的]数据中?

#include <string>
template<typename T>
class DynArray {
private:
  int capacity;
  int used;
  T* data;
public:
  DynArray(int initialCap) : capacity(initialCap), used(0), data((T*)new char[sizeof(T)*capacity]) {}
  void add(const T& e) {
    //TODO: if the dynarray is full, grow
    data[used++] = e; //ERROR! Should use copy constructor!!!
  }
};

int main() {
  DynArray<std::string> a(5);
  a.add(std::string("abc"));
}

3 回复 | 直到 6 年前

zedu 6 年前

您应该使用Placement New:

void add(const T& e) {
    //TODO: if the dynarray is full, grow
    new (data + used) T(e);
    used++;
 }

Placement New在已分配的内存中构造一个对象。

Remy Lebeau 6 年前

如果你想做什么,你需要打电话给 T 的 copy constructor 使用 placement-new . 别忘了实现 Rule of 3/5/0 也:

template<typename T>
class DynArray {
private:
  int capacity;
  int used;
  T* data;

public:
  DynArray(int initialCap = 0) : capacity(0), used(0), data(0) {
    reserve(initialCap);
  }

  DynArray(const DynArray &src) : capacity(0), used(0), data(0) {
    reserve(src.capacity);
    for(int i = 0; i < src.used; ++i) {
      add(src.data[i]);
    }
  }

  // C++11 and higher only...
  DynArray(DynArray &&src) : capacity(src.capacity), used(src.used), data(src.data) {
    src.capacity = src.used = 0;
    src.data = 0;
  }

  ~DynArray() {
    clear();
    delete[] reinterpret_cast<char*>(data);
  }

  DynArray& operator=(const DynArray &rhs) {
    if (&rhs != this) {
      DynArray(rhs).swap(*this);
    }
    return *this;
  }

  // C++11 and higher only...
  DynArray& operator=(DynArray &&rhs) {
    DynArray(std::move(rhs)).swap(*this);
    return *this;
  }

  void swap(DynArray &other) {
    std::swap(data, other.data);
    std::swap(used, other.used);
    std::swap(capacity, other.capacity);
  }

  void clear() {
    resize(0);
  }

  void reserve(int newCap) {
    // TODO: round up newCap to an even block size...
    if (newCap <= capacity) return;
    T *newData = reinterpret_cast<T*>(new char[sizeof(T) * newCap]);
    for(int i = 0; i < used; ++i) {
      new (newData + i) T(data[i]);
    }
    delete[] reinterpret_cast<char*>(data);
    data = newData;
    capacity = newCap;
  }

  void resize(int newSize) {
    if (newSize < 0) newSize = 0;
    if (newSize == used) return;
    if (newSize > used) {
      reserve(newSize);
      for(int i = used; i < newSize; ++i) {
        new (data + i) T();
        ++used;
      }
    }
    else {
      for(int i = used-1; i >= newSize; --i) {
        data[i]->~T();
        --used;
      }
    }
  }

  void add(const T& e) {
    if (used == capacity) {
        reserve(capacity * 1.5);
    }
    new (data + used) T(e);
    ++used;
  }
};

#include <string>

int main() {
  DynArray<std::string> a(5);
  a.add("abc");
}

gchen 6 年前

这个 DynArray 类有一种类型 T ,所以您应该简单地分配一个t类型的数组,其大小为 initialCap ,这很简单

new T[initialCap];

对于内置类型,例如int,元素保持未初始化状态。

对于其他的,比如string,调用t的默认构造函数来初始化元素。

在add方法中,我们希望复制到一个新对象中,但是不能使用operator=因为operator=将首先破坏现有对象

data[used++] = e; 这很好。它指派 e 到 data[used] -调用字符串的赋值运算符,不会造成任何问题。但是,当阵列增长时,您需要分配双容量的新阵列、复制元素并销毁旧数据。