56

I have a c++ stack named pages. As I have no clear() function to clear a stack, I wrote the following code:

stack<string> pages;
//here is some operation
//now clearing the stack
while(!pages.empty())
    pages.pop();

Now my question: is there a better efficient way to clear the stack?

peterh
  • 11,875
  • 18
  • 85
  • 108
Misbah Ahmad
  • 759
  • 2
  • 10
  • 20
  • 8
    Have you tried assigning an empty stack to your stack? – krzaq Oct 23 '16 at 10:06
  • No, thanks for your suggestion (y) – Misbah Ahmad Oct 23 '16 at 10:06
  • You asked about efficiency. Creating a new stack may not be more efficient, as it will lead to more heap allocations. The underlying container will by default be a `deque`. If you use a `deque` or `vector` you will throw away the allocated memory you have already claimed for the container, which could otherwise be reused. – Paul Rooney Oct 23 '16 at 10:14
  • @PaulRooney the same argument could be used the other way around. Destroying types with trivial destructors in a loop could be more wasteful than a (possibly elided) allocation. Moreover, keeping the allocated memory may be the opposite of what he wants. It's all up to making an informed decision. – krzaq Oct 23 '16 at 10:27
  • Of course. I'm not saying one is better than the other, just that it's something to consider based on the Op's needs. – Paul Rooney Oct 23 '16 at 10:30
  • Not sure what efficiency problem you are really experiencing, but you can always trade space for speed. Do not clear the container but keep an extra flag to indicate that it should be treated as empty. Wrap the container and the flag in a class of your own. – Christian Hackl Oct 23 '16 at 11:04

5 Answers5

52

In general you can't clear copying containers in O(1) because you need to destroy the copies. It's conceivable that a templated copying container could have a partial specialization that cleared in O(1) time that was triggered by a trait indicating the type of contained objects had a trivial destructor.

If you want to avoid loop.

pages=stack<std::string>();

or

stack<std::string>().swap(pages);
v78
  • 2,803
  • 21
  • 44
  • Is there a way to do this (in C++14) without having to explicitly state the type? – John H. Jul 21 '18 at 13:04
  • 8
    All containers have `clear` -- except `array`. Is that the reason `stack` does not have `clear`? If so, wouldn't it be more useful to avoid or ignore that exception? Not having `clear` for `stack` seems weird, when you're using it. – John H. Jul 21 '18 at 20:31
  • 7
    @JohnH. Yes: `pages = {};` – jhasse Sep 20 '18 at 15:44
  • When I use it, it empties all other stacks, I am not sure what's wrong. – Joseph Dec 03 '19 at 18:57
  • It can be the case that all your stack are just references of one actual object. @Joseph. – v78 Dec 05 '19 at 11:31
19

I don't think there is a more efficient way. A stack is a well defined data type, specifically designed to operate in a LIFO context, and not meant to be emptied at once. For this you could use vector or deque (or list), which are basically the underlying containers; a stack is in fact a container adaptor. Please see this C++ Reference for more information.

If you don't have a choice, and you have to use stack, then there is nothing wrong with the way you do it. Either way, the elements have to be destroyed if they were constructed, whether you assign a new empty stack or pop all elements out or whatever.

I suggest to use a vector instead; it has the operations you need indeed:

  • size (or resize)
  • empty
  • push_back
  • pop_back
  • back
  • clear

It is just more convenient, so you can use the clear method. Not sure if using vector is really more performant; the stack operations are basically the same.

Ely
  • 10,860
  • 4
  • 43
  • 64
0

What about assigning a new empty stack to it?

pages = stack<string>();

It won't remove elements one by one and it uses move assignment so it has the potential to be quite fast.

Piotr Siupa
  • 3,929
  • 2
  • 29
  • 65
0

make it into a smart pointer:

stack.reset();
stack = make_shared<stack<string>>();
Tracker647
  • 29
  • 6
-6

What about subclassing std::stack and implementing a simple clear() method like this, accessing underlying container c ?

public:
    void clear() { c.clear(); }
serget
  • 504
  • 1
  • 4
  • 6
  • 1
    This is non-standard and a bad idea for [a few reasons](https://stackoverflow.com/questions/6806173/subclass-inherit-standard-containers#7110262). The underlying container name will vary depending on the implementation and it is not guaranteed that the implementation doesn't rely on some variables other than the underlying container, and clearing it could corrupt the state of the stack. – asu Jul 18 '18 at 16:31
  • 2
    Despite the criticism of this answer, this appears to be the most efficient solution, if not the most portable. – The Matt Dec 30 '20 at 20:17
  • What would be the type of the underlying container? – Mikolasan Nov 09 '22 at 17:27