Boost logo

Boost :

Subject: Re: [boost] [string] proposal
From: Ivan Le Lann (ivan.lelann_at_[hidden])
Date: 2011-01-26 05:24:12


Le mercredi 26 janvier 2011 à 09:29 +0100, Matus Chochlik a écrit :
> On Tue, Jan 25, 2011 at 5:12 AM, Dean Michael Berris
> <mikhailberis_at_[hidden]> wrote:
> > On Mon, Jan 24, 2011 at 7:36 PM, Dave Abrahams <dave_at_[hidden]> wrote:
> >> On Fri, Jan 21, 2011 at 5:00 PM, Ivan Le Lann <ivan.lelann_at_[hidden]> wrote:
> >>>
> >>> ----- "Nevin Liber" <nevin_at_[hidden]> wrote :
> >>>
> >>> Isn't rope worth a try here ?
> >>
> >> Absolutely!
> >>
> >
> > +1 -- now if there was just a rope class that is part of the standard
> > (and not an SGI extension) then it should definitely be a good
> > candidate for how a string can efficiently store data without
> > requiring linear memory complexity to the length of the text. :)
> >
> >> <shameless plug>
> >> The author of rope is giving the keynote at BoostCon this year.
> >> </shamelses>
> >>
> >
> > Coolness. :)
> >
>
> Some years ago, when I first discovered the SGI's implementation
> of STL and its rope class my first thought was 'Cool'.
> Then I wrote a couple of (in the hindsight) rather synthetic
> simple programs exploiting those cool features of rope
> and it outperformed the std::string almost in every one of them.
>
> Then I tried to use it in a more real world scenarios, like for
> example passing them to WINAPI. Then I returned to
> std::string :)
>

[ disclaimer: extremely premature implementation detail :) ]

I don't know about SGI's rope internals.
My understanding of rope in the real world use case you mention is that
it does lazy "c_str" evaluation. Now, if you only give verbatim back to
the OS a string it gave you, there is no reason for c_str to be slow.
If you did string manipulation, then you'll pay for this at c_str call,
but you had to pay for this eventually. I see no penalty here.

To illustrate this, I understand an immutable rope as roughly :

boost::make_recursive_variant <
  boost::shared_ptr <const std::basic_string <code_unit_type>>,
  boost::shared_ptr <const std::list <boost::recursive_variant_>>
>::type

Here c_str should be trivial in basic_string case.

Ivan.


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk