opIndex, opSlice, length for joiner?

[Jonathan M Davis via Digitalmars-d]

On Wednesday, 20 January 2016 at 17:36:29 UTC, Maverick Chardet 
wrote:
> The most important issue that comes to my mind is that the 
> operations would not take constant time... A trivial 
> implementation would be in O(k) where k is the number of joined 
> ranges, and with some precomputation in O(k) time and space we 
> can make length O(1) and opIndex and opSlice O(log k)... Would 
> that be a problem?

The various range primitives all need to be O(1). We need to be 
able to rely on the big-o complexity of the primitives used by 
ranges, or the performance of various algorithms will tank when 
used with ranges that don't stick to the expected big-o 
complexities. So, if a range type cannot provide a primitive as 
O(1), it should not provide that primitive. If that weren't the 
case, then we'd have stuff like length, opIndex, and opSlice for 
narrow strings, but we don't.

std.container lists the algorithmic complexity for its various 
operations for the same reason, and as I understand it, its 
replacement that Andrei is working on is going to do the same.

- Jonathan M Davis