Временная сложность оператора delete []

Ответ 1

::operator delete[] документируется на cplusplus.com (который иногда нахмуривается):

operator delete[] можно вызывать явно как регулярную функцию, но в С++ delete[] - это оператор с очень специфическим поведением: выражение с оператором delete[], сначала вызывает соответствующие деструкторы для каждого элемента в array (если они относятся к типу класса), а затем вызывает функцию operator delete[] (т.е. эту функцию) для освобождения хранилища.

поэтому деструктор называется n раз (один раз для каждого элемента), а затем функция "освобождения" памяти освобождается один раз.

^{Обратите внимание, что каждое уничтожение может занять другое время (или даже сложность), чем другие. Как правило, большинство разрушений бывают быстрыми и имеют одинаковую сложность... Но это будет не так, если каждый уничтоженный элемент является сложным деревом или node или графом...}

Для примитивных типов, таких как int, фиктивный деструктор int является no-op. Возможно, компилятор оптимизировал бы это (если задано).

Вы должны проверить реальный C++11 стандарт или, по крайней мере, его поздний n3337, в котором говорится (спасибо Matteo Italia за указание, что в комментарии) в п. 5.3.3.6 страницы 110 n3337:

Если значение операнда выражения-удаления не является значением нулевого указателя, выражение-delete будет вызывать деструктор (если есть) для объекта или элементов удаляемого массива. В случае массив, элементы будут уничтожены в порядке убывания адреса (то есть в обратном порядке завершения их конструктора; см. 12.6.2)

Если вы используете -and trust enough- GCC 4.8 или лучше, вы могли бы использовать компилятор g++ с -fdump-tree-phiopt или -fdump-tree-all (будьте осторожны, они сбрасывают много файлов!) или плагин MELT, чтобы запросить промежуточный Gimple представление некоторого примера. Или используйте -S -fverbose-asm, чтобы получить код ассемблера. И вы также хотите добавить флаги оптимизации, такие как -O1 или -O2...

^{NB: IMHO, cppreference.com - также интересный сайт о С++, см. там о delete (как прокомментировано Cubbi)}

Ответ 2

Реализация delete и delete[] состоит из двух фаз:

• рекурсивный вызов деструкторам (если есть)
• освобождение памяти для удаленного объекта

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

Вторая точка не покрывается спецификацией С++. Таким образом, любой комплект компилятора/ОС может свободно принимать свою собственную стратегию.

Общая стратегия выделения/освобождения памяти выделяет целую страницу памяти при необходимости из ОС, а затем в каждом new/new[], возвращая кусок соответствующего размера, длина и атрибуты которого затем сохраняются внутри как верхний/нижний колонтитул. Соответствующий delete/delete[] может быть таким же простым, как обозначение того же фрагмента, что и "свободный", что явно O (1).

Если сложность освобождения памяти равна O (1), то сложность a delete по существу регулируется вызовами деструкторов. Реализация по умолчанию ничего (почти) ничего не делает, и O (1) для одного вызова, таким образом, общий O (n), где n - это число звонков (например, если объект destructed имеет два поля, деструктор которых вызывается, затем n = 1 (object) + 2 (o. fields) = 3).

Объединяя все части: вы можете произвольно увеличивать сложность, выполняя операции в деструкторе (который может быть написан вами), но вы не можете "выполнить лучше" ¹, чем O (n) (n, определенный в предыдущем абзаце). Формально правильный способ сформулировать это: "сложность delete - это Omega (n)" .

¹ позвольте мне быть немного неформальным в этой точке

Ответ 3

Для типов классов теоретическая сложность O(n). Деструктор вызывается для каждого элемента. Конечно, это зависит от реализации, чтобы придерживаться наблюдаемого поведения, поэтому, если деструктор является не-оператором или поведение такое же, как при простое выделение всего фрагмента как освобожденного, сложность может быть просто O(1).

Для примитивных типов компилятор, скорее всего, сразу выпустит весь фрагмент памяти, таким образом, сложность O(1).

Ответ 4

Какова временная сложность оператора delete[]?

Сумма требуемого времени, конечно, определена. Однако оператор применяется только к указателю на 1D-массив и, следовательно, O (1).Забастовкa >

Я имею в виду, как он реализован - он выполняет итерацию по всем элементам в массиве и вызывает деструктор для каждого элемента?

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

Этот оператор делает то же самое для примитивных типов (int и т.д.) и определяемые пользователем типы?

Сравнение несправедливо, потому что примитивные типы не имеют определяемого пользователем деструктора, и они не могут быть полиморфными.
Например, delete[] в полиморфном классе - это поведение undefined. то есть.

Base* p1 = new Derived, *p2 = new Derived[2];
delete p1; // ok
delete[] p2;  // bad