std.string.reverse() for mutable array of chars
Jonathan M Davis
jmdavisProg at gmx.com
Fri Dec 9 10:27:01 PST 2011
On Friday, December 09, 2011 12:44:37 bearophile wrote:
> Jonathan M Davis:
> > It sounded like you were,
>
> Right, I was :-) But you have changed my mind when you have explained me
> that nothing in std.algorithm is grapheme-aware. So I have reduced the
> amount of what I am asking for.
So, now you're asking that char and wchar arrays be reversible with reverse
such that their code points are reversed (i.e. the result is the same as if
you reversed an array of dchar). Well, I'm not sure that you can actually do
that with the same efficiency. I'd have to think about it more. Regardless, the
implementation would be _really_ complicated in comparison to how reverse
works right now. char[] and wchar[] don't work with reverse, because their
elements aren't swappable. So, you can't just swap elements as you iterate in
from both ends. You'd have to be moving stuff off into temporaries as you
swapped them, because the code point on one side wouldn't necessarily fit where
the code point on the other side was, and in the worst case (i.e. all of the
code points on one half of the string are multiple code units and all of those
on the other side are single code units), you'd pretty much end up having to
copy half the array while you waited for enough space to open up on one side
to fit the characters from the other side. So, regardless of whether it has the
same computational complexity as the current reverse, its memory requirements
would be far more.
I don't think that the request is completely unreasonable, but also I'm not
sure it's acceptable for reverse to change its performance characteristics as
much as would be required for it to work with arrays of char or wchar -
particularly with regards to how much memory would be required. In general,
the performance characteristics of the algorithms in Phobos don't vary much
with regards to the type that that's used. I'm pretty sure that in terms of
big-o notation, the memory complexity wouldn't match (though I don't recall
exactly how big-o notation works with memory rather than computational
complexity).
- Jonathan M Davis
More information about the Digitalmars-d
mailing list