C++: speed of std::stack::pop() method

Question

I'm writing a lighter version of some containers from STL for myself.

(I know that STL was written by professional programmers and I am too stupid or too ambitious if think that I can write it better than they did. When I wrote my list (only with method I need), it worked few times faster. So, I thought it's a good idea. But, anyway.)

I was disappointed by speed of std::stack::pop(). I glanced at souses and found that there's no great algorithm. Nearly as I did, I suppose:

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

But it works much slower than STL's one.

erase(--end());

Can anybody explain me why iterator erase is faster?

Answer 1

It's a bit hard to say much about the performance of the standard library stack, because it's a container adapter, not a container in itself. All the operations get passed through to the underlying container with (at most) minor modifications.

There are a couple of obvious possibilities though. First of all, you're apparently using a linked list; by default, std::stack will use a vector, at least if memory serves. Second, it's just erasing the item, which destroys the object, but does not release the underlying memory. Yours appears to destroy the object and delete the memory.

Answer 2

Because of delete topE.

With STL (at least for the SGI implementation), there is no automatic delete on pop(). If you've dynamically allocated the elements in the stack, it's up to you to deallocate before calling pop().

The STL pop just shortens the stack size by one (and destroys the last object - not necessarily a heap delete).

The next thing is that (it looks like) you're using a linked list to store the stack. That's going to be wayyyy slower than the default STL container (SGI uses deque) because you'll lose cache locality and require dynamic allocation for each element (new/delete) - whereas a deque will dynamically allocate chunks of the stack at a time.

You said it best:

STL was written by professional programmers and I am too stupid or too ambitious if think that I can write it better than they did

At least for now :) Try and see how close you get!