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.
