api-guidelines icon indicating copy to clipboard operation
api-guidelines copied to clipboard

Methods named `len`, `is_empty` and `capacity` should take constant time

Open nik-rev opened this issue 4 months ago • 1 comments

Today, I wanted to switch to using Vec::with_capacity instead of Vec::new while iterating over a toml_edit::Table:

let v = Vec::with_capacity(table.len());

But to my surprise, the Table::len method actually takes O(n) time, as it is implemented with Iterator::count:

/// Returns the number of non-empty items in the table.
pub fn len(&self) -> usize {
    self.iter().count()
}

/// Returns true if the table is empty.
pub fn is_empty(&self) -> bool {
    self.len() == 0
}

This is surprising and can make people's code slower, without them realizing why. Library authors should choose different names for a len method if it doesn't take constant time, such as count.

I found a discussion about this from 2017, and decided to open a PR to add this guideline

nik-rev avatar Jul 25 '25 12:07 nik-rev

Another data point from kdl: https://github.com/kdl-org/kdl-rs/issues/133

nik-rev avatar Aug 15 '25 07:08 nik-rev