代码之家 › 专栏 › 技术社区 › Oliver

如何实现自定义模板排序功能?

std-pair compare templates sorting c++

Oliver · 技术社区 · 11 年前

我有一个成对的向量,我希望它只按关键字进行稳定排序(这可能会发生多次)。我不使用 multimap 因为它不是显式稳定的。因此,我提供了一个自定义比较函数 stable_sort 。我现在正在努力将此函数模板化。下面是一个简短的测试实现,向您展示用例:

#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;
}

提供的排序功能可在 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 效果很好,没什么可抱怨的。首先,我尝试将这些对的元素模板化:
comp2 不起作用: test.cpp:25:3: error: no matching function for call to 'stable_sort' .
comp3 失败,错误消息与 计算机2 .

这个模板函数有什么问题?

2 回复 | 直到 6 年前

Angew is no longer proud of SO 11 年前

stable_sort 本身是一个模板,其第三个参数的类型是模板参数。这意味着你不能传递函数模板作为参数,因为模板参数推导不能在这里应用——没有什么可以告诉你要进行哪个实例化。因此,您必须明确指定模板参数:

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

然而,如果您为此提供一个函子,您会过得更好:

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

这样,实际的模板参数推导就被推迟到所需类型已知的时候。

honk 6 年前

自从 C++14 ,您也可以使用 lambda expression 而不是使用模板。这是因为C++14允许使用泛型lambda,其函数参数可以用 auto 类型说明符:

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

通过这种方式,您的代码变得相当短,但仍然适用于任何类似的代码 std::pair 钥匙

Code on Ideone