c++ - 二元谓词如何工作？

Question

在下面的代码中，在二进制谓词函数 mycomparison 中，为什么首先从 L2(即 2.1)而不是从 L1(1.4)获取第一项？同样，第二个是从 L1 获取第一个项目。并且这种行为是特定于此功能(合并)还是可以扩展到其他功能。我们可以假设容器的顺序将决定传递给二元谓词函数的顺序吗？

#include <iostream>
#include <list>
bool mycomparison(double first, double second)
{
    std::cout <<"first "<< first << " " << "second "<< second << "\n"; 
    return (int (first) <  int (second) );
}

int main()
{
    std::list<double> L1, L2;
    L1.push_back(3.1); L1.push_back(2.2); L1.push_back(2.9);
    L2.push_back(3.7); L2.push_back(7.1); L2.push_back(1.4);
    L1.sort(); L2.sort();
    L1.merge(L2);

    std::cout << "L1 contains: ";
    for (std::list<double>::iterator it = L1.begin(); it != L1.end(); ++it)
        std::cout << *it << ",  ";
    std::cout << '\n'; 

    L2.push_back(2.1);
    L2.push_back(3.2);

    std::cout << "L2 contains: ";
    for (std::list<double>::iterator it = L2.begin(); it != L2.end(); ++it)
        std::cout << *it << ",  ";
    std::cout << '\n';

    L1.merge(L2, mycomparison);

    std::cout << "L1 contains: ";
    for (std::list<double>::iterator it = L1.begin(); it != L1.end(); ++it)
        std::cout << *it << ",  ";
    std::cout << '\n';
    return 0;
}

输出

L1 contains: 1.4,  2.2,  2.9,  3.1,  3.7,  7.1,  
L2 contains: 2.1,  3.2,  
first 2.1 second 1.4
first 2.1 second 2.2
first 2.1 second 2.9
first 2.1 second 3.1
first 3.2 second 3.1
first 3.2 second 3.7
first 3.2 second 7.1
L1 contains: 1.4,  2.2,  2.9,  2.1,  3.1,  3.7,  3.2,  7.1,  

这是一个使用二元谓词或比较的排序函数。然而，传递给函数的项目也是“乱序的”。在 myfunction 变量中，我将获得 vector (71) 中的第二项，而不是第一项 (32)。为什么？

#include <iostream>     // std::cout
#include <algorithm>    // std::sort
#include <vector>       // std::vector

bool myfunction(int i, int j) { 
    std::cout << i << " " <<j<<"\n" ; 
    return (i<j); }

int main() {
    int myints[] = { 32,71,12,45 };
    std::vector<int> myvector(myints, myints + 4);               

    std::sort(myvector.begin(), myvector.end(), myfunction); 

    std::cout << "myvector contains:";
    for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';

    return 0;
}

输出

71 32
71 32
12 32
45 12
45 71
45 32
myvector contains: 12 32 45 71

Answer 1

在 Strict Weak Ordering 中例如您使用 mycomparison 函数定义的对象，两个对象可能不相等但“相等”。在您的情况下，由于 mycomparison(2.2, 2.1) 和 mycomparison(2.1, 2.2) 都是假的，因此数字 2.1 和 2.2 在该顺序中是等效的。

所以L1的最终顺序实际上是按照mycomparison顺序排序的，因为2.2,2.9 和 2.1 都被认为是等效的。另外，std::list::merge保证已经在 *this(2.2 和 2.9)中的元素出现在从参数列表(2.1)中移动的等效元素之前)。您可以看到也遵守了此行为。