c++ - C++:std::stack::pop()方法的速度

我正在为自己编写一些STL容器的简化版本。

(我知道STL是由专业程序员编写的，如果认为自己可以比他们做得更好，那么我会太愚蠢或过于野心勃勃。当我编写列表(仅使用所需的方法)时，它的运行速度快了几倍。所以，我认为这是个好主意。不过，无论如何。)

我对std::stack::pop()的速度感到失望。我瞥了一眼souses，发现那里没有很好的算法。我想几乎和我一样:

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());

谁能解释为什么迭代器擦除速度更快？

最佳答案

由于delete topE。

使用STL(至少对于SGI实现)，不会对pop()进行自动删除。如果您已经动态分配了堆栈中的元素，则需要在调用pop()之前取消分配。

STL pop仅将堆栈大小缩短1(并破坏最后一个对象-不一定是删除堆)。

接下来的事情是(看起来)您正在使用链接列表来存储堆栈。这将比默认的STL容器慢得多(SGI使用deque)，因为您将丢失缓存局部性，并且需要为每个元素(new / delete)动态分配-而deque会一次动态分配堆栈块。

您说得最好:



至少现在:)尝试看看你有多近!