Andrei Alexandrescu wrote:
Don wrote:
Andrei Alexandrescu wrote:
Don wrote:
Andrei Alexandrescu wrote:
I've worked valiantly on defining the range infrastructure and
making std.algorithm work with it. I have to say that I'm even more
pleased with the result than I'd ever expected when I started.
Ranges and concepts really make for beautiful code, and I am sure
pretty darn efficient too.
There's a lot to sink one's teeth in, but unfortunately the code
hinges on a compiler fix that Walter was kind enough to send me
privately. I did document the work, but the documentation doesn't
really make justice to the extraordinary possibilities that lay
ahead of us. Anyhow, here's a sneak preview into the up-and-coming
ranges and their algorithms.
http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_range.html
http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_algorithm.html
Ranges are easy to define and compose efficiently. It was, however,
a pig to get a zip(r1, r2, ...) working that can mutate back the
ranges it iterates on. With that, it's very easy to e.g. sort
multiple arrays in parallel. Similarly, chain(r1, r2, ...) is able
to offer e.g. random iteration if all components offer it, which
means that you can do crazy things like sorting data that sits
partially in one array and partially in another.
Singly-linked list ranges are in, and to my soothing I found an
answer to the container/range dichotomy in the form of a topology
policy. A range may or may not be able to modify the topology of
the data it's iterating over; if it can, it's a free-standing
range, much like built-in arrays are. If it can't, it's a limited
range tied to a container (of which I defined none so far, but give
me time) and it's only the container that can mess with the
topology in controlled ways. More on that later.
Feedback welcome.
Andrei
Awesome stuff. Will take some time to adjust my thought processes
for this.
Some minor comments:
* Is Repeat simply a single-parameter form of Cycle? I can't see any
difference between them.
Cycle takes a range and essentially provides a (potentially mutable!)
way of iterating it. Repeat just gives one element. At the moment
that element is also mutable, so the difference is moot. I'll
consider removing Repeat.
* Uniq docs should at least add one word: Iterates
[[consecutively]] unique elements of the given range.
* find:
To find the last element of [[a bidirectional]] haystack satisfying
pred, call find!(pred)(retro(haystack)).
(unless Retro also works for forward ranges, which seems unlikely).
Thanks (and correct).
* There's no pushHeap. Is it planned?
I plan to do something nicer: make Heap an entity of its own instead
of a collection of disparate functions. I'm unsure about the name
because I mean "the computer science heap" as opposed to "the heap
for allocating memory".
Even better. You might consider including adjustHeap, which is used in
eg Dijkstra's algorithm. Stepanov said it was intended to have been
public in the STL, but got dropped for political reasons <g>.
(Sorry, this fell through the cracks.) What does adjustHeap do? I have
heap adjustment as part of pop() and the constructor.
Andrei
adjustHeap is used to restore the heap invariant after the value of a
single element has been changed.