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?

Answer 1

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