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

What problem does this solve,

See Dietmar's answer 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).

Answer 2

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.