c++ - 如何将比较器添加到自定义排序函数

Question

所以我已经实现了合并排序，出于所有意图和目的，它也可以是一个自定义排序函数，并且我已经开始将它变成一个模板函数。

我遇到问题的地方是当我想增加传递自定义比较函数的可能性以便以不同方式排序时。 (例如 std::greater 和 std::less 或任何自定义的)。

我已经验证了当我用 T 替换整数时排序算法有效。我如何从这里添加自定义比较函数以便也对自定义对象等进行排序？

template <  typename T, 
            class Compare>
void merge( vector<T> &arr, int start, int mid, int end, Compare comp ) 
{
    int lptr = start; 
    int rptr = mid+1; 
    int tempptr = 0; 

    vector<T> temp( end - start + 1 ); 

    for ( int i = 0; i<temp.size(); i++)
    {
        if ( lptr > mid ) //done with left-section, just move the right elements
        {   
            temp[tempptr] = arr[rptr];
            rptr++;
        } else if ( rptr > end ) //done with right-section, just move the left elements
        {
            temp[tempptr] = arr[lptr];
            lptr++; 
        } else if ( comp( arr[rptr], arr[lptr] )) // right item < left item, move right item
        {
            temp[tempptr] = arr[rptr]; 
            rptr++; 
        } else          //otherwise left item < right item, move left item
        {
            temp[tempptr] = arr[lptr];
            lptr++; 
        }
        tempptr++;
    }

    for ( int i = 0; i<temp.size(); i++)
    {
        arr[start + i] = temp[i]; 
    }
}






template <  typename T, 
            class Compare>
void mergeSort( vector<T> &arr, int start, int end, Compare comp)
{   

    //if we're down to single elements, do nothing
    if ( start < end ){
        //call to right and left 'child' 
        int mid = (start + end) / 2; 

        mergeSort( arr, start, mid ); 
        mergeSort( arr, mid + 1, end );

        //call to merge
        merge( arr, start, mid, end ); 
    }
}



int main()
{   
    vector<float> arr = {7,8, 2, 6.6, 1, 4.1, 5, 3, 8, 9};
    cout << "before sorting:" << endl;
    for ( auto n : arr ) 
        cout << n << ", ";
    cout << endl;
    mergeSort( arr, 0, arr.size() - 1); 

    cout << "after sorting:" << endl;
    for ( auto n : arr ) 
        cout << n << ", ";
    cout << endl;

    return 0; 
};

提前致谢。

Answer 1

考虑到您有一个 class or struct CustomType

C++11 之前

struct CustomCompare
{
    bool operator ()(const CustomType& a, const CustomType& b)
    {
        return a.Watever < b.Watever;
    }
};

//usage
merge(vector<CustomType> ..., CustomCompare());

发布 c++11，using lambdas :

auto CustomCompare = [](const CustomType & a,const CustomType& b)
{
    return a. .... ;
};
//usage
merge(vector<CustomType> ..., CustomCompare);

还有第三种选择:

您可以使用 std::less 但必须存在一个operator <这需要你的 CustomType作为参数

例子:

struct CustomType
{
    //...
    bool operator < (const CustomType& other)const
    {
        return this->Whatever < other.Whatever;
    }
};

而且你可以专攻std::less :

namespace std
{
    template <>
    struct less <CustomType>
    {
        bool operator()(const CustomType & a, const CustomType & b)
        {
            return ...
        }
    };
}