Re:In C++, is empty() faster than comparing the size with zero?
by klyrs on Thursday October 28, 2021 @04:09PM
(#29031236)
> I'm not sure I can think of an example of such a data structure?
C style strings are the classical example. Computing the size (strlen) takes linear time. Not saying that this is a good idea or anything, but it's extremely common.
One could imagine a binary tree implemented in a similar manner. It costs a little time and memory to keep track of the current size, but it almosy always pays off.
Re:In C++, is empty() faster than comparing the size with zero?
by kllrnohj on Thursday October 28, 2021 @08:22PM
(#29033801)
Which is long since fixed with std:string & co. The data structure concept of a string has no need for linear length calculation. Rather, C just did strings badly.
C style strings are the classical example. Computing the size (strlen) takes linear time. Not saying that this is a good idea or anything, but it's extremely common.
One could imagine a binary tree implemented in a similar manner. It costs a little time and memory to keep track of the current size, but it almosy always pays off.