c++ - 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 Ma 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).