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

Question

我正在为自己编写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());

任何人都可以解释为什么迭代器擦除更快？

Answer 1

因为delete topE.

使用STL(至少对于SGI实现),没有自动删除pop().如果您已动态分配堆栈中的元素,则由您在调用之前解除分配pop().

STL pop只是将堆栈大小缩短一个(并销毁最后一个对象 - 不一定是堆删除).

接下来就是(看起来像)你正在使用链表来存储堆栈.这将是wayyyy比默认的STL容器较慢(SGI使用deque),因为你会失去缓存位置,需要动态分配的每个元素(new/ delete) -而deque将动态地在时间分配堆栈块.

你说得最好:

STL是由专业程序员编写的,如果我认为我可以写得比他们更好,我就太愚蠢或太野心勃勃

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