1

I am using std::stack for an project and I need to travel on it for checking same values. I checked member functions but, I could not find an appropriate one for this task.

The first idea that came up is using a copy stack but, the program might waste lots of extra space in this case, and not using an user-defined stack class is important at this level of the project (Yeah, I made a design mistake... ).

So, any idea?

Thank you!

ciyo
  • 725
  • 4
  • 16
  • 36

1 Answers1

5

Avoid std::stack, it's just a useless wrapper that dumbs down the interface of the underlying container. Use a std::vector with push_back/pop_back for insert insertion/removal (insertion/removal at the end is amortized O(1)) or std::deque, whence you can push/pop on either side without significant changes in performances (still amortized O(1)). In both cases you can walk all the elements using their random-access iterators.

(the same holds for std::queue: it's useless, use directly std::deque (not vector) with push_back/pop_front)

Matteo Italia
  • 123,740
  • 17
  • 206
  • 299
  • I did not know that vector has these kinds of methods. Thank you, again. – ciyo Nov 18 '13 at 14:42
  • A `std::stack` is not useless. Yes, its functionality is much reduced compared to its underlying container, but that's also its strength: it's *only* a stack and if that's all one needs, then this makes the program clearer and easier to maintain than using, say, a `std::deque`. – Walter Sep 28 '15 at 11:37
  • @Walter: please provide one case where it actually made the program "cleaner and easier to maintain"; in my experience it only made me waste a lot of time renaming `pop` to `pop_back`, `push` to `push_back` and `top` to `back` whenever I needed to access the underlying container for any reason (for oh-so-rare scenarios like iterating over the elements after the first part of an algorithm accumulated them on the stack; printing the stack content for logging/debugging purposes; passing the full stack to any other function to process the elements; peeking at more than one element on the top). – Matteo Italia Sep 28 '15 at 22:30
  • @MatteoItalia If you want more than a stack (i.e. iterators etc), don't use a stack. It's as simple as that. – Walter Sep 29 '15 at 08:46
  • Is a car useless because you cannot haul boxes bigger than fit in the trunk? I could buy a truck but then I'm driving around in a truck all day just in case I need it's truck functionality one day in the far future. Yeah, a car is useless if you need to haul a ton of goods. So always buy a truck? That seems like bad advice. – David Rector Aug 03 '18 at 19:38
  • 1
    @DavidRector: there's no car here, there is just a nice regular truck with the loading bay welded to let you load only tiny packets. – Matteo Italia Aug 03 '18 at 22:13
  • @Matteo Italia: I don't know, if the class is lighter weight, I would think of it as a car, not a truck. I get the point but I don't think a limited class is useless unless you have a use that goes beyond what it supplies. Otherwise, I could say that a deque is useless because it doesn't have the features of a KD-tree. Well, that's only true if I need a KD-tree and not a deque. "Useless" is just a bit extreme. "Limited" would be a better description of the stack class (which I never use because it is too limited). – David Rector Aug 06 '18 at 20:36
  • 1
    @DavidRector: the class isn't more lightweight or anything, as under it there's `std::vector` or `std::deque` or whatever you pass to it as template parameter, it just restricts the interface of the underlying container. The analogy with `deque` being useless because it isn't a KD-tree doesn't hold - a `deque` is a different data structure than a KD-tree, an `std::stack` is *literally* an `std::vector` locked down to a dumb interface. – Matteo Italia Aug 06 '18 at 22:22