c++ - 为什么用于 C++ 中的 sort() 、 max_element() 函数等 STL 函数的 lambda 函数需要两个参数作为输入？

Question

我试图了解 lambda 函数在 sort() 运算符中的使用。有一个存储person类型对象的 vector ； sort() 函数用于迭代 vector person 并根据类成员 id 对其进行排序。

我不明白为什么排序函数中使用的 lambda 函数需要两个输入，即。 p1 和p2 ？为什么不只输入一个对象p1？我一直认为 sort() 和 max_element() 等 STL 函数将迭代器返回到一个元素。

class Person
    {
      private:
        string firstName;
        string lastName;
        int id;

      public:
        Person(const string& fn, const string& ln, int i)
             : firstName(fn), lastName(ln), id(i) { }

        const string& getFirstName() const { return firstName; }
        const string& getLastName() const { return lastName; }
        int getID() const { return id; }
    };

main(){
vector<Person> people;
people.push_back(Person("Davor", "Loayza", 62341));
people.push_back(Person("Eva", "Lopez", 12345));
people.push_back(Person("Julio", "Sanchez", 54321));
people.push_back(Person("Adan", "Ramones", 70000));

sort(people.begin(), people.end(), [](const Person& p1, const Person& p2)
{
  return p1.getID() < p2.getID();
});
return 0;
}

编辑:可能我需要重申我的问题，我的问题是迭代器增量如何在 sort() 函数中发生。最开始iterator = people.begin()时，p1赋什么值，p2赋什么值？同样，当 iterator=people.end() 时会发生什么？我很难理解这个过程背后的逻辑？

Answer 1

要理解std::sort，您必须首先理解什么是排序。这是给你的练习:

给自己找一副牌。我假设您知道哪张卡片的等级 compared 高于另一张卡片；否则这可能会造成混淆。 ace 是高于 king 还是低于 two 都无关紧要。你现在可以忽略花色。

将卡片排成一排(或扇形以节省空间)。目标是找出等级较高的牌是否在等级较低的牌之前。想一想如何找到它？

方法如下:从第一张卡片开始，然后是第二张卡片。 比较他们的排名。第一张卡的等级是否高于第二张？如果是这样，我们得出结论，我们寻求的答案是“是的，在一张较低等级的牌之前有一张较高等级的牌”。如果第一张牌的等级不高于第二张，那么我们还不能回答这个问题。我们必须继续将第二张卡片与第三张卡片进行比较，然后重复该过程。

如果您到达一副牌的尽头，但没有找到排名较低的牌之前的排名较高的牌，那么我们寻求的答案是“否”。让我们称这样的牌组为已排序(或已排序)。

第二个练习:如果牌组没有排序，你怎么能让它排序？

方法如下:就像第一个练习一样，从前两张牌开始。这一次，如果他们的顺序不对，交换他们的位置，让拳头变成第二个，第二个变成第一个。现在，这两张卡片按照彼此的关系 排序。然后移动到第二个和第三个并重复该过程。您会发现您可能需要多次重复此过程，因为一次迭代不一定足够。

让我们称此过程为排序(更具体地说，这是比较排序)。这就是 std::sort 所做的。它一次比较两个元素，并交换元素直到任何相邻对之间的所有比较都为真，即直到范围被排序。

您在两张 卡片之间进行的比较类似于通过std::sort 的比较函数对象参数完成的比较步骤。如果您一次只看一张卡片，您将无法确定它是否处于有序位置。

---

Why does lambda function used for stl functions such as sort() , max_element() function in C++ take two arguments as input?

因为这些函数的比较函数对象参数表示迭代器范围的两个元素之间的顺序关系。顺序关系是二元关系。

why not just input one object p1?

因为一元关系不能表示顺序。

I always thought stl functions such as sort() and max_element() return iterator to one element.

how many iterators does sort() function return?

std::sort 根据文档返回 void。也就是说，这些函数返回的内容与比较函数对象参数的参数无关。

my question was how does iterator increment occur in sort() function

这不是指定的。算法的实现者可以选择如何增加迭代器。排序算法通常使用多个迭代器。

At the very beginning when iterator = people.begin(), what value is assigned to p1 and what value is assigned to p2?

排序算法不必从范围的开头开始。不清楚您指的是什么 iterator。

p1 和 p2 将是 [first, last) 范围内的一些对元素。究竟哪一对由算法决定。