Реализация push_back (T && c) в пользовательском классе Vector <T> - PullRequest
Новая
       82

Реализация push_back (T && c) в пользовательском классе Vector <T>

0 голосов
/ 07 апреля 2020

Как часть присваивания в Uni, я должен реализовать частичный клон класса stl :: vector. Я справился почти со всей функциональностью, но я озадачен тем, как сделать push_back (T && c). Нам не разрешено реализовывать emplace так, как использует сам STL. Объект, используемый для проверки реализации push_backs, проверяет, какие конструкторы и операторы вызываются на нем. Для этого ТОЛЬКО конструктор Move может быть вызван. Из-за всей короны hoohaa чрезвычайно трудно получить какую-либо помощь от учителя / других учеников.

Это то, что я имею до сих пор: 

template <typename T>
void Vector<T>::push_back(T&& c)
{
  // code that resizes the vector if needed. Checked to make sure it doesn't invoke anything.
  T* a = new T(std::move(c)); // Invokes the Move Constructor, which is fine.
  auto b = (_vector_data+_vector_size); // Destination
  //std::move(); Move invokes MA
  //std::swap(b, a); // Doesn't work, swaps but the value of a ends up somewhere else, I use this method in push_back(const T& c) successfully.
  //std::copy(); // Copy invokes CA
  ++_vector_size;
}

_vector_data это T *, _vector_size это a size_t.

Чтобы проиллюстрировать, почему я подумал об этих шаблонах, есть еще один push_back: 

template <typename T>
void Vector<T>::push_back(const T& c)
{
  // code that resizes the vector if needed.
  T* a = new T(c); // Invokes CC.
  auto b = (_vector_data+_vector_size); // Destination
  std::swap(b, a);
  ++_vector_size;
}

Я в полной растерянности, что мне делать. Я просмотрел исходный материал, книгу и Google, но, полагаю, я был бы слишком глуп, чтобы понять, что я делаю неправильно или где искать: P Halp?

Я также посмотрел на это: Векторная реализация push_back move , которая выглядит как моя первая попытка. Тест не пройден, поскольку в последней строке вызывается оператор назначения копирования, что приводит к ошибочному утверждению.

Редактировать:

Для пояснения. Часть тестовой программы выполняет это: 

struct C {
    static std::string usedConstr;
    void Test() {}
    C() {
        usedConstr += "DC";
    }
    C(const C& c) {
        usedConstr += "CC";
    }
    C(C&& c) {
        usedConstr += "MC";
    }
    C& operator=(const C& c) {
        usedConstr += "CA";
        return *this;
    }
    C& operator=(C&& c) {
        usedConstr += "MA";
        return *this;
    }
};

std::string C::usedConstr{};

//Test push_back&&
void TestMove() {
    Vector<C> a;
    C c;
    assert(C::usedConstr == "DC");
    a.reserve(4);
    C::usedConstr = "";
    a.push_back(c);
    assert(C::usedConstr == "CC");
    C::usedConstr = "";
    a.push_back(std::move(c));
    assert(C::usedConstr == "MC");
}

Где это последнее утверждение, которое не удалось. Я не могу туда добраться, только вызвав конструктор Move.

Ответы [ 2 ]

2 голосов
/ 07 апреля 2020

std::vector обычно реализуется путем выделения памяти через operator new или некоторого распределителя, передаваемого в векторный класс, и создания новых объектов в этом хранилище. Вот некоторая демонстрация для случая вызова operator new напрямую без использования распределителя. (Реальное std::vector всегда использует распределитель, std::allocator по умолчанию.): 

_vector_data = static_cast<T*>(::operator new(sizeof(T)*new_capacity));

Это выделяет память, но явно не создает никаких объектов. (Обратите внимание, что это память правильно выровнена только для типов с невыровненным выравниванием , но это должно быть приемлемым ограничением.)

Затем, чтобы поместить новый объект в это хранилище, вы должны использовать нераспределенное место размещения новое : 

template <typename T>
void Vector<T>::push_back(T&& c)
{
    ::new(static_cast<void*>(_vector_data+_vector_size)) T(std::move(c));
    ++_vector_size;
}

(только для того, чтобы сначала убедиться, что емкости достаточно)

Если вас это не волнует В некоторых случаях, связанных с перегрузками класса operator new, вы можете использовать 

new(_vector_data+_vector_size) T(std::move(c));

вместо 

::new(static_cast<void*>(_vector_data+_vector_size)) T(std::move(c));

и 

operator new

вместо 

::operator new

Чтобы удалить элементы, вы бы затем явно вызвали их деструкторы, например, 

(_vector_data+_vector_size)->~T();

и освободили бы память, вызвав operator delete, соответствующий форме, которую вы использовали для operator new.

Технически это имеет неопределенное поведение до C ++ 20, потому что арифметика указателя c, как в _vector_data+_vector_size, допустима только в том случае, если _vector_data указывает на элемент массива, но мы никогда не создавали массив. Начиная с C ++ 20 этот массив создается неявно .

Невозможно реализовать std::vector, который имеет правильную семантику массива для указателей на его элементы в соответствии с заданными вами требованиями. до C ++ 20, не полагаясь на семантику, которая является неопределенным поведением в соответствии со стандартом, хотя это неопределенное поведение является скорее техническим, и, вероятно, никогда не вызовет проблем на практике.

0 голосов
/ 07 апреля 2020

Казалось бы, вы забыли настроить размер вектора в этой версии push_back. 

template <typename T>
void Vector<T>::push_back(T&& c)
{
  T* a = new T(std::move(c)); // Invokes the Move Constructor, which is fine.
  auto b = (_vector_data+_vector_size); // Destination
  std::move(b,a);
  ++_vector_size;  // WHOOPS
}

И, поскольку я здесь, нет необходимости назначать указатель на a. Это неправильный пункт назначения. 

void Vector<T>::push_back(T&& c)
{
  auto b = (_vector_data+_vector_size); // Correct destination
  b = new T(std::move(c)); // Invokes the Move Constructor, which is fine.
  ++_vector_size;
}
...