c++ - 自定义排序 C++ 列表

Question

//
//  TemplateArray.cpp
//  C++
//
//  Created by FatJoe  on 03/12/2018.
//  Copyright © 2018 FatJoe . All rights reserved.
//

#include <stdio.h>
#include <iostream>

/*

 This code demonstrates representing an array and array adder using objects
 Overloading the [] operator

 */

#include<list>
#include <map>

using namespace std;

class person{

public:
    int i;
    person(int j):i(j){}


};

class comparer{

public:
    bool operator()(const person& first, const person& second)const{
        cout << "operator() called" << endl;
        return true;
    };
};

int main(){

    list<person> personlist;
    list<person>::iterator itr = personlist.begin();
    personlist.insert(itr,person(1));
    personlist.insert(itr,person(2));
    personlist.insert(itr,person(3));


    for(itr=personlist.begin(); itr!=personlist.end(); itr++){
        cout << (*itr).i << "Person no." << endl;
    };

    personlist.sort(comparer());


    for(itr=personlist.begin(); itr!=personlist.end(); itr++){
        cout << (*itr).i << "Person no." << endl;
    };

    personlist.sort(comparer());


    for(itr=personlist.begin(); itr!=personlist.end(); itr++){
        cout << (*itr).i << "Person no." << endl;
    };


    return 0;
}

我正在尝试编写我自己的排序标准，我正在测试我自己的一些代码。

在我的比较器仿函数中，我返回 true，这意味着第一个参数将与第二个参数交换。

但是，我很难理解如果列表中有 3 个元素，为什么比较器仿函数被调用 3 次，肯定是比较(1,2)然后比较(2,3)？

Answer 1

除了n log n 复杂度之外std::list 的排序算法未指定。您需要查看您正在使用的任何运行时库的源代码，以了解它是如何实现的。您应该能够使用调试器单步执行代码。

因为你的比较函数不符合 Compare 的规范你的代码有未定义的行为。