This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: Should the complexity of std::list::size() be O(n) or O(1)?
On 11/29/05, Peter Dimov <pdimov@mmltd.net> wrote:
> Jonathan Wakely wrote:
> std::list is often the right choice when either:
>
> - the element size is sufficiently large so that deque degenerates into a
> (much) less efficient or capable list;
All those are good points, but I've quoted that one as it's also a
good argument for not having an O(N) size() ... if you use list
because it copes with very large N, you definitely don't want O(N)
size!
jon