在 C++ 中工作排序函数

Question

我正在阅读我的朋友代码，遇到了这部分sort(c + 1, c + n + 1, compare);其中 c 是类客户的对象，定义为

class customer {
public:
int si;
int fi;
int pi;
};

并编写一个函数

bool compare(customer a, customer b)
{
    if (a.pi < b.pi) 
    {
        return true;
    }
    else if (a.pi > b.pi) 
    {
        return false;
    }
    else 
    {
        return a.fi < b.fi;
    }
}

任何人都可以解释一下排序功能的工作原理以及此比较功能如何与排序功能链接。

Answer 1

std：：sort 定义为：

template <class RandomAccessIterator, class Compare>
  void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
// Sorts the elements in the range [first,last) into ascending order.
// The elements are compared using operator< for the first version, and comp for the second.

在您的情况下，我假设c指的是客户集合中的一个条目，因为调用

sort(c + 1, c + n + 1, compare);

将对紧随集合中c的客户n排序，使用compare确定顺序。

std：：sort 将使用某种排序算法（在大多数实现中可能是快速排序）为您执行排序。为了做到这一点，它需要能够比较两个元素。这就是compare函数发挥作用的地方：

Binary function that accepts two elements in the range as arguments,
and returns a value convertible to bool. The value returned indicates
whether the element passed as first argument is considered to go before
the second in the specific strict weak ordering it defines.

在您的情况下，compare 函数将按pi的升序和fi的升序（在相等的pi内）对客户进行排序。

Answer 2

在C++ std：：sort 是一个标准的库函数，通常使用快速排序来实现。它作为模板函数实现，此重载在比较器的类型上模板化，然后该函数将可调用对象作为其第三个参数，并将其用作排序的比较函数。通常，这意味着编译器将能够将比较函数内联到排序函数模板的模板实例化中，尽管它最终可能成为函数调用。