len, is_empty, capacity should all take constant-time

[clarfonthey]

This is the case in all libstd collections and I think that it's reasonable to put this in the guidelines. Although it's stated that is_empty may be faster than len == 0, it should be clarified that len should always take constant time to execute regardless. Users should expect that even for collections like LinkedList and HashMap, checking the length is constant-time.

[Nemo157]

What is the guideline for when this isn't the case? Add an extra couple of bytes to store the length, or use a name like calculate_len to show that it's non-O(1)?

For reference I have a crate that currently implements an O(log(n)) len function, so wondering if I should change this if this makes it into the guidelines. In my case I'm not sure whether the cost of updating the length in multiple places on every operation would be worth it to reduce this rarely used operation down to O(1).

[jonhoo]

VecMap relatively recently adopted a constant-time len()/is_empty() in contain-rs/vec-map#33, and users there seemed to generally think the trade-off was worth it. This may of course be different for other use-cases where the overhead of a few bytes is significant.

[BurntSushi]

I think it's more important that len/is_empty remain constant time, by convention. If that isn't appropriate for your use case, then I'd recommend just choosing a different name. For example, there is an iterator adapter called count. But in general, I don't think there is a standard name for such things.

[ahmedcharles]

Note, for linked lists (which are niche data structures), the tradeoff between constant time slice and constant time len is complicated. To make it less complicated, specifying len as being amortized constant time makes sense.