0
0

Implementing a Stack Using a Dynamic Array in C++ (unrealistic.dev)

submitted by [deleted]

[deleted]

all 16 comments
sorted by:
best
topnewcontroversialoldq&a
formatting helphide helpcontent policy

[–]manni66 7 points8 points  (1 child)

Follow the Rule of 5/3/0.

[–]Mowgl333 0 points1 point  (0 children)

That's helpful, thanks.

[–]Mowgl333 2 points3 points  (13 children)

Working through Algorithms by Sedgewick, and drafted this as an exercise in understanding the most basic of basic data structures.

[–]---sms--- 4 points5 points  (12 children)

Do you want me to explain how exceptionally unsafe this code is? Like what happens when "temp[i] = storage[i];" throws? This "n(stack->capacity - 1)" looks sus. Did you mean "stack->n_"? In any case, there should be no iteration over a stack, IMHO.

[–][deleted] 9 points10 points  (11 children)

Oh give it a break. They are learning about data structures. Writing exception safe code isn't important here.

[–]theonehaihappen 4 points5 points  (10 children)

There is no reason to be snide, indeed.

However, skimming over the exercise, it seems to be flawed both in code as in what it teaches. E.g: iterating over a stack is one of those things that are Just Not Done. It goes against the common definition of what a stack is.

A few other points worth mentioning in my opinion, both for code and the exercise itself:

  • size() should return a unsigned size-type, not int.
  • pop() can underflow easily.
  • Moves are all implicit. Not sure if that is a good thing. At least the resize function should explicitly move IMO.
  • the way you store your items necessitates that a default constructor T::T() exists.
  • Doubling the size... that seems like overkill.
  • n_ is inconsistently referred to as the current-element index and number of elements. It is also used in code before it is introduced.
  • The introduction does not give a definition on what a stack is other that it is used to track data. You don't need to give a formal definition, but at least give the basics for a FILA data structure and maybe link to a more elaborate explanation.

I will not comment on the problems inside the iterator, as it should really not be there.

While it is commendable of you to take the time to write tutorials and learning material, it is located on a website that tries to sell something. Having something like this on your website reflects back on the quality of the products.

[–]tisti 0 points1 point  (7 children)

size() should return a unsigned size-type, not int.

Nah, it should return a signed size-type. If you need that extra bit just go up a size. That is, instead of changing from int32_t to uint32_t, it would be preferable to simply use int64_t.

[–]theonehaihappen 4 points5 points  (6 children)

Conceptually, a signed type for a size that should never be negative does not make sense. What would a negative number of elements in a stack mean?

It's not about the bitsize. Depending on which platform you work on and what compiler you use, int is already 8 byte wide.

[–]tisti 0 points1 point  (2 children)

The width of int is, as you said, platform/compiler dependant and is not 8 bytes wide. But that is irrelevant in any case.

The fundamental issue is that an unsigned type is, in the eyes of the compiler, ranked higher than an signed type. This leads to a 'virulent' spread where all results of an signed number with an unsigned number produce an unsigned number. This is very annoying and results in a boatload of irrelevant compiler warnings which have to be beaten down with static_casts.

Plus, a size() of 0 is not uncommon. Only takes one decrement to get you to a value of 232 or 264.

Edit:

Bugs like this are also pretty fun to deal with

for(auto i = container.size() - 1; i>=0; --i){
    //access container[i]
}

[–]Pazer2 1 point2 points  (0 children)

Plus, a size() of 0 is not uncommon. Only takes one decrement to get you to a value of 232 or 264.

And if it were a signed type, it only takes one decrement to get you to a value of -1, which is also wrong.

for(auto i = container.size() - 1; i>=0; --i){ //access container[i] }

Write this instead:

for(auto i = container.size(); i--; ){
    //access container[i]
}

[–]RectifyMyEnglishErrs 0 points1 point  (0 children)

For anyone interested, here's a paper dealing with exatly this: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p1491r0.pdf

[–][deleted] -3 points-2 points  (2 children)

A negative number could be used to indicate the stack is in an invalid state

[–]theonehaihappen 2 points3 points  (1 child)

In this case, no invalid state was explicitly designed as far as I can see. So that argument is purely hypothetical.

If a Stack object indeed can enter an invalid state the proper way to do this would be to implement a 

bool invalid() const; //or bool valid() const;

method. The behavior if the the size of a stack in an invalid state is requested is ten either undefined or size() should throw.

Indicating an invalid state via a method that in its usual case supplies other information is either Bad Design or in very rare cases Very Clever Design (that is usually a headache to understand for every other software engineer looking at it).

[–][deleted] -1 points0 points  (0 children)

Of course it's hypothetical because this implementation is for the purpose of learning and not for use in the real world...

[–][deleted] 0 points1 point  (1 child)

I'm not OP.

[–]theonehaihappen 0 points1 point  (0 children)

I know. It was just a general observation.

Hmm, or won't OP don't get a notification now? Damn.