137

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 a 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?

3

4 Answers 4

85

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).

7
  • 4
    Hey, were you the one to whom STL said, "Of course you can do template argument deduction in your head" in the talk woolstar linked?
    – Kerrek SB
    Commented Dec 4, 2013 at 21:12
  • 14
    Nope, I wasn't there, but there are people with far more conforming compilers in their heads than I have :) Commented Dec 4, 2013 at 23:02
  • 1
    I guess "diamond operator" refers to <> in the linked proposal, but that proposal did not introduce <> - it is existing syntax for an empty template parameter list. "Diamond operator functors" would be a bit less confusing.
    – Qwertie
    Commented Jan 22, 2019 at 22:13
  • @JonathanWakely - Do you maybe known why std::string does not specify a heterogeneous comparator?
    – Martin Ba
    Commented Jun 7, 2022 at 6:40
  • Does this work for std::unordered_set? Commented Dec 21, 2022 at 8:36
37

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.

4
  • Thanks - see my comment on the other question: Do you get the transparent behaviour by default?
    – Kerrek SB
    Commented Dec 1, 2013 at 23:10
  • 8
    @KerrekSB: the transparent behavior is enable when is_transparent is defined in the comparison function object according to 23.2.4 [associative.reqmts] paragraph 13. The default comparison function objects is std::less<Key> according to 23.4.2 [associative.map.syn] and 23.4.3 [associative.set.syn]. According to 20.10.5 [comparison] paragraph 4 the general template for std::less<...> does not define a nested type is_transparent but the std::less<void> specialization does. That is, no, you don't get a transparent operator by default. Commented Dec 1, 2013 at 23:45
  • Do you have any idea for the naming? I mean why is_transparent?
    – plasmacel
    Commented Jun 19, 2018 at 20:01
  • You want a "concrete example where this is useful"? Here's my use case
    – spraff
    Commented Jan 5, 2019 at 15:23
23

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.

6
  • 1
    Does std::set<std::string> actually benefit from "passing the char const * through", or do you need to make a std::set<std::string, std::less<>>?
    – Kerrek SB
    Commented Dec 1, 2013 at 23:09
  • @Kerrek I think "passing the char const *" was the problem they were trying to avoid, if I'm not mistaken. Look at the wording: 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<std::string>, which would construct a std::string temporary for every comparison. The LWG considered this performance problem to be a serious issue.
    – user1508519
    Commented Dec 1, 2013 at 23:20
  • Your quote and mine of paragraph 13 say the opposite: "unless the type exists / does not exist"...?!
    – Kerrek SB
    Commented Dec 1, 2013 at 23:22
  • 5
    @KerrekSB, that's my fault, N3657 was supposed to say "exists" but I wrote "does not exist" ... it was a late paper written at the last minute. The draft standard is correct. Commented Dec 4, 2013 at 18:20
  • 4
    Yes, it might be clearer to quote what I meant to say not what I actually said at the time :) Commented Dec 4, 2013 at 18:23
7

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)

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.