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

On Tue, 27 Jan 2009 05:13:31 +0300, Steven Schveighoffer <schveiguy@yahoo.com> wrote:

> "Denis Koroskin" wrote
>> On Mon, 26 Jan 2009 23:37:25 +0300, Denis Koroskin <2korden@gmail.com>
>> wrote:
>>> Checking if a range is empty() prior to accessing its head is useful. If
>>> empty() is const, you can't do that.
>>
>> Err.. if empty() is not const and you have a const range reference.
>
> empty not being const does not imply that you can't access a const member.
> Empty not being const allows all access.  The question is whether a wrapping
> range (or any range for that matter) should implement empty as const, as an
> empty that IS const cannot call a non-const function of a member.
>
> -Steve
>
>

I didn't say non-const empty restricts any member access, did I?

My point is, if empty() returns false (and you can't know it because empty() is not const) you may get either an invalid result, access violation or an exception on member access:

void foo(Range)(const Range r)
{
   // is r empty? can I /safely/ access its head?
   // let's cross our fingers and try it
   // hoping that it is either not empty or throws an exception
   auto head = r.head;
   ...
}

Denis Koroskin wrote:
> My point is, if empty() returns false (and you can't know it because empty() is not const) you may get either an invalid result, access violation or an exception on member access:
> 
> void foo(Range)(const Range r)
> {
>    // is r empty? can I /safely/ access its head?
>    // let's cross our fingers and try it
>    // hoping that it is either not empty or throws an exception
>    auto head = r.head;
>    ...
> }
> 

Then it's good design to implement empty() as const. In some cases, you might not be able to (I believe someone mentioned IO streams as such a case). There, empty() might also throw.

"Denis Koroskin" wrote
> On Tue, 27 Jan 2009 05:13:31 +0300, Steven Schveighoffer <schveiguy@yahoo.com> wrote:
>
>> "Denis Koroskin" wrote
>>> On Mon, 26 Jan 2009 23:37:25 +0300, Denis Koroskin <2korden@gmail.com> wrote:
>>>> Checking if a range is empty() prior to accessing its head is useful.
>>>> If
>>>> empty() is const, you can't do that.
>>>
>>> Err.. if empty() is not const and you have a const range reference.
>>
>> empty not being const does not imply that you can't access a const
>> member.
>> Empty not being const allows all access.  The question is whether a
>> wrapping
>> range (or any range for that matter) should implement empty as const, as
>> an
>> empty that IS const cannot call a non-const function of a member.
>>
>> -Steve
>>
>>
>
> I didn't say non-const empty restricts any member access, did I?

Sorry, I sort of misinterpreted what you said.  You said, "If empty() is const you can't do that." and then sent out a followup email saying "Err.. if empty() is not const and you have a const range reference."  I interpreted that as you replacing the statement "If empty() is const" with "if empty() is not const and you have a const range reference," making the complete statement "if empty() is not const and you have a const range reference, you can't do that."  Which means I thought you meant, if you have an empty that is not const and a const range reference (which I interpreted as the reference to the data inside the range), then empty cannot access the const member.  I see now what you were saying.

However, I don't think this is a common situation.  A range is a struct so it can be a value type.  Having a const reference to a range means you can easily copy everything out of the const range to a non-const range with a const reference to the data.  Note that if I parameterize my range based on the data type, const Range!(T) should be implicitly convertable to Range!(const T), where the range itself is made mutable, but the data reference is const.  So there is little point to making a range itself const.

That being said, I'll also point out that creating a const range reference to access a single element from a range is a very questionable practice, the design might be better served to just access that element directly from the data container itself.  Similarly with random access, any container that provides a random access range to its data will most likely also provide an opIndex to get the data directly.  Ranges being structs, they are only really useful in functions that already know the data type, or template functions which are told the data type.  I don't see any reason why you can't substitute the data structure itself that supplies a length and opIndex member instead of the range.

-Steve