Let's say I have a large struct, S, and I sort an array of them according to one field:
auto sorted = someArr.sort!((a, b) => a.field < b.field);
Now, I have this SortedRange, but I can only use binary searches and the like if I manufacture an entire S element. But I should be able to search using something like:
sorted.binarySearch!((a, b) => a.field < b)(fieldVal);
This is not available. In fact, the only place where binary search is implemented in Phobos is in std.range, inside the SortedRange package.
I think binarySearch, and the other search mechanisms there, should be available as standalone functions. They can't be proven to be correct at compile time, but that's not important. I don't care if the answer might be WRONG because the sort assumption is incorrect, I just shouldn't have to reimplement binary search on my own, phobos should have this building block available.
Comment #1 by petar.p.kirov — 2020-05-05T23:17:33Z
The following works:
struct S
{
string s;
int field;
}
void main()
{
import std;
auto someArr = 100.iota
.map!(i => S("asd", i))
.array
.randomShuffle;
someArr.sort!((a, b) => a.field < b.field);
someArr
.map!(x => x.field)
.assumeSorted!((a, b) => a < b)
.equalRange(42)
.writeln;
}
So where does this approach fall short? Performance, convenience, and accessibility?
Comment #2 by schveiguy — 2020-05-06T12:25:47Z
(In reply to ZombineDev from comment #1)
> So where does this approach fall short? Performance, convenience, and
> accessibility?
So for example, if I wanted the S values that had the field value 42, this does not work. Instead I have to construct an S:
someArr
.equalRange(S("asd", 42))
.writeln;
Which isn't always easy or practical (S might be a large complicated struct, with only constructors that require valid data for fields that I don't care about).
In my code, I'm now doing:
auto idx = someArr.binarySearch!((S, v) => S.field < v)(val);
if(idx != someArr.length && someArr[idx].field == val) { /* use someArr[idx] */ }
This can be easily captured into a function (I know my values are unique so I don't need to bother with an "equal range").
My contention is that I shouldn't have to write my own binarySearch function to get this kind of functionality.
I suppose I could also do:
someArr
.map!(x => x.field)
.enumerate
.assumeSorted!((a, b) => a[1] < b[1])
.equalRange(tuple(0, 42))
.map!(a => someArr[a[0]])
.writeln;
But again, we are talking about a LOT of work, not only in range-transform acrobatics, but in the compiler actually calling lots of intermediary functions, just to do a simple search an already-sorted data.
A binary search is a simple base component that should be available for constructing more complicated items. We shouldn't hide it inside SortedRange with a very constrained set of interfaces.
Comment #3 by robert.schadek — 2024-12-01T16:36:40Z