c++ - C++排序自适应函数

Question

我想为不同类型的不同集合创建自适应冒泡排序功能。代码示例:

#include <iostream>
#include <vector>
#include <functional>

template <typename CollectionType, typename ValueType>
void bubbleSort(CollectionType& ar, size_t size, std::function<bool(ValueType, ValueType)> comparator)
{
    bool isSorting = false;
    for (size_t i = 0; i < size - 1; i++)
    {
        isSorting = true;
        for (size_t j = 0; j < size; j++)
        {
            if (comparator(ar[j], ar[j + 1]))
            {
                std::swap(ar[j], ar[j + 1]);
                isSorting = false;
            }
        }
        if (isSorting)
        {
            return;
        }
    }
}

int main()
{
    std::vector<int> vector = {7, 9, 1, 5, 8, 1, 8, 3, 7, 3};
    bubbleSort(vector, vector.size(), [](int a, int b) { return a > b; });

    for(const auto& val : vector)
    {
        std::cout << val << " ";
    }

    return EXIT_SUCCESS;
}

但是我遇到了以下问题:

/home/vova/Desktop/Temp/main.cpp:37:73: error: no matching function for call to ‘bubbleSort(std::vector<int>&, std::vector<int>::size_type, main()::<lambda(int, int)>)’ bubbleSort(vector, vector.size(), [](int a, int b) { return a > b; });

/home/vova/Desktop/Temp/main.cpp:6:6: note: candidate: template<class CollectionType, class ValueType> void bubbleSort(CollectionType&, size_t, std::function<bool(ValueType, ValueType)>) void bubbleSort(CollectionType& ar, size_t size, std::function<bool(ValueType, ValueType)> comparator)

/home/vova/Desktop/Temp/main.cpp:6:6: note:   template argument deduction/substitution failed:

/home/vova/Desktop/Temp/main.cpp:37:73: note:   ‘main()::<lambda(int, int)>’ is not derived from ‘std::function<bool(ValueType, ValueType)>’ bubbleSort(vector, vector.size(), [](int a, int b) { return a > b; });

如果我为函数设置模板参数:

bubbleSort<std::vector<int>, int>(...)  

然后它起作用了，但对我来说它看起来并不漂亮。它如何纠正？

Answer 1

您的 lambda 不是 std::function，std::function 的模板参数不能从 lambda 的参数推导出来。

但是您不需要将 std::function 作为比较器，模板“Comparator”参数就可以了。这就是标准库为有序容器中的比较器所做的。例如

template <typename CollectionType, typename Comparitor>
void bubbleSort(CollectionType& ar, size_t size, Comparitor comparator)
{
    bool isSorting = false;
    for (size_t i = 0; i < size - 1; i++)
    {
        isSorting = true;
        for (size_t j = 0; j < size; j++)
        {
            if (comparator(ar[j], ar[j + 1]))
            {
                std::swap(ar[j], ar[j + 1]);
                isSorting = false;
            }
        }
        if (isSorting)
        {
            return;
        }
    }
}