как реализовать эффективное добавление в C ++ шаблонный класс списка - PullRequest
Новая
       48

как реализовать эффективное добавление в C ++ шаблонный класс списка

0 голосов
/ 01 февраля 2019

Предположим, у нас есть шаблонный класс списка c ++.Да, вектор существует, но суть заключается в том, чтобы знать, как решить эту проблему.

Конструктор выделяет блок из n объектов типа T, но не инициализируется, поскольку они еще не используются.

В методе add мы хотим скопировать новый объект, но использование operator = невозможно, поскольку operator = сначала уничтожит существующий объект, который никогда не был инициализирован.Как копировать один объект в данные [используемые]? 

#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 ]

0 голосов
/ 01 февраля 2019

Вы должны использовать размещение new: 

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

Размещение new создает объект в уже выделенной памяти.

0 голосов
/ 01 февраля 2019

Для того, что вы пытаетесь сделать, вам нужно вызвать T конструктор копирования , используя place-new .И не забудьте также реализовать правило 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");
}
0 голосов
/ 01 февраля 2019

Класс DynArray имеет тип T, поэтому вы должны просто выделить массив типа T с размером initialCap, который просто 

new T[initialCap];

Для встроенных типовНапример, int, элементы остаются неинициализированными.

Для других, таких как строка, для инициализации элементов вызывается конструктор T по умолчанию.

В методе add нам нужноскопировать в новый объект, но использование operator = невозможно, потому что operator = сначала уничтожит существующий объект

data[used++] = e; Это прекрасно.Он присваивает e на data[used] - вызывает оператор присваивания строки, и это не вызовет никаких проблем.Однако, когда ваш массив увеличивается, вам нужно будет выделить новые массивы с двойной емкостью, скопировать элементы и уничтожить старые данные.

...