What are transparent comparators?

Question

In C++14, associative containers seem to have changed from C++11 – [associative.reqmts]/13 says:

The member function templates find, count, lower_bound, upper_bound, and equal_range shall not participate in overload resolution unless the type Compare::is_transparent exists.

What is the purpose of making an comparator "transparent"?

C++14 also provides library templates like this:

template <class T = void> struct less {
    constexpr bool operator()(const T& x, const T& y) const;
    typedef T first_argument_type;
    typedef T second_argument_type;
    typedef bool result_type;
};

template <> struct less<void> {
    template <class T, class U> auto operator()(T&& t, U&& u) const
    -> decltype(std::forward<T>(t) < std::forward<U>(u));
    typedef *unspecified* is_transparent;
};

So for example, std::set<T, std::less<T>> would not have a transparent comparator, but std::set<T, std::less<>> would have one.

What problem does this solve, and does this change how standard containers work? For example, the template parameters of std::set are still Key, Compare = std::less<Key>, ..., so does the default set lose its find, count, etc. members?

Answer 1

In C++11 there are not member templates find(), lower_bound(), etc. That is, nothing is lost by this change. The member templates were introduced with n3657 to allow heterogeneous keys being used with the associative containers. I don't see any concrete example where this is useful except for the example which is good and bad!

The is_transparent use is intended to avoid unwanted conversions. If the member templates were unconstrained, existing code may pass through objects directly which would have been converted without the member templates. The example use-case from n3657 is locating an object in a std::set<std::string> using a string literal: with the C++11 definition a std::string object is constructed when passing a string literals to the corresponding member function. With the change it is possible to use the string literal directly. If the underlying comparison function object is implemented exclusively in terms of std::string that is bad because now a std::string would be created for each comparison. On the other hand, if the underlying comparison function object can take a std::string and a string literal, that may avoid construction of a temporary object.

The nested is_transparent type in the comparison function object provides a way to specify if the templated member function should be used: if the comparison function object can deal with heterogeneous arguments, it defines this type to indicate that it can deal with different arguments efficiently. For example, the new operator function objects just delegate to operator<() and claim to be transparent. That, at least, works for std::string which has overloaded less than operators taking char const* as argument. Since these function objects are also new, even if they do the wrong thing (i.e. require a conversion for some type) it would, at least, not be a silent change resulting in a performance degradation.

Answer 2

Stephan T Lavavej talks about problems where the compiler keeps creating temporaries, and how his proposal of transparent operator functors will solve this in c++1y

GoingNative 2013 - Dont help the Compiler (at about the hour mark)

Answer 3

_{The following is all copy-pasta from n3657.}

Q. What is the purpose of making an comparator "transparent"?

A. The associative container lookup functions (find, lower_bound, upper_bound, equal_range) only take an argument of key_type, requiring users to construct (either implicitly or explicitly) an object of the key_type to do the lookup. This may be expensive, e.g. constructing a large object to search in a set when the comparator function only looks at one field of the object. There is strong desire among users to be able to search using other types which are comparable with the key_type.

Q. What problem does this solve

A. The LWG had concerns about code like the following:

std::set<std::string> s = /* ... */;
s.find("key");

In C++11 this will construct a single std::string temporary and then compare it with elements to find the key.

With the change proposed by N3465 the std::set::find() function would be an unconstrained template which would pass the const char* through to the comparator function, std::less, which would construct a std::string temporary for every comparison. The LWG considered this performance problem to be a serious issue. The template find() function would also prevent finding NULL in a container of pointers, which causes previously valid code to no longer compile, but this was seen as a less serious issue than the silent performance regression

Q. does this change how standard containers work

A. This proposal modifies the associative containers in and by overloading the lookup member functions with member function templates. There are no language changes.

Q. so does the default set lose its find, count, etc. members

A. Almost all existing C++11 code is unaffected because the member functions are not present unless new C++14 library features are used as the comparison functions.

To quote Yakk,

In C++14, std::set::find is a template function if Compare::is_transparent exists. The type you pass in does not need to be Key, just equivalent under your comparator.

and n3657,

Add paragraph 13 in 23.2.4 [associative.reqmts]: The member function templates find, lower_bound, upper_bound and equal_range shall not participate in overload resolution unless the type Compare::is_transparent does not exist does exist.

n3421 provides an example of "Transparent Operator Functors".

The full code is here.

Answer 4

What problem does this solve,

See Dietmar and remyabel's answer.

and does this change how standard containers work?

No, not by default.

The new member function template overloads of find etc. allow you to use a type that is comparable with the container's key, instead of using the key type itself. See N3465 by Joaquín Mª López Muñoz for rationale and a detailed, carefully written proposal to add this feature.

At the Bristol meeting the LWG agreed that the heteregeneous lookup feature was useful and desirable, but we could not be sure that Joaquín's proposal would be safe in all cases. The N3465 proposal would have caused serious problems for some programs (see the Impact on existing code section). Joaquín prepared an updated draft proposal with some alternative implementations with different trade-offs, which was very useful helping the LWG understand the pros and cons, but they all risked breaking some programs in some way so there was no consensus to add the feature. We decided that although it wouldn't be safe to add the feature unconditionally, it would be safe if it was disabled by default and only "opt in".

The key difference of the N3657 proposal (which was a last-minute revision by myself and STL based on N3465 and a later unpublished draft by Joaquín) was to add the is_transparent type as the protocol that can be used to opt in to the new functionality.

If you don't use a "transparent functor" (i.e. one that defines a is_transparent type) then the containers behave the same as they've always done, and that's still the default.

Iff you choose to use std::less<> (which is new for C++14) or another "transparent functor" type then you get the new functionality.

Using std::less<> is easy with alias templates:

template<typename T, typename Cmp = std::less<>, typename Alloc = std::allocator<T>>
  using set = std::set<T, Cmp, Alloc>;

The name is_transparent comes from STL's N3421 which added the "diamond operators" to C++14. A "transparent functor" is one which accepts any argument types (which don't have to be the same) and simply forwards those arguments to another operator. Such a functor happens to be exactly what you want for heterogeneous lookup in associative containers, so the type is_transparent was added to all the diamond operators and used as the tag type to indicate the new functionality should be enabled in associative containers. Technically, the containers don't need a "transparent functor", just one that supports calling it with heterogeneous types (e.g. the pointer_comp type in https://stackoverflow.com/a/18940595/981959 is not transparent according to STL's definition, but defining pointer_comp::is_transparent allows it to be used to solve the problem). If you only ever lookup in your std::set<T, C> with keys of type T or int then C only needs to be callable with arguments of type T and int (in either order), it doesn't need to be truly transparent. We used that name partly because we couldn't come up with a better name (I would have preferred is_polymorphic because such functors use static polymorphism, but there's already a std::is_polymorphic type trait which refers to dynamic polymorphism).