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

### 870. Do unordered containers not support function pointers for predicate/hasher?

Section: 22.2.7 [unord.req] Status: C++11 Submitter: Daniel Krügler Opened: 2008-08-17 Last modified: 2016-01-28

Priority: Not Prioritized

View other active issues in [unord.req].

View all other issues in [unord.req].

View all issues with C++11 status.

Discussion:

Good ol' associative containers allow both function pointers and function objects as feasible comparators, as described in 22.2.6 [associative.reqmts]/2:

> Each associative container is parameterized on `Key` and an ordering relation `Compare` that induces a strict weak ordering (25.3) on elements of Key. [..]. The object of type `Compare` is called the comparison object of a container. This comparison object may be a pointer to function or an object of a type with an appropriate function call operator.[..]

The corresponding wording for unordered containers is not so clear, but I read it to disallow function pointers for the hasher and I miss a clear statement for the equality predicate, see 22.2.7 [unord.req]/3+4+5:

> Each unordered associative container is parameterized by `Key`, by a function object `Hash` that acts as a hash function for values of type `Key`, and by a binary predicate `Pred` that induces an equivalence relation on values of type `Key`.[..]

> A hash function is a function object that takes a single argument of type `Key` and returns a value of type `std::size_t`.

> Two values `k1` and `k2` of type `Key` are considered equal if the container's equality function object returns `true` when passed those values.[..]

and table 97 says in the column "assertion...post-condition" for the expression `X::hasher`:

> `Hash` shall be a unary function object type such that the expression `hf(k)` has type `std::size_t`.

Note that 20.14 [function.objects]/1 defines as "Function objects are objects with an `operator()` defined.[..]"

Does this restriction exist by design or is it an oversight? If an oversight, I suggest that to apply the following

[ 2009-07-28 Reopened by Alisdair. No longer solved by concepts. ]

[ 2009-10 Santa Cruz: ]

> Ask Daniel to provide proposed wording that: makes it explicit that function pointers are function objects at the beginning of 20.14 [function.objects]; fixes the "requirements" for typedefs in 20.14.6 [refwrap] to instead state that the function objects defined in that clause have these typedefs, but not that these typedefs are requirements on function objects; remove the wording that explicitly calls out that associative container comparators may be function pointers.

[ 2009-12-19 Daniel updates wording and rationale. ]

[ 2010-02-11 Moved to Tentatively Ready after 5 positive votes on c++std-lib. ]

Rationale:

The below provided wording also affects some part of the library which is involved with callable types (20.14.3 [func.def]/3). Reason for this is that callable objects do have a lot in common with function objects. A simple formula seems to be:

> callable objects = function objects + pointers to member

The latter group is excluded from function objects because of the expression-based usage of function objects in the algorithm clause, which is incompatible with the notation to dereference pointers to member without a concept map available in the language.

This analysis showed some currently existing normative definition differences between the above subset of callable objects and function objects which seem to be unintended: Backed by the Santa Cruz outcome function objects should include both function pointers and "object[s] with an operator() defined". This clearly excludes class types with a conversion function to a function pointer or all similar conversion function situations described in 12.2 [over.match]/2 b. 2. In contrast to this, the wording for callable types seems to be less constrained (20.14.3 [func.def]/3):

> A callable type is a [..] class type whose objects can appear immediately to the left of a function call operator.

The rationale given in N1673 and a recent private communication with Peter Dimov revealed that the intention of this wording was to cover the above mentioned class types with conversion functions as well. To me the current wording of callable types can be read either way and I suggest to make the intention more explicit by replacing

> [..] class type whose objects can appear immediately to the left of a function call operator

by

> [..] class type whose objects can appear as the leftmost subexpression of a function call expression 7.6.1.3 [expr.call].

and to use the same definition for the class type part of function objects, because there is no reason to exclude class types with a conversion function to e.g. pointer to function from being used in algorithms.

Now this last term "function objects" itself brings us to a third unsatisfactory state: The term is used both for objects (e.g. "Function objects are objects[..]" in 20.14 [function.objects]/1) and for types (e.g. "Each unordered associative container is parameterized [..] by a function object Hash that acts as a hash function [..]" in 22.2.7 [unord.req]/3). This impreciseness should be fixed and I suggest to introduce the term function object type as the counter part to callable type. This word seems to be a quite natural choice, because the library already uses it here and there (e.g. "Hash shall be a unary function object type such that the expression `hf(k)` has type `std::size_t`." in Table 98, "`X::hasher`" or "Requires: `T` shall be a function object type [..]" in 20.14.17.3.6 [func.wrap.func.targ]/3).

Finally I would like to add that part of the issue 870 discussion related to the requirements for typedefs in 20.14.6 [refwrap] during the Santa Cruz meeting is now handled by the new issue 1290.

Obsolete rationale:

> [ San Francisco: ]

> > This is fixed by N2776.

Proposed resolution:

1. Change 20.14 [function.objects]/1 as indicated:

   > 1 Function objects are objects with an `operator()` defined. An object type (6.8 [basic.types]) that can be the type of the postfix-expression in a function call (7.6.1.3 [expr.call], 12.2.2.2 [over.match.call]) is called a function object type*. A function object is an object of a function object type. In the places where one would expect to pass a pointer to a function to an algorithmic template (Clause 25 [algorithms]), the interface is specified to accept an object with an `operator()` defined a function object. This not only makes algorithmic templates work with pointers to functions, but also enables them to work with arbitrary function objects.

   > > * Such a type is either a function pointer or a class type which often has a member `operator()`, but in some cases it can omit that member and provide a conversion to a pointer to function.

2. Change 20.14.3 [func.def]/3 as indicated: [The intent is to make the commonality of callable types and function object types more explicit and to get rid of wording redundancies]

   > 3 A callable type is a pointer to function, a pointer to member function, a pointer to member data, or a class type whose objects can appear immediately to the left of a function call operator function object type (20.14 [function.objects]).

3. Change [bind]/1 as indicated:

   > 1 The function template `bind` returns an object that binds a function callable object passed as an argument to additional arguments.

4. Change 20.14.15 [func.bind]/1 as indicated:

   > 1 This subclause describes a uniform mechanism for binding arguments of function callable objects.

5. Change 20.14.17 [func.wrap]/1 as indicated:

   > 1 This subclause describes a polymorphic wrapper class that encapsulates arbitrary function callable objects.

6. Change 20.14.17.3 [func.wrap.func]/2 as indicated [The reason for this change is that 20.14.17.3 [func.wrap.func]/1 clearly says that all callable types may be wrapped by `std::function` and current implementations indeed do provide support for pointer to members as well. One further suggested improvement is to set the below definition of Callable in italics]:

   > 2 A function callable object `f` of type `F` is Callable Callable for argument types `T1, T2, ..., TN` in `ArgTypes` and a return type `R`, if, given lvalues `t1, t2, ..., tN` of types `T1, T2, ..., TN`, respectively, the expression `INVOKE(f, declval<ArgTypes>()..., Rt1, t2, ..., tN)`, considered as an unevaluated operand (7 [expr]), is well formed (20.7.2) and, if `R` is not `void`, convertible to `R`.

7. Change 20.14.17.3.2 [func.wrap.func.con]/7 as indicated:

   >     function(const function& f);
   >     template <class A> function(allocator_arg_t, const A& a, const function& f);

   > > ...

   > > 7 Throws: shall not throw exceptions if `f`'s target is a function pointer or a function callable object passed via `reference_wrapper`. Otherwise, may throw `bad_alloc` or any exception thrown by the copy constructor of the stored function callable object. [Note: Implementations are encouraged to avoid the use of dynamically allocated memory for small function callable objects, e.g., where `f`'s target is an object holding only a pointer or reference to an object and a member function pointer. — end note]

8. Change 20.14.17.3.2 [func.wrap.func.con]/11 as indicated:

   >     template<class F> function(F f);
   >     template <class F, class A> function(allocator_arg_t, const A& a, F f);

   > > ...

   > > 11 [..] [Note: implementations are encouraged to avoid the use of dynamically allocated memory for small function callable objects, for example, where `f`'s target is an object holding only a pointer or reference to an object and a member function pointer. — end note]

9. Change 20.14.17.3.5 [func.wrap.func.inv]/3 as indicated:

   >     R operator()(ArgTypes... args) const

   > > ...

   > > 3 Throws: `bad_function_call` if `!*this`; otherwise, any exception thrown by the wrapped function callable object.

10. Change 20.14.17.3.6 [func.wrap.func.targ]/3 as indicated:

    >     template<typename T>       T* target();
    >     template<typename T> const T* target() const;

    > > ...

    > > 3 Requires: `T` shall be a function object type that is Callable (20.14.17.3 [func.wrap.func]) for parameter types `ArgTypes` and return type `R`.

11. Change 22.2.6 [associative.reqmts]/2 as indicated: [The suggested removal seems harmless, because 25.8 [alg.sorting]1 already clarifies that `Compare` is a function object type. Nevertheless it is recommended, because the explicit naming of "pointer to function" is misleading]

    > 2 Each associative container is parameterized on `Key` and an ordering relation `Compare` that induces a strict weak ordering (25.8 [alg.sorting]) on elements of `Key`. In addition, `map` and `multimap` associate an arbitrary type `T` with the `Key`. The object of type `Compare` is called the comparison object of a container. This comparison object may be a pointer to function or an object of a type with an appropriate function call operator.

12. Change 22.2.7 [unord.req]/3 as indicated:

    > 3 Each unordered associative container is parameterized by `Key`, by a function object type `Hash` that acts as a hash function for values of type `Key`, and by a binary predicate `Pred` that induces an equivalence relation on values of type Key. [..]

13. Change 25.1 [algorithms.general]/7 as indicated: [The intent is to bring this part in sync with 20.14 [function.objects]]

    > 7 The `Predicate` parameter is used whenever an algorithm expects a function object (20.14 [function.objects]) that when applied to the result of dereferencing the corresponding iterator returns a value testable as `true`. In other words, if an algorithm takes `Predicate pred` as its argument and `first` as its iterator argument, it should work correctly in the construct `if (pred(*first)){...}`. The function object `pred` shall not apply any nonconstant function through the dereferenced iterator. This function object may be a pointer to function, or an object of a type with an appropriate function call operator.

14. Change 20.11.1.3 [unique.ptr.single]/1 as indicated:

    > 1 The default type for the template parameter `D` is `default_delete`. A client-supplied template argument `D` shall be a function pointer or functor object type for which, given a value `d` of type `D` and a pointer `ptr` of type `T*`, the expression `d(ptr)` is valid and has the effect of deallocating the pointer as appropriate for that deleter. `D` may also be an lvalue-reference to a deleter.