This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [C++] Should the complexity of std::list::size() be O(n) or O(1)?

Gabriel Dos Reis wrote:
Howard Hinnant <hhinnant@apple.com> writes:

[...]

Conclusion:  Yes, you can store the size externally.  But you loose
performance and/or functionality in the above members that will also
have to be recoded.

I think I'm still unconvinced that we have to change list::size, here.

Since it was a mistake to put it there in the first place, why shall
we penalize proper list operations by trying to make an error run
faster?

The current status quo is the worst of both worlds. You can't rely on O(1) size, and you can't rely on O(1) splice (or the size being absent, presumably for footprint reasons.) It needs to be specified one way or the other, and when you have to commit to a choice, O(1) is a clear winner, IMO.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]