This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of NAD Concepts status.

### 1111. associative containers underconstrained

Section: 24.4 [associative] Status: NAD Concepts Submitter: Alisdair Meredith Opened: 2009-04-29 Last modified: 2016-01-28

Priority: Not Prioritized

View all other issues in [associative].

View all issues with NAD Concepts status.

Discussion:

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`.

[ Batavia (2009-05): ]

> We agree with the proposed resolution.

> Move to Review.

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 24.4 [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
> >        {
> >          ...
> >        };
> >      }