This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: performance analysis producer_consumer.cc TEST_T5
On Tue, Feb 17, 2004 at 09:30:44AM -0700, law@redhat.com wrote:
> In message <4030DE6D.50607@redhat.com>, Will Cohen writes:
> >I looked over the code a bit more. The tight loop that the code spends
> >most of its time is the result of the size() operation. The code is
> >counting the number of elements in the list. ...
>
> Funny, a one of the customers you visited a couple weeks ago has
> complained repeatedly about not having an efficient means to get the
> number of objects on a list....
std::list<>::size() is linear in N because the alternative would be
to make splicing linear. The latter is the more commonly called in
a loop. (The splice operation on lists is among the most clever and
appealing features of the STL. I claim credit for naming it.)
If you're very interested in the size of the container, you'll use
a different data structure, or keep a separate count. Note that
maintaining a count is also linear in N, it's just that the cost is
amortized over as many times as you look at it.
Nathan Myers
ncm-nospam@cantrip.org