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

["Peter Dimov" <pdimov at mmltd dot net>]

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.