std :: sort()的c ++自定义比较函数

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<pair<K,V>> items;  

以及使用std :: sort()按键对此向量进行排序的一些方法

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

我内部有编译错误,其中说

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

.什么是错误？

Answer 1

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

它说:

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

• 排版 -比较函数返回真,如果所述第一参数小于所述第二.比较函数的签名应等效于以下内容:bool cmp(const Type1 &a, const Type2 &b);

另外,这是一个如何std::sort使用自定义C++ 14多态lambda 的示例:

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

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

Answer 3

你的比较功能甚至没有错.

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

它应该返回bool不是正值或负值.双方(bool)1并(bool)-1都true让你的功能说每一个对象前下令所有其他对象,这显然是不可能的.

您需要将小于运算符,而不是模型strcmp或memcmp风格比较.

请参阅StrictWeakOrdering,它描述了函数必须满足的属性.