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

Section: 23.2.8 [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 23.2.7 [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 23.2.8 [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 22.10 [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 22.10 [function.objects]; fixes the "requirements" for typedefs in 22.10.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 (22.10.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 (22.10.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 22.10 [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 23.2.8 [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 22.10.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 22.10.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 22.10 [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 26 [algorithms]), the interface is specified to accept an object with an operator() defineda 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 22.10.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 (22.10 [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 22.10.15 [func.bind]/1 as indicated:

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

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

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

  6. Change 22.10.17.3 [func.wrap.func]/2 as indicated [The reason for this change is that 22.10.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 functioncallable 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 22.10.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 22.10.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 22.10.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 22.10.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 (22.10.17.3 [func.wrap.func]) for parameter types ArgTypes and return type R.

  11. Change 23.2.7 [associative.reqmts]/2 as indicated: [The suggested removal seems harmless, because 26.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 (26.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 23.2.8 [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 26.1 [algorithms.general]/7 as indicated: [The intent is to bring this part in sync with 22.10 [function.objects]]

    7 The Predicate parameter is used whenever an algorithm expects a function object (22.10 [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.3.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.