C ++ новый / удалить сложность гарантия по стандарту

Question

Есть ли гарантия сложности для операций выделения памяти в последних стандартах c ++? То есть, если у меня есть класс A, чей конструктор и деструктор по умолчанию выполняются в O (1), что такое big-O для «new A [N]» и «delete [] A»? Есть ли какая-либо сложность гарантии для нового int [N]?

Answer 1

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

Существуют сложные структуры управления кучей во время выполнения C ++, построенные на основе управления памятью на уровне ОС, которое может включать блокировки на уровне приложений, блокировки на уровне ОС, подкачки на основе файлов и т. д. c. По этим причинам в приведенном ниже ответе не обсуждается выделение памяти как таковое.

Однако, если мы сосредоточимся на новом выражении, сшиваем вместе [expr.new/22]:

Новое выражение, создающее объект типа T, инициализирует этот объект следующим образом: (22.1) Если новый инициализатор опущен, объект инициализируется по умолчанию ([dcl.init]).

и [dcl.init / 7]:

Инициализация по умолчанию объекта типа T означает: .... (7.2) Если T является типом массива, каждый элемент инициализируется по умолчанию .

Я могу заключить, что сложность такой операции будет O (N).

Answer 2

Я сомневаюсь, что есть какие-то точные гарантии, поскольку слишком многое зависит от платформы (представьте себе какую-то действительно странную теоретическую платформу, которую никто никогда не сделает, но сможет). Тем не менее, вы можете сделать определенные ожидания. Если создание и удаление занимает O(1), то ...

delete A[] размера n либо O(1), либо O(n) в зависимости от того, является ли A тривиально разрушаемым или требует нетривиального Процедура удаления. O(1) на самом деле может быть большим (не совсем O(1)), поскольку освобождение большого фрагмента последовательной памяти может занять некоторое время, но оно все еще незначительно в большем объеме вещей.

То же самое верно для new A[n]. Это может занять около (подделки) O(1), если A является тривиально конструируемым (например, int, т. Е. Разрешены данные tra sh) или O(n), если каждый элемент требует некоторой обработки O(1).

Как правило, вы не должны забывать случаи, когда строительство и разрушение затягиваются на A и могут занять много времени.