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.

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.