Partial template type deduction

Question

I am writing a template meant to sort tuples by their elements at compile-time specified indices. I have code that works, but is a pain to use because I have to specify the type of the binary function used to sort the tuple elements.

template <typename BinaryFunction, int Index>
struct sort_by_index_t {
  explicit sort_by_index_t(const BinaryFunction& binary_function)
      : binary_function(binary_function) {}

  template <typename Tuple>
  bool operator()(const Tuple& left, const Tuple& right) const {
    return binary_function(std::get<Index>(left),
                           std::get<Index>(right));
  }

 private:
  const BinaryFunction binary_function;
};

template <typename BinaryFunction, int Index>
sort_by_index_t<BinaryFunction, Index>
sort_by_index(const BinaryFunction& binary_function) {
  return sort_by_index_t<BinaryFunction, Index>(binary_function);
}

So if I want to sort by the first element in the tuple, I have to type:

sort_by_index<std::less<char>, 0>(std::less<char>());

Instead, I'd rather have an interface such as the below to avoid duplication, but it does not currently compile.

sort_by_index<0>(std::less<char>());

I don't see a way to automatically deduce Index (and it would be unnecessary), but sort_by_index should be able to deduce the type of BinaryFunction.

How can I rewrite the above so that I do not need to specify the type of BinaryFunction?

score 7 · Accepted Answer · answered Apr 06 '16 at 18:58

Index is non-deducible, so it must be explicitly provided. Explicitly provided template arguments can only be provided from left-to-right, whereas the ordering of the template arguments doesn't matter for deduction so it's a simple fix to just reorder them to make sure Index goes first:

template <int Index, typename BinaryFunction> // only this line needs to change
sort_by_index_t<BinaryFunction, Index>
sort_by_index(const BinaryFunction& binary_function) {
  return sort_by_index_t<BinaryFunction, Index>(binary_function);
}

That said, this is unsatisfying because we're conflating two seemingly unrelated things - the binary function that we're using as a comparator, and the data that we're actually comparing. And we have to write a lot of code here that's basically just repetitive boilerplate.

In the ranges proposal, Eric Niebler, Sean Parent, and Andrew Sutton argue for algorithms taking invokable projections. If you have a C++14 compiler, I'd encourage you to implement them so that you can just write something like:

// polymorphic getter
template <size_t I>
auto getter() {
    return [](auto&& tuple) {
        return std::get<I>(std::forward<decltype(tuple)>(tuple));
    };
}

// just use the getter as a projection
std::sort(container_of_tuples,
    std::less<char>{},  // this is the binary function
    getter<0>());       // this is the projection

As a top user in C++, can you please introduce me the best book for learning C++? — Shafizadeh, Apr 06 '16 at 19:11
@Shafizadeh [Definitive C++ Book Guide and list](http://stackoverflow.com/q/388242/2069064) — Barry, Apr 06 '16 at 19:12
Me, I'd implement `order_by( projection, base_order = std::less<> )` rather than reimplement `std::sort` with projection support. — Yakk - Adam Nevraumont, Apr 07 '16 at 13:53
@Barry The top post there lacks any decent post-C++11 template books? Not sure if any exist. — Yakk - Adam Nevraumont, Apr 07 '16 at 13:55
@Yakk Want to write one? I'm not aware of any. Unfortunately most of the good ones are effectively obsolete by not covering any of the new stuff (e.g. Abrahams or Alexandrescu). — Barry, Apr 07 '16 at 13:58

score 4 · Answer 2 · answered Apr 06 '16 at 18:36

Template type deduction works from right to left. If the rightmost template parameter must be specified, then so must every other template parameter. The following slight modification to the above allows for the much cleaner interface. Essentially, the Index template parameter must come before BinaryFunction since sort_by_index cannot automatically deduce Index.

template <int Index, typename BinaryFunction>
struct sort_by_index_t {
  explicit sort_by_index_t(const BinaryFunction& binary_function)
      : binary_function(binary_function) {}

  template <typename Tuple>
  bool operator()(const Tuple& left, const Tuple& right) const {
    return binary_function(std::get<Index>(left),
                           std::get<Index>(right));
  }

 private:
  const BinaryFunction binary_function;
};

template <int Index, typename BinaryFunction>
sort_by_index_t<Index, BinaryFunction>
sort_by_index(const BinaryFunction& binary_function) {
  return sort_by_index_t<Index, BinaryFunction>(binary_function);
}

The below now compiles:

sort_by_index<0>(std::less<char>());

Partial template type deduction

2 Answers2

Linked