<functional>: boyer_moore_searcher and boyer_moore_horspool_searcher should accept ADL-incompatible element types

[frederick-vs-ja]

Describe the bug

The following program doesn't compile with MSVC STL due to ADL which attempts to complete a bad type.

#include <algorithm>
#include <functional>

template <class T>
struct holder {
    T t;
};

struct incomplete;

int main() {
    using validator = holder<incomplete>*;
    validator varr[1]{};
    (void) std::search(varr, varr + 1, std::boyer_moore_searcher<const validator*>{varr, varr + 1});
    (void) std::search(varr, varr + 1, std::boyer_moore_horspool_searcher<const validator*>{varr, varr + 1});
}

After the changes in #4379, the bug of MSVC STL comes from allocator comparison and iterator operations in unordered_map which is internally used by both searchers.

STL/stl/inc/functional

Line 2541 in 192a840

unordered_map<_Value_t, _Diff, _Hash_ty, _Pred_eq> _Map;

Command-line test case

Godbolt link.

Other standard library implementations seem to be buggy due to similar reasons.

Expected behavior

This example compiles.

STL version

Microsoft Visual Studio Community 2022
Version 17.9.0 Preview 5.0

Additional context

_STD-qualification doesn't work for this case. We may need to change the type of the unordered_map to avoid undesired ADL, which may be dangerous for ABI-compatibility.

[StephanTLavavej]

We talked about this at the weekly maintainer meeting and while this may technically be a bug, it's super low priority and basically everything else is more important to spend reviewer time on. We'd be fine with this being broken forever, barring an example of a reasonable program that needs this. (The vast majority of Boyer-Moore searches will be using plain old character types, nothing exotic.)