Proposed resolution:

For ordered containers, replace

Predicate<auto, Key, Key> Compare = less<Key>

with

StrictWeakOrder<auto, Key, Key> Compare = less<Key>

For unordered containers, replace

Predicate<auto, Key, Key> Compare = less<Key>

with

EquivalenceRelation<auto, Key, Key> Compare = less<Key>

As in the following declarations:

Associative containers [associative]

1 Headers <map> and <set>:

Header <map> synopsis

   namespace std {
     template <ValueType Key, ValueType T,
               PredicateStrictWeakOrder<auto, Key, Key> Compare = less<Key>,
               Allocator Alloc = allocator<pair<const Key, T> > >
       requires NothrowDestructible<Key> && NothrowDestructible<T>
             && CopyConstructible<Compare>
             && AllocatableElement<Alloc, Compare, const Compare&>
             && AllocatableElement<Alloc, Compare, Compare&&>
     class map;

     ...

     template <ValueType Key, ValueType T,
               PredicateStrictWeakOrder<auto, Key, Key> Compare = less<Key>,
               Allocator Alloc = allocator<pair<const Key, T> > >
       requires NothrowDestructible<Key> && NothrowDestructible<T>
             && CopyConstructible<Compare>
             && AllocatableElement<Alloc, Compare, const Compare&>
             && AllocatableElement<Alloc, Compare, Compare&&>
     class multimap;

     ...

   }

Header <set> synopsis

   namespace std {
     template <ValueType Key, PredicateStrictWeakOrder<auto, Key, Key> Compare = less<Key>,
               Allocator Alloc = allocator<Key> >
       requires NothrowDestructible<Key> && CopyConstructible<Compare>
             && AllocatableElement<Alloc, Compare, const Compare&>
             && AllocatableElement<Alloc, Compare, Compare&&>
     class set;

     ...

     template <ValueType Key, PredicateStrictWeakOrder<auto, Key, Key> Compare = less<Key>,
               Allocator Alloc = allocator<Key> >
       requires NothrowDestructible<Key> && CopyConstructible<Compare>
             && AllocatableElement<Alloc, Compare, const Compare&>
             && AllocatableElement<Alloc, Compare, Compare&&>
     class multiset;

     ...

   }

23.4.1p2 Class template map [map]

 namespace std {
   template <ValueType Key, ValueType T,
             PredicateStrictWeakOrder<auto, Key, Key> Compare = less<Key>,
             Allocator Alloc = allocator<pair<const Key, T> > >
     requires NothrowDestructible<Key> && NothrowDestructible<T>
           && CopyConstructible<Compare>
           && AllocatableElement<Alloc, Compare, const Compare&>
           && AllocatableElement<Alloc, Compare, Compare&&>
   class map {
     ...
   };
 }

23.4.2p2 Class template multimap [multimap]

 namespace std {
   template <ValueType Key, ValueType T,
             PredicateStrictWeakOrder<auto, Key, Key> Compare = less<Key>,
             Allocator Alloc = allocator<pair<const Key, T> > >
     requires NothrowDestructible<Key> && NothrowDestructible<T>
           && CopyConstructible<Compare>
           && AllocatableElement<Alloc, Compare, const Compare&>
           && AllocatableElement<Alloc, Compare, Compare&&>
   class multimap {
     ...
   };
 }

23.4.3p2 Class template set [set]

 namespace std {
   template <ValueType Key, PredicateStrictWeakOrder<auto, Key, Key> Compare = less<Key>,
             Allocator Alloc = allocator<Key> >
     requires NothrowDestructible<Key> && CopyConstructible<Compare>
           && AllocatableElement<Alloc, Compare, const Compare&>
           && AllocatableElement<Alloc, Compare, Compare&&>
   class set {
     ...
   };
 }

23.4.4p2 Class template multiset [multiset]

 namespace std {
   template <ValueType Key, PredicateStrictWeakOrder<auto, Key, Key> Compare = less<Key>,
             Allocator Alloc = allocator<Key> >
     requires NothrowDestructible<Key> && CopyConstructible<Compare>
           && AllocatableElement<Alloc, Compare, const Compare&>
           && AllocatableElement<Alloc, Compare, Compare&&>
   class multiset {
     ...
   };
 }

23.5 Unordered associative containers [unord]

1 Headers <unordered_map> and <unordered_set>:

Header <unordered_map> synopsis

 namespace std {
   // 23.5.1, class template unordered_map:
   template <ValueType Key,
             ValueType T,
             Callable<auto, const Key&> Hash = hash<Key>,
             PredicateEquivalenceRelation<auto, Key, Key> Pred = equal_to<Key>,
             Allocator Alloc = allocator<pair<const Key, T> > >
     requires NothrowDestructible<Key> && NothrowDestructible<T>
           && SameType<Hash::result_type, size_t>
           && CopyConstructible<Hash> && CopyConstructible<Pred>
           && AllocatableElement<Alloc, Pred, const Pred&>
           && AllocatableElement<Alloc, Pred, Pred&&>
           && AllocatableElement<Alloc, Hash, const Hash&>
           && AllocatableElement<Alloc, Hash, Hash&&>
     class unordered_map;

   // 23.5.2, class template unordered_multimap:
   template <ValueType Key,
             ValueType T,
             Callable<auto, const Key&> Hash = hash<Key>,
             PredicateEquivalenceRelation<auto, Key, Key> Pred = equal_to<Key>,
             Allocator Alloc = allocator<pair<const Key, T> > >
     requires NothrowDestructible<Key> && NothrowDestructible<T>
           && SameType<Hash::result_type, size_t>
           && CopyConstructible<Hash> && CopyConstructible<Pred>
           && AllocatableElement<Alloc, Pred, const Pred&>
           && AllocatableElement<Alloc, Pred, Pred&&>
           && AllocatableElement<Alloc, Hash, const Hash&>
           && AllocatableElement<Alloc, Hash, Hash&&>
     class unordered_multimap;

   ...
 }

Header <unordered_set> synopsis

 namespace std {
   // 23.5.3, class template unordered_set:
   template <ValueType Value,
             Callable<auto, const Value&> Hash = hash<Value>,
             PredicateEquivalenceRelation<auto, Value, Value> class Pred = equal_to<Value>,
             Allocator Alloc = allocator<Value> >
     requires NothrowDestructible<Value>
           && SameType<Hash::result_type, size_t>
           && CopyConstructible<Hash> && CopyConstructible<Pred>
           && AllocatableElement<Alloc, Pred, const Pred&>
           && AllocatableElement<Alloc, Pred, Pred&&>
           && AllocatableElement<Alloc, Hash, const Hash&>
           && AllocatableElement<Alloc, Hash, Hash&&>
     class unordered_set;

   // 23.5.4, class template unordered_multiset:
   template <ValueType Value,
             Callable<auto, const Value&> Hash = hash<Value>,
             PredicateEquivalenceRelation<auto, Value, Value> class Pred = equal_to<Value>,
             Allocator Alloc = allocator<Value> >
     requires NothrowDestructible<Value>
           && SameType<Hash::result_type, size_t>
           && CopyConstructible<Hash> && CopyConstructible<Pred>
           && AllocatableElement<Alloc, Pred, const Pred&>
           && AllocatableElement<Alloc, Pred, Pred&&>
           && AllocatableElement<Alloc, Hash, const Hash&>
           && AllocatableElement<Alloc, Hash, Hash&&>
     class unordered_multiset;

   ...
 }

23.5.1p3 Class template unordered_map [unord.map]

 namespace std {
   template <ValueType Key,
             ValueType T,
             Callable<auto, const Key&> Hash = hash<Key>,
             PredicateEquivalenceRelation<auto, Key, Key> Pred = equal_to<Key>,
             Allocator Alloc = allocator<pair<const Key, T> > >
     requires NothrowDestructible<Key> && NothrowDestructible<T>
           && SameType<Hash::result_type, size_t>
           && CopyConstructible<Hash> && CopyConstructible<Pred>
           && AllocatableElement<Alloc, Pred, const Pred&>
           && AllocatableElement<Alloc, Pred, Pred&&>
           && AllocatableElement<Alloc, Hash, const Hash&>
           && AllocatableElement<Alloc, Hash, Hash&&>
   class unordered_map
   {
     ...
   };
 }

23.5.2p3 Class template unordered_multimap [unord.multimap]

 namespace std {
   template <ValueType Key,
             ValueType T,
             Callable<auto, const Key&> Hash = hash<Key>,
             PredicateEquivalenceRelation<auto, Key, Key> Pred = equal_to<Key>,
             Allocator Alloc = allocator<pair<const Key, T> > >
     requires NothrowDestructible<Key> && NothrowDestructible<T>
           && SameType<Hash::result_type, size_t>
           && CopyConstructible<Hash> && CopyConstructible<Pred>
           && AllocatableElement<Alloc, Pred, const Pred&>
           && AllocatableElement<Alloc, Pred, Pred&&>
           && AllocatableElement<Alloc, Hash, const Hash&>
           && AllocatableElement<Alloc, Hash, Hash&&>
   class unordered_multimap
   {
     ...
   };
 }

23.5.3p3 Class template unordered_set [unord.set]

 namespace std {
   template <ValueType Value,
             Callable<auto, const Value&> Hash = hash<Value>,
             PredicateEquivalenceRelation<auto, Value, Value> class Pred = equal_to<Value>,
             Allocator Alloc = allocator<Value> >
     requires NothrowDestructible<Value>
           && SameType<Hash::result_type, size_t>
           && CopyConstructible<Hash> && CopyConstructible<Pred>
           && AllocatableElement<Alloc, Pred, const Pred&>
           && AllocatableElement<Alloc, Pred, Pred&&>
           && AllocatableElement<Alloc, Hash, const Hash&>
           && AllocatableElement<Alloc, Hash, Hash&&>
   class unordered_set
   {
     ...
   };
 }

23.5.4p3 Class template unordered_multiset [unord.multiset]

 namespace std {
   template <ValueType Value,
             Callable<auto, const Value&> Hash = hash<Value>,
             PredicateEquivalenceRelation<auto, Value, Value> class Pred = equal_to<Value>,
             Allocator Alloc = allocator<Value> >
     requires NothrowDestructible<Value>
           && SameType<Hash::result_type, size_t>
           && CopyConstructible<Hash> && CopyConstructible<Pred>
           && AllocatableElement<Alloc, Pred, const Pred&>
           && AllocatableElement<Alloc, Pred, Pred&&>
           && AllocatableElement<Alloc, Hash, const Hash&>
           && AllocatableElement<Alloc, Hash, Hash&&>
   class unordered_multiset
   {
     ...
   };
 }

[ Batavia (2009-05): ]

We agree with the proposed resolution.

Move to Review.

According to table 87 (n2857) the expression X::key_equal for an unordered container shall return a value of type Pred, where Pred is an equivalence relation.

However, all 4 containers constrain Pred to be merely a Predicate, and not EquivalenceRelation.