Should the complexity of std::list::size() be O(n) or O(1)?

[Peter Dimov]

Joe Buck wrote:
> On Tue, Nov 29, 2005 at 06:42:22PM +0200, Peter Dimov wrote:
>> I think that the general consensus is that while it is theoretically
>> possible to implement a non-contiguous conforming string as an
>> academic exercise, no implementation does that today, or will in the
>> future, because there is simply no point in doing so.
>
> What about the SGI rope class?  The idea is to optimize the storage of
> many strings, taking advantage of common substrings.
>
> SGI was kind enough to give it a different name, though it mostly
> obeyed the specification of std::basic_string.

It's possible to implement a non-contiguous string that mostly obeys the 
specification, of course. Just not a std::string.