C ++: скорость метода std :: stack :: pop ()

Question

Я пишу облегченную версию некоторых контейнеров из STL для себя.

(Я знаю, что STL был написан профессиональными программистами, и я слишком глуп или слишком честолюбив, если думаю, что могу написать это лучше, чем они. Когда я писал свой список (только с помощью метода, который мне нужен), он работал несколько раз быстрее. Итак, я подумал, что это хорошая идея. Но, в любом случае.)

Я был разочарован скоростью std::stack::pop(). Я взглянул на Соуза и обнаружил, что нет хорошего алгоритма. Я полагаю, почти так же, как и я:

void pop()
{
  if(topE) // topE - top Element pointer
  {
     Element* n_t = topE->lower; // element 'under' that one
     delete topE;
     topE = n_t;
  }
}

Но он работает намного медленнее, чем у STL.

erase(--end());

Кто-нибудь может мне объяснить, почему стирание итератора происходит быстрее?

Answer 1

Из-за delete topE.

С STL (по крайней мере для реализации SGI) автоматическое удаление на pop() отсутствует. Если вы динамически распределяете элементы в стеке, вам нужно освободить их перед вызовом pop().

Всплывающее окно STL просто сокращает размер стека на единицу (и уничтожает последний объект - не обязательно удаление кучи).

Следующее, что (похоже) вы используете связанный список для хранения стека. Это будет wayyyy медленнее, чем контейнер STL по умолчанию (SGI использует deque), потому что вы потеряете локальность кэша и потребует динамического выделения для каждого элемента (new / delete) - тогда как deque будет динамически распределять порции стека за один раз.

Ты сказал это лучше всего:

STL был написан профессиональными программистами, и я слишком глуп или слишком честолюбив, если думаю, что могу написать это лучше, чем они

По крайней мере, пока :) Попробуйте и посмотрите, как близко вы подходите!

Answer 2

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

Хотя есть несколько очевидных возможностей.Прежде всего, вы, очевидно, используете связанный список;по умолчанию std::stack будет использовать вектор, по крайней мере, если память служит.Во-вторых, это просто стирает элемент, который уничтожает объект, но не освобождает основную память.Ваш, кажется, уничтожает объект и удаляет память.