Shrink_to_fit() vs swap trick

У меня есть игра, в которой определенные игровые объекты появляются сразу, а затем исчезают, когда их уничтожают/убивают. Игровые объекты являются элементами в std::vector, и я хотел бы свести к минимуму использование памяти. Я привык к трюку подкачки,

std::vector<gameObject>(gameObjectVector.begin(), gameObjectVector.end()).swap(gameObjectVector);

но я заметил встроенный shrink_to_fit() из С++ 11. Однако он имеет линейную сложность, в то время как своп-трюк является постоянным. Разве своп-трюк не превосходит всех?

Ответ 1

Трюк с обменом не является фактически постоянным. Стоимость выполнения фактического свопа действительно равна O (1), но тогда стоимость деструктора std::vector срабатывает и очищает все выделенное пространство. Это может потенциально иметь стоимость & Omega; (n), если базовые объекты имеют нетривиальные деструкторы, так как std::vector должен идти и вызывать эти деструкторы. Там также затраты на вызов конструкторов копирования для всех элементов, хранящихся в исходном векторе, что аналогично & Omega; (n).

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

Ответ 2

Принятый ответ, который также получил на isocpp.org, неверен.

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