Как реализовать vector :: clear ()? (цель исследования)

Question

Я пытаюсь реализовать свой собственный векторный класс (в учебных целях). В настоящее время я застрял на vector::clear(), как я могу это реализовать? Так не может быть, правда?

void clear() {
    for (size_t i = 0; i < _size; ++i) {
        _data = 0;//can't work with custom class
    }
}

Или

void clear() {
    delete[] _data;
    _data = new T[_cap];
    _size = 0;
}//can we make it better?

Или просто:

void clear() {
    _size = 0;//fastest, but user can still access the data
}
T& operator[](size_t pos) {
    if (pos >= _size) throw;//added to prevent from accessing "cleared" data
    return _data[pos];
}

Копался через libcxx и выяснилось, что они используют alloc_traits :: destroy , которые уничтожают каждый элемент в _data ??? Вот мой атрибут класса

T* _data;
size_t _size;
size_t _cap;

Answer 1

Если вы сохраняете емкость, превышающую размер, это означает, что вам нужно учитывать выделенную память, которая не содержит никаких объектов. Это означает, что подход new T[_cap] просто не работает:

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

Итак, вам нужно отделить выделение памяти от создания объекта :

• выделить память с помощью operator new. Обратите внимание, что это отличается от новое выражение , с которым вы наиболее знакомы.
• создать объект в выделенной памяти с помощью конструктора на месте (также известного как размещение new)
• уничтожить объект, явно вызвав деструктор
• освободить память с помощью operator delete

C ++ 17 приносит некоторую полезность функции для этой цели: std::uninitialized_default_construct, uninitialized_copy, std::destroy et c .; дополнительные сведения см. в Dynami c управлении памятью

Если вы хотите быть более универсальным c например std::vector, вы можете использовать вместо него распределители .

Имея это в виду, теперь отвечу на ваш конкретный c вопрос о clear. Поведение std::vector::clear: «Удаляет все элементы из контейнера. После этого вызова size() возвращает ноль. [...] Оставляет capacity() вектора без изменений». Если вам нужно такое же поведение, это означает:

void clear() noexcept
{
    for (T* it = _data; it != _data + _size; ++it)
        it->~T();

    // or
    std::destroy(_data, _data + size);

    _size = 0;
}

Как видите, реализация чего-то вроде std::vector далеко не тривиальна и требует некоторых экспертных знаний и методов.

Другой источник осложнений - строгая безопасность исключений . Давайте для примера рассмотрим случай push_back. Наивная реализация могла бы сделать это (псевдокод):

void push_back(const T& obj)
{
    if size == capacity
         // grow capacity
         new_data = allocate memory
         move objects from _data to new_data
         _data = new_data
         update _cap

    new (_data + _size) T{obj}; // in-place construct
    ++_size;
}

А теперь подумайте, что произойдет, если конструктор перемещения одного объекта бросит вызов при переходе к новой большей памяти. У вас есть утечка памяти, и самое худшее: у вас остались некоторые объекты в вашем векторе в перемещенном состоянии. Это переведет ваш вектор в недопустимое внутреннее состояние. Вот почему важно, чтобы std::vector::push_back гарантировал, что либо:

1. оператор успешен, либо
2. , если выбрано исключение, функция не действует.

Другими словами, он гарантирует, что никогда не оставляет объект в «промежуточном» или недопустимом состоянии, как это делает наша наивная реализация.

Answer 2

Единственная обязанность clear - вызвать деструктор для любых объектов, находящихся в массиве, и установить размер массива равным 0 (http://www.cplusplus.com/reference/vector/vector/clear/). Многие реализации на самом деле не освобождают память, а просто устанавливают конечный и последний указатели в массиве на начальный указатель после прохождения вектора и вызова деструктора для каждого элемента. Это делается как оптимизация, так что память все еще доступна, а вектор готов к go, если в вектор помещаются новые элементы.

Если вам не нужна эта конкретная оптимизация, ваша версия clear (), где вы просто удаляете [] данные, а затем перераспределяете, вполне разумно. Все зависит от того, какие компромиссы вы хотите сделать.