standard ranges

[Roman D. Boiko]

On Thursday, 28 June 2012 at 05:10:43 UTC, Jonathan M Davis wrote:
> On Thursday, June 28, 2012 08:59:32 Gor Gyolchanyan wrote:
>> Currently strings below dstring are only applicable in 
>> ForwardRange
>> and below, but not RandomAccessRange as they should be.
>
> Except that they shouldn't be, because you can't do random 
> access on a narrow
> string in O(1). If you can't index or slice a range in O(1), it 
> has no
> business having those operations. The same goes for length. 
> That's why narrow
> strings do not have any of those operations as far as ranges 
> are concerned.
> Having those operations in anything worse than O(1) violates 
> the algorithmic
> complexity guarantees that ranges are supposed to provide, 
> which would
> seriously harm the efficiency of algorithms which rely on them. 
> It's the same
> reason why std.container defines the algorithmic complexity of 
> all the
> operations in std.container. If you want a random-access range 
> which is a
> string type, you need dchar[], const(dchar)[], or dstring. That 
> is very much
> on purpose and would not change even if strings were structs.
>
> - Jonathan M Davis

Pedantically speaking, it is possible to index a string with 
about 50-51% memory overhead to get random access in 0(1) time. 
Best-performing algorithms can do random access in about 35-50 
nanoseconds per operation for strings up to tens of megabytes. 
For bigger strings (tested up to 1GB) or when some other 
memory-intensive calculations are performed simultaneously, 
random access takes up to 200 nanoseconds due to memory-access 
resolution process.