Boost logo

Boost :

From: David Abrahams (dave_at_[hidden])
Date: 2005-11-30 07:28:27

I suggest we all review:

It reveals efficiency bugs in


Sort story: std::list::size is not O(1) (surprise!)

attached mail follows:

To: C++ libraries mailing list
Message c++std-lib-16084

On Oct 26, 2005, at 3:03 PM, Howard Hinnant wrote:

> I recommend just commenting out list::size in your std header, run
> the tests, and see what fails to compile. And then check if you
> approve of the use of std::list::size in each of those cases. If
> you do this experiment, I'd love to know the results.
> And having to experiment this way is exactly my point.
> In fact, run the experiment again and comment out the "splice some"
> signature this time. My bet is that list::size will be used much
> more often than list::splice-some.

I decided to do this survey myself:

If boost authors can be bitten by list::size (after peer reviews from
other boost members), just imagine what it is doing out in the


Dave Abrahams
Boost Consulting

Boost list run by bdawes at, gregod at, cpdaniel at, john at