Comment #0 by bearophile_hugs — 2014-05-18T08:15:07Z
void main() {
import std.stdio, std.algorithm, std.range;
auto odds = 30.iota.filter!q{ a % 2 }.assumeSorted;
odds.upperBound(12).writeln;
}
DMD 2.066alpha gives:
C:\dmd2\src\phobos\std\range.d(8613,9): Error: static assert "Specify SearchPolicy.linear explicitly for SortedRange!(FilterResult!(unaryFun, Result), "a < b")"
temp.d(4,20): instantiated from here: upperBound!(cast(SearchPolicy)3, int)
The code compiles and works if I add SearchPolicy.linear:
void main() {
import std.stdio, std.algorithm, std.range;
auto odds = 30.iota.filter!q{ a % 2 }.assumeSorted;
odds.upperBound!(SearchPolicy.linear)(12).writeln;
}
But monarch_dodra said:
> for a sorted linked list (or forward iterators in general),
> you can find the result with O(N) *walk* iterations, but still
> only O(log(N)) *comparison* iterations.
> It's not used in phobos (as far as I know of anyways). It *could*
> be implemented in SortedRange's BinaryFind though.
I think it's worth supporting SearchPolicy.binarySearch (that is the default one for upperBound) for InputRanges too.
Comment #1 by monarchdodra — 2014-05-18T15:19:27Z
It requires Forward iteration minimum.
Comment #2 by robert.schadek — 2024-12-01T16:21:11Z