Re: how to get top N distinct elements from range?

[Andrea Fontana]

On Saturday, 9 March 2013 at 01:00:26 UTC, bearophile wrote:
This is a shortened version of the filter(), it calls pred only 
n times, but it calls _input.front n*2 times. If _input.front 
is not deterministic (that means it's not pure, as in the case 
of distinct filtering function) it gives wrong results:


struct FilterResult(alias pred, Range) {
    Range _input;

    this(Range r) {
        _input = r;
        while (!_input.empty && !pred(_input.front)) {
            _input.popFront();
        }
    }

    @property bool empty() { return _input.empty; }

    void popFront() {
        do {
            _input.popFront();
        } while (!_input.empty && !pred(_input.front));
    }

    @property auto ref front() {
        return _input.front;
    }
}


This isn't exactly a bug of filter(), it's a design decision of 
not caching _input.front.

Bye,
bearophile

Not funny btw :) It's not so easy to find out. And it's not easy 
to write a "cached map" function if you use classes or some 
pointers as ElementType...