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?

Angew is no longer proud of SO · Accepted Answer · 2013-09-13 09:57:15Z

5

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.

answered Sep 13, 2013 at 9:57

Angew is no longer proud of SO

172k18 gold badges377 silver badges478 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

honk · Accepted Answer · 2018-12-13 14:39:11Z

0

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

edited Dec 13, 2018 at 14:39

answered Dec 13, 2018 at 14:31

honk

9,87311 gold badges83 silver badges90 bronze badges

Collectives™ on Stack Overflow

How can I implement a custom template sort function?

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related