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

[Joe Buck]

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.