C++ размещение нового в домашнем векторном контейнере

Question

Здесь есть некоторые вопросы, похожие на них, но они не могли помочь мне разобраться в этом. Кроме того, я даю полный пример кода, поэтому другим может быть проще понять.

Я создал векторный контейнер (не использовал stl для соображений памяти), который использовал только оператор = для push_back *, и как только я пришел на новое место размещения, я решил ввести в него дополнительный «emplace_back» **.

* (T :: оператор = ожидается иметь дело с управлением памятью)

** (название взято из аналогичной функции в станд :: вектор, который я столкнулся позже, оригинальное название I это было беспорядок).

Я прочитал кое-что из-за опасности использования нового нового оператора new [], но не мог понять, соответствует ли это или нет, а если нет, что с ним не так, и что я должен заменить , поэтому я буду благодарен за вашу помощь.

Это Каус упрощенный код, без итераторов, и не расширенные функциональные возможности, но это делает пункт:

template <class T> 
class myVector { 
public : 
    myVector(int capacity_) { 
     _capacity = capacity_; 
     _data = new T[_capacity]; 
     _size = 0; 
    } 

    ~myVector() { 
     delete[] _data; 
    } 

    bool push_back(T const & t) { 
     if (_size >= _capacity) { return false; } 
     _data[_size++] = t; 
     return true; 
    } 

    template <class... Args> 
    bool emplace_back(Args const & ... args) { 
     if (_size >= _capacity) { return false; } 
     _data[_size].~T(); 
     new (&_data[_size++]) T(args...); 
     return true; 
    } 

    T * erase (T * p) { 
     //assert(/*p is not aligned*/); 
     if (p < begin() || p >= end()) { return end(); } 
     if (p == &back()) { --_size; return end(); } 
     *p = back(); 
     --_size; 
     return p; 
    } 

    // The usual stuff (and more) 
    int capacity()   { return _capacity;    } 
    int size()    { return _size;     } 
    T * begin()    { return _data;     } 
    T * end()    { return _data + _size;   } 
    T const * begin() const { return _data;     } 
    T const * end() const { return _data + _size;   } 
    T & front()    { return *begin();    } 
    T & back()    { return *(end() - 1);   } 
    T const & front() const { return *begin();    } 
    T const & back() const { return *(end() - 1);   } 
    T & operator[] (int i) { return _data[i];    } 
    T const & operator[] (int i) const { return _data[i]; } 
private: 
    T * _data; 
    int _capacity; 
    int _size; 
}; 

Благодарности

Answer 1

Я читал некоторые вещи об опасности использования размещение нового по сравнению с оператором new [], но не удалось выяснить, соответствует ли следующее: , а если нет, то что с ним не так [...]

Для operator new[] против размещения новых, это действительно очень плохо (как в типично-crashy тип неопределенного поведения), если вы смешиваете две стратегии вместе.

Главный выбор, который вы обычно должны сделать, - это использовать тот или иной. Если вы используете operator new[], то вы заранее создадите все элементы для всей емкости контейнера и перезапишите их в таких методах, как push_back. Вы не уничтожаете их при удалении в методах, таких как erase, просто держите их там и настраивайте размер, перезаписывайте элементы и т. Д. Вы оба создаете и распределяете несколько элементов за один раз с помощью operator new[], и уничтожаете и освобождаете их всех за один раз, используя operator delete[].

Почему Размещение Новый используется для стандартных контейнеров

Первое, что нужно понять, если вы хотите, чтобы начать прокатки свои собственные векторы или другие стандартные-совместимые последовательности (которые не просто связаны структуры с одним элементом на узел) таким образом, который фактически уничтожает элементы при их удалении, создает элементы (а не просто перезаписывать их) при добавлении, заключается в том, чтобы отделить идею выделения памяти для контейнера и построения элементов для него на месте. Так что, наоборот, в этом случае размещение нового неплохо. Это принципиальная необходимость достижения общих качеств стандартных контейнеров. Но в этом контексте мы не можем смешивать его с operator new[] и operator delete[].

Например, вы можете выделить память для хранения 100 экземпляров T в reserve, но вы также не хотите, чтобы их также устанавливали по умолчанию. Вы хотите построить их в таких методах, как push_back, insert, resize, fill ctor, range ctor, copy ctor и т. Д.- методы, которые фактически добавляют элементы, а не только способность их удерживать. Вот почему нам нужно размещение новое.

В противном случае мы потеряем общность std::vector, которая позволяет избежать построения элементов, которые не существуют, может копировать построить в push_backs, а не просто перезаписать существующие с operator= и т.д.

Итак, давайте начнем с конструктора:

_data = new T[_capacity]; 

... это вызовет конструкторы по умолчанию для всех элементов. Мы не хотим этого (ни требование по умолчанию для ctor, ни этот расход), так как цель использования placement new заключается в построении элементов на месте выделенной памяти, и это уже построило бы все элементы. В противном случае любое использование места размещения в любом месте будет пытаться построить уже построенный элемент во второй раз и будет UB.

Вместо этого вы хотите что-то вроде этого:

_data = static_cast<T*>(malloc(_capacity * sizeof(T))); 

Это только дает нам сырой кусок байтов.

Во-вторых, для push_back, вы делаете:

_data[_size++] = t; 

Это пытается использовать оператор присваивания, и после нашей предыдущей модификации, на неинициализированного/недопустимый элемент, который еще не был построен. Таким образом, мы хотим:

new(_data + _size) T(t); 
++size; 

... что делает его использование конструктора копирования. Это делает его совпадением с тем, что должно делать push_back: создание новых элементов в последовательности вместо простой перезаписи существующих.

Ваш метод стирания требует некоторой работы даже на базовом уровне логики, если вы хотите обрабатывать удаления из середины контейнера. Но только с точки зрения управления ресурсами, если вы используете новое место размещения, вы хотите вручную вызвать деструкторы для удаленных элементов. Например:

if (p == &back()) { --_size; return end(); } 

... должно быть больше как:

if (p == &back()) 
{ 
    --size; 
    (_data + _size)->~T(); 
    return end(); 
} 

Ваш emplace_back вручную вызывает деструктор, но он не должен этого делать. emplace_back должен добавлять, а не удалять (и уничтожать) существующие элементы. Он должен быть очень похож на push_back, но просто вызывает движение ctor.

Ваш деструктор делает это:

~myVector() { 
    delete[] _data; 
} 

Но опять же, это UB, когда мы берем этот подход. Мы хотим, чтобы что-то подобное:

~myVector() { 
    for (int j=0; j < _size; ++j) 
     (_data + j)->~T(); 
    free(_data); 
} 

Там по-прежнему намного больше, чтобы покрыть как исключение-безопасности, которая в целом отличается банкой червей.

Но это должно помочь вам начать с правильного использования места размещения нового в структуре данных против некоторого распределителя памяти (malloc/free в этом примерном случае).

И последнее, но не менее важное:

(не может использовать СТЛ по причинам памяти)

... это может быть необычная причина. Ваша реализация не обязательно использует меньшую память, чем vector с reserve, вызываемой заранее, чтобы дать ей capacity. Вы можете сбрить несколько байтов на уровне каждого контейнера (не на уровне каждого элемента) с выбором 32-битных интегралов и не нужно хранить распределитель, но это будет очень небольшая экономия памяти в обмен на лодку работы.

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

В конце концов мне пришлось изобретать некоторые vectors и векторные контейнеры по причинам ABI (нам нужен контейнер, через который мы могли бы пройти через наш API, гарантированный тем же ABI, независимо от того, какой компилятор использовался для создания плагина) , Даже тогда я бы предпочел бы просто использовать std::vector.

Обратите внимание, что если вы просто хотите взять под контроль то, как vector выделяет память, вы можете сделать это, указав свой собственный распределитель с помощью совместимого интерфейса. Это может быть полезно, например, если вам нужен vector, который выделяет 128-битную выровненную память для использования с выровненными инструкциями перемещения с использованием SIMD.