Partial template type deduction

5
votes

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?

2
c++templatesc++11

2 Answers

6
votes

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
2
votes

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>());