C++中针对std::sort()的自定义比较函数

Question

我想为std::sort()创建自定义比较函数，以对一些键值对std::pair进行排序。

这是我的函数：

 template <typename K, typename V>
 int comparePairs(const void* left, const void* right){
        if((((pair<K,V>*)left)->first) <= (((pair<K,V>*)right)->first))
            return 1;
        else 
            return -1;
    }

然后，在某个类中，我有一个成员为vector of pairs的类成员：

vector<pair<K,V>> items;  

使用std::sort()对这个向量按键进行排序的一些方法。

std::sort(items.begin(), items.end(), comparePairs<K,V>);

我在 <某处> 遇到编译错误，错误信息如下:

"无法将参数从 'std::pair<_Ty1,_Ty2>' 转换为 'const void*'"

这是什么错误？

- vard

---

你为什么要将参数作为void*而不是std::pair呢？ - Dominic Rodger

你犯了一个错误，把std::sort和需要使用const void *参数的qsort的比较函数混淆了。为std::sort编写一个正确的比较函数，该函数接受对pair<K, V>的引用作为参数，问题就会解决。 - user4815162342

为什么有人会点赞这个内容呢？它明显缺乏研究、阅读、关注、思考或其他任何东西。 - Jim Balter

Answer 1

看这里：http://en.cppreference.com/w/cpp/algorithm/sort。

它说：

template< class RandomIt, class Compare >
void sort( RandomIt first, RandomIt last, Compare comp );

• comp - 比较函数，如果第一个参数小于第二个参数，则返回true。比较函数的签名应该等同于以下内容：bool cmp(const Type1 &a, const Type2 &b);

此外，以下是使用自定义的C++14多态lambda表达式使用std::sort的示例：

std::sort(std::begin(container), std::end(container),
          [] (const auto& lhs, const auto& rhs) {
    return lhs.first < rhs.first;
});

- Felix Glas

Answer 2

std::pair已经具备所需的比较运算符，它使用每个对的两个元素执行词典比较。要使用它，您只需为类型K和V提供比较运算符。

还要注意，std::sort需要一个严格弱序比较，而<=并不满足该要求。例如，您需要为K和V提供小于比较运算符<。有了这个设置，您只需要：

std::vector<pair<K,V>> items; 
std::sort(items.begin(), items.end()); 

如果你真的需要提供自己的比较函数，那么你需要类似于以下内容：

template <typename K, typename V>
bool comparePairs(const std::pair<K,V>& lhs, const std::pair<K,V>& rhs)
{
  return lhs.first < rhs.first;
}

- juanchopanza

Answer 3

你的比较函数甚至不能算是错误。

它的参数应该是存储在范围内的类型，即 std::pair<K,V>，而不是 const void*。

它应该返回bool而不是正或负值。因为(bool)1 和 (bool)-1 都是 true，所以你的函数会认为每个对象都排在任何其他对象之前，这显然是不可能的。

你需要建模小于运算符，而不是 strcmp 或 memcmp风格的比较。

参见严格弱序，其中描述了函数必须满足的属性。

- Jonathan Wakely