реализация std :: vector pop_back ()

Question

Я только начал работу со своими структурами данных, и я реализую какой-то массив в виде списка (~ = std :: vector). Мне было интересно, как pop_back () реализован так, чтобы он имел постоянную сложность? Он должен уменьшить размер на 1 и удалить последний элемент. Теперь я где-то видел, что он в основном уменьшает размер на 1 и уничтожает последний элемент с помощью некоторого итератора / указателя, но тогда почему мы не можем реализовать pop_front () таким же образом и просто перенаправить наш указатель на первый элемент на следующий?

template <typename T>
ArrayList<T>& ArrayList<T>::pop_back()
{
    --size_;
    auto p = new T[size_];
    std::copy(elements_,elements_+size_,p);
    delete [] elements_;   //elements_ being my pointer
    elements_ = p;
    return *this;
}

Answer 1

Это не так, как обычно реализуется pop_back (). Хотя это деталь реализации, обычно ваш массив list / vector / dynamici c отслеживает два размера: один фактический размер списка, а другой - емкость. Емкость - это размер основной выделенной памяти. Теперь pop_back () просто уменьшает размер на 1 и запускает деструктор для последнего элемента (не путайте уничтожение, то есть вызов метода ~T() с оператором delete). Это ничего не перемещает. Емкость остается прежней. Вся операция не зависит от размера списка (в отличие от вашей реализации).

Обратите внимание, что вы не можете сделать то же самое с pop_front () простым способом. Вы должны будете отслеживать начало и конец списка, а также основную память (и в зависимости от подхода: либо размер хранилища и емкость, либо рассчитать их во время выполнения). Что требует больше памяти и потенциально больше операций с процессором. А также такая структура становится странной. Вы знаете емкость, вы знаете размер, но вы на самом деле не знаете, сколько push_back () вы можете сделать до того, как произойдет изменение размера (вы знаете только, что число ограничено «емкость минус размер», но оно может быть меньше). Если вы не добавите эту информацию в свою структуру, которая снова либо потребляет память, либо процессор.

Примечание: Если вы собираетесь использовать необработанные деструкторы, не используйте оператор delete[] совсем. Операция удаления в значительной степени "вызов деструкторов + освобождение памяти". И поэтому, если вы уничтожите вручную, то дополнительный вызов delete[] приведет к неопределенному поведению. Если вы на самом деле не выделяете char памяти (независимо от T) и не используете для размещения новых (что также требует некоторых ручных вычислений размера и смещения). И это хороший способ реализации такого вектора, хотя требуется дополнительная осторожность (ручное отслеживание памяти - ab *** h).

Answer 2

Причина, по которой у вас возникают проблемы с реализацией pop_back() со сложностью O (1), заключается в том, что, используя new[] и delete[], вы связали время жизни содержащихся в них объектов с хранилище ваших объектов. Под этим я подразумеваю, что при создании необработанного динамически распределенного массива с использованием new T[n]; происходят две вещи: 1) выделяется хранилище и 2) объекты создаются в этом хранилище. И наоборот, delete[] сначала уничтожит все объекты (вызовет их деструкторы), а , а затем высвободит базовую память обратно в систему.

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

В вашей функции pop_back() оказывается, что вы хотите иметь возможность уничтожить только один объект в массиве без уничтожения всех других объектов или освобождения их хранилища. К сожалению, это невозможно при использовании new[] и delete[]. Способ, которым std::vector и некоторые другие контейнеры работают вокруг этого, заключается в использовании языковых возможностей более низкого уровня. Как правило, это делается путем выделения непрерывной области необработанной памяти (набираемой как unsigned char или std::byte, или с использованием таких помощников, как std::aligned_storage), выполнения тонн проверок бухгалтерского учета и безопасности и дополнительная работа, а затем использование размещение new для создания объекта в этой необработанной памяти. Чтобы получить доступ к объекту, вы должны вычислить смещения в (массиве) необработанной памяти и использовать reinterpret_cast, чтобы получить указатель на объект, который вы там поместили. Это также требует явного вызова деструктора объекта. Работая на этом низком уровне, буквально каждая деталь времени жизни объекта находится в ваших руках, и это очень утомительно и подвержено ошибкам. Я не рекомендую делать это. Но это возможно, и это позволяет реализовать std::vector::pop_back() в сложности O (1) (без аннулирования итераторов для предыдущих элементов).

Answer 3

Когда вы pop_back на стандартном векторе, вы фактически не освобождаете связанную память. Только последний элемент уничтожается, size уменьшается, а capacity - нет. Другие элементы не копируются и не перемещаются. Это трудно скопировать с помощью пользовательских контейнеров, потому что вы не можете delete или уничтожить отдельный элемент массива.

По этой причине std::vector<T> фактически не использует массив T. Он выделяет необработанную неинициализированную память (что-то вроде std::aligned_storage) и выполняет размещение new для создания элементов в этом выделении по мере необходимости. Размещение new - это версия new, которая не выделяет, а вместо этого получает указатель, в котором она должна создавать объект. Это означает, что время жизни объекта не связано напрямую с его распределением и однозначно позволяет вам уничтожать элементы индивидуально, не освобождая его базовую память, вызывая его деструктор. Внутренне это будет выглядеть примерно так: pop_back() { back().~T(); --size; }.

Answer 4

Мне было интересно, как реализован pop_back (), чтобы он имел постоянную сложность? Он должен уменьшить размер на 1 и удалить последний элемент.

Точно. Это все, что нужно сделать. Неважно, сколько элементов у вас есть.

Это определение постоянной сложности.

Теперь я где-то видел, что он в основном уменьшает размер на 1 и уничтожает последний элемент через некоторые итератор / указатель

Это верно. Память все еще распределена, но живущий там объект подвергается логическому разрушению.

, но тогда почему мы не можем реализовать pop_front () таким же образом и просто перенаправить наш указатель на первый элемент на следующий ?

Можно! Вот как работает std::deque, поэтому std::deque имеет pop_front() с постоянной сложностью.

Однако вы не можете сделать это, поддерживая другие дешевые операции, потому что это обязательно вызывает фрагментацию памяти после несколько раз. Память распределяется по частям, а векторы должны быть распределены по смежным частям. Представьте, что векторы просто «игнорировали» первый элемент, если вы pop_front() сделали это - теперь сделайте это пятьсот раз. У вас неиспользованная память, просто сидящая там вечно. Фигово! А что, если вы хотите добавить на фронт сейчас? В конце концов, если вы не захотите использовать бесконечную память, вам придется разделить вашу память на отдельные куски, но это нарушит гарантированную непрерывность.

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