Re: [boost] [gsoc] Request Feedback for Boost.Ustr Unicode String Adapter

Subject: Re: [boost] [gsoc] Request Feedback for Boost.Ustr Unicode String Adapter
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2011-08-14 10:12:44

Soares Chen Ruo Fei wrote:

>> with non-Unicode CJK encodings
>> like Shift-JIS or GBK there is no
>> way to go backward

> Ahh I see so that's quite nasty, but actually it still can be done
> with the sacrifice on efficiency. Basically since the iterator already
> has the begin and end boundary iterators it can simply reiterate all
> over from the beginning of the string. Although doing so is roughly
> O(N^2) it shouldn't make significant impact as developers rarely use
> this multi-byte encoding and even seldom use the reverse decoding
> function.

As a general point, I believe it's a bad idea to hide a surprise like 
O(N^2) instead of O(N) complexity in a "rare" case.  Doing so means 
that users will implement something that seems to work, and then get 
bitten later when it doesn't work in the field.  (For example, the 
first time that a customer in Japan tries to process a 1 MB file and it 
takes a million times longer than expected.)

It would be better to not provide the inefficient case at all.  Compare 
with how std::list doesn't provide random access, even though it could 
do so in O(N).  Looking at your character set iterator, it seems to me 
that you could have a forward-only iterator and a bidirectional 
iterator for UTF, but only the former for these other encodings.  Not 
storing the begin iterator when only forward iteration is needed also 
saves space.

Regards,  Phil.