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

Я пишу более легкую версию некоторых контейнеров из STL для себя.C++: скорость std :: stack :: pop() метод

(Я знаю, что 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());

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

источник

2010-07-14 Ben Usman

Список, возможно, самый худший/самый медленный контейнер. Тот факт, что вы используете список для вашего стека, делает его хуже, потому что 'std :: stack' не (по умолчанию). – GManNickG

@GMan - Черт, я об этом не думал - я не использую std :: stack, поэтому я забыл, что он по умолчанию делит deque. Хорошая точка зрения. – Steve314

@GMan, Ну, и если мне нужна не сортированная группа объектов и возможность пройти через все (итерацию), что мне использовать? Задавать? –

Из-за delete topE.

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

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

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

Вы сказали, что лучше:

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

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

источник

2010-07-14 19:06:53 Stephen

@Charles: Вызывается деструктор объекта. 'delete' не вызывается, потому что объекты не хранятся в качестве указателей в контейнерах STL. –

@Charles Bailey - если вы храните указатели, он не будет удален. Destroy вызовет деструктор объекта - не обязательно удалить кучу. Мое редактирование сделало это более ясным? – Stephen

Я не поймал несколько вещей: 1. В чем разница между «удалением по указателю» (из кучи) и уничтожением объекта? 2. Я пытался выяснить, как работает deque, но нашел только одну тему форума: http://cboard.cprogramming.com/cplusplus-programming/78898-how-do-deques-work.html, в которой люди говорит, что deque - это связанный список. Странный. –

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

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

источник

2010-07-14 19:06:07

Фактически, 'std :: stack' использует deque по умолчанию. –

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

ответ

Смежные вопросы