Suggestion: Operator `in` for slices

Biotronic simen.kjaras at
Mon Dec 20 13:07:40 UTC 2021

On Monday, 20 December 2021 at 11:28:52 UTC, Araq wrote:
> On Monday, 20 December 2021 at 11:04:00 UTC, Dennis wrote:
>> And this is my biggest problem with that argument: it's about 
>> this mystical function that takes a generic data structure and 
>> uses the `in` operator multiple times on it, which can now 
>> suddenly be called on an array, ruining performance to the 
>> surprise of the programmer.
>> What is this function? Does it exist in Phobos currently?
> And how come it cannot store the result of the "in" operation 
> in a local variable for re-use? And how exactly is calling an 
> oh-so-efficient sub-linear O(log N) function repeatedly when 
> you can save the result in a local *not* a problem?

     bool isSubset(T1, T2)(T1 needles, T2 haystack) {
         foreach (needle; needles) {
             if (!(needle in haystack)) return false;
         return true;

If 'in' is O(1), that's a fairly sensible implementation. If it's 
O(N), it's not. Since the lookup uses different arguments each 
time, local variables can't help you.

Note that, of course, there's no problem if `x in arr` is a 
simple bounds check - if your bounds check on an array is O(N), 
you're doing it wrong.


More information about the Digitalmars-d mailing list