Document number: N3421=12-0111 Date: 2012-09-20 Project: Programming Language C++, Library Working Group Reply-to: Stephan T. Lavavej Making Operator Functors greater<> I. Introduction This is a proposal to make 's operator functors easier to use and more generic. II. Motivation And Scope The operator functors provided by are a wonderful time-saver. Although we now have C++11's general-purpose lambdas, C++98's special-purpose functors (mostly unchanged in C++11) are still more compact. Compare: sort(v.begin(), v.end(), greater()); sort(v.begin(), v.end(), [](const ValueType& l, const ValueType& r) { return l > r; }); Operator functors are especially important for containers like map>, where lambdas are difficult to use. Unfortunately, the operator functors currently suffer from two major problems. First, they require their argument types to be explicitly specified. The compiler already has this information at the point of functor invocation, so requiring the user to provide it results in unnecessary verbosity. (It's also fairly easy to imagine how redundantly specified information could lead to correctness problems. Consider a vector, sorted with greater. If the container is changed to vector without the comparator being simultaneously changed, the elements will be truncated before being compared. The compiler may emit a truncation warning, but it would be better to make this scenario completely impossible.) To solve this first problem, this proposal introduces the syntax greater<>. This functor has a templated function call operator, capable of accepting arbitrary argument types. This improves both algorithm calls and container types like map>. In fact, compare: sort(v.begin(), v.end(), greater<>()); // this proposal sort(v.begin(), v.end(), [](l, r) { l > r; }); // hypothetical, NOT PROPOSED HERE Even if they're proposed and accepted in the future, ultra-terse polymorphic lambdas would still be more verbose than the operator functors proposed here. The second problem with the operator functors is that their function call operators are homogeneous, with signatures like T (const T&, const T&) for the arithmetic operators and bool (const T&, const T&) for the comparators. This is problematic in several ways: * In a units library, Watts * Seconds returns Joules, which is completely incompatible with a homogeneous signature. * Consider vector v containing null-terminated strings sorted in increasing lexicographic order, and std::string str. In C++11, lower_bound() has been carefully specified to accept different element and value types. Therefore, lower_bound(v.begin(), v.end(), str) will compare elem < str, which is great. Now consider what happens when the strings are sorted in decreasing lexicographic order. We have to provide a comparator, and greater is doubly incorrect (it compares pointers, and str isn't implicitly convertible to const char *). lower_bound(v.begin(), v.end(), str, greater()) works, but is inefficient. Every invocation of greater's function call operator will construct a temporary std::string from elem. This inefficiency is a direct result of the homogeneous signature not being "transparent". * Consider std::plus being invoked with two std::strings, when at least one is a modifiable rvalue. The homogeneous signature T (const T&, const T&) will perform an unnecessary copy. To solve this second problem's many manifestations, this proposal's templated function call operators are perfectly forwarding and perfectly returning (with decltype), which makes them completely transparent. Finally, while we're in the neighborhood - when bit_and, bit_or, and bit_xor were added in C++11, bitwise NOT was left out. This operator is as useful as the other unary operators provided by (std::negate and std::logical_not), so this proposal recommends adding bit_not. This is optional and can be removed without affecting the rest of the proposal. This proposal is intended to benefit all users of 's operator functors, from novices to experts. (Learning to say greater<> is strictly simpler than learning to say greater.) This proposal is not entirely based on existing practice, but a reference implementation is available. See "VIII. Implementation" at the end of this proposal, which provides examples of using greater<> with set and plus<> with transform(). It is essentially a direct copy of the Standardese, non-intrusively (and non-conformantly, of course) applied over a C++11 Standard Library implementation. Also see "VII. References" for a heterogeneous but non-transparent implementation in Origin. III. Impact On The Standard This proposal has no dependencies beyond a C++11 compiler and Standard Library implementation. (It depends on perfect forwarding, decltype, and trailing return types.) Nothing depends on this proposal. This proposal is almost a pure extension. It doesn't affect C++11 user code at all, except that "using namespace std;" will drag in bit_not. It almost entirely consists of additions to the C++11 Standard Library, except that it modifies the declarations of the operator functors by giving them default template arguments. IV. Design Decisions A. The major difficulty here is that C++98 took all the good names! If we were designing the operator functors from scratch, ideally std::greater/etc. would be ordinary non-templated structs with the templated function call operators proposed here. Unfortunately, we can't simply de-templatize the structs - doing so would break the world (far worse than C++11 immutable sets). Nor can we "overload" struct templates with non-templated structs (14 [temp]/5), or even play games with using-directives (7.3.4 [namespace.udir]/6). There are many naming possibilities, for example: * Providing std::modern::greater. This is problematic because users can't say "using namespace std; using namespace std::modern;" for convenience. * Providing std::Greater. This would avoid the need for this proposal's empty angle brackets, but this capitalization style would be novel to the Standard. (Also, in the presence of using-directives, the new names could conflict with user names, requiring qualification.) * Providing std::greater<>, chosen by this proposal. This requires empty angle brackets, but avoids introducing novel capitalization. If the names Greater, Plus, etc. are strongly desired, a best-of-both-worlds approach would be to simply add "typedef greater<> Greater;" to this proposal. That would allow users to choose their preferred style, with trivial costs to specification/implementation complexity. B. The technique of using default template arguments and explicit specializations for void was chosen for its non-intrusiveness. greater isn't valid C++11 (it would attempt to form a reference to void, forbidden by 8.3.2 [dcl.ref]/1). Additionally, while users are permitted to specialize Standard Library machinery (17.6.4.2.1 [namespace.std]/1), such specializations must involve user-defined types. C. Additional template parameters with default template arguments could be added - for example, in order to permit heterogeneous but fixed signatures of the form R (X, Y). This was rejected due to its complexity and obscurity. In the extremely rare event that neither the completely homogeneous nor the completely transparent operator functors are appropriate, and neither is a lambda (e.g. lambdas are inconvenient for maps), then handwritten functors are the simplest, most direct solution. D. In this proposal, all of the perfectly forwarding function call operators are also perfectly returning, even those for the comparators. While hardcoding bool here wouldn't harm 99.9% of code, it wouldn't benefit anything, and it would harm the 0.1% of extremely generic code that cares about comparison operators returning types other than bool. E. bit_not's homogeneous signature T (const T&) exactly mirrors negate's. Their behavior is nearly identical except that bitwise NOT forbids floating-point inputs, 5.3.1 [expr.unary.op]/8, /10: "The operand of the unary - operator shall have arithmetic or unscoped enumeration type and the result is the negation of its operand. Integral promotion is performed on integral or enumeration operands. [...] The type of the result is the type of the promoted operand." "The operand of ~ shall have integral or unscoped enumeration type; the result is the one's complement of its operand. Integral promotions are performed. The type of the result is the type of the promoted operand." F. Following an argument from symmetry, this proposal adds bit_not. However, it doesn't add any other operator functors. Unary plus remains unloved (ironically, I believe it was added to C for symmetry). Operator functors for left shift, right shift, address-of, and indirection could be useful; consider transform(v.begin(), v.end(), back_inserter(ptrs), address_of<>()). They aren't currently proposed because I view them as slightly beyond "completely trivial to specify". (Should they be completely transparent, or should we continue to provide fixed forms? Should address_of use op&, or std::addressof() to get the True Address? And so forth.) G. This proposal leaves implementers no "wiggle room", but none is necessary here. H. I am not aware of any existing libraries that provide transparent operator functors like this. (Again, see "VII. References" for a heterogeneous but non-transparent implementation in Origin.) V. Standardese 1. In 20.8 [function.objects]/2, change: // 20.8.4, arithmetic operations: template struct plus; template struct minus; template struct multiplies; template struct divides; template struct modulus; template struct negate; // 20.8.5, comparisons: template struct equal_to; template struct not_equal_to; template struct greater; template struct less; template struct greater_equal; template struct less_equal; // 20.8.6, logical operations: template struct logical_and; template struct logical_or; template struct logical_not; // 20.8.7, bitwise operations: template struct bit_and; template struct bit_or; template struct bit_xor; to: // 20.8.4, arithmetic operations: template struct plus; template struct minus; template struct multiplies; template struct divides; template struct modulus; template struct negate; template <> struct plus; template <> struct minus; template <> struct multiplies; template <> struct divides; template <> struct modulus; template <> struct negate; // 20.8.5, comparisons: template struct equal_to; template struct not_equal_to; template struct greater; template struct less; template struct greater_equal; template struct less_equal; template <> struct equal_to; template <> struct not_equal_to; template <> struct greater; template <> struct less; template <> struct greater_equal; template <> struct less_equal; // 20.8.6, logical operations: template struct logical_and; template struct logical_or; template struct logical_not; template <> struct logical_and; template <> struct logical_or; template <> struct logical_not; // 20.8.7, bitwise operations: template struct bit_and; template struct bit_or; template struct bit_xor; template struct bit_not; template <> struct bit_and; template <> struct bit_or; template <> struct bit_xor; template <> struct bit_not; This adds "= void" default template arguments, "" explicit specializations, and "bit_not". 2. In 20.8.4 [arithmetic.operations], 20.8.5 [comparisons], 20.8.6 [logical.operations], and 20.8.7 [bitwise.operations], change every occurrence of "template " to "template ". 3. At the end of 20.8.4 [arithmetic.operations], add: template <> struct plus { template auto operator()(T&& t, U&& u) const -> decltype(std::forward(t) + std::forward(u)); }; operator() returns std::forward(t) + std::forward(u). template <> struct minus { template auto operator()(T&& t, U&& u) const -> decltype(std::forward(t) - std::forward(u)); }; operator() returns std::forward(t) - std::forward(u). template <> struct multiplies { template auto operator()(T&& t, U&& u) const -> decltype(std::forward(t) * std::forward(u)); }; operator() returns std::forward(t) * std::forward(u). template <> struct divides { template auto operator()(T&& t, U&& u) const -> decltype(std::forward(t) / std::forward(u)); }; operator() returns std::forward(t) / std::forward(u). template <> struct modulus { template auto operator()(T&& t, U&& u) const -> decltype(std::forward(t) % std::forward(u)); }; operator() returns std::forward(t) % std::forward(u). template <> struct negate { template auto operator()(T&& t) const -> decltype(-std::forward(t)); }; operator() returns -std::forward(t). 4. At the end of 20.8.5 [comparisons], add: template <> struct equal_to { template auto operator()(T&& t, U&& u) const -> decltype(std::forward(t) == std::forward(u)); }; operator() returns std::forward(t) == std::forward(u). template <> struct not_equal_to { template auto operator()(T&& t, U&& u) const -> decltype(std::forward(t) != std::forward(u)); }; operator() returns std::forward(t) != std::forward(u). template <> struct greater { template auto operator()(T&& t, U&& u) const -> decltype(std::forward(t) > std::forward(u)); }; operator() returns std::forward(t) > std::forward(u). template <> struct less { template auto operator()(T&& t, U&& u) const -> decltype(std::forward(t) < std::forward(u)); }; operator() returns std::forward(t) < std::forward(u). template <> struct greater_equal { template auto operator()(T&& t, U&& u) const -> decltype(std::forward(t) >= std::forward(u)); }; operator() returns std::forward(t) >= std::forward(u). template <> struct less_equal { template auto operator()(T&& t, U&& u) const -> decltype(std::forward(t) <= std::forward(u)); }; operator() returns std::forward(t) <= std::forward(u). 5. At the end of 20.8.6 [logical.operations], add: template <> struct logical_and { template auto operator()(T&& t, U&& u) const -> decltype(std::forward(t) && std::forward(u)); }; operator() returns std::forward(t) && std::forward(u). template <> struct logical_or { template auto operator()(T&& t, U&& u) const -> decltype(std::forward(t) || std::forward(u)); }; operator() returns std::forward(t) || std::forward(u). template <> struct logical_not { template auto operator()(T&& t) const -> decltype(!std::forward(t)); }; operator() returns !std::forward(t). 6. Change 20.8.7 [bitwise.operations]/1 from: "The library provides basic function object classes for all of the bitwise operators in the language (5.11, 5.13, 5.12)." to: "The library provides basic function object classes for all of the bitwise operators in the language (5.11, 5.13, 5.12, 5.3.1)." This adds a reference to 5.3.1 [expr.unary.op], following the order bit_and, bit_or, bit_xor, bit_not. 7. At the end of 20.8.7 [bitwise.operations], add: template struct bit_not { T operator()(const T& x) const; typedef T argument_type; typedef T result_type; }; operator() returns ~x. template <> struct bit_and { template auto operator()(T&& t, U&& u) const -> decltype(std::forward(t) & std::forward(u)); }; operator() returns std::forward(t) & std::forward(u). template <> struct bit_or { template auto operator()(T&& t, U&& u) const -> decltype(std::forward(t) | std::forward(u)); }; operator() returns std::forward(t) | std::forward(u). template <> struct bit_xor { template auto operator()(T&& t, U&& u) const -> decltype(std::forward(t) ^ std::forward(u)); }; operator() returns std::forward(t) ^ std::forward(u). template <> struct bit_not { template auto operator()(T&& t) const -> decltype(~std::forward(t)); }; operator() returns ~std::forward(t). VI. Acknowledgements Thanks to Andrew Sutton, as this proposal was developed as a result of chatting with him about this idea at GoingNative and Kona. In particular, he developed the void specialization technique and reviewed this proposal. Any deficiencies in this proposal, and the monstrous pun in its title, are exclusively my fault. Thanks to Bill Plauger, Deskin Miller, and James McNellis for reviewing this proposal. VII. References All of the citations in this proposal are to Working Paper N3376: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3376.pdf For somewhat similar machinery in a previous branch of Origin, see: http://code.google.com/p/origin/source/browse/trunk/core/include/origin/functional.hpp?spec=svn417&r=417 This machinery was heterogeneous, but not transparent; o_greater<>'s function call operator had the signature bool (const T&, const U&). It additionally permitted T and U to be manually specified. VIII. Implementation Compiled with Visual C++ 2012 RTM. C:\Temp>type meow.cpp namespace std { template struct plus; template struct minus; template struct multiplies; template struct divides; template struct modulus; template struct negate; template struct equal_to; template struct not_equal_to; template struct greater; template struct less; template struct greater_equal; template struct less_equal; template struct logical_and; template struct logical_or; template struct logical_not; template struct bit_and; template struct bit_or; template struct bit_xor; // We don't need to declare bit_not here, as it's new. // We don't need to declare the explicit specializations here, as // nothing in the C++11 Standard Library will attempt to instantiate them. } #include #include namespace std { template <> struct plus { template auto operator()(T&& t, U&& u) const -> decltype(std::forward(t) + std::forward(u)) { return std::forward(t) + std::forward(u); } }; template <> struct minus { template auto operator()(T&& t, U&& u) const -> decltype(std::forward(t) - std::forward(u)) { return std::forward(t) - std::forward(u); } }; template <> struct multiplies { template auto operator()(T&& t, U&& u) const -> decltype(std::forward(t) * std::forward(u)) { return std::forward(t) * std::forward(u); } }; template <> struct divides { template auto operator()(T&& t, U&& u) const -> decltype(std::forward(t) / std::forward(u)) { return std::forward(t) / std::forward(u); } }; template <> struct modulus { template auto operator()(T&& t, U&& u) const -> decltype(std::forward(t) % std::forward(u)) { return std::forward(t) % std::forward(u); } }; template <> struct negate { template auto operator()(T&& t) const -> decltype(-std::forward(t)) { return -std::forward(t); } }; template <> struct equal_to { template auto operator()(T&& t, U&& u) const -> decltype(std::forward(t) == std::forward(u)) { return std::forward(t) == std::forward(u); } }; template <> struct not_equal_to { template auto operator()(T&& t, U&& u) const -> decltype(std::forward(t) != std::forward(u)) { return std::forward(t) != std::forward(u); } }; template <> struct greater { template auto operator()(T&& t, U&& u) const -> decltype(std::forward(t) > std::forward(u)) { return std::forward(t) > std::forward(u); } }; template <> struct less { template auto operator()(T&& t, U&& u) const -> decltype(std::forward(t) < std::forward(u)) { return std::forward(t) < std::forward(u); } }; template <> struct greater_equal { template auto operator()(T&& t, U&& u) const -> decltype(std::forward(t) >= std::forward(u)) { return std::forward(t) >= std::forward(u); } }; template <> struct less_equal { template auto operator()(T&& t, U&& u) const -> decltype(std::forward(t) <= std::forward(u)) { return std::forward(t) <= std::forward(u); } }; template <> struct logical_and { template auto operator()(T&& t, U&& u) const -> decltype(std::forward(t) && std::forward(u)) { return std::forward(t) && std::forward(u); } }; template <> struct logical_or { template auto operator()(T&& t, U&& u) const -> decltype(std::forward(t) || std::forward(u)) { return std::forward(t) || std::forward(u); } }; template <> struct logical_not { template auto operator()(T&& t) const -> decltype(!std::forward(t)) { return !std::forward(t); } }; template struct bit_not { T operator()(const T& x) const { return ~x; } typedef T argument_type; typedef T result_type; }; template <> struct bit_and { template auto operator()(T&& t, U&& u) const -> decltype(std::forward(t) & std::forward(u)) { return std::forward(t) & std::forward(u); } }; template <> struct bit_or { template auto operator()(T&& t, U&& u) const -> decltype(std::forward(t) | std::forward(u)) { return std::forward(t) | std::forward(u); } }; template <> struct bit_xor { template auto operator()(T&& t, U&& u) const -> decltype(std::forward(t) ^ std::forward(u)) { return std::forward(t) ^ std::forward(u); } }; template <> struct bit_not { template auto operator()(T&& t) const -> decltype(~std::forward(t)) { return ~std::forward(t); } }; } #include #include #include #include #include #include #include using namespace std; int main() { vector v; v.push_back("cute"); v.push_back("fluffy"); v.push_back("kittens"); set> s; s.insert("HUNGRY"); s.insert("EVIL"); s.insert("ZOMBIES"); vector dest; transform(v.begin(), v.end(), s.begin(), back_inserter(dest), plus<>()); for (const auto& elem : dest) { cout << elem << endl; } } C:\Temp>cl /EHsc /nologo /W4 /MTd meow.cpp meow.cpp C:\Temp>meow cuteZOMBIES fluffyHUNGRY kittensEVIL