3 ms·
> 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.
by klyrs 5y ago
> 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.
- kllrnohj 5y agoWhich 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.