range and algorithm-related stuff

[Andrei Alexandrescu]

Sergey Gromov wrote:
> Sun, 25 Jan 2009 13:53:43 -0800, Andrei Alexandrescu wrote:
> 
>> Christopher Wright wrote:
>>> Andrei Alexandrescu wrote:
>>>> Sergey Gromov wrote:
>>>>> Sat, 24 Jan 2009 17:09:07 -0800, Andrei Alexandrescu wrote:
>>>>>
>>>>>> I'm working on the new range stuff and the range-based algorithm. In 
>>>>>> all likelihood, you all might be pleased with the results.
>>>>>>
>>>>>> I wanted to gauge opinions on a couple of issues. One is, should the 
>>>>>> empty() member function for ranges be const? On the face of it it 
>>>>>> should, but I don't want that to be a hindrance. I presume non-const 
>>>>>> empty might be necessary sometimes, e.g. figuring out if a stream is 
>>>>>> empty effectively means fetching an element off it.
>>>>> I have a hard time imagining a use for a const range.
>>>> Read-only arrays for example.
>>> A range is essentially an iterator. It has to change its internal state 
>>> to move to the next element. So a const range will not allow you to 
>>> iterate over the members of a const array. It will allow you to iterate 
>>> over a single element, either once or an infinite number of times.
>> A range offering random access can give me any element without the range 
>> actually changing.
> 
> This restricts you to algorithms working exclusively with random-access
> ranges.  Any more generic algos won't work with const ranges.  How many
> of those do you have?

Stable partition, everything related to binary search, heap functions, 
and radial iteration come to mind.

Anyhow, for now let's go with requiring ref returns and we'll see how 
that fares.

I'm almost done with std.algorithm. (I am cheating because Walter 
emailed me a fixed dmd that allows ref returns from template funs.) Very 
exciting. I will post the documentation as soon as I'm done.


Andrei