How can I implement a custom template sort function?

Question

I have a vector of pairs that I want to be stable sorted only by the key (which may occur multiple times). I do not use a multimap for this, because it is not explicitly stable. Therefore, I supply a custom compare function to stable_sort. I'm struggling now with templatizing this function. A brief test implementation follows to show you the use case:

#include <iostream>
#include <algorithm>
#include <vector>

#include "test.h"

using namespace std;

int main() {
  typedef pair<int, int> TPair;

  vector<TPair> data(10);

  data[0] = make_pair(7, 1); 
  data[1] = make_pair(3, 2); 
  data[2] = make_pair(8, 0); 
  data[3] = make_pair(5, 1); 
  data[4] = make_pair(3, 1); 
  data[5] = make_pair(2, 0); 
  data[6] = make_pair(7, 0); 
  data[7] = make_pair(6, 0); 
  data[8] = make_pair(5, 0); 
  data[9] = make_pair(3, 0); 

  stable_sort(data.begin(), data.end(), comp1);

  for (unsigned int i = 0; i < 10; ++i) {
    cout << data[i].first << "\t" << data[i].second << endl;
  }

  return 0;
}

The supplied sorting function is available in test.h:

#include <vector>

#ifndef TEST_H_
#define TEST_H_

using namespace std;

bool comp1(pair<int, int> const & a, pair<int, int> const & b) {
  return a.first < b.first;
}

template <typename TElemA, typename TElemB>
bool comp2(pair<TElemA, TElemB> const & a, pair<TElemA, TElemB> const & b) {
  return a.first < b.first;
}

template <typename TPair>
bool comp3(TPair const & a, TPair const & b) {
  return a.first < b.first;
}

#endif

• comp1 works well, nothing to complain. First I tried to templatize the elements of the pairs:
• comp2 doesn't work: test.cpp:25:3: error: no matching function for call to 'stable_sort'.
• comp3 fails with the same error message as comp2.

What is wrong with this template function?

Answer 1

stable_sort is itself a template, the type of its third parameter is a template parameter. This means that you cannot pass a function template as the argument, because template argument deduction cannot apply here - there's nothing to tell which instantiation you'd be after. So you'd have to specify the template argument explicitly:

stable_sort(data.begin(), data.end(), comp2<int, int>);

However, you'll be better off if you provide a functor for that:

struct comp2
{
  template <typename TElemA, typename TElemB>
  bool operator() (pair<TElemA, TElemB> const & a, pair<TElemA, TElemB> const & b) const {
    return a.first < b.first;
  }
};

stable_sort(data.begin(), data.end(), comp2());

That way, the actual template argument deduction is postponed until the time when the desired types are known.

Answer 2

Since C++14, you can also use a lambda expression instead of using a template. This is, because C++14 allows for generic lambdas, whose function parameters can be declared with the auto type specifier:

std::stable_sort(std::begin(data), std::end(data), [](auto const &a, auto const &b){
    return a.first < b.first;
});

This way your code becomes rather short, but still works for any comparable std::pair key.

Code on Ideone