HN Explorer

6 comments

[ 0.63 ms ] story [ 15.9 ms ] thread
jamesfinlayson
That's quite a handy optimisation from gcc - I only dabble in C++ so maybe it would be obvious to someone that uses it day to day, but I had a good look at that code and couldn't see any obvious way to make is_empty O(1) based on its implementation.
Miiko
Two questions: who is Travis Downs, and why he decided to re-implement 'size' method with different name 'count_nodes' and O(N) complexity?
htk
Why is is_empty comparing to bigger than zero instead of equals?
jb1991
That’s a common optimization, not just with this particular requirement. Choose the thing that is most ambiguous that gives you the answer you need, and it’s more likely to result in a simpler hardware instruction.
rafaelvasco
Probably because , for this case, comparing for > or < is faster than equality comparison. Which from my experience is true.
htk
The author edited the article and corrected is_empty to is_not_empty.