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 Thu, Feb 19, 2004 at 05:25:53PM +0100, Theodore Papadopoulo wrote:
>
> dhruvbird@gmx.net said:
> > Why can't the library have a configure option to determine whether the
> > size() function will be O(N) or not. It would be easy to provide both
> > versions in the library AFAIK.
>
> And why can't we keep the size and incrementally keep it when it is
> cheap to do so. When it is not (eg for splicing), we invalidate the
> size and reestimate it (in 0(N)) the first time the size of the list
> is requested.
>
> This way people would have an O(N) cost in general and (hopefully often) a
> constant cost between "safe" operations...
>
> Now, this incurs a test and an increment for each addition/deletion
> and I do not know the average cost increase because of that....
Something important is being missed here... the essence of the STL is
its definition of the iterator interface. Any particular container
or algorithm in the library is _just_an_example_. If it doesn't do
precisely what you want, it takes only a little time to make one of
your own that does. If you do it right, it will work with everything
else, and that's the point.
The STL containers shouldn't be expected to do anything clever that
might incur costs that not everybody wants to pay. They do the simple
thing, that is right almost all the time.
Nathan Myers
ncm@cantrip.org