RFC: patched searchsortedfirst, searchsortedlast, searchsorted, and insorted available in DataStructures.jl?

[StephenVavasis]

A number of Julia users including me have been stung by unexpected behavior in the searchsorted suite of functions in Base, namely, that the by transformation is applied also to the key. There is a recent discussion (https://discourse.julialang.org/t/problem-with-searchsortedfirst/73332/31) of this on discourse, but it has come up before. This makes the suite awkward to use when the by function is something like first that extracts part of a larger object. A PR https://github.com/JuliaLang/julia/pull/35418 to fix this problem was rejected by the core team. I am wondering: Would it make sense to offer patched versions of these Base function in the DataStructures package? Note DataStructures already overloads Base.searchsortedfirst, etc., specifically for sorted containers, so it would not be totally random.

[oxinabox]

No, I don't think so? Not if that means monkey-patching Base via type-piracy. It's too evil to inflict on our >1000 downstream packages.

[StephenVavasis]

I was thinking of a new type, say SortedVector, that would patch this issue. So the user would say: searchsorted(SortedVector(my_vector, extract_key_from_record=(x->x.first)), key, by=func). Then the docstring for Base.searchsorted could briefly mention the awkwardness of applying by to the key and the existence of this alternative.

[oxinabox]

ah, in that case i think it is less evil, but better to put in a new package in JuliaCollections or elsewhere. I think you should have the rights sufficient to create such a new package