View mode: basic / threaded / horizontal-split · Log in · Help
June 30, 2012
Creating a Sub-view of a non - RA (hasSlicing) range.
I've been enjoying my time with D's ranges, but something is 
nagging at me: If the range is not random access, then how does 
one create a sub-view of that range?

Say I have a forward range (for example, an SList[]). I would 
like to create a new range containing only the first 5 elements 
of that old range. How can I do that?

I see no logical reason that prevents me from doing it, since C++ 
iterators can do it quite fine. (the C++ algorithms that work 
only on RA ranges is mostly for efficiency reasons). Not being 
able to do this would severely limit the amount of containers 
that can seamlessly merge with algorithms.

For example, I can't call splitter on an SList. Not sure if this 
is just "not currently supported", or just not possible...

Any thoughts?
June 30, 2012
Re: Creating a Sub-view of a non - RA (hasSlicing) range.
> Say I have a forward range (for example, an SList[]). I would 
> like to create a new range containing only the first 5 elements 
> of that old range. How can I do that?
>

std.algorithm.take.

But I would generally avoid SList.
June 30, 2012
Re: Creating a Sub-view of a non - RA (hasSlicing) range.
On Saturday, 30 June 2012 at 11:35:07 UTC, Tobias Pankrath wrote:
> std.algorithm.take.
>
> But I would generally avoid SList.

Thanks, but isn't that kind of a crutch solution?

I mean:

1) It creates a new type, so any attempt to use it to modify an 
existing range becomes impossible:
void main()
{
  SList!int slist;
  foreach(i; iota(5,0,-1))
    slist.insertFront(i);

  sr1 = take(sr1, 2); //Nope, not gonna happen
  writeln(sr1);
}

2) The new range is defined as a fixed length from the beginning 
of the range, as opposed to start and finish points. If I were to 
insert new items into my Slist, the new range would just bump the 
top items out of its range.

3) This doesn't work for BidirectionalRanges: The resulting range 
is forward only. For the same reason, it is not possible to have 
a TakeLast for bidirectional ranges.

----
Doesn't D offer any approach to "grow" a range?
June 30, 2012
Re: Creating a Sub-view of a non - RA (hasSlicing) range.
Tobias Pankrath:

> But I would generally avoid SList.

It's not good.

And in general linked lists are quite overrated. On modern CPUs 
it's not easy to find situations where a linked list is better 
than a dynamic array or a chunked array (that is a dynamic array 
of pointers to arrays. It's often used to implement deques, etc).


Regarding arrays, maybe a StableVector will be good to have in 
Phobos:
http://www.boost.org/doc/libs/1_50_0_beta1/doc/html/container/non_standard_containers.html#container.non_standard_containers.stable_vector

Bye,
bearophile
June 30, 2012
Re: Creating a Sub-view of a non - RA (hasSlicing) range.
On Saturday, 30 June 2012 at 12:27:38 UTC, bearophile wrote:
> Tobias Pankrath:
>
>> But I would generally avoid SList.
>
> It's not good.
>
> And in general linked lists are quite overrated.
> ...
> Bye,
> bearophile

I appreciate the input, which I (mostly) agree with (I still love 
list's splice ability, which can be very powerful), but this 
isn't really what the question is about.

It's about getting generic algorithms to work with any generic 
range. Right now, they appear (to me) to heavily favor RA, even 
when they should theoretically support simple bidirectionality...

Those that do support directionality do it using "cheat" using 
take. For example:

void main()
{
  SList!int slist;
  foreach(i; iota(5,0,-1))
    slist.insertFront(i);

  auto rnge = slist[];
  auto fs = findSplit!("a == b")(rnge, [3]);

  writeln(fs[0]); // [1, 2]
  slist.insertAfter(take(rnge, 1), 25); //insert 25 between [1, 2]
  writeln(fs[0]); // [1, 25] !?  Should arguably be [1, 25, 2]
}

This, arguably, is not normal behavior. SList modeling forward 
ranges, ranges to the list should not be bounded by a fixed size.

And again, had my input been a BDList (if it existed), findSplit 
would have returned 3 forwardRanges, which is also arguably wrong.
June 30, 2012
Re: Creating a Sub-view of a non - RA (hasSlicing) range.
On 30-Jun-12 15:35, Tobias Pankrath wrote:
>> Say I have a forward range (for example, an SList[]). I would like to
>> create a new range containing only the first 5 elements of that old
>> range. How can I do that?
>>
>
> std.algorithm.take.
>
> But I would generally avoid SList.

Indeed. I'd be hard pressed to devise realistic use case where it 
performs better.

That makes me think that a proper type people should be using is the 
unrolled list, that is a list of fixed-sized array chunks.

Or even chunked array like bearophile suggests.
-- 
Dmitry Olshansky
June 30, 2012
Re: Creating a Sub-view of a non - RA (hasSlicing) range.
On 6/30/12 7:31 AM, monarch_dodra wrote:
> I've been enjoying my time with D's ranges, but something is nagging at
> me: If the range is not random access, then how does one create a
> sub-view of that range?

Use take or takeExactly.

> Say I have a forward range (for example, an SList[]). I would like to
> create a new range containing only the first 5 elements of that old
> range. How can I do that?

take(r, n) or takeExactly(r, n).

> I see no logical reason that prevents me from doing it, since C++
> iterators can do it quite fine.

Actually, not at all. Iterators are a lot worse off than ranges here.

C++'s std::forward_list (and generally any iterator-providing 
singly-linked list) only offers an iterator to the first element. (The 
"end" iterator is a wrapped null pointer. This is by definition of the 
structure - singly-linked lists don't track their last element.)

So if you were to to take 5 elements off a std::forward_list, you can't 
use lst.begin() and lst.begin() + 5 because there's no addition; you'd 
need to define a new iterator type that combines a forward iterator with 
an integer, and iterate using that. It's all painstaking revealing how 
much a range is better for such. This is because the range keeps 
together the iteration limits, whereas iterators insist on the fact that 
the iteration limits belong separately.

> (the C++ algorithms that work only on RA
> ranges is mostly for efficiency reasons). Not being able to do this
> would severely limit the amount of containers that can seamlessly merge
> with algorithms.
>
> For example, I can't call splitter on an SList. Not sure if this is just
> "not currently supported", or just not possible...
>
> Any thoughts?

It must be very well understood what the structural limits of 
singly-linked lists impose on their iteration. There's no way to take 5 
elements off a SList and pretend that's pretty much the same as taking 
the whole list.

We could build a design for using splitter with SLists only if the 
element type of splitter's result is different from SList's native range.


Andrei
June 30, 2012
Re: Creating a Sub-view of a non - RA (hasSlicing) range.
On 6/30/12 8:24 AM, monarch_dodra wrote:
> On Saturday, 30 June 2012 at 11:35:07 UTC, Tobias Pankrath wrote:
>> std.algorithm.take.
>>
>> But I would generally avoid SList.
>
> Thanks, but isn't that kind of a crutch solution?
>
> I mean:
>
> 1) It creates a new type, so any attempt to use it to modify an existing
> range becomes impossible:
> void main()
> {
> SList!int slist;
> foreach(i; iota(5,0,-1))
> slist.insertFront(i);
>
> sr1 = take(sr1, 2); //Nope, not gonna happen
> writeln(sr1);
> }

One can't expect that to happen more than suspending a law of physics. 
The state needed for iterating an entire slist is a pointer. The state 
needed for iterating at most n elements of an slist is a pointer plus 
and integer. They're just different notions.

> 2) The new range is defined as a fixed length from the beginning of the
> range, as opposed to start and finish points. If I were to insert new
> items into my Slist, the new range would just bump the top items out of
> its range.

SList's range is not defined by start and finish points. It's defined as 
the start point, and the finish point is implicit by use of a sentinel 
(the null pointer).

> 3) This doesn't work for BidirectionalRanges: The resulting range is
> forward only. For the same reason, it is not possible to have a TakeLast
> for bidirectional ranges.

Not sure I understand this, but when we get into the realm of bidir 
ranges, things get a fair amount better. How would TakeLast work?


Andrei
June 30, 2012
Re: Creating a Sub-view of a non - RA (hasSlicing) range.
On 6/30/12 9:15 AM, Dmitry Olshansky wrote:
> On 30-Jun-12 15:35, Tobias Pankrath wrote:
>>> Say I have a forward range (for example, an SList[]). I would like to
>>> create a new range containing only the first 5 elements of that old
>>> range. How can I do that?
>>>
>>
>> std.algorithm.take.
>>
>> But I would generally avoid SList.
>
> Indeed. I'd be hard pressed to devise realistic use case where it
> performs better.

Singly-linked lists are frequently used with lock-free algorithms. 
Generally it's simplistic to compare slists with arrays as to "which 
performs better" because they have different primitives.

Andrei
June 30, 2012
Re: Creating a Sub-view of a non - RA (hasSlicing) range.
On Saturday, 30 June 2012 at 14:22:06 UTC, Andrei Alexandrescu 
wrote:
>> 2) The new range is defined as a fixed length from the 
>> beginning of the
>> range, as opposed to start and finish points. If I were to 
>> insert new
>> items into my Slist, the new range would just bump the top 
>> items out of
>> its range.
>
> SList's range is not defined by start and finish points. It's 
> defined as the start point, and the finish point is implicit by 
> use of a sentinel (the null pointer).
Well, what about in the case of a BidirRange from a BDList? 
Surelly, it would be defined by a start and finish point?

Take, on the other hand, creates a range, which is defined by a 
start point, and a fixed length. Inserting elements into the 
middle of the original list would bump elements out of the "take 
range", which remains fixed sized.

On the other hand, had I manually shrunk my BDlistRange until it 
was 5 elements long, and then inserted elements into the midle of 
the list, it would cause my BDListRange to grow, and nothing to 
drop out of it.

On Saturday, 30 June 2012 at 14:22:06 UTC, Andrei Alexandrescu 
wrote:
> On 6/30/12 8:24 AM, monarch_dodra wrote:
>> 3) This doesn't work for BidirectionalRanges: The resulting 
>> range is
>> forward only. For the same reason, it is not possible to have 
>> a TakeLast
>> for bidirectional ranges.
>
> Not sure I understand this, but when we get into the realm of 
> bidir ranges, things get a fair amount better. How would 
> TakeLast work?
>
>
> Andrei

Well, if we forget Slist, and just focus on a standard 
BidirectionalRange, say comming from a DList. Things don't really 
get any better, because take still returns just a ForwardRange.

There is no way of doing, say:

BidirectionalRange aBD = ...;

//Create subrange...
//aBD = take(aBD, 5); //Error, wrong type
auto subrange = take(aBD, 5);

if(subrange.back == 5) //Error, subrange does not have a back 
method.
                       //...But that's strange, because aBD IS a 
bidiretinal range

Since the Take Range it is defined by a begining point and a 
length, there is no way it could give Bidir access.

----
I came to D after reading your talk on ranges, and I really liked 
(and am still enjoying) the concept. However, with C++, when you 
iterate over [First, Last), you are also creating a two new 
ranges: [First, Current) & [Current, Last). D doesn't provide 
that, it only provides a way to shrink the current range and 
create [Current, Last).

Using range, you don't get [First, Current). At best, you only get
a)A forward range only
b)A fixed size range
c)A range of another type
« First   ‹ Prev
1 2
Top | Discussion index | About this forum | D home