C++ implementation of Alexandrescu's Range ideas
Paul Moore
range proposal. Overall, I can see how programming with ranges could
be quite a pleasant experience. I've dabbled briefly with the
implementation in the D standard library, but it's quite difficult to
get a feel for ranges per se, as I don't know the D language.
Before I leap in and start trying to code my own (necessarily naive)
implementation of range-based algorithms, is there an existing
implementation anywhere that I could use?
Thanks,
Paul
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Sheff
> I have read with interest the discussions on Andrei Alexandrescu's
> range proposal. Overall, I can see how programming with ranges could
> be quite a pleasant experience. I've dabbled briefly with the
> implementation in the D standard library, but it's quite difficult to
> get a feel for ranges per se, as I don't know the D language.
>
> Before I leap in and start trying to code my own (necessarily naive)
> implementation of range-based algorithms, is there an existing
> implementation anywhere that I could use?
>
> Thanks,
> Paul
Navaneeth
and avoid top-posting. -mod }
Hi,
There is Boost::Range (http://www.boost.org/doc/libs/1_39_0/libs/range/
index.html) available.
On Jul 29, 3:57 am, Paul Moore <p.f.mo...@gmail.com> wrote:
> I have read with interest the discussions on Andrei Alexandrescu's
> range proposal. Overall, I can see how programming with ranges could
> be quite a pleasant experience. I've dabbled briefly with the
> implementation in the D standard library, but it's quite difficult to
> get a feel for ranges per se, as I don't know the D language.
>
> Before I leap in and start trying to code my own (necessarily naive)
> implementation of range-based algorithms, is there an existing
> implementation anywhere that I could use?
>
> Thanks,
> Paul
>
> --
> [ Seehttp://www.gotw.ca/resources/clcm.htmfor info about ]
Andrei Alexandrescu
> Hi,
>
> There is Boost::Range (http://www.boost.org/doc/libs/1_39_0/libs/range/
> index.html) available.
There's a related discussion on Boost's mailing list
(gmane.comp.lib.boost.devel on server news.gmane.org). You'll recognize
it by the title. :o)
Andrei
Paul Moore
> There is Boost::Range (http://www.boost.org/doc/libs/1_39_0/libs/range/
> index.html) available.
I was aware of Boost::Range, but the Range concept implemented there
seems to use different primitive operations - Alexandrescu's forward
range requires empty(), front() and popFront(), for example, where
Boost::Range appears to reqire begin() and end() functions returning
iterators.
Thanks,
Paul.
Paul Moore
> Yes, try ITL (Interval Template Library) :http://itl.sourceforge.net
Again, I'm not sure I see (for example) a Forward Range concept
supporting front(), empty() and popFront(), and algorithms for working
with such objects, in this library. I'll dig further, but the fact
that the library dates from before Andrei's presentation makes me
think that I won't find what I'm looking for in there.
Thanks for the pointer, though.
Paul.
Florian Weimer
> On 29 July, 07:29, Sheff <sheffm...@mail.ru> wrote:
>> Yes, try ITL (Interval Template Library) :http://itl.sourceforge.net
>
> Again, I'm not sure I see (for example) a Forward Range concept
> supporting front(), empty() and popFront(), and algorithms for working
> with such objects, in this library. I'll dig further, but the fact
> that the library dates from before Andrei's presentation makes me
> think that I won't find what I'm looking for in there.
Why? The range concept arises naturally when you try to translate the
STL to a more type-safe language than C++. You have to make sure that
the two iterators refer to the same container, and the best way to do
this without really fancy type systems (or a run-time check) is to put
them into the same object.
I suspect that it wasn't done for the STL because compilers at that
time didn't do scalar replacement of aggregates for multi-member
structs, so it wasn't possible to achieve the goal of matching
performance of hand-written code.
Mathias Gaunard
> I suspect that it wasn't done for the STL because compilers at that
> time didn't do scalar replacement of aggregates for multi-member
> structs, so it wasn't possible to achieve the goal of matching
> performance of hand-written code.
Or maybe it was because iterators are more versatile and you can
express more things with a pair of iterators that can be decombined
and recombined.
Thomas J. Gritzan
> On 29 sep, 00:57, Florian Weimer <f...@deneb.enyo.de> wrote:
>
>> I suspect that it wasn't done for the STL because compilers at that
>> time didn't do scalar replacement of aggregates for multi-member
>> structs, so it wasn't possible to achieve the goal of matching
>> performance of hand-written code.
>
> Or maybe it was because iterators are more versatile and you can
> express more things with a pair of iterators that can be decombined
> and recombined.
>
No. You can express the same things with both concepts because you can
build adapters that map one concept to the other (there are adapters in
Boost.Range).
One reason to choose the pair-of-iterators idiom was that raw pointers
should be valid iterators. It is very compiler friendly and effective to
use pointers as iterators because the compiler don't has to optimize
away any class overhead.
--
Thomas
Mathias Gaunard
> No. You can express the same things with both concepts because you can
> build adapters that map one concept to the other (there are adapters in
> Boost.Range).
Boost.Range is just a glorified pair of iterators, Alexandrescu's
ranges are fundamentally different, they replace iterators altogether.
I have already discussed in the past how some things that you can do
with iterators can't be done with Alexandrescu's ranges.
Basically anything that involves recombining beginnings and ends.
If I have two ranges, [a, b] and [c, b], with c in [a, b], with
iterators I can generate in constant time the range [a, c], which
cannot be done with the interface Alexandrescu has provided, since it
lacks a way of representing positions effectively and to combine or
recombine them into ranges.
In other words, scrapping iterators is not possible without losing
some expressivity. And I believe Alexandrescu acknowledges that too.
--
Andrei Alexandrescu
> On 5 oct, 20:20, "Thomas J. Gritzan" <phygon_antis...@gmx.de> wrote:
>
>> No. You can express the same things with both concepts because you can
>> build adapters that map one concept to the other (there are adapters in
>> Boost.Range).
>
> Boost.Range is just a glorified pair of iterators, Alexandrescu's
> ranges are fundamentally different, they replace iterators altogether.
>
> I have already discussed in the past how some things that you can do
> with iterators can't be done with Alexandrescu's ranges.
>
> Basically anything that involves recombining beginnings and ends.
> If I have two ranges, [a, b] and [c, b], with c in [a, b], with
> iterators I can generate in constant time the range [a, c], which
> cannot be done with the interface Alexandrescu has provided, since it
> lacks a way of representing positions effectively and to combine or
> recombine them into ranges.
>
> In other words, scrapping iterators is not possible without losing
> some expressivity. And I believe Alexandrescu acknowledges that too.
I sure do.
Speaking of range recombination (and using your notation), I recently
realized one extra primitive is needed: bool sameFront(r1, r2) that
returns true if and only if ranges r1 and r2 have the same front (they
may have distinct backs).
Without sameFront it is, I think, impossible to implement STL's rotate
on singly-linked lists. I was vaguely aware of the matter as I was
working on rotate, but I pedaled my way out by comparing the addresses
of the front()s of the two ranges. Languages that don't allow address
taking need a full-fledged primitive.
With sameFront() in tow you can create a range that, given two ranges
[a, b] and [c, d] returns a range that effectively iterates [a, c]. That
range would have a distinct type though: it would store both ranges and
then bump "a" until the ranges have the same front, i.e. a == c.
The operation not being type-invariant it is less expressive than the
iterators version. However, it is also more general and could be
specialized for certain ranges to stay type-invariant.
Andrei