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)?


Paolo Carlini <pcarlini@suse.de> writes:

> Howard Hinnant wrote:
> 
> [snip the real beef, will return to it later, thanks!!!]
> 
> > It is somewhat analogous to:
> >
> > basic_string(const charT* s);
> > basic_string(const charT* s, size_type n);
> >
> > Now certainly you might want to pass a non-null-terminated char* to a 
> > string, and the second ctor is handy for that.  But you also might 
> > already know the length of a null-terminated char* from previous 
> > computations, and use the second ctor for that case too.  Why have 
> > basic_string do an O(n) computation that you've already gone to the 
> > trouble to compute?
> 
> Exactly! Earlier today I came to the *very same* conclusion, it's the
> closer analogous!

But the analogy here is that splice() should insert only the first
'n' elements...


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