design choices are the most interesting parts of every design doc I'm looking for - the "what" and "how" is obvious from the code but the "why" is something that code unfortunately cannot capture...
Thank you for an interesting article. Your point about deque is very right, but my understanding is that as the N grows bigger, vector will sometimes have to reallocate-and-copy memory. I expect that such an overhead may far outweigh any benefit, in some scenarios.
However, when I tried with bigger N values, vector did slow down to a point where it had similar performance to the deque one, I don't see it getting slower than deque ever. Maybe my understanding about memory reallocation in vector is not right.
Also, not so interestingly though, I see that vector is always slower than deque with -O0.
Nit, but a quick typo correction on the code:
1) op_push and op_pop should have different values.
2) pushed counter needs to be decreased when popping.
Yes. Good point and this what I do. Never understood why the design choice of deque.
design choices are the most interesting parts of every design doc I'm looking for - the "what" and "how" is obvious from the code but the "why" is something that code unfortunately cannot capture...
Interesting fact to be recalled !
Was your intent only to populate the stack ?
Because as Yooseong said, by doing op_pop = 1 + checking if stack is empty before top() an pop() I observed reversed results.
In fact deque versatility may be overlooked. I often see in code non-reserved vector which feel like some kind of laziness or unconsciousness.
My favorite link on SO: https://stackoverflow.com/questions/6292332/what-really-is-a-deque-in-stl
> Was your intent only to populate the stack ?
Well, stacks are used for pushing and popping, so push_back and pop_back are my best friends.
> In fact deque versatility may be overlooked.
Nobody argues with this - but this versatility comes at a cost and this cost is not justified for stacks.
Thank you for an interesting article. Your point about deque is very right, but my understanding is that as the N grows bigger, vector will sometimes have to reallocate-and-copy memory. I expect that such an overhead may far outweigh any benefit, in some scenarios.
However, when I tried with bigger N values, vector did slow down to a point where it had similar performance to the deque one, I don't see it getting slower than deque ever. Maybe my understanding about memory reallocation in vector is not right.
Also, not so interestingly though, I see that vector is always slower than deque with -O0.
Nit, but a quick typo correction on the code:
1) op_push and op_pop should have different values.
2) pushed counter needs to be decreased when popping.
> vector will sometimes have to reallocate-and-copy memory. I expect that such an overhead may far outweigh any benefit, in some scenarios.
That goes against amortized analysis of dynamic arrays, which is O(1)*
> I don't see it getting slower than deque ever
This agrees with amortized analysis, so it's expected :)
> I see that vector is always slower than deque with -O0.
This doesn't really matter since nobody should care about -O0 performance.
And thanks for catching the corrections!