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

[Paolo Carlini <pcarlini at suse dot de>]

Geoffrey Keating wrote:

>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...
>  
>
Humm, you mean the analogy is not perfect, because in the case of the
basic_string constructors, as long as n < strlen(s) everything remains
consistent, only, you construct a shorter string (than the first, slower
constructor, would construct). In case of list::splice, if n <
distance(first, last) awful things happen, the list becomes internally
inconsistent... Well, the basic_string constructor too has to be used in
a careful way, n > strlen(s) is no good...

(the above always considering null-terminated "C" strings)

Paolo.